遺傳算法在高校排課中的應用

劉海燕

摘要：隨著我國高等教育的發展，各高校都力爭在有限的資源下，更為有效地提高教育教學質量，在這個過程中合理地安排培養方案中的課程是一個非常重要的環節，因為這個環節包括教師、學生、教室三個方面的合理應用，本文通過研究高校排課的具體環節和所遇到的問題，針對教室安排、沖突判斷和時間設定三個方面來設定遺傳算法的參數，利用遺傳算法對種群進行初始化和進化，尋找最佳的排課結果，并對算法進行仿真驗證，結果表明，遺傳算法可以應用在高校智能排課當中。

關鍵詞：排課 遺傳算法 多目標 優化

中圖分類號：G642? 文獻標識碼：A? 文章編號：1009-5349（2019）03-0153-02

隨著各高校學生數目的增多;教學質量和教學效果日益被重視;教室、教師、多媒體越來越緊缺;那么如何能將這些資源更為合理地利用，優化各種資源，把最有限的資源最大化地讓學生們利用是各大高校面臨的最難的一個課題，而且各高校為了學生們的個性發展，有一些課程需要選課，有一些課程不需要選課，這無形中加大了排課的難度，因此傳統的手工排課很難滿足學校的要求，應用計算機技術結合智能算法進行排課已經成為高校教學管理發展的必然趨勢。各種智能算法也就隨之產生了。在諸多的排課要求當中，如何綜合地考慮這些要求，并應用算法編排出合理的課表已經是各研究人員和教務一線人員研究的方向。

排課算法是實現智能排課的核心部分，本文將結合學校的實際情況分析課表編排的實際原則和具體要求，綜合各種課表的約束，挖掘排課當中會遇到的各種因素，在設定遺傳算法的各個參數，并通過實際仿真驗證算法的可行性與可信性。

一、遺傳算法

遺傳算法的思想是根據生物進化論的基本思想，將需要解決的問題建立起數學模型，模擬生物進化的整個過程，仿生基因的復制、交叉以及突變來不斷優化個體，從而找到最優化的解，并不斷地淘汰適應度比較低的解。

（1）編碼。計算機識別的是0～1代碼，所以需要將所面向的問題數字化，編輯成二進制數組的形式。遺傳算法中的編碼選擇、交叉和突變都必須是數字類型的編碼進行改變。

（2）選擇。選擇更優化的解作為算法的結果，也就是個體適應度高的就會被留下，適應度函數低的就會被舍棄，如果個體數目為N，那么每個個體被選中的概率就是f（Xi）/（f（X1）+f（X2）+…+f（Xn），也就是所謂的輪盤賭算法。

（3）適應度函數。適應度函數是遺傳算法來衡定個體是否是最佳結果的標準，然后確定該值是否再向下遺傳，有很多問題是直接將目標函數設定為適應度函數，從而確定選定的值是否為最佳。

（4）交叉函數。交叉運算是遺傳算法很關鍵的一步，是以一定的概率將個體當中某處進行交換，一般的步驟是先將群體中的多個個體進行隨機配對，然后再隨機設定交叉點的位置，最后交換染色體相應位置的基因，計算產生新基因的適應度。

（5）變異運算。變異運算是對一個染色體的某一位或者是某一段進行變異操作使其成為新的染色體，首先挑選染色體變異的位置，然后對相應位置的數值進行變異操作。

二、排課問題分析

（一）排課分析指標

1.排課最基本的要求

排課最基本的要求是不能沖突，同一時間同一批學生只能上一門課，同一時間一名教師只能上一門課，教室容量要滿足學生數的要求，教室類型也要和要求保持一致。

其中td表示某一天學生上課的節數，n表示學生們則可以有課的天數，全校各個班級平均值用總數除以班級總數，一般來說，大學里課程平均每天三節左右，因此如果平均值特別高就可能說明教學環節設計不合理或是排課時分布很不均勻。全校課程分布均勻也說明教室利用率高，因此是一個重要指標。此外，要將上課時間設定優先級，盡量將必修課安排在優先級比較高的時間，如果課程超過兩學時，盡量保證有兩節課是間隔分布，教室要根據人數來設定選擇，學生連續的課不要兩個校區來回跑。

（二）排課問題的具體設計

1.遺傳算法編碼

