基于遺傳算法的實訓室多重優先排課方法研究*

梁慧娜，周勁樺

(廣東農工商職業技術學院 計算機系 實訓中心，廣東 廣州 510507)

0 引言

排課問題就是在給定教師資源、教室資源和開課計劃的前提下，如何合理地安排課表問題。其實質是含約束條件的目標函數優化問題，是運籌學中的時間表問題(Timetable Problems，TTPs)[1]。1975 年， EVEN S 證明了高校排課問題在本質上屬于NP完全問題[2]。遺傳算法GA作為隨機優化與搜索方法，通過對可行解進行選擇、交叉、變異等遺傳算法的作用使種群不斷進化，最后得到全局最優解或近似最優解，成為求解排課問題的主要方法[3]。

近年來，高職院校不斷進行擴招，專業、學生、教師不斷增加，使得教室、實訓室等資源變得緊缺，排課問題變得越來越嚴峻。由于各個學校的具體情況各不相同，通用的排課軟件已不能很好地適應每個學校。本文對我院一校多區等實際情況和計算機實訓室課程的特點進行了深入分析，在使用遺傳算法的基礎上結合多重優先的方法先得到初始種群，然后通過遺傳算法的選擇、交叉、變異、迭代進行尋優，最終得到優質課表[4]。相對于其他利用遺傳算法解決排課問題的算法，該算法更具針對性，主要體現在對課程的多重優先的分層編排和課程編碼設計上。

1 計算機系實訓室排課問題分析

本學院有約兩萬名學生，計算機系有學生兩千多名，分布在兩個校區，一、二年級的學生在北校區、三年級的學生在西校區。教師同時擔任兩個校區的課程。學院教務處負責安排理論+實踐課程的理論學時（在多媒體教室上），計算機系負責安排理實一體化課程和理論+實踐課程的實訓學時（在本系實訓室上），計算機實訓室排課是在教務處已排好的理論課課表的基礎上進行。本系有30多間實訓室，除少數專業實訓室（如攝影室、手繪室、網絡實訓室等），大部分均為普通機房，可承擔一般課程的實訓教學，普通機房的配置分為高、中、低三級，根據課程的要求最大化地利用好實訓資源，提高教學效果。

根據本學院的實際情況，實訓室排課除了要滿足一般課表的要求，還有一些特別要求，應遵循的基本原則有：

（1）硬約束條件，即必須滿足的條件：

①教師不能沖突，同一教師在同一時間不能教授兩門課程（課程包括實訓課和理論課）；

②實訓室不能沖突，同一實訓室在同一時間不能安排兩門課程；

③班級不能沖突，同一班級在同一時間不能安排兩門課程（課程包括實訓課和理論課）；

④教師不能在同一個半天在不同校區上課；

⑤課程必須安排在符合基本實訓要求的實訓室上，專業性很強的課程要專門安排專業性實訓室，一般課程按內容要求不能低于最低配置的實訓室；

⑥實訓室容量必須滿足上課學生人數，現有實訓室的容量一般都大于班級人數的編排；

⑦全院公共選修課時間段不安排課程。

（2）軟約束條件，不一定要滿足，但滿足能得到較優解：

①同一門課程在一周之內應間隔排列。如某課程周學時為4學時，以2學時為一個教學單位，需安排兩次，兩次的安排時間有合理間隔；

②同一班級的課程應在一周內分散安排；

③課程盡量安排在上課效果好的時間段，晚上和周五的下午盡量不排課；

④對于上課時間有特殊要求的教師和課程盡量滿足其時間要求。

在以上列出的軟硬約束中，硬約束必須要滿足，而軟約束是在滿足硬約束的前提下盡量滿足。

2 排課遺傳算法設計

2.1 編碼設計

