劉海燕

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

關(guān)鍵詞：排課 遺傳算法 多目標(biāo) 優(yōu)化

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

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

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

一、遺傳算法

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

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

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

（3）適應(yīng)度函數(shù)。適應(yīng)度函數(shù)是遺傳算法來衡定個體是否是最佳結(jié)果的標(biāo)準(zhǔn)，然后確定該值是否再向下遺傳，有很多問題是直接將目標(biāo)函數(shù)設(shè)定為適應(yīng)度函數(shù)，從而確定選定的值是否為最佳。

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

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

二、排課問題分析

（一）排課分析指標(biāo)

1.排課最基本的要求

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

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

（二）排課問題的具體設(shè)計

1.遺傳算法編碼

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

2.產(chǎn)生初始基因和沖突的檢測

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

3.適應(yīng)度函數(shù)的選擇

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

4.選擇函數(shù)

采用輪盤賭來選擇基因，該方法將一個輪盤分為多個區(qū)域，區(qū)域的大小是根據(jù)適應(yīng)度的大小來劃分，適應(yīng)度值高，所占的比例就大，也就是下一代會更適應(yīng)目標(biāo)。

5.交叉和變異

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

6.遺傳算法流程

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

三、實例分析

（一）測試數(shù)據(jù)

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

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

（二）仿真結(jié)果分析

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

四、結(jié)論

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

參考文獻：

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

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

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

[4]張旭.基于遺傳算法的中職在線排課系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機產(chǎn)品與流通，2017（11）.

責(zé)任編輯：趙慧敏