基于局部狀態計算的模擬退火算法求解排課問題

馬超

摘要：編排課程表是教學工作開展的基礎，因此排課問題的解決有著重大的現實意義。作為典型的組合優化問題，隨著課程規模的增加以及約束條件的多樣化、復雜化，人工求解排課問題顯得不現實。在分析排課問題需要滿足的約束條件上建立課程表模型，使用基于局部狀態計算的模擬退火算法來減小計算范圍對模型求解。（近似）最優的求解結果證明了模型的有效性和求解方法的可行性。

關鍵詞：排課系統 模擬退火 局部狀態計算

中圖分類號：TP311.52 文獻標識碼：A 文章編號：1007-9416（2016）08-0149-02

1 引言

排課工作是教學管理的一項重要內容，其實質是為每個班級安排合理的課程、時間、教室和教師，制定課程表以保證教學工作能按時有序進行。課程表編排的合理化和人性化直接影響著后續教學工作的效率。S.Even于1975年證明了排課問題在本質上屬于NP完全問題[1]。隨著班級、課程量的增加以及約束條件的復雜化，傳統的人工排課方法耗時耗力，甚至難以排出合理的課程表。不少文獻對遺傳算法解決排課問題進行了研究[2][3][4]，遺傳算法在求解該問題時搜索效率較低，容易陷入局部極值。事實上，遺傳算法更適用于無約束的優化問題求解。由于遺傳算法的解和軟色體基因編碼間有著對應規則，因此適應度較高的兩個個體經雜交后可能產生較差的子代，甚至子代會成為非法軟色體（不滿足基因編碼規則）。文獻[5]使用蟻群算法對排課問題進行了研究，蟻群算法的缺點是計算耗時較長，螞蟻運動的隨機性致使收斂速度較慢， 算法容易停滯不前。鑒于以上，本文使用基于局部狀態計算的模擬退火算法對排課問題進行求解。

2 問題描述和建立模型

2.1 問題描述

作為典型的組合優化問題，排課問題涉及班級、課程、教師、時間和教室五個因素，其實質是給定資源在一系列約束條件下的分配，因此排課問題屬于約束滿足問題[6]。一方面，課程表必須滿足硬約束以保證不發生時空沖突，另一方面，課程表要盡量滿足軟約束去考慮某些課程或者教師的特殊要求。教學的最小單位定義為基本時間段BTD（Basic Time Duration），一個BTD可以認為是一節課或者一個課時。

課程表必須滿足硬約束，從教學資源分配的觀點看，硬約束有下面三點：

（1）班級約束：一個班級在一個課時內只能上一門課。

（2）教師約束：一個教師在一個課時內只能上一門課。

（3）教室約束：一個教室在一個課時內只能上一門課。

軟約束隨具體情況而變，綜合看來有下面幾點：

（1）教師A的課程只能安排在上午。

（2）教師B的課程需要有連課（比如1、2節都為英語課）。

（3）教師C的課只能安排在周一和周三。

（4）某些課只能安排在特定教室（實驗課等）。

（5）考慮到備課負擔和教學效果，課程編排要盡量均勻。

2.2 模型建立

如前所述，排課問題中所涉及的因素有班級、課程、教師、教室、時間。我們對教學資源的假定如下：有m間教室，每周上n天課，每天有p個課時，（比如上午四節，下午三節，那么一天的課時數為7），則每周共有m*n*p個時空單元（課時單元）。我們把所有的時空單元劃分為一個行數為m、列數為p*n的二維數組TimeTable[m][p*n]。如果有8間教室，每周上課5天（星期一至星期五），每天7節課，那么該二維數組就為TimeTable[7×5]。二維數組的每個元素TimeTable[i][j]（0≤i≥7，0≤j≥34）與哪一天（date）、哪一節（order）的對應關系為：

date=j/7（取整）

order=j%7（取余）。

3 基于局部狀態計算的模擬退火排課算法

模擬退火算法[4]（Simulated annealing，SA）的基本原理是模擬固體在退火過程中總是從能量高的狀態向能量最低的平衡態轉換的思想尋找最優解，通過冷卻溫度的不斷降低來控制退火過程。SA在每個溫度下設計解的隨機變化，并以一定的概率接受差的解。隨著能量的降低，接受差的解的概率也顯著降低。因此，SA在高能狀態下具有逃離局部最優解的能力，在低能狀態下可以收斂得到全局最優解。