使用二維矩陣來表示一個總的課表。橫坐標表示時間，縱坐標表示實訓室，課程信息包括課程名稱、授課教師、班級、實訓室要求等信息。排課就可以簡化成將課程信息放入這個二維矩陣。采用這種操作，不可能出現同一時間的教室沖突，只要保證在同一時間中教師和班級不沖突，同一半天中教師沒有被安排在不同校區就可以得到一份可行課表。具體編碼設計如下：

（1）二維矩陣的橫坐標表示時間片

高職院校的課程一般兩節課連上，兩節課為一次課，上午兩次課，下午兩次課，因課程較多，有時晚上也需排課。每次課作為一個時間片來安排課程，每天6個時間片，每周5天，則可分為30個時間片。

每個時間片表示為Tij,i∈{1,2,3,4,5}，j∈{1,2,3,4,5,6}，i表示星期幾，j表示一天內的哪一個時間片。具體如表1所示。

表1 時間片示意圖

（2）二維矩陣的縱坐標表示實訓室

實訓室代碼設置為4位，R=（R1R2R3R4），其中：R1表示實訓室所在校區：1表示北校區，2表示本部；R2表示實訓室的配置類型：1表示高配置，2表示中配置，3表示低配置，4表示攝影室，5表示手繪室，6表示網絡實訓室；R3表示實訓室可容納的學生數；R4表示各類型實訓室的編號。

（3）課程信息代碼

課程信息代碼設置為10位，C=（C1C2C3C4C5C6C7C8C9C10），其中：C1表示實訓室所在校區：1表示北校區；2表示本部；C2表示對實訓室的配置類型要求，具體代碼表示與R2相同；C3表示班級人數；C4、C5表示班級代碼；C6、C7表示教師代碼；C8、C9表示課程名稱；C10表示課程每周需上的次數。每門課程根據學時確定每周需上課的次數，一般為1～3。

2.2 初始群體

2.2 .1 初始群體的產生

排課需考慮的約束很多，如果全部直接使用隨機生成的方式很難得到有效的無沖突課表，故本文根據實訓室排課的特點，有針對性地設計了多重優先和隨機生成相結全的方法，生成無沖突課表作為初始基因。

初始基因（無沖突課表）的生成分為兩大部分：

（1）初排

先將課表分為北校區課表和西校區課表兩部分，分別進行預排。初排時將課室信息采用多重優先和隨機的方法將其分層安排到相關的教室，對課室的安排先遵守約束性再隨機，使得實訓資源的分配達到最大化。安排的時間片均隨機。具體如下：

①在已排好理論課的課表基礎上，將全院選修課的時間片標注出來，該時間段不排課；

②將少量的對實訓室有特別要求的課程排入指定的實訓室，如攝影課排入攝影室，手繪課排入多功能手繪室，時間隨機；

③將少量人數多的課程安排到能容納該人數的符合要求的實訓室，時間隨機。因為只有極少的班級人數比較多，也只有一兩個實訓室的容量比較大，一般實訓室的容量都是60位，一般班級的人數也不超過60，所以一般實訓室能容納大部分的班級；

④將對實訓室配置要求為高的課程隨機排入高配置實訓室，時間隨機；

⑤將對實訓室配置要求為中的課程隨機排入剩余的高配置實訓室后，再隨機排入中配置實訓室，時間隨機；

⑥將對實訓室配置要求為低的課程隨機排入剩余的中配置實訓室后，再隨機排入低配置實訓室，時間隨機。

在分配時，同一課程優先分配到同一實訓室。

（2）調整

經過預排后，所安排的實訓室已能滿足課程的需要，而且配置高的實訓室利用率比較高，實現了資源的最大化利用。但現階段的課表有可能會出現教師上課時間沖突、學生上課時間沖突、教師同一個半天被分配到不同校區等問題，所以要進行總體調整。具體操作流程如下：

① 將預排好的北校區和西校區課表合并成一個總課表；

②在同一時間上檢查是否有同一個老師，如果有，則調整到該老師沒有上課的其他時間片，實訓室不變；

