徐萍

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

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

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2016）14-0166-02

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

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

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

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

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

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

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

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

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

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

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

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

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é)果表明：當處于1到350代時遺傳算法可以很快很明顯的在排課系統(tǒng)中得到提升，當處于400代時遺傳算法的特點就開始顯現(xiàn)出來，此時在4.810e-004之間進行收斂，此時的遺傳算法會在最優(yōu)解附近進行收斂和徘徊，甚至會停止。

3 結(jié)束語

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

參考文獻：

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

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

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

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

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

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

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

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

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

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