模擬退火算法的關鍵是要找到一個目標函數，排課問題中的各種約束是建立目標函數的依據，這些約束分為硬約束和軟約束。我們對不同的約束賦予不同的影響因子（權重），硬約束決定了排課方案是否可行，軟約束決定排課方案是否夠好。

3.1 算法流程

為了算法流程的描述簡潔，T0表示退火的初始溫度，Tmin表示退火的結束溫度，降溫方式使用指數衰減。INNER_TIMES為每個溫度下的課程表隨機變化次數。算法流程如圖1所示。

3.2 模型求解的算法關鍵

3.2.1 新課程表的隨機產生

Step1：隨機產生一個數i（i∈[0， m-1]），選出教室TimeTable[i]。

Step2：隨機產生兩個數j，k（j，k∈[0， n*p-1]），選出step1中教室的兩個課時TimeTable[i][j]和TimeTable[i][k]，確保TimeTable[i][j]≠TimeTable[i][j]，即兩個課時所代表的課程不同。

Step3：對step2中兩個課時的課程進行交換，產生新的課程表。新課程表是否被接受取決于其和當前課程表的目標函數差及概率。

3.2.2 目標函數設計

（1）基于局部狀態計算的目標函數。新課程表相比當前課程表只有一個教室的兩個課時順序發生了變化，參與變化的課程只有兩門課。在計算課程表的目標函數值時，不變的那些課時無需參與計算，因為這部分是一個定值，我們只需要計算發生變化的部分，然后得到目標函數差即可。假設課程表不變部分的目標函數是value_constant，當前課程表由課程TimeTable[i][j]和TimeTable[i][k]決定的目標函數值部分是value_variation1，新課程表由課程TimeTable[i][j]和TimeTable[i][k]決定的目標函數值部分是vale_variation2， 目標函數差值是value_diff.value_variation1和value_variation2都取決于TimeTable[i][j]和TimeTable[i][k]，確切地說是取決于課時TimeTable[i][j]和TimeTable[i][k]對應課程上面的約束（硬約束和軟約束）。基于局部計算的原理公式如下：

value_diff=（value_constant + value_variation2）

-（value_constant+value_variation1）

=value_variation2-value_variation1

這樣目標函數在計算時不用考慮整張課程表，只需考慮發生交換的兩個課時，計算范圍得以大大縮小。

（2）約束的完備性：目標函數要計算到排課要求的所有約束。

（3）約束的影響因子：硬約束的影響因子要高于軟約束；軟約束的影響因子確定原則，越重要的軟約束（根據排課面臨的現實情況權衡），其影響因子越高（不應高過硬約束），確保算法優先滿足。

3.2.3 SA參數設置

T0=1000，Tmin=0.001，退火速率設置為0.98，INNER_TIME = 1000。

4 結果與結論

本文用C語言實現了對某年級課程表的建模和算法求解，基于局部狀態計算的模擬退火算法大大減少了計算量，求解出的課程表如圖2所示，經驗證完全滿足約束條件。由于每個學校的開課情況和約束條件存在差別，所以設計出通用的排課程序不是很實際，但本文對排課問題的建模方法和基于局部狀態計算的模擬退火算法求解有著一定的啟發和借鑒意義。

參考文獻

[1]Garey M R， Johnson D S. Compute and Intractability： A Guide to the theory of NP completeness [M]. San Francisco： W H， Freeman &Co Ltd. ，1979.

[2]崔玉連，楊先鋒.改進遺傳算法在排課問題中的應用研究[J].微型電腦應用，2013，29（10）：48-51.

[3]王園園.遺傳算法在高校排課系統中的應用[J].淮北職業技術學院學報，2015，14（3）：134-135.

[4]江蕭，弋改珍，袁嵐清.遺傳算法在排課系統中的應用與設計研究[J].電腦知識與技術，2014，10（5）：1032-1035.

[5]張 林.基于蟻群算法的排課系統研究與設計[D].合肥： 安徽大學碩士學位論文， 2005.

[6]Bartak R， Salido MA， Rossi F. Constraint satisfaction techniques in planning and scheduling [J]. Journal of Intelligent Manufacturing， 2010，21： 5-15.