基于改進遺傳算法的排課系統

江民斌

一、引言

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

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

二、遺傳算法及編碼

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

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

三、適應度函數與種群初始化

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

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

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

四、遺傳算子的改進

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

（一）節次優先級問題

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

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

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

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

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

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

五、實驗結果

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

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