遺傳算法在高校排課中的應(yīng)用

劉海燕

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

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

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

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

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

一、遺傳算法

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

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

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

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

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

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

二、排課問題分析

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

1.排課最基本的要求

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

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

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

1.遺傳算法編碼

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

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

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

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

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

4.選擇函數(shù)

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

5.交叉和變異

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

6.遺傳算法流程

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

三、實(shí)例分析

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

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

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

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

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

四、結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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