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

馬超

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

關(guān)鍵詞：排課系統(tǒng) 模擬退火 局部狀態(tài)計算

中圖分類號：TP311.52 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2016）08-0149-02

1 引言

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

2 問題描述和建立模型

2.1 問題描述

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

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

（1）班級約束：一個班級在一個課時內(nèi)只能上一門課。

（2）教師約束：一個教師在一個課時內(nèi)只能上一門課。

（3）教室約束：一個教室在一個課時內(nèi)只能上一門課。

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

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

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

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

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

（5）考慮到備課負(fù)擔(dān)和教學(xué)效果，課程編排要盡量均勻。

2.2 模型建立

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

date=j/7（取整）

order=j%7（取余）。

3 基于局部狀態(tài)計算的模擬退火排課算法

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

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

3.1 算法流程

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

3.2 模型求解的算法關(guān)鍵

3.2.1 新課程表的隨機(jī)產(chǎn)生

Step1：隨機(jī)產(chǎn)生一個數(shù)i（i∈[0， m-1]），選出教室TimeTable[i]。

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

Step3：對step2中兩個課時的課程進(jìn)行交換，產(chǎn)生新的課程表。新課程表是否被接受取決于其和當(dāng)前課程表的目標(biāo)函數(shù)差及概率。

3.2.2 目標(biāo)函數(shù)設(shè)計

（1）基于局部狀態(tài)計算的目標(biāo)函數(shù)。新課程表相比當(dāng)前課程表只有一個教室的兩個課時順序發(fā)生了變化，參與變化的課程只有兩門課。在計算課程表的目標(biāo)函數(shù)值時，不變的那些課時無需參與計算，因為這部分是一個定值，我們只需要計算發(fā)生變化的部分，然后得到目標(biāo)函數(shù)差即可。假設(shè)課程表不變部分的目標(biāo)函數(shù)是value_constant，當(dāng)前課程表由課程TimeTable[i][j]和TimeTable[i][k]決定的目標(biāo)函數(shù)值部分是value_variation1，新課程表由課程TimeTable[i][j]和TimeTable[i][k]決定的目標(biāo)函數(shù)值部分是vale_variation2， 目標(biāo)函數(shù)差值是value_diff.value_variation1和value_variation2都取決于TimeTable[i][j]和TimeTable[i][k]，確切地說是取決于課時TimeTable[i][j]和TimeTable[i][k]對應(yīng)課程上面的約束（硬約束和軟約束）?；诰植坑嬎愕脑砉饺缦拢?/p>

value_diff=（value_constant + value_variation2）

-（value_constant+value_variation1）

=value_variation2-value_variation1

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

（2）約束的完備性：目標(biāo)函數(shù)要計算到排課要求的所有約束。

（3）約束的影響因子：硬約束的影響因子要高于軟約束；軟約束的影響因子確定原則，越重要的軟約束（根據(jù)排課面臨的現(xiàn)實情況權(quán)衡），其影響因子越高（不應(yīng)高過硬約束），確保算法優(yōu)先滿足。

3.2.3 SA參數(shù)設(shè)置

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

4 結(jié)果與結(jié)論

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

參考文獻(xiàn)

[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ìn)遺傳算法在排課問題中的應(yīng)用研究[J].微型電腦應(yīng)用，2013，29（10）：48-51.

[3]王園園.遺傳算法在高校排課系統(tǒng)中的應(yīng)用[J].淮北職業(yè)技術(shù)學(xué)院學(xué)報，2015，14（3）：134-135.

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

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

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