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

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

（佳木斯大學，黑龍江 佳木斯 154007）

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

1 排課問題的約束條件

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

1.1 數學模型表示

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

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

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

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

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

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

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

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

1.2 硬約束條件

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

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

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

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

1.3 軟約束條件

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

（1）一門課程的多次課程應盡量分散開，不要連續。

（2）學生的所有課程不應過分集中，盡量避免某天空課的情況。

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

（4）主要課程應盡量安排在上午。

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

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

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

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

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

2 算法設計

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

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

圖1 遺傳算法基本流程

2.2 排課問題染色體編碼

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

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

2.3 設置遺傳參數

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

2.4 生成初始種群

初始種群是進行遺傳迭代的基礎，后續遺傳過程在此種群上進行。種群規模不宜過大。

2.5 選擇操作

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

2.6 交叉操作

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

2.7 變異操作

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

3 實例

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

圖3 實際排課結果

4 總結

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

［1］ 陳靜.自動排課系統算法的分析與設計［J］.科技情報開發與經濟，2007，17（34）：199－201.

［2］ 王小平，曹立明.遺傳算法—理論、應用與軟件實現［M］.西安：西安交通大學出版社，2002.

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

［4］ 蘇仰娜.基于遺傳算法的優化排課系統［J］.河南大學學報，2005，35（1）：75－78.

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