一種基于遺傳算法的時(shí)間表問(wèn)題求解算法

　　時(shí)間表問(wèn)題又稱(chēng)課表問(wèn)題，就是解決對時(shí)間和空間資源爭奪而引發(fā)沖突。20世紀70年代中期，美國S.Even等人論證了課表問(wèn)題是NP完全類(lèi)問(wèn)題。理論和時(shí)間表明，只要課表所涉及的任何信息量稍有變化，就會(huì )導致課表編排選擇方案的劇增，即“組合爆炸”。一般作法是針對具體的應用環(huán)境，忽略一些限制條件，但這樣會(huì )造成使用效果的不理想。本文中提出利用特定條件對課程與教室分批，采用遺傳算法對時(shí)間表問(wèn)題進(jìn)行求解，給出了編碼形式、遺傳算子規則及適應度函數，通過(guò)對某學(xué)校課表編排數據的計算，驗證了算法的有效性。對時(shí)間表問(wèn)題的優(yōu)化求解，起到一定的效果。

1 課表編排問(wèn)題的描述

　　結合上述課表編排的4個(gè)條件，課表問(wèn)題就轉化為二部復圖Hb(V，E)的匹配問(wèn)題。

2 課表編排問(wèn)題的遺傳算法

　　遺傳算法是基于生物的進(jìn)化與選擇機制的優(yōu)化算法。遺傳算法通過(guò)維持一個(gè)群體，并按個(gè)體的適應度的大小重復的進(jìn)行選擇。交叉和變異等操作來(lái)實(shí)現群體內個(gè)體結構的重組，將性能良好的解結構遺傳下去，提高后代的適應能力，從而進(jìn)化到最優(yōu)或次優(yōu)解。遺傳算法的基本步驟：確定編碼方案，確定適應函數，確定選擇策略，控制參數的選擇，遺傳算子的設計，算法終止準則的確定等。

2.1 編碼方案

　　二進(jìn)制編碼是最常用的編碼方案，他類(lèi)似于生物染色體的組成，從而易于用生物遺傳理論來(lái)解釋并使得遺傳操作容易表現。且采用二進(jìn)制編碼時(shí)，算法處理的模式數最多。(設采用k進(jìn)制編碼，碼長(cháng)為1，則所表示的最大整數為k1，模式數為(k+1)1?？梢宰C明k=2時(shí)使得k1=const(常數)時(shí)(k+1)1取得最大值)。但該種編碼方案有相鄰整數的二進(jìn)制編碼可能具有較大的海明距離，如：7和8的二進(jìn)制表示為：0111，1000。這種缺陷在解決連續化問(wèn)題時(shí)降低搜索效率。故在本問(wèn)題求解中，采用格雷碼相鄰整數僅有一位不同的特性可克服二進(jìn)制編碼相鄰證書(shū)可能具有較大海明距離的缺陷。他的解碼過(guò)程如下：

　　設有一格雷碼串(bnbn-1…b0)其解碼過(guò)程如下：

　　串長(cháng)為m1×n1，m1為各參數(即課程)的編碼長(cháng)度；n1為參數的個(gè)數(即課程的門(mén)數)，串中個(gè)參數所對應的值為該門(mén)課程所選“時(shí)間一教室對”集的序號，這樣構造串結構m1最短，故串長(cháng)也最短。

2.2 控制參數選擇

　　(1)種群規模N：筆者經(jīng)過(guò)反復實(shí)驗發(fā)現：N值大進(jìn)化較慢，但易搜索到全局較優(yōu)解，而N值小時(shí)進(jìn)化速度快，但不易搜索到較優(yōu)解，權衡效率和性能，一般N取值為20～100，經(jīng)過(guò)實(shí)驗問(wèn)題N取值為40比較合適。

　　(2)雜交操作

　　(3)變異操作

　　變異算子一般一次只改變一條染色體上的一個(gè)基因，比如，染色體Xt=(1，8，3，6，5)，變異的基因是第3位，則變異后Xt+1=(1，8，7，6，5)。

2.3 適應度函數

　　由于課表編排問(wèn)題是求目標函數最大值，適應度函數定義如下：

　　其中Wij為第i個(gè)體串中對應第j門(mén)課所選”時(shí)間—教室對”集的權重。Count為第i個(gè)個(gè)體所對應的各門(mén)課程之間的沖突次數。C為一負數，其絕對值足夠大，以致于只要出現一次沖突，該適應只便為負，這樣便于終止準則的選定(因為所求解即要求無(wú)任何沖突)。但容易造成各個(gè)體間適應值相差過(guò)大的情況，所以采用線(xiàn)形排名的選擇策略。終止條件為：

　　(1)該種群中最大適應值為一正數；

　　(2)2當前種群中最大適應值與以前各代中最大適應值相差不大，這時(shí)說(shuō)明效果不太顯著(zhù)，再進(jìn)化下去沒(méi)有必要。

3 實(shí)驗結果及結論

　　本算法用C語(yǔ)言進(jìn)行驗證，交叉概率均為0.8，變異概率0.2，種群規模設為70。對某學(xué)校課表編排數據進(jìn)行實(shí)驗，算法運行2 000代，獲得了滿(mǎn)意的結果，所獲得的時(shí)刻表沒(méi)有沖突。當算法運行超過(guò)4 000代以后，其結果會(huì )出現幾處沖突外，但總體結果是比較滿(mǎn)意的。通過(guò)手工調整很容易獲得一個(gè)一個(gè)滿(mǎn)意的時(shí)間表。

　　時(shí)間表問(wèn)題是一個(gè)典型的NP完全問(wèn)題，本文通過(guò)對該問(wèn)題的數學(xué)模型的分析，提出以遺傳算法進(jìn)行求解，算法的運行結果說(shuō)明了該方法是可行的。實(shí)際應用中，還要考慮更多的約束條件，這將是下一步的工作重點(diǎn)。