基于改進遺傳算法的排課問題研究

范明杰 懷麗波

摘 要：針對遺傳算法在解決排課問題中易陷入局部最優(yōu)解的缺陷.提出一種改進的遺傳算法。在傳統(tǒng)遺傳算法基礎之上.融合模擬退火思想.使交叉得到的子代以一定概率進入下一代.并對傳統(tǒng)的基于概率的計算方法進行改進.編排出優(yōu)質(zhì)的課表。實驗結(jié)果表明改進算法不僅加快了前期進化速度.而且解決了遺傳算法后期易陷入局部最優(yōu)解的缺陷。

關鍵詞：遺傳算法;排課;模擬退火。

中圖分類號：TP301.6

文獻標志碼：A

0 引言

排課問題是一個多目標、多約束的優(yōu)化決策問題，是一個NP組合優(yōu)化問題r。由于排課的這些特點，排課是教務管理工作中的一個難點。目前我國高校所使用的排課系統(tǒng)大部分只面向于課表編排、解決課程表編排過程中的資源沖突，而沒有充分考慮資源分配的優(yōu)化問題，完全用計算機實現(xiàn)排課的所有過程。

遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的仿生算法[2]。是一種通過模擬自然進化過程搜索最優(yōu)解的方法。其主要特點是群體搜索策略和種群中個體之間的信息交換，具有優(yōu)越的全局搜索能力以及很強的健壯性。適合維數(shù)較高、環(huán)境復雜、問題結(jié)構(gòu)不十分清楚的場合[3]。實踐證明，遺傳算法對于組合優(yōu)化中NP完全問題非常有效[4]。但遺傳算法也存在一些缺陷，如存在易收斂到局部最優(yōu)解的早熟現(xiàn)象等。

1 相關問題簡述

1.1 排課問題

在排課問題中，我們的主要任務是將班級、老師、課程、教室安排在一周內(nèi)某一不發(fā)生沖突的時間。在排課過程中必須嚴格遵守以下硬約束條件：

（1）在某一時間段對某一教師，最多只能為其安排一門課程的教學任務;

（2）在某一時間段對某一班級，最多只能為其安排一門課程;

（3）在某一時間段對某一教室，最多只能安排一門課程;

此外，排課還有一些軟約束條件，在2.2節(jié)會詳細說明。

1.2 遺傳算法

遺傳算法由J.H.Holland教授的學生J.D.Bagley在1967年首先提出[5]，1975年Holland教授出版了第一本系統(tǒng)論述遺傳算法的專著《自然界和人工系統(tǒng)的自適應性》（ Adaptation in Naturaland Artificial Systems）[6]，標志著遺傳算法正式誕生。遺傳算法是一種模擬生物進化機制的隨機搜索算法。其基本思想為：以初始種群為起點，根據(jù)種群中每個個體對環(huán)境的適應度施加特定操作，實現(xiàn)優(yōu)勝劣汰的進化過程。通過多代的進化，使其解逐步逼近最優(yōu)解[7-8]。算法步驟[9]如下：

1）初始化第一代種群。

2）進入繁衍期，進行交叉和變異操作，評估已知染色體適應度，按照適應度進行染色體選擇，形成下一代。

3）不斷繁衍，直至進化終止條件成立。

遺傳算法不需要計算目標函數(shù)的導數(shù)和梯度，也不要求目標函數(shù)具有連續(xù)性，并且算法具有內(nèi)在的隱含并行性和全局尋優(yōu)能力[10]。目前，遺傳算法已被廣泛應用于數(shù)值優(yōu)化、組合優(yōu)化、機器學習、圖像識別、神經(jīng)網(wǎng)絡和模糊控制等眾多領域。

2 改進遺傳算法排課研究

2.1編碼

本次研究中，用一個基因表示一個課元，即一個班級（可能是合班級）的一門課程的所有課次的教師、時間序列和教室安排。基因的構(gòu)成為：課程號十班級序列十教師號十教室號十時間序列。其中課程號，班級序列（合班級則有多個班級號，否則僅有一個班級號），教師號在教學計劃中已經(jīng)給出，教室號和時間號由排課系統(tǒng)產(chǎn)生。染色體是由基因組成的串，一條染色體即為一種排課方案。

2.2 適應度函數(shù)

一個好的排課方案應該盡量滿足一些人為制定的軟約束條件。在本次研究中主要考慮如下軟約束條件：

2.3 遺傳操作

2.3.1 選擇

