改進遺傳算法在排課問題中的應用研究

崔玉連，楊新鋒

0 引言

高校排課問題是一個多元分配問題，它研究如何把學生和老師分配給課程、課程單元或者班級，如何把上課事件分配給教室和時間[1]。1975年S.Even證明了高校排課問題在本質上屬于NP完全問題。解決此類問題的常用方案有貪婪算法、遺傳算法、模擬退火算法、專家系統算法、蟻群算法、圖論算法等。因遺傳算法具有群體搜索策略、群體中個體之間的信息交換不依賴于初始參數的特點和良好的并行性、通用性、穩定性，成為求解該類問題的主流方法[2]。

1 遺傳算法

遺傳算法(Genetic Algorithms, GA)是一種利用模擬自然進化過程而搜索最優解的算法，是通過研究達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程而產生的，是一種運算速度較快、系統性較強的新型算法[3]。

遺傳算法模擬自然進化過程，包括選擇、交叉、變異等操作[4]。首先在基礎問題數據中隨機地選取若干個體形成初始種群，然后運用適應度函數計算個體的適應度函數值。根據適應度函數值，判斷每個個體是否滿足優化準則，如果不滿足就繼續生產下一代個體，可以通過交叉、變異操作生產新的個體，從而構成新的種群，再計算新種群中每個個體的適應度函數值，若滿足優化準則就停止迭代，否則繼續進行下一代種群的生產，直到滿足優化準則為止。

2 排課問題描述

2.1 排課問題的約束條件

排課問題需要考慮的相關因素很多，包括課程、班級、教師、教室、時間及上課事件等，其概念模型，如圖1所示：

圖1 排課問題概念模型

需要解決的利益沖突有多種，排課過程中的沖突可以用約束條件來表示。排課問題中的約束條件分為3類：基本約束、硬約束和軟約束。

（1）基本約束是指各因素之間不可能發生的沖突，屬于不可調和矛盾，滿足基本約束是排課的最基本要求。基本約束條件包括：1）班級的約束：一個班級在一個時間內只能上一門課程；2）教師的約束：一個教師在一個時間內只能上一門課程；3）教室的約束：一個教室在一個時間內只能有一門課程。

（2）硬約束是依據學校的實際情況，排課時必須遵循的原則，否則即使安排出課表，生成的課表也不能完整執行。硬約束條件包括：1）按照最小的時間單元（2學時）安排上課時間；2）每門課程都有特定的教學資源；3）教室容量既要能夠容納上課的班級，但又不能超出太多；4）對特定的不能排課時間進行預處理。

（3）軟約束的滿足與不滿足不影響課表的正常執行。一個完美的課程表應該“人性化”，應該考慮的軟約束條件包括：1）盡量在把必修課安排在上午，選修課安排在下午，晚上盡量不安排課；2）一門課在一個星期中的上課時間盡量分散；3）一個教師的課不能連續排滿一整天；4）學生課表中的上課時間不能過分集中；5）同一班級或教師相鄰時間段的上課地點不能相距太遠；

2.2 建立排課問題數學模型

根據以上分析，編排課程表的過程中所涉及的實體集合有：課程、班級、教師、時間、教室，可以如下表示：

時間與教室組成的時間-教室對可以用時間集合與教室集合的笛卡爾積[5]來表示。

其中課程是關鍵實體，與其他實體都有關。課程包括如下屬性：

其中hi為周學時，ci表示該課程的上課學生，可以為多個學生。pi為該課程的任課教師，可以為多個教師。ti表示該課程的上課時間，包括該課程各次上課的時間。ri為該課程的上課教室，每個時間唯一對應一個上課教室。

在以上的5元組中，前3個為已知元組，后兩個為待求元組。

課表編排就是求L到N的冪集2N的一個映射，即ψ:L—＞2N，并滿足基本約束條件。

3 改進遺傳算法在排課中的應用

基于改進遺傳算法的自動排課實現流程，如圖2所示：

圖2 基于改進遺傳算法的自動排課實現流程

遺傳算法可定義為一個8元組[6]：

其中，C為個體編碼方式，P0為初始群體，M為種群規模，Φ為選擇算子，F為交叉算子，N為變異算子，E為個體適應度評價函數，T為遺傳運算終止條件。除了以上8元組之外，還有兩個與遺傳操作相關的參數：

Pc：交叉概率，一般取0.20～0.95;

Pm：變異概率，一般取0.0001～0.1。

自動排課的改進遺傳算法設計就是要將以上 8元組具體化。

3.1 三維編碼

遺傳算法最常用的編碼方式是二進制編碼。結合實際應用需求，均衡考慮制約排課系統的各因素，采用三維編碼，其優點為可方便地利用三維數組保存排課相關信息，編碼和解碼直觀，進行交叉和變異運算時沖突檢測和適應度計算方便以及程序實現復雜度低等。

一個采用三維編碼表示的染色體可直觀地看作一個立方體，如圖3所示：

圖3 三維編碼圖

圖中，X軸為時間軸，每個時間間隔對應一個時間坐標，如X1、X2分別代表周一上午第一、二節課（大課）。以一周5個工作日、每個工作日四個時間段計，共有20個坐標值（X1-X20）。Y軸每一間隔代表一間教室，Z軸每一間隔代表一個授課事件。其中，Z坐標（授課事件）又可劃分為Za（教師）、Zb（課程）和Zc（班級）三個分量。

三維坐標可唯一地確定的一個小方塊，稱作個體基因。其值定義如下：