遺傳算法需要對所分析的問題進行編碼，設定為最基本的基因，班級號、教師編號、課程信息組成編碼，需要說明的是大學里每門課程都是兩小節連上，也就是如果周一到周五全上課的話將是25個時間段;課程編號包含了課程的所有信息，在課程編號前面加上一位設定教師的第幾節課，從而更能全面地考慮課程安排;同理，班級序號和教師編號也包含了班級信息和教師信息，因此，系統要得到完善的課表就需要對編碼進行分析和處理。

2.產生初始基因和沖突的檢測

遺傳算法首先需要生成初始群體，這初始群體的設定要避免各種沖突，如果算法運行當中產生沖突，就需要將沖突的時段換掉，消除沖突。

3.適應度函數的選擇

排課問題是一個多種約束的問題，在數學里也就是所求目標在有多個條件束縛的條件下尋找最佳解，遺傳算法需要根據適應度函數的值來確定解的改進和進化方向，因此適應度函數是一個非常關鍵的問題，為了各個方面達到最優，我們設定多個子函數，然后將子函數的和作為整個算法的適應度函數。

4.選擇函數

采用輪盤賭來選擇基因，該方法將一個輪盤分為多個區域，區域的大小是根據適應度的大小來劃分，適應度值高，所占的比例就大，也就是下一代會更適應目標。

5.交叉和變異

在排課中最簡單的交叉就是交換班級，首先判斷交換的班級是否合適，如果合適，將兩條染色體相應位置進行交叉，遺傳算法變異是以特定的概率找到兩個染色體，交換相應的位置，然后判斷是否滿足各種不沖突的條件。

6.遺傳算法流程

具體的遺傳算法流程是：①首先將排課問題數字化，初始化各個指標產生種群;②計算每一個排課方法的適應度;③選擇優異的染色體，進行下一代子體;④對種群中的個體交叉和變異，從而新生個體，再計算新的個體適應度來確定是否進入下一代;⑤判斷是否目前是最優的排課方案，如果是就可以結束程序否則再轉換到②繼續進行計算。

三、實例分析

（一）測試數據

測試數據來自于我校建工學院2017—2018第二學期秋季課表，所有測試過程采用VC++進行編程，基本數據見下表：

其中交叉概率和變異概率通過程序運行的結果可以進行調整。本文通過多次試驗得出當交叉率為0，2，變異概率為0.05時取得了較好的排課結果。

（二）仿真結果分析

由圖表可知當迭代次數達到設定次數的時候算法的適應度值已經趨于穩定，適應度值也是很高，且整個算法對排課的計算過程在10分鐘以內。盡管如此，在實驗過程中，遺傳算法的排課結果還存在著一些問題，比如單雙周的課程還不能很好地排課，特殊教室不能滿足課程的需求，特殊時段要求過多導致程序出現問題，因此出現問題的課程還需要進行再次檢驗，當然這也是少數的特殊情況，也是由于人性化要求過多導致的。因此，在錄入排課要求的時候下屬學院也要衡量其可行性，盡量減少過多要求的課程。

四、結論

通過對排課問題的分析，判斷是一種多目標的優化問題，為了減少人工排課效率低下，容易發生錯誤的問題，本文提出采用先進的遺傳算法來完成該項復雜的任務。仿真結果表明，遺傳算法可以在一定程度上解決排課過程中產生的問題，大量減少了教務工作者的勞動力，是值得推廣的。但是由于排課是一個數據量非常大，考慮問題非常多，約束條件十分復雜，并且不斷變化的綜合性問題，本課題在排課算法思考當中還有很多地方不完備，設計還不是很完美，比如單雙周課程、特殊課程以及提高運行速度等方面，以后也將繼續思考該方面的問題，將遺傳算法的一些方面進行改進，從而達到最佳的排課效果。

參考文獻：

[1]馬傳志，刁樹民，張曉勇等.基于改進遺傳算法的排課方法研究[J].中原工學院學報，2013（2）.

[2]姜靜，譚博學，姜琳.基于改進自適應遺傳算法的仿真研究[J].山東理工大學學報（自然科學版），2008（6）.

[3]宋岐.基于遺傳算法的排課系統開發探究[J].電子測試，2016（Z1）.

[4]張旭.基于遺傳算法的中職在線排課系統的設計與實現[J].計算機產品與流通，2017（11）.

責任編輯：趙慧敏