基于遺傳算法解決排課問(wèn)題的探索

馬傳志，呂志武，曲思龍，周 虹，王 蕊，明艷春

（佳木斯大學(xué)，黑龍江 佳木斯 154007）

在學(xué)校的教務(wù)管理工作中，排課工作是一項(xiàng)繁重而復(fù)雜的工作。排課工作涉及的因素眾多，波及面廣，這一工作的結(jié)果直接影響教學(xué)工作的有序進(jìn)行。作為一個(gè)涉及多因素的優(yōu)化組合問(wèn)題，學(xué)校的排課工作已經(jīng)被證明是一個(gè)NP完全類問(wèn)題，利用常規(guī)算法進(jìn)行求解會(huì)面臨諸多問(wèn)題，很難有效求解，常常引起大量的沖突而使得排課無(wú)法進(jìn)行下去。近年來(lái)，這一問(wèn)題引起了很多人的重視，進(jìn)行了多種不同方式的嘗試，取得了一定的成果。遺傳算法作為一種解決NP完全類問(wèn)題的有效算法，可以被應(yīng)用于排課問(wèn)題中。

1 排課問(wèn)題的約束條件

排課問(wèn)題涉及的因素比較多，包括任課教師、授課班級(jí)、所學(xué)課程、學(xué)習(xí)教室、上課時(shí)間等，眾多的因素必須滿足一定的條件進(jìn)行組合才是合理的，所排出的課表才是可行的，否則將導(dǎo)致教學(xué)任務(wù)無(wú)法有效完成，影響教學(xué)工作正常進(jìn)行。為了研究算法，首先要將排課問(wèn)題進(jìn)行有效表示，分析在排課過(guò)程中要滿足的各種條件。

1.1 數(shù)學(xué)模型表示

分析了排課問(wèn)題所涉及的因素后，可將一個(gè)排課問(wèn)題進(jìn)行如下模型表示：

任課教師集：P＝｛p1，p2，p3，…，pn｝

所學(xué)課程集：L＝｛l1，l2，l3，…，ln｝

授課班級(jí)集：C＝｛c1，c2，c3，…，cn｝

學(xué)習(xí)教室集：R＝｛r1，r2，r3，…，rn｝

上課時(shí)間集：T＝｛t1，t2，t3，…，tn｝

其中，任課教師、授課班級(jí)和所學(xué)課程可以組合為一個(gè)授課安排，學(xué)習(xí)教室和上課時(shí)間可以組合為一個(gè)教室時(shí)間安排，組合簡(jiǎn)化后，排課問(wèn)題就演變成為一個(gè)授課安排尋找合理的教室時(shí)間安排的任務(wù)。

在此基礎(chǔ)上，可以進(jìn)一步分析排課問(wèn)題過(guò)程中要滿足的條件，經(jīng)過(guò)分類簡(jiǎn)化，條件可以分為兩類：硬約束條件和軟約束條件。

1.2 硬約束條件

硬約束條件是在排課過(guò)程中必須滿足的條件，硬約束條件是無(wú)法改變的客觀條件，只有在解決這類條件的基礎(chǔ)上，排課工作才具有實(shí)際意義，才是一個(gè)可行的結(jié)果。一般來(lái)說(shuō)，硬約束條件有如下幾種：

（1）一名任課教師在同一時(shí)間只能上一門課。

（2）一個(gè)上課班級(jí)在同一時(shí)間只能上一門課。

（3）一個(gè)學(xué)習(xí)教室在同一時(shí)間只能上一門課。

1.3 軟約束條件

軟約束條件是相對(duì)于硬約束條件而言的，這類條件不是必須滿足，不具有強(qiáng)制性，在可能的情況之下盡量滿足這類條件會(huì)使排課的效果得到改善，有利于教學(xué)工作順利進(jìn)行。而且這類條件對(duì)不同的課程、不同情況會(huì)有變化，不完全固定。常見的軟約束條件有如下幾種：

（1）一門課程的多次課程應(yīng)盡量分散開，不要連續(xù)。

（2）學(xué)生的所有課程不應(yīng)過(guò)分集中，盡量避免某天空課的情況。

（3）同一教師的多次課程盡量不連續(xù)安排，最好隔天安排。

（4）主要課程應(yīng)盡量安排在上午。

（5）晚間盡量不安排課程。

（6）周六、周日盡量不安排課程。

（7）保證教室的利用率。

（8）某些課程對(duì)教室的要求，如盡量為多媒體等條件。

有些軟約束條件在某一特定條件下可能要求必須滿足，這時(shí)可轉(zhuǎn)化為硬約束條件來(lái)進(jìn)行排課。

