基于遺傳算法解決排課問題的探索

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

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

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

1 排課問題的約束條件

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

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

分析了排課問題所涉及的因素后，可將一個排課問題進行如下模型表示：

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

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

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

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

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

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

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

1.2 硬約束條件

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

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

（2）一個上課班級在同一時間只能上一門課。

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

1.3 軟約束條件

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

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

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

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

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

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

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

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

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

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

2 算法設(shè)計

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

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

圖1 遺傳算法基本流程

2.2 排課問題染色體編碼

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

圖2 排課問題染色體編碼方案

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

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

2.4 生成初始種群

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

2.5 選擇操作

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

2.6 交叉操作

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

2.7 變異操作

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

3 實例

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

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

4 總結(jié)

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

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

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

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

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

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