基于遺傳算法的優(yōu)化排課系統(tǒng)研究

徐萍

摘要：該文基于學(xué)分制排課出現(xiàn)的問題，分析了遺傳算法原理并對(duì)其進(jìn)行了改進(jìn)。指出了遺傳算法中選擇方法使用輪盤方法。最終將改進(jìn)的遺傳算法應(yīng)用到選課系統(tǒng)中，結(jié)果表明改進(jìn)算法對(duì)系統(tǒng)使用度有顯著提升。

關(guān)鍵詞：遺傳算法；排課系統(tǒng)；交叉概率

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）14-0166-02

教學(xué)過程中，排課問題一直是一個(gè)讓人頭疼的問題，特別隨著教學(xué)模式的改革，又對(duì)排課問題提出了新要求。實(shí)質(zhì)上排課問題作為組合優(yōu)化中的一種典型問題，早成為世界七大難題中的一種。遺傳算法（genetic algorithm，簡稱GA）是一種進(jìn)化算法，這種算法主要借鑒了生物學(xué)中適者生存、優(yōu)勝劣汰的規(guī)律。由于遺傳算法是最佳化的搜索算法，因此人們?cè)谘芯繌?fù)雜的排課問題時(shí)一般采用遺傳算法，且取得了一定的研究成果。但在當(dāng)前的研究成果中依然還存在兩個(gè)問題，一是排課算法經(jīng)過多次運(yùn)行后發(fā)現(xiàn)終應(yīng)值結(jié)果是不同的，這表面當(dāng)前排課算法離完全收斂于全局最優(yōu)解還有一定的差距；二是搜索最優(yōu)解時(shí)一般采用完全隨機(jī)方法進(jìn)行搜索，這種方法搜索效率較低，沒有一個(gè)十分明確的搜索方向。

生物學(xué)中有一個(gè)著名的雜種優(yōu)勢(shì)理論，這個(gè)理論認(rèn)為不同遺傳因素的動(dòng)植物雜交產(chǎn)生的后代比著純種親本后代有著十分明顯的優(yōu)勢(shì)，如其繁殖能力較強(qiáng)、抗逆性較強(qiáng)等，并認(rèn)為這是自然界中普遍存在的一種現(xiàn)象。雜交優(yōu)勢(shì)主要表現(xiàn)為動(dòng)植物遺傳因素差異越大則其雜交優(yōu)勢(shì)就越為明顯；動(dòng)植物親本越純，其后代就具有較明顯的雜交優(yōu)勢(shì)。

1 排課系統(tǒng)中遺傳算法設(shè)計(jì)

遺傳算法第一步是通過隨機(jī)方式產(chǎn)生多個(gè)求解問題的編碼，這些編碼稱為染色體，這些染色體可以組成群體。通過適度函數(shù)對(duì)群體中的每個(gè)染色體進(jìn)行評(píng)估，選擇適應(yīng)度高的染色體，并將這些染色體參加到遺傳操作中，通過遺傳操作形成新的種群。采用迭代的方法，直到到達(dá)算法設(shè)置的終點(diǎn)條件，該算法結(jié)束。在高校排課系統(tǒng)中，每一次教學(xué)課程便是一個(gè)染色體，染色體的結(jié)構(gòu)可以用向量表示：排課結(jié)果是由所有教學(xué)課程組成，該結(jié)構(gòu)是一個(gè)二維數(shù)組，該結(jié)構(gòu)比較復(fù)雜同時(shí)數(shù)據(jù)量大。遺傳算法中引入適應(yīng)函數(shù)用于選擇優(yōu)異的數(shù)據(jù)，排課系統(tǒng)中的適應(yīng)函數(shù)是由約束條件轉(zhuǎn)化得到的，這些因素包括：教室利用率、教師上課時(shí)間分布及班級(jí)課程分布等。

遺傳算法為排課系統(tǒng)內(nèi)核，因此性能優(yōu)異的遺傳算法直接影響到排課系統(tǒng)運(yùn)行。遺傳算法由4個(gè)參數(shù)控制：選擇、交叉、變異及終止。

1）選擇。排課系統(tǒng)中遺傳算法的選擇操作方法是使用輪盤賭博方法，根據(jù)輪盤上的區(qū)域比例進(jìn)行分配。其中適應(yīng)度高的所占的比例高，因而選中的可能性就高，適應(yīng)度低的所占比例低，選中的可能性就低。輪盤方法作為選擇操作可以避免基因缺失從而提高了計(jì)算效率及全局收斂性。

2）交叉。交叉參數(shù)是染色體與染色體之間形成新的染色體方法，遺傳算法的全局搜索速度由交叉所控制。在高校排課系統(tǒng)中，涉及課表合理性，因此不能使用雙點(diǎn)交叉及單點(diǎn)交叉，通常使用交叉時(shí)間段；在此需要考慮到班級(jí)內(nèi)部交叉可能會(huì)影響到其他班級(jí)課表合理性。在使用交叉運(yùn)算時(shí)需要進(jìn)行沖突計(jì)算，確保生產(chǎn)的課表是合理的。如圖1為交叉運(yùn)算流程。