選擇采用輪盤賭選擇法，具體步驟為：首先根據(jù)種群中個體的適應度不同，將整個種群分布在輪盤上。然后對每個個體的概率進行累積，所有個體的概率和為100%，每個個體占其中的一個百分比段，個體的適應度越大，在輪盤上占的比例就越大。選擇時系統(tǒng)隨機產(chǎn)生一個O～1的百分數(shù)，該數(shù)落在哪個個體的百分比段，就選擇哪個個體，這種選擇法對適應度高的個體選種的機會相對就多，也就是實現(xiàn)了優(yōu)勝劣汰，同時也存在著選擇適應度小的個體的可能性，這樣又保證了群體的多樣性，使保留在較差個體中的優(yōu)秀基因段有機會得以保存[11]。

2.3.2 交叉

交叉算法流程如下：

Stepl：根據(jù)種群各個個體適應度，運用輪盤賭選擇法選出雙親Pl，P2。

Step2：依次更新子代child每一個課元的教室號。更新child某個課元教室號cr_no的策略為：從Pl，P2隨機選取一個父代P，取出P的對應課元的教室號，賦給cr_no。

Step3：求出子代每一個課元的時間分配優(yōu)先度。課元的時間號分配優(yōu)先度一課元班級的周總學時十課元教師的周總教學課時十課元教室的周總課時。

Step4：更新子代未分配時間且時間分配優(yōu)先度最高課元的時間序列ti_list。更新策略為：從Pl，P2隨機選取一個父代P，取出P的對應課元的時間序列，賦給ti_list。

Step5：進行沖突檢查，如果發(fā)生沖突，執(zhí)行Step6，否則執(zhí)行Step7。

Step6：進行沖突處理，處理成功執(zhí)行Step7，否則執(zhí)行Stepl。

Step7：判斷子代是否存在未分配時間的課元。是則執(zhí)行Step4，否則執(zhí)行Step8。

Step8：求child的適應度，比較Pl，P2適應度，優(yōu)先度最高的父親記為P _best。求出兩代個體的適應度差值△f=fitness（P__best）-fitness（ child）。

Step9：計算child進入種群下一代的概率Pc。

Stepl0：取隨機數(shù)r=rand （0，1），如果r

沖突檢查：傳統(tǒng)遺傳算法在有約束的組合優(yōu)化算法中有一定缺點，比如變異新個體以及隨機交叉產(chǎn)生的新個體很可能是無意義的個體[12]，表現(xiàn)在本研究中即為產(chǎn)生沖突課元，因此必須進行沖突檢查。沖突檢查分為時間沖突檢查和教室沖突檢查。時間沖突檢查：更新某個課元時間片為T后，若該課元的班級或者教師在T時間已經(jīng)安排課程，則發(fā)生時間沖突，否則不發(fā)生時間沖突。教室沖突檢查：更新某個課元時間片為T后，若該課元的教室在T時間已經(jīng)安排課程，則發(fā)生教室沖突，否則不發(fā)生教室沖突。

沖突處理分為時間沖突處理和教室沖突處理。

時間沖突處理算法如下：

Stepl：生成l-dch·wcd隨機排列的亂序時間序列RTI，dch為一天能安排的最大學時，wcd為一周上課的天數(shù)。

Step2：取出RTI的第一個未使用的時間片，賦給沖突課元的沖突時間片T。

Step3：對更新的課元進行沖突檢查。若新課元不發(fā)生沖突，輸出時間沖突處理成功，算法結(jié)束。否則執(zhí)行Step4。

Step4：檢查RTI是否存在未取出的時間片。是則執(zhí)行Step2，否則輸出時間沖突處理失敗。

教室沖突處理算法中需要計算某個教室的更換概率。計算方法如下

Pcr—update（cr）=cr_hour（cr）/WH

（8）

其中，cr_hour （cr）為求出教室cr的周安排課時。WH為一周能安排的最大課時。

教室沖突處理算法如下：

Stepl：判斷沖突課元的教室cr是否為指定安排教室。是則執(zhí)行Step7。否則執(zhí)行Step2.

Step2：計算cr所有同類型教室的更換概率。根據(jù)這些教室的更換概率，建立教室選擇輪盤。

Step3：計算cr的教室更換概率Pcr。取0～1隨機數(shù)r，若r≤Pcr，則執(zhí)行Step4.否則執(zhí)行Step7。

Step4：檢測輪盤是否為空。是則返回處理失敗，算法結(jié)束。否則輪盤賭選擇出新的教室new一cr，將new_cr從教師選擇輪盤上去除，并把new一cr賦給cr。

Step5：對新課元進行沖突檢查。發(fā)生沖突則執(zhí)行Step6，否則輸出處理成功，算法結(jié)束。

Step6：判斷沖突類型。若為時間沖突，執(zhí)行Step7，否則執(zhí)行Step3。

Step7：進行時間沖突處理。返回時間沖突處理結(jié)果。

