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

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

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

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

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

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

2.1 編碼方案

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

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

　　串長(zhǎng)為m1×n1，m1為各參數(shù)(即課程)的編碼長(zhǎng)度；n1為參數(shù)的個(gè)數(shù)(即課程的門數(shù))，串中個(gè)參數(shù)所對(duì)應(yīng)的值為該門課程所選“時(shí)間一教室對(duì)”集的序號(hào)，這樣構(gòu)造串結(jié)構(gòu)m1最短，故串長(zhǎng)也最短。

2.2 控制參數(shù)選擇

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

　　(2)雜交操作

　　(3)變異操作

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

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

　　由于課表編排問(wèn)題是求目標(biāo)函數(shù)最大值，適應(yīng)度函數(shù)定義如下：

　　其中Wij為第i個(gè)體串中對(duì)應(yīng)第j門課所選”時(shí)間—教室對(duì)”集的權(quán)重。Count為第i個(gè)個(gè)體所對(duì)應(yīng)的各門課程之間的沖突次數(shù)。C為一負(fù)數(shù)，其絕對(duì)值足夠大，以致于只要出現(xiàn)一次沖突，該適應(yīng)只便為負(fù)，這樣便于終止準(zhǔn)則的選定(因?yàn)樗蠼饧匆鬅o(wú)任何沖突)。但容易造成各個(gè)體間適應(yīng)值相差過(guò)大的情況，所以采用線形排名的選擇策略。終止條件為：

　　(1)該種群中最大適應(yīng)值為一正數(shù)；

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

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

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

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