③在北校區、西校區同一半天的時間上檢查是否有同一個老師，如果有，則調整時間片，實訓室不變。

④在同一時間上檢查是否有同一個班級，如果有，則調整到該班級沒有上課的其他時間片，實訓室不變。

經過調整，得到初始無沖突課表。課表的樣式如表2所示。一份課表作為一個基因V。

表2 課表樣式

2.2 .2 初始群體規模

2.3 適應度函數

初始群體均為無沖突課表，滿足了課表的硬約束條件，但對軟約束條件的滿足是不一樣的。為了判斷課表的優質程度，得到最優課表，需根據排課的軟約束條件構造相應的適應度函數進行評價。初排時已充分考慮實訓室優質資源的高效使用，現評價只需考慮課程安排的時間。

（1）上課時間效果值計算

課程盡量安排在上課效果好的時間。一般上午上課效果優于下午；下午優于晚上；周一、周二優于周四、周五等。設定的每天各個時間段的效果值如表3所示。

表3 每天各個時間片上課的效果值

整個課程表中占用上課時間的效果值之和為：

（2）課程間隔效果值計算

同一門課程一般一周內安排兩次，在一周之內應間隔排列，間隔效果值如表4所示。

表4 每天各個時間段的效果值

整個課表的課程間隔效果值為：

式（2）中，E表示同一課程一周內的間隔時間的效果值，m為課程的門數。

（3）適應度函數

歸總上面約束函數，得出總的適應度函數為：

其中，p、q為權值，p=30，q=50。

2.4 選擇算子

為防止已經搜尋到的最優解丟失，讓上一次群體中適應度最大的20%的課表直接進入下一代群體中，另外80%的個體使用“輪盤選種”的方法選擇進入下一代基因。

2.5 交叉

因為作為每個基因的課表都是無沖突課程，故在進行交叉和變異時要設計好交叉的方法，不改變課表無沖突的狀態。這里以半天的2個時間片的課程安排作為交換單元，因為如果以一個時間片作為交換因子，有可能在半天里將同一位教師分配到不同校區。教務處已排的理論課程、已定的選修課時間、周五晚上的時間單元對應的內容不作交叉，保留原位。

2.6 變異

在同一時間片里將課程調整到達到最基本配置要求的實訓室的空時間片中。因變異的區域限定在同一時間片里，故可以保證課程表的沖突狀態。

2.7 判斷終止條件

根據需要進行迭代次數的設置，可隨時停止運算。

2.8 得出適應度最高的課程表

計算出適應度最高的課表作為最終優質課表。

3 各類型課程表的生成

由得到的最終優質課表生成各類型的課程表，包括教室安排表、教師安排表、班級安排表。

4 實驗

使用Visual Studio 2010的C#作為實驗程序的編寫工具。程序中通過導入外部文件的方式，可隨時設置教室、班級、教師、課程、學時安排等約束條件，通過遺傳算法的多次迭代得出具有較高適應度的課表。程序運行結果表明，算法的前期收斂速度很快，后期變慢，因為初始基因已為無沖突課表，要得到效率值較優的課表只需較少的迭代次數與時間即可。

5 結論

本文針對我院一校多區等實際情況和計算機實訓課程的特點，基于遺傳算法，使用多重優先的法則先得到無沖突課表作為初始基因，相對于其他使用遺傳算法解決排課問題的方法更高效，設計了效果適應度函數、選擇、交叉和變異的方法，算法快速收斂，能有效得到優質課表。

[1] 廖宇力.基于遺傳算法的排課問題適應度函數設計[J].現代計算機（專業版），2010(4):53-57.

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

[3] 鐘耀廣,劉群鋒.基于遺傳算法的高校排課數學模型[J].東莞理工學院學報,2012，19（5）:4-8.

[4] 于干,張軍. 遺傳算法在自動排課中的應用研究[J].科技向導,2011(30):10-11.