交叉結(jié)果的確定：交叉獲得的子代進入種群下一代的概率計算方法是本文算法改進的核心。設交叉的得到的子代child進入種群下一代的概率為Pc，并規(guī)定雙親中最優(yōu)個體P_best進入下一代的概率Pp =1- Pc。求出兩代適應度差值△，一fitness （P__best）-fitness（ child）.

在傳統(tǒng)的遺傳算法中，Pc=1;

其中g為當前進化代數(shù)，gturn為（0，1）的一個設定常數(shù)。gmax為最大進化代數(shù)。

改進算法不僅在進化前期能夠明顯加快進化速度，而且在進化后期提高了全局搜索能力，能夠較好地解決遺傳算法易陷入局部最優(yōu)解的缺點。

2.3.3 變異

變異操作能夠改善算法的局部搜索能力和維持種群多樣性，分為教室變異和時間變異。

具體流程如下：

3 實驗結(jié)果及分析

為了驗證算法的有效性，以延邊大學5棟教學樓、工學院的5個班級、28個教師、55門課程、20個教室進行仿真實驗。種群規(guī)模取20，模擬退火溫度T = Tmax* 0.96generation，Tmax為最高退火溫度，取Tmax =1000，generation，為迭代代數(shù)。令gturn=0.3，gmax =400。實驗結(jié)果如下：

表一給出了三種算法在不同進化次數(shù)下適應度的比較，圖3給出了三種算法適應度曲線的比較圖。

圖3中的曲線給出了三種算法種群中最優(yōu)適應度隨進化代數(shù)的增加的變化趨勢。可見，在前120代，原混合算法和改進混合算法最優(yōu)適應度增長速度明顯快于傳統(tǒng)遺傳算法。120代左右，傳統(tǒng)遺傳算法和原混合算法均陷入局部最優(yōu)解，改進混合算法最優(yōu)適應度仍呈現(xiàn)良好的增長趨勢。

4 結(jié)論及展望

通過實驗結(jié)果，可以看出改進算法不僅加快了遺傳算法前期進化速度，而且解決了遺傳算法后期易陷入局部最優(yōu)解的缺陷。但公式（10）尚存在進一步的改進空間，包括gturn合適值的自適應選取，以及△f≥0 and g≥gturn*g情況下表達式的進一步優(yōu)化，從而使改進算法性能達到更優(yōu)。

參考文獻

[1]宗薇，高校智能排課系統(tǒng)算法的研究與實現(xiàn)[J]，計算機仿真，2011，（12）：389-392.

[2]劉勇，康立山，陳毓屏，非數(shù)值并行算法[M].北京：科學出版社，1998：150-161.

[3] 呂聰穎，智能優(yōu)化方法的研究與應用[M].北京：中國水力水電出版社，2014.：28-29.

[4]肖俊，遺傳算法的工程應用[J]，計算機科學，2005， （11） ：247 - 248.

[5]BAGLEY J D.The behavior of adaptive systems whichemploy genetic and correlation algorithms [D].University ofMichigan， 1967.

[6]HOLLAND J H. Adaptation in natural and artificial systems[M].MIT press， 1975.

[7] JONG K A D.An analysis of the behavior of a class ofgenetic adaptive systems [Dl. University of Michigan， 1975.

[8] GOLDBERG，D E.Genetic algorithms in search， optimiza-tion， and machine learning [M].Addison-Wesley Publishing.Co.Inc.1989.

[9]高史義，羅小華，盧宇峰，等.基于遺傳算法的功能覆蓋率收斂技術[J].浙江大學學報：工學版，2015，（8）：1509-1515.

[10]賀毅朝，王熙照，李文斌，等，基于遺傳算法求解折扣{O-l）背包問題的研究[J].計算機學報，2016，39（ 12）：2614 -2630.

[11]陳行平，陳江，陳啟華.基于遺傳算法的高校排課系統(tǒng)設計[J].紹興文理學院學報，2004，24（10）：25-28.

[12]劉華森，程文明，張銘奎，等，基于改進遺傳算法的旅客列車席位分配組合優(yōu)化[J].中國鐵道科學，2016，37 （6）：113 -120.

[13]曹恒智，余先川，單親遺傳模擬退火及在組合優(yōu)化問題中的應用[J].北京郵電大學學報，2008，31（3）：38- 41.

[14]劉懷春，劉懷亮，李秀煥，等.改進的混合遺傳模擬退火算法及其在組合優(yōu)化中的應用研究[J].現(xiàn)代計算機：專業(yè)版，2004，（1）：14-16，41.

[15]李敬花.余峰，樊付見，等，基于遺傳模擬退火融合算法的船舶分段裝配序列優(yōu)化[J].計算機集成制造系統(tǒng)，2013，19（1）：39-45.