基于改進(jìn)遺傳算法的排課問(wèn)題研究

范明杰 懷麗波

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

關(guān)鍵詞：遺傳算法;排課;模擬退火。

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：A

0 引言

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

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

1 相關(guān)問(wèn)題簡(jiǎn)述

1.1 排課問(wèn)題

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

（1）在某一時(shí)間段對(duì)某一教師，最多只能為其安排一門(mén)課程的教學(xué)任務(wù);

（2）在某一時(shí)間段對(duì)某一班級(jí)，最多只能為其安排一門(mén)課程;

（3）在某一時(shí)間段對(duì)某一教室，最多只能安排一門(mén)課程;

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

1.2 遺傳算法

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

1）初始化第一代種群。

2）進(jìn)入繁衍期，進(jìn)行交叉和變異操作，評(píng)估已知染色體適應(yīng)度，按照適應(yīng)度進(jìn)行染色體選擇，形成下一代。

3）不斷繁衍，直至進(jìn)化終止條件成立。

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

2 改進(jìn)遺傳算法排課研究

2.1編碼

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

2.2 適應(yīng)度函數(shù)

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

2.3 遺傳操作

2.3.1 選擇

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

2.3.2 交叉

交叉算法流程如下：

Stepl：根據(jù)種群各個(gè)個(gè)體適應(yīng)度，運(yùn)用輪盤(pán)賭選擇法選出雙親Pl，P2。

Step2：依次更新子代child每一個(gè)課元的教室號(hào)。更新child某個(gè)課元教室號(hào)cr_no的策略為：從Pl，P2隨機(jī)選取一個(gè)父代P，取出P的對(duì)應(yīng)課元的教室號(hào)，賦給cr_no。

Step3：求出子代每一個(gè)課元的時(shí)間分配優(yōu)先度。課元的時(shí)間號(hào)分配優(yōu)先度一課元班級(jí)的周總學(xué)時(shí)十課元教師的周總教學(xué)課時(shí)十課元教室的周總課時(shí)。

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

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

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

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

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

Step9：計(jì)算child進(jìn)入種群下一代的概率Pc。

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

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

沖突處理分為時(shí)間沖突處理和教室沖突處理。

時(shí)間沖突處理算法如下：

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

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

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

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

教室沖突處理算法中需要計(jì)算某個(gè)教室的更換概率。計(jì)算方法如下

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

（8）

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

教室沖突處理算法如下：

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

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

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

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

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

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

Step7：進(jìn)行時(shí)間沖突處理。返回時(shí)間沖突處理結(jié)果。

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

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

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

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

2.3.3 變異

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

具體流程如下：

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

4 結(jié)論及展望

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

參考文獻(xiàn)

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

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

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

[4]肖俊，遺傳算法的工程應(yīng)用[J]，計(jì)算機(jī)科學(xué)，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]高史義，羅小華，盧宇峰，等.基于遺傳算法的功能覆蓋率收斂技術(shù)[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2015，（8）：1509-1515.

[10]賀毅朝，王熙照，李文斌，等，基于遺傳算法求解折扣{O-l）背包問(wèn)題的研究[J].計(jì)算機(jī)學(xué)報(bào)，2016，39（ 12）：2614 -2630.

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

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

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

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

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