基于改進遺傳算法的排課系統(tǒng)

江民斌

一、引言

時間表(Timetabling)問題是一類優(yōu)化組合受限多元資源的調(diào)度問題，其擁有非常廣泛的應用領域，像醫(yī)院病房調(diào)度、航班時刻表、列城市公路運營、車時刻表等等。到目前已經(jīng)證明該類問題是一種NP完全問題，而NP完全問題不存在時間復雜度為多項式時間的算法。本文中的編排學校課程表是解決時間表問題的一個應用.

解決這類問題早期主要是以臨界資源分配算法為主，后來美國Michigan大學學者Holland提出了遺傳算法，遺傳算法是一種借鑒了自然界遺傳和選擇機制的搜索算法，具有魯棒性強、通用、簡單等的優(yōu)點。但遺傳算法本身存在算法初期早熟現(xiàn)象、算法后期進化緩慢的現(xiàn)象，本文利用加權(quán)可控方法改進遺傳算子,從而有效地克服了這一缺點。

二、遺傳算法及編碼

遺傳算法是一種搜索最優(yōu)解或局部最優(yōu)解的方法，這種方法的實現(xiàn)是通過模擬自然的進化過程得來的。它結(jié)合了在生物科學中遺傳的概念與計算機科學中的算法概念，由潛在的問題可能的解集的某個種群開始，以不斷進化的方式持續(xù)地迭代種群, 逐漸地產(chǎn)生出互不相同的各種基因組合，不同的問題解，最終搜索出我們所期望問題的最優(yōu)解或近似最優(yōu)解。簡單遺傳算法只使用變異算子、交叉算子、選擇算子這三個基本遺傳算子，其操作過程可以說相當簡單，但它們提供給了遺傳算法一個很基本很簡單的框架。定義：SGA=(E，M，P，C，Ψ，T,Φ，r)，式中，E為個體適應函數(shù)，M為群體的大小，通常取 20~100，P為初始種群，C為個體編碼，可以用固定長度二進制符號串來進行編碼，Ψ為使用基本位變異算子，T為終止條件，通常終止進化迭代數(shù)為100~500，Φ為使用比例選擇算子，r為使用單點交叉算子。

首先是編碼，使得能在此基礎上可適用未來的遺傳演化操作，本文中采用十進制數(shù)制編碼方法。我們設定每條染色體代表每位任課老師的課表，基本的染色體編碼為:任課老師編碼+上課班級編碼+選修課程編碼+授課教室編碼十時間安排。例：某任課老師的身份編號為1347要講授“數(shù)據(jù)結(jié)構(gòu)”這一門專業(yè)基礎課程，“數(shù)據(jù)結(jié)構(gòu)”課程的編號為8217，每一周的課時量大小為4，所授班級的編號設若為01801、01802，首先我們可以隨機地產(chǎn)生上課時間，再隨機選擇合適的教室，這時我們就可以利用預定的組合規(guī)則生成染色體如:“134701801018028217024012241“，這里的后9位代表上課時間（星期二的34節(jié)和星期四的12節(jié)）。

三、適應度函數(shù)與種群初始化

遺傳算法在進化中要是需要選取下一代種群個體，它是是以個體的適應度數(shù)值的大小為依據(jù)來進行的。因此一個適應函數(shù)的設計，其好壞最終結(jié)果，而其可能具體表現(xiàn)為遺傳算法的收斂緩慢，不能在較短時間結(jié)束，失去了實際意義，另外也可能會導致這種算不并不能找到最優(yōu)解甚至不能逼近近似最優(yōu)解。本文中，設計適應函數(shù)的主要考慮是采用賦相應權(quán)值，最終對沖突進行加權(quán)求和來實現(xiàn)，比如：我們設計以權(quán)值Wi代表的是第i條規(guī)則的重要程度，若是某染色體違反了某條規(guī)則i，則將其值Pi置為1(若沒有違反規(guī)則i，則Pi值為0)，其受到的懲罰值為Wi*Pi，對染色體中存在的沖突進行加權(quán)求和并加上1后，再求其倒數(shù)，即適應度函數(shù)可以設計為，染色體的加權(quán)總和與1相加的倒數(shù)值。

這樣一來，我們得到的染色體適應函數(shù)數(shù)值越大，表示該染色體擁有越好的教室和授課時段，因此我們將其看成一個好的個體，使其在下一代的演化中的生存可能性變得更大。

