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

梁慧娜，周勁樺

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

②同一班級的課程應在一周內(nèi)分散安排；

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

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

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

2 排課遺傳算法設計

2.1 編碼設計

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

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

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

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

表1 時間片示意圖

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

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

（3）課程信息代碼

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

2.2 初始群體

2.2 .1 初始群體的產(chǎn)生

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

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

（1）初排

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

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

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

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

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

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

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

在分配時，同一課程優(yōu)先分配到同一實訓室。

（2）調(diào)整

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

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

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

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

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

經(jīng)過調(diào)整，得到初始無沖突課表。課表的樣式如表2所示。一份課表作為一個基因V。

表2 課表樣式

2.2 .2 初始群體規(guī)模

2.3 適應度函數(shù)

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

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

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

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

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

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

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

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

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

式（2）中，E表示同一課程一周內(nèi)的間隔時間的效果值，m為課程的門數(shù)。

（3）適應度函數(shù)

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

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

2.4 選擇算子

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

2.5 交叉

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

2.6 變異

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

2.7 判斷終止條件

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

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

計算出適應度最高的課表作為最終優(yōu)質課表。

3 各類型課程表的生成

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

4 實驗

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

5 結論

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

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

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

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

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