3）變異。變異參數(shù)在遺傳算法中為新個(gè)體的產(chǎn)生提供輔助作用，遺傳算法的局部搜索能力就是由變異決定的。為了算法搜索能力的提高需要將變異和交叉結(jié)合在一起。高校排課系統(tǒng)需要考慮到課表的合理性，使用簡單的變異方法不能解決課表合理性。因此需要使用變異概率，算法中的變異概率通常很小，在變異時(shí)會(huì)產(chǎn)生一個(gè)隨機(jī)數(shù)r（0

4）算法終止條件。當(dāng)個(gè)體到達(dá)最有條件，同時(shí)適應(yīng)度也剛好飽和，進(jìn)行進(jìn)化算法也不會(huì)找到更好結(jié)果。在排課系統(tǒng)中對(duì)進(jìn)化次數(shù)進(jìn)行限制，通常迭代次數(shù)在200到600之間。

2 優(yōu)化排課系統(tǒng)實(shí)現(xiàn)

優(yōu)化排課系統(tǒng)的實(shí)現(xiàn)是以服務(wù)器/客戶機(jī)環(huán)境為基礎(chǔ)的，在此系統(tǒng)中將排課、課程表管理、資源管理等結(jié)合在一起，學(xué)校各院系都分配到了排課的相關(guān)工作內(nèi)容。各院系在排課時(shí)，首先通過客戶機(jī)填寫相關(guān)的開課信息，開課信息填寫完畢后會(huì)通過網(wǎng)絡(luò)傳輸至服務(wù)器中，服務(wù)器會(huì)根據(jù)開課信息進(jìn)行排課，然后再講排課安排發(fā)送至各院系，最后院系將排課表打印出來即可，如果排課相出現(xiàn)不合理的情況時(shí)，各院系可自行進(jìn)行調(diào)整。如圖3所示為優(yōu)化排課系統(tǒng)流程圖。

針對(duì)上述分析算法，本文使用C#語言進(jìn)行代碼編寫。部分代碼如下所示。

Class CourseUnit

{

List Schedule = new List（）；

private int ID；

private const int CourseCount = 8；

private const int WeekDay = 5；

private int[] Array = new int[WeekDay * CourseUnit.CourseCount]；

private CourseUnit （int id， int[]array）

{

Array = array；

ID = id；

}

}

結(jié)果表明：當(dāng)處于1到350代時(shí)遺傳算法可以很快很明顯的在排課系統(tǒng)中得到提升，當(dāng)處于400代時(shí)遺傳算法的特點(diǎn)就開始顯現(xiàn)出來，此時(shí)在4.810e-004之間進(jìn)行收斂，此時(shí)的遺傳算法會(huì)在最優(yōu)解附近進(jìn)行收斂和徘徊，甚至?xí)Ｖ埂?/p>

3 結(jié)束語

除了基于遺傳算法來優(yōu)化排課系統(tǒng)外，要想進(jìn)一步的對(duì)排課系統(tǒng)進(jìn)行優(yōu)化，還要從下面幾個(gè)地方入手：對(duì)課程表問題出現(xiàn)的先行條件進(jìn)行提取，再將這些條件集中起來通過對(duì)搜索引擎的優(yōu)化對(duì)排課進(jìn)行優(yōu)化；對(duì)排課中出現(xiàn)的各種問題進(jìn)行綜合、全面的考慮，找出這些問題之間的規(guī)律；排課中會(huì)出現(xiàn)各種狀況，但狀況不同其權(quán)值是不同的，因此就需要去權(quán)值進(jìn)行衡量、考慮。

參考文獻(xiàn)：

[1] 汪曉飛， 李曉寧. GA編碼方案在高校排課系統(tǒng)中的應(yīng)用[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2008， 29（17）： 4565-4567.

[2] 于娟， 尹積棟. 面向排課系統(tǒng)的遺傳算法改進(jìn)研究[J]. 太原理工大學(xué)學(xué)報(bào)， 2012（5）： 573-579.

[3] Srinivas M. Genetic algorithms： A survey[J]. Computer， 1994， 26（6）： 17-26.

[4] 蘇仰娜. 基于遺傳算法的優(yōu)化排課系統(tǒng)[J]. 河南大學(xué)學(xué)報(bào)：自然科學(xué)版， 2005（1）： 76-77.

[5] 郭俊恩， 刁文廣. 基于規(guī)則和遺傳算法的實(shí)驗(yàn)室排課算法研究[J]. 河南大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2014， 44（3）： 356-359.

[6] 彭復(fù)明， 吳志健. 基于多種群遺傳算法的排課方法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2010（22）： 4877-4880.

[7] 傅亞莉. 基于遺傳算法的高職院校排課系統(tǒng)的研究與實(shí)踐[J]. 吉林廣播電視大學(xué)學(xué)報(bào)， 2010（11）.

[8] 廖宇力. 基于遺傳算法的排課問題適應(yīng)度函數(shù)設(shè)計(jì)[J]. 現(xiàn)代計(jì)算機(jī)：專業(yè)版， 2010（4）：9.

[9] 滕姿， 鄧輝文， 楊久俊. 基于遺傳算法的排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用， 2007（S2）.

[10] 胡義偉， 謝勇， 鄭金華. 基于遺傳算法的綜合性大學(xué)排課系統(tǒng)研究[J]. 中國教育信息化， 2007（21）.