一種基于遺傳算法的時間表問題求解算法

摘 要：排課問題是一個多因素的優(yōu)化決策問題，是組合規(guī)劃中的典型問題，其屬于NP完全類問題。給出了該問題的數(shù)學模型。遺傳算法借鑒生物界自然選擇和遺傳機制，使用群體搜索技術，處理傳統(tǒng)搜索方法難以解決的復雜的非線性問題。針對時間表問題，提出一種基于遺傳算法的解決方法，定義了一個新穎的染色體編碼方式，基于該編碼，進一步分析并設計出交叉和變異2個遺傳操作，運行結果顯示該方法可行。

關鍵詞：時間表問題；組合規(guī)劃；遺傳算法；多因素優(yōu)化決策；編碼方案

中圖分類號：TP311.11文獻標識碼：B

文章編號：1004-373X(2008)08-082-02

Algorithm for Sloving Time Table Questions Based on GA

WANG Ting，WU Chenwen

(School of Electronic and Information Engineering，Lanzhou Jiaotong University，Lanzhou，730070，China)

Abstract：Timetable problem is a multifactor optimized decision problem and is typical problem in constitution and planning.It has been proved as a kind of NPcomplete problem.Genetic Algorithm(GA) is based on the biological mechanism of natural selection and heredity，leveraging colony searching technology，and is particularly applicable for the resolution of complicatednonlinear problems intractable with traditional searching methods.This paper designs the genetic arithmetic about the time table problems，a new method chromosome encoding is designed，based on which Genetic operations crossover and mutation are proposed.The experimental result shows the algorithm works well.

Keywords：time table question;genetic algorithm;multifactor optimized decision;encoding scheme

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

1 課表編排問題的描述

設有班級集合C={c1，c2，…，ca}，教師集合P={p1，p2，…，pβ}，教室集合R={r1，r2，…，rγ}和時間的集合T={t1，t2，…，tμ}。時間與教師的笛卡爾積稱為N=T×R={(t1，r1)，(t2，r2)，…，(tμ，rγ)}N中的元素稱為時間教室對。給出1組課程L={L1，L2，…，Lλ}，L中的元素代表一個5元組{h(i)，p(i)，c(i)，r(i)，req(i)}。其中h(i)為周學時數(shù);p(i)∈P為任課教師;c(i) ∈C為上課班級;r(i) ∈R為可用教室;req(i)∈{req1，req2，…，reqθ}是一組時間，教室和教學方式等的限制條件或要求。

課表編排就是要求L到N的冥集 2N 中的一個映射，即ψ:L>2N并滿足如下條件: 

(1) 設ψ(Li)=X∈2，如果Xi中選用的時間集合{t1，t2，…，tn}T，選用的教集合為R(i)a，則要求:

R(i)aR(i)

(2) 如果ψ(Lm)=X′mψ(Ln)=Xn，且m≠n，則必須Xm∩Xn=，即同一時間中一教室不能被兩門以上的課占用。

(3) 如果ψ(Lm)=X′mψ(Ln)=X′n，且m≠n，則當c(m)∩c(n)≠或p(m)=p(n)時，就有:{t(m)1，t(m)2，…，t(m)μ}∩{t(n)1，t(n)2，…，t(n)μ}=φ，即同一班級不能同時上2門以上的課滿足Req(i)中的限制條件與要求。

(4) 設有二部復圖Hb(V，E)包含有頂點集合劃分為2個子集X和Y，其中的元素分別與給定的課程和時間教室對一一對應，E中的元素表示各門課與時間教室對的關系，若課程Li∈X在時間教室對集{(t(i)1，r(i)1)，(t(i)2，r(i)2)，…，(t(i)μ，r(i)γ)}∈Y中的數(shù)字，則Ei=({Li}，{(t(i)1，r(i)1)，(t(i)2，r(i)2)，…，(t(i)μ，r(i)γ)})∈E。

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

2 課表編排問題的遺傳算法

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

2.1 編碼方案

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

設有一格雷碼串(bnbn1…b0)其解碼過程如下:



if b0:=1 then x=1 else x=0；

for i:=1 to n do

if b1=1 then

x:=2i+1-1-x；/*用其對稱特性*/

串長為m1×n1，m1為各參數(shù)(即課程)的編碼長度;n1為參數(shù)的個數(shù)(即課程的門數(shù))，串中個參數(shù)所對應的值為該門課程所選“時間教室對”集的序號，這樣構造串結構m1最短，故串長也最短。

2.2 控制參數(shù)選擇

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

(2) 雜交操作

雜交算子是遺傳算法中最常用，最重要的算子，通過雜交運算從一對母代染色體產(chǎn)生2個子代染色體。通常使用的雜交算子有單點雜交算子和雙點雜交算子。其中單點雜交算子首先隨機選擇一個雜交點，將該雜交點到染色體末尾的基因片段互換，比如:設第t代的2個個體為Xta=(1，2，3，4，5)和Xtb=(6，7，8，4，5)，設雜交點為3，則得到新一代的2個個體為Xt+1a=(1，2，3，9，10)和Xtb=(6，7，8，4，5)。2點雜交則是依概率交換2個父串具有同樣長度的二進制串，其中0表示不交換，1表示交換。這個二進制串稱為雜交模版；然后則根據(jù)該模版對2父串施行雜交，所得的2個新串即為后代串。經(jīng)過實驗發(fā)現(xiàn)當種群規(guī)模N較小時，采用雙點交叉性能優(yōu)于單點交叉；但當種群規(guī)模N較大時，單點交叉反而優(yōu)于均勻雙點交叉。另外雜交概率取值為P0=0.8。

(3) 變異操作

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

2.3 適應度函數(shù)

由于課表編排問題是求目標函數(shù)最大值^[3]，適應度函數(shù)定義如下:

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

(1) 該種群中最大適應值為一正數(shù);

(2) 2當前種群中最大適應值與以前各代中最大適應值相差不大，這時說明效果不太顯著，再進化下去沒有必要。

3 實驗結果及結論

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

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

參 考 文 獻

［1］石純一，張鈸，林堯瑞.專家系統(tǒng)原理與實踐\\[M\\].北京：清華大學出版杜，1986.

［2］潘正軍，康立山.演化計算\\[M\\].北京：清華大學出版社，1998.

［3］黃干平，陳洛資.解“時間表問題”（TTP）的啟發(fā)式算法［J］.計算機應用與軟件，1997，14(2):6064，59.

作者簡介 王 婷 女，1981年出生，甘肅蘭州人，碩士。主要從事計算機算法，演化計算、計算機網(wǎng)絡方面的研究工作。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文