為了給后面的遺傳操作（選擇、交叉、變異）提供進化的進化的基礎，所以首先需要初始化種群得到最初起始代。在本文中，由于是采每次對具體的某一位任課老師進行遺傳操作，這時的初始化時參數(shù)設定就一定要考慮到時間和教室，做好其參數(shù)的設定，目的是為了避免一個遺傳進化得到一個不合理的結(jié)果――小班級占用大教室，這里面我們可以設定額外的參數(shù)包括教室可容人數(shù)的最優(yōu)逼近，此外還需要考慮到上課時間合理性安排等。本系統(tǒng)中，為了生成初始課表，我們采用隨機搜索空閑空間的方法來生成。再對保留一個空閑集給每一個班級，idleTime(c)和一個未搜索空間SearchTime(c)，對從Lc(c∈C)令nosearchTime(c)=idleTime(c)，產(chǎn)生隨機時間p ∈nosearchTime (c)。若是發(fā)現(xiàn)有沖突的話，則nosearchTime (c)=nosearchTime (c)-l，然后接著繼續(xù)搜索。否則timetable(c，p)=Lc(c∈C)。idleTime (c)=idleTime(c)-l。反復循環(huán)上述過程，直到生成了我們目標需要的課表。

四、遺傳算子的改進

在對課程編排問題的分析過程中，對于任何一種編排策略的評價相對來說比較難，情況也顯得非常復雜，因為這中間包含有許許多多的來自任課老師、上課班級、授課教室等方方面面的要求與規(guī)則。課程編排中的規(guī)則，我們一般使用預定義約束條件的這種方式來約定遵守，從而要求可以把它們描述為我們對課程安排策略的目的，而這可以按照課程編排的一些關鍵因素對時間有要求的共性，借由統(tǒng)計所安排的時間這種方式來滿足要求。

（一）節(jié)次優(yōu)先級問題

我們對有特殊要求的課進行的優(yōu)先度表示，是學生是否愿意上此節(jié)課的程度刻畫，也可以是對于人們上這節(jié)課所得到的效率的高低。時間優(yōu)先度 （O 1）反映對課程的每個節(jié)次的級別，由管理員借經(jīng)驗或一些歷史數(shù)據(jù)的統(tǒng)計來設置，體現(xiàn)不同學生在不同學期的特殊要求。

在節(jié)次優(yōu)先級的基礎上，我們可以對交叉運算作一個調(diào)整，即在操作上對優(yōu)先級相差更大者給予更高的交叉概率，概率計算方式為兩個優(yōu)先度的距離與優(yōu)先度和的一個比值。這樣一來，對結(jié)果的節(jié)次優(yōu)先級滿意度采用節(jié)次優(yōu)先級平均值來進行評估分析了。

我們用 表示在一次課程編排中第i個開課第j課次上第k節(jié)課的優(yōu)先度,p是總的開課數(shù)，Si是第i個開課的課次數(shù)，Tij是第i個開課第j課次的上課節(jié)數(shù)。于是我們可以用所有的 的和去除以所有Tij的和即可以得到節(jié)次優(yōu)先級平均值，假設結(jié)果用 表示，可以看出， 值越大越好，因為它意味著安排的節(jié)次越好。

（二）課時分布均勻度問題

在排課的具體要求上，應該避免課程在班級課表上的安排異常地某一個整天無課或課程集中于某一天的現(xiàn)象，本文用課時分布均勻度來評估課程編排中在每天的日課程的均勻程度，我們用 表示班級每天上課的平均節(jié)數(shù)，參數(shù) 為班級參數(shù)Ci在第d日的節(jié)數(shù)，參數(shù)dw為總的工作日數(shù)量，則關于一個班級的課時分布日方差值 可以用dw個工作日內(nèi)所有 的幾何平均值來計算得到。

定義了這樣的衡量標準后，為達到目標的極大化，可采取的策略是結(jié)合遺傳算子，對變異運算進行加權(quán)控制，當某天課程較滿時，加大變異的權(quán)重，調(diào)適后判斷課時分布日方差值 的大小，班級課時日分布方差越小，則體現(xiàn)了相應的課時日分布也就越均勻，這樣就在總體上為我們保證了學校課時的日分布走勢趨向于均勻，也就可以避免在某天中里面的某節(jié)次排課教室使用的高峰，這樣一來就可以在一定程度上提高了授課教室的利用率。

五、實驗結(jié)果

實驗首先對擁有527個教師，312個班級，以及412門課程和165個大小教室的輸入按周一至周五僅排白天第1節(jié)到第8節(jié)進行自動排課，其中上午時間優(yōu)先，另外對一些特殊課程，特殊教師的相應課程在初始化參數(shù)的時候作了優(yōu)先級設置，在演化過程中進行人工加權(quán)參數(shù)干預，最終得到了較好的排課效果。另一組實驗表明，當輸入數(shù)據(jù)逼近飽和需求――需要的教室*時間接近可支配的教室*時間數(shù)時，演化過程明顯變慢，在沒達到理想解的情況下，出現(xiàn)了“高原現(xiàn)象”。

潘偉.基于遺傳算法的魯棒控制問題研究［D］東北大學,2006