徐萍

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

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

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

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

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

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

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

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

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

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

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

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

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

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

針對上述分析算法，本文使用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代時遺傳算法可以很快很明顯的在排課系統(tǒng)中得到提升，當(dāng)處于400代時遺傳算法的特點就開始顯現(xiàn)出來，此時在4.810e-004之間進(jìn)行收斂，此時的遺傳算法會在最優(yōu)解附近進(jìn)行收斂和徘徊，甚至?xí)Ｖ埂?/p>

3 結(jié)束語

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

參考文獻(xiàn)：

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

[2] 于娟， 尹積棟. 面向排課系統(tǒng)的遺傳算法改進(jìn)研究[J]. 太原理工大學(xué)學(xué)報， 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é)報：自然科學(xué)版， 2005（1）： 76-77.

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

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

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

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

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

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