改進遺傳算法在排課問題中的應(yīng)用研究

崔玉連，楊新鋒

0 引言

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

1 遺傳算法

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

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

2 排課問題描述

2.1 排課問題的約束條件

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

圖1 排課問題概念模型

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

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

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

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

2.2 建立排課問題數(shù)學(xué)模型

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

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

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

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

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

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

3 改進遺傳算法在排課中的應(yīng)用

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

圖2 基于改進遺傳算法的自動排課實現(xiàn)流程

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

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

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

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

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

3.1 三維編碼

遺傳算法最常用的編碼方式是二進制編碼。結(jié)合實際應(yīng)用需求，均衡考慮制約排課系統(tǒng)的各因素，采用三維編碼，其優(yōu)點為可方便地利用三維數(shù)組保存排課相關(guān)信息，編碼和解碼直觀，進行交叉和變異運算時沖突檢測和適應(yīng)度計算方便以及程序?qū)崿F(xiàn)復(fù)雜度低等。

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

圖3 三維編碼圖

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

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

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

3.2 產(chǎn)生初始種群

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

產(chǎn)生初始種群的步驟如下：

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

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

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

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

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

3.3 個體適應(yīng)度評價函數(shù)

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

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

評價函數(shù)制約因素的期望值及其權(quán)值確定為：

期望值 Pl：對應(yīng)教室利用率（上課人數(shù)/教室可容納人數(shù)），權(quán)值w1=1；

期望值P2：對應(yīng)同一門課程的均勻分布（如表1所示），權(quán)值w2=l；

期望值P3：對應(yīng)體育課上課時間，權(quán)值w3=20。如表2所示：

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

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

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

3.4 自適應(yīng)地產(chǎn)生交叉、變異概率

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

其中：0

3.5 選擇操作實現(xiàn)

第1步：將當(dāng)代種群中所有染色體的適應(yīng)度函數(shù)值進行累加求和得到總的適應(yīng)度函數(shù)值。

第2步：用每一個染色體的適應(yīng)度函數(shù)值除以總的適應(yīng)度函數(shù)值求出每個染色體的選擇率。

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

3.6 交叉操作實現(xiàn)

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

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

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

第4步：計算出新產(chǎn)生的兩個個體的適應(yīng)度函數(shù)值。

3.7 變異操作實現(xiàn)

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

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

第3步：根據(jù)染色體發(fā)生變異的位置對應(yīng)的授課事件的具體情況，給這個授課事件重新安排上課教室和上課時間，從而產(chǎn)生出新的個體。

第4步：計算出新產(chǎn)生個體的適應(yīng)度函數(shù)值。

3.8 課程表的生成

第1步：在數(shù)據(jù)庫中建立一個課程空表;

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

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

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

4 測試與分析

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

表3 原排課系統(tǒng)與優(yōu)化后系統(tǒng)排課情況對照表

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

5 總結(jié)

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

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

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

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

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

[5]石慧,彭曉紅,鄔志紅,舒遠仲.求解多校區(qū)排課問題的基因?qū)徊孢z傳算法.[J]計算機工程與應(yīng)用,2010(18)91-93

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