染色體全部基因塊被賦值后，染色體就代表了一個課表編排方案。

3.2 產生初始種群

群體初始化的目的在于為后面的遺傳操作提供初始群體P0。群體的規模M表示群體所含個體的數量。M取值一般為 20～100。

產生初始種群的步驟如下：

第1步：建立一個三維數組（三維數組表示染色體），把數組中所有元素的初值置0；

第2步：確定授課事件表中的第一個授課事件在一周內的授課次數，用M來表示，根據這個M值將染色體三維數組第一層（垂直Z軸的層）中隨機的M個位置值置1，其它不變；

第3步：確定授課事件表中的下一個授課事件在一周內的授課次數，用N來表示，根據這個N值將對應的染色體三維數組中的那層（垂直Z軸的層）中隨機的N個位置值置1，其它不變；

第4步：重復第3步，直到處理完所有的授課事件為止；

第5步：建立新的染色體三維數組，并重復第2步、第3步和第4步，直到染色體三維數組的個數達到種群規模的大小為止。

3.3 個體適應度評價函數

遺傳算法是在個體適應度評價函數的引導下進行的。由于需要考慮的約束因素很多，因此在設計個體適應度評價函數時，要充分考慮各種因素對評價函數的影響。

針對高校在編排課程表過程中所考慮的實際約束因素，染色體的個體適應度評價函數可以定義為：

評價函數制約因素的期望值及其權值確定為：

期望值 Pl：對應教室利用率（上課人數/教室可容納人數），權值w1=1；

期望值P2：對應同一門課程的均勻分布（如表1所示），權值w2=l；

期望值P3：對應體育課上課時間，權值w3=20。如表2所示：

表1 同一門課程的兩次上課時間間隔及P2取值

表2 體育課上課時間及P3取值

計算個體適應度的方法為：如果存在教師沖突、班級沖突、資源沖突或教室容量沖突，則個體適應度值為 0；如果不存在任何沖突，則個體適應度值為：（同一門課程的均勻分布期望值×1）+（自習上課時間期望值×20）。

3.4 自適應地產生交叉、變異概率

根據以下兩個表達式分別計算交叉概率和變異概率：

其中：0

3.5 選擇操作實現

第1步：將當代種群中所有染色體的適應度函數值進行累加求和得到總的適應度函數值。

第2步：用每一個染色體的適應度函數值除以總的適應度函數值求出每個染色體的選擇率。

第3步：根據選擇率將每一個染色體復制到下一代種群中。

3.6 交叉操作實現

第 1步：從待交叉的個體集合中隨機地選取兩個個體（設為A和B）;

第2步：隨機地選擇A和B發生交叉的位置（設為N UM）;

第3步：將A中Z坐標大于NUM的所有基因塊與B中相同位置的基因塊交換基因值;

第4步：計算出新產生的兩個個體的適應度函數值。

3.7 變異操作實現

第1步：從待變異的個體集合中隨機地選取出一個個體（設為A）。

第2步：采用隨機地方式確定A發生變異的位置，也即確定三維數組中垂直Z軸的某一層。

第3步：根據染色體發生變異的位置對應的授課事件的具體情況，給這個授課事件重新安排上課教室和上課時間，從而產生出新的個體。

第4步：計算出新產生個體的適應度函數值。

3.8 課程表的生成

第1步：在數據庫中建立一個課程空表;

第2步：根據三維數組第一層（垂直于Z軸的層）對應的授課事件及該授課事件所處的上課時間和上課教室，填寫課程表的第一條記錄（如果該授課事件有多個上課時間則填寫多條記錄）

第3步：根據三維數組的下一層（垂直于Z軸的層）對應的授課事件及該授課事件所處的上課時間和上課教室，填寫課程表的下一條記錄（如果該授課事件有多個上課時間則填寫多條記錄）;

第4步：重復第3步，直到三維數組中所有的層（垂直于 Z軸的層）都處理完畢，即所有的授課事件都填入了課程表。

4 測試與分析

在某高校中，利用其原排課系統及采用本文改進算法優化的排課系統分別對某院計算機相關專業學生所上第一學期課程進行了排課測試，共涉及6個班級，35門課程，占用10個教室。測試結果，如表3所示：

表3 原排課系統與優化后系統排課情況對照表

通過上表分析，證明優化后的排課系統確實在很大程度上改善了原有排課系統的不足。

5 總結

本文的研究只是針對某高校的課表編排實際問題，對利用遺傳算法求解排課問題作了一些有益的嘗試，具有一定的局限性。對于比較完善的通用排課系統遺傳算法求解方法還有待進一步的研究。

[1]Gotlieb.The Construction of Class Teacher Time Tables.[c]Proceeding IFIP Congress,Amsterdam,1963:73-74

[2]廖宇力.基于遺傳算法的排課問題適應度函數設計.[J]現代計算機（專業版）,2010(4):18-20

[3]杜健,董玉才,王惠德.基于遺傳算法的高等院校排課系統研究.[J]信息系統工程,2010(8):23-25

[4]趙曉慶,熊璋,方義.高校智能排課系統的設計與實現.[J]計算機與現代化,2004(11):103-105

[5]石慧,彭曉紅,鄔志紅,舒遠仲.求解多校區排課問題的基因對交叉遺傳算法.[J]計算機工程與應用,2010(18)91-93

[6]姜靜,譚博學,姜琳.基于改進自適應遺傳算法的仿真研究.[J]山東理工大學學報（自然科學版）,2008,22(6):10-12