2 算法設(shè)計(jì)

有了上述模型表示和約束條件后，可在此基礎(chǔ)上進(jìn)行算法設(shè)計(jì)。本算法以基本遺傳算法為基礎(chǔ)，進(jìn)行相應(yīng)改進(jìn)和參數(shù)設(shè)置，適應(yīng)于排課問(wèn)題的求解。

2.1 遺傳算法基本流程（如圖1所示）

圖1 遺傳算法基本流程

2.2 排課問(wèn)題染色體編碼

綜合分析排課問(wèn)題中所涉及的各種因素，其染色體編碼方案如圖2所示：

圖2 排課問(wèn)題染色體編碼方案

2.3 設(shè)置遺傳參數(shù)

遺傳參數(shù)是遺傳過(guò)程進(jìn)行下去的一個(gè)關(guān)鍵，在運(yùn)行之前設(shè)置。參數(shù)的設(shè)置對(duì)遺傳迭代次數(shù)和收斂都有影響。其中變異概率應(yīng)取較小的值，否則，會(huì)對(duì)遺傳進(jìn)程產(chǎn)生不利影響，使得運(yùn)算效率下降。

2.4 生成初始種群

初始種群是進(jìn)行遺傳迭代的基礎(chǔ)，后續(xù)遺傳過(guò)程在此種群上進(jìn)行。種群規(guī)模不宜過(guò)大。

2.5 選擇操作

選擇操作以適應(yīng)度的值為基本參考，所以適應(yīng)度的計(jì)算較為重要。在排課問(wèn)題具體操作時(shí)，適應(yīng)度值的高低與被選中的概率直接對(duì)應(yīng)。

2.6 交叉操作

在基本遺傳算法中，原則上可以在任意位置進(jìn)行交叉操作。本排課算法中，考慮到實(shí)際情況，對(duì)數(shù)據(jù)進(jìn)行授課安排和教室時(shí)間安排的分解，交叉時(shí)不破壞此分解單位，以此來(lái)保證交叉操作的實(shí)際意義。在此基礎(chǔ)上，兩個(gè)染色體進(jìn)交叉操作，保持課表有效性。

2.7 變異操作

變異操作是保持遺傳多樣性的一種重要手段，本排課算法設(shè)計(jì)過(guò)程中以變異操作來(lái)產(chǎn)生新個(gè)體。考慮到課表編排工作的特殊性，照顧到課表本身的特點(diǎn)，變異操作在基因內(nèi)部進(jìn)行，不越界，使得新生個(gè)體的合理性得到了有效保證。另外，為避免對(duì)求解產(chǎn)生不利影響，變異操作以較低概率進(jìn)行。

3 實(shí)例

在實(shí)驗(yàn)中采用了我校新生的數(shù)據(jù)信息，種群規(guī)模為100，交叉概率采用0.4，變異概率采用0.01，排課取得了滿意的結(jié)果，無(wú)沖突，滿足了所設(shè)定的約束條件。實(shí)際排的結(jié)果如圖3所示。

圖3 實(shí)際排課結(jié)果

4 總結(jié)

根據(jù)排課問(wèn)題本身的特點(diǎn)，采用所設(shè)計(jì)的遺傳算法進(jìn)行排課取得了較好的效果。排課問(wèn)題是一個(gè)復(fù)雜的NP完全性問(wèn)題，因素多，數(shù)據(jù)量大，在沖突解決過(guò)程中需要的知識(shí)較多，本文中的算法對(duì)實(shí)際問(wèn)題做了部分簡(jiǎn)化，仍有待改進(jìn)之處，在今后的研究中將繼續(xù)完善。

［1］ 陳靜.自動(dòng)排課系統(tǒng)算法的分析與設(shè)計(jì)［J］.科技情報(bào)開發(fā)與經(jīng)濟(jì)，2007，17（34）：199－201.

［2］ 王小平，曹立明.遺傳算法—理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安：西安交通大學(xué)出版社，2002.

［3］ 許秀林，胡克瑾.基于約束滿足和遺傳算法的排課算法基于約束滿足和遺傳算法的排課算法［J］.計(jì)算機(jī)工程，2010，36（14）：281－284.

［4］ 蘇仰娜.基于遺傳算法的優(yōu)化排課系統(tǒng)［J］.河南大學(xué)學(xué)報(bào)，2005，35（1）：75－78.

［5］ 陳皓，崔杜武，崔穎安，等.族群進(jìn)化算法［J］.軟件學(xué)報(bào)，2010，21（5）：978－990.