葉 靖 喻 昕

（廣西大學(xué)計算機與電子信息學(xué)院，廣西 南寧 530004）

排課是教務(wù)部門的常務(wù)性工作，現(xiàn)在許多高校仍然采取計算機輔助人工排課的方式編排課程表。最近十幾年，我國的高等教育事業(yè)迅猛發(fā)展，但教學(xué)資源卻相對有限，很多學(xué)校都面臨著教室和教師資源緊張的問題，在這種現(xiàn)狀下，排課工作的難度和復(fù)雜度都增加了。目前的排課方式，已經(jīng)越來越不易于充分利用已有的資源解決變化著的需求，而且在效率方面的不足也有待提高[1]。因此，研究高效、靈活的自動排課系統(tǒng)，極具現(xiàn)實意義。

排課問題作為時間表問題(Timetable Problems，TTPs)，已被公認(rèn)是NP難解問題，作為組合優(yōu)化問題的一個分支，它是國內(nèi)外許多學(xué)者研究的熱點。智能算法是目前求解復(fù)雜優(yōu)化問題的一類有效方法，它在求解問題時不需要或者只需要很少的關(guān)于問題的先驗信息。這類算法具有很強的魯棒性，而且在多數(shù)情況下都能求得比較滿意的解。常用的方法有：遺傳算法、蟻群算法、模擬退火算法、禁忌搜索等。這些方法都在排課問題中有過應(yīng)用，但每種方法在實際應(yīng)用中又各有優(yōu)劣。本文提出一種遺傳-蟻群混合算法，將遺傳算法與蟻群算法融合，依靠遺傳算法生成信息素分布，利用蟻群算法求精確解，通過優(yōu)勢互補來獲得良好的優(yōu)化性能與時間性能。

1 排課問題描述

排課問題主要涉及的因素有：教師、班級、課程、教室、時段等，要求課程表的安排在這幾個方面不能發(fā)生沖突[2]。為了避免沖突，引入了“約束條件”的概念。排課過程的約束條件可分為“硬約束”和“軟約束”兩類。

硬約束是衡量排課方案可行與否的標(biāo)準(zhǔn)，是排課中必須滿足的。硬約束包括：

（1）同一教師在同一時段只能安排在一個教室授課；

（2）同一個班級在同一時段只能在一個教室上課；

（3）同一教室在同一時段只能安排一門課程；

（4）一門課程被安排的教室座位數(shù)應(yīng)大于或等于該門課程上課人數(shù)。

軟約束是衡量排課方案優(yōu)劣的標(biāo)尺，排課過程中滿足更佳，不能滿足也無妨，滿足與否往往與排課實際情況相關(guān)。軟約束包括：

（1）盡量為專業(yè)課程或較難掌握的課程安排上課效果好的時間段；

（2）同一個班級一周內(nèi)某門課程有多次，則幾次課在時間上必須有一定的間隔；

（3）體育課應(yīng)安排在下午或者上午的第二大節(jié)，體育課后面要避免安排講授課；

（4）實驗課等實踐課程應(yīng)排在下午或晚上。

2 用遺傳-蟻群混合算法解決排課問題

2.1 遺傳算法

遺傳算法（Genetic Algorithm，GA）是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計算模型，是一類借鑒生物界的適者生存、優(yōu)勝劣汰進(jìn)化規(guī)律演化而來的隨機化搜索方法。它是由美國Michigan大學(xué)的John Holland教授1975年首先提出。

遺傳算法是從隨機產(chǎn)生的一個種群開始的，這個種群代表了問題可能潛在的解集，每個種群由經(jīng)過編碼的N個個體組成，每個個體實際是染色體帶有特征的實體。在每一代，根據(jù)個體適應(yīng)度的大小挑選個體，適應(yīng)度大的則被認(rèn)為是優(yōu)良的個體，繼續(xù)進(jìn)化，并借助遺傳學(xué)中的遺傳算子進(jìn)行交叉、變異，產(chǎn)生出代表新解集的種群。這一過程就像自然界的物種進(jìn)化，子代比父代更適應(yīng)環(huán)境。經(jīng)過逐代演化，最終可以產(chǎn)生問題的近似最優(yōu)解。

遺傳算法應(yīng)用到排課中的主要演算步驟[3]如下：

（1）隨機產(chǎn)生一定數(shù)目的初始種群；

（2）對個體的適應(yīng)度進(jìn)行評估，如果個體的適應(yīng)度符合優(yōu)化準(zhǔn)則，則輸出最佳個體及其代表的最優(yōu)解，并結(jié)束計算，否則轉(zhuǎn)向第（3）步；

（3）依據(jù)適應(yīng)度選擇再生個體；

（4）按照一定的交叉概率和交叉方法生成新的個體；

（5）按照一定的變異概率和變異方法生成新的個體；

（6）由交叉和變異產(chǎn)生新一代的種群，然后返回第（2）步。

2.1.1 編碼

常用的編碼方法有二進(jìn)制編碼和浮點數(shù)編碼。為增強程序的可操作性，本文采用十進(jìn)制編碼。每條染色體代表一位教師的課表，其結(jié)構(gòu)如下：

教師ID 班級ID 課程ID 教室 上課時間

例如：數(shù)信學(xué)院的張三老師要給林學(xué)院林學(xué)專業(yè) 2010級1班的同學(xué)上高等數(shù)學(xué)這門課，張三老師的ID為“3692”，林學(xué)院林學(xué)專業(yè)2010級1班ID為“1802101”，高等數(shù)學(xué)這門課程的ID為“110075”，經(jīng)選擇，選定1號樓2層第5間教室，排定的上課時間為星期二第一大節(jié)，則生成的染色體為：“3692 1802101 110075 010205 21”。

2.1.2 適應(yīng)度函數(shù)

遺傳算法在進(jìn)化中是以每個個體的適應(yīng)度值為依據(jù)來選取下一代種群的。在本系統(tǒng)中，適應(yīng)度函數(shù)由以下評價函數(shù)構(gòu)成：節(jié)次優(yōu)度a、日組合優(yōu)度b、組合可行性c、分布優(yōu)化度d、資源優(yōu)化度e。單門課程的適應(yīng)度函數(shù)為：

F=(a*x+b*y)*c*d*e

其中，x和y分別表示節(jié)次優(yōu)度和日組合優(yōu)度所占的權(quán)重，x+y=1，適應(yīng)度函數(shù)的最大值為1。

全局課表的適應(yīng)度函數(shù)為：

其中，n是種群中課程的門數(shù)。

2.1.3 種群操作

（1）初始化種群

在本文中，采取以教師課表作為染色體。根據(jù)教學(xué)計劃中的安排，教師、班級及課程之間的對應(yīng)關(guān)系是已經(jīng)確定的，首先對這三者的ID進(jìn)行編碼并組合，然后安排上課時間，最后安排上課教室。

（2）選擇操作

選擇操作的目的，是為了從當(dāng)前群體中選出優(yōu)良的個體，使它們有機會作為父代繁殖下一代。個體適應(yīng)度越高，其被選擇的機會就越多。選擇操作實現(xiàn)的方法有很多，如適應(yīng)度比例方法、最佳個體保存方法、期望值方法等。本文采用期望值方法。

在適應(yīng)度比例方法中，當(dāng)個體數(shù)不太多時，依據(jù)產(chǎn)生的隨機數(shù)有可能會出現(xiàn)不正確地反映個體適應(yīng)度的選擇，即存在統(tǒng)計誤差。為克服這種誤差，期望值方法用了如下思想：

①計算群體中每個個體在下一代生存的期望數(shù)目：

M=fi/∑fi/n

②若某個體被選中并要參與配對和交叉，則它在下一代中的生存的期望數(shù)目減去 0.5；若不參與配對和交叉，則該個體的生存期望數(shù)目減去1。

③在上一步的兩種情況中，若一個個體的期望值小于零時，則該個體不參與選擇。

（3）交叉操作

交叉操作是遺傳算法中最主要的遺傳操作，通過交叉操作可以得到新一代個體。根據(jù)前面選擇操作的結(jié)果，選取兩條染色體作為父代，再取一隨機值r（0＜r＜1）與系統(tǒng)預(yù)設(shè)的交叉概率PC比較，若r＜PC，就執(zhí)行交叉操作，否則不執(zhí)行。

本文選用一點交叉方式。一點交叉又叫簡單交叉，具體操作是：在個體串中設(shè)定一個交叉點，實行交叉時，該點前或后的兩個個體的部分結(jié)構(gòu)進(jìn)行互換，并生產(chǎn)兩個新個體。本文中的交叉點設(shè)置在第17和第18個基因座之間。交叉時，該交叉點后的兩個個體的部分碼串互相交換，即交換兩個染色體的教室編碼和上課時間編碼，這樣既不會影響到每位教師所教授的課程，也不會造成教師課表內(nèi)含其他教師的教授課程或每代演化后染色體結(jié)構(gòu)不合理等問題[4]。

（4）變異操作

變異操作的目的在于挖掘群體中個體的多樣性，克服有可能限于局部解的弊病。變異操作與交叉操作相似，在變異時先產(chǎn)生一個隨機值 r（0＜r＜1），與變異概率 Pm比較，若 r＜Pm，則執(zhí)行變異操作，否則不執(zhí)行。

基于排課問題的特性，本文采用基本位變異，即隨機選擇一個染色體的兩個或多個基因座，將基因值互換。例如，有一染色體編碼為：

3692 1802101 110075 010205 21

它表示星期二的第一大節(jié)有“高等數(shù)學(xué)”這門課，執(zhí)行變異操作后，該染色體變成：

3692 1802101 110075 010205 41

“高等數(shù)學(xué)”這門課調(diào)整到星期四的第一大節(jié)進(jìn)行，這樣染色體的適應(yīng)度就得到了極大的提高。

在變異操作中，Pm不能取得太大，如果 Pm＞0.5，遺傳算法就退化為隨機搜索，而遺傳算法的一些重要的數(shù)學(xué)特征和搜索能力也不復(fù)存在了[5]。

2.2 蟻群算法

蟻群算法又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型算法。它由Marco Dorigo 1992年在其博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。

昆蟲學(xué)家經(jīng)過長期的觀察研究發(fā)現(xiàn)：螞蟻在尋找食物時，會在其通過的路徑上釋放一種特殊的分泌物——信息素，并通過此分泌物來尋找路徑。當(dāng)它們行進(jìn)到一個未走過的路口時，會隨機選擇一條路徑進(jìn)行前行，同時釋放與路徑長度有關(guān)的信息素。螞蟻走過的路徑越長，釋放的信息量越小。后面的螞蟻會根據(jù)路徑上信息量的大小來選擇路徑，信息量較大的路徑被選擇的概率也越大，這就形成了一個正反饋機制。隨著時間的推移，最優(yōu)路徑上的信息量越來越大，而其他路徑上的信息量則逐漸減弱，最終蟻群會以此找出最優(yōu)路徑。蟻群對環(huán)境還有很強的適應(yīng)能力，它們在行進(jìn)途中遇到障礙物時，也能很快地重新找到最優(yōu)路徑。蟻群在覓食的過程中，雖然單個螞蟻的能力有限，但整個蟻群內(nèi)部依靠信息素的作用交換著路徑信息，使得整個蟻群具有很高的自組織性，并最終依靠集體的力量找出最優(yōu)路徑。

蟻群算法只能解決用圖結(jié)構(gòu)描述的問題。因此要將蟻群算法應(yīng)用到排課問題中，首先要將排課問題用圖結(jié)構(gòu)G來描述：

其中：N ——圖的頂點集合；

S ——邊的集合；

C ——邊集有關(guān)的權(quán)值的集合。

排課工作是根據(jù)教學(xué)計劃來安排的，在教學(xué)計劃中，已經(jīng)確定了課程、教師、班級之間的匹配關(guān)系，排課人員需要做的就是為其合理安排時間和教室。因此，課程、教師、班級、時段、教室五個元素之間的匹配可轉(zhuǎn)化為＜課程、教師、班級＞關(guān)系與＜時間、教室＞關(guān)系，排課問題也就轉(zhuǎn)化為解決＜課程、教師、班級＞與＜時間、教室＞所構(gòu)成的二分圖的最大匹配問題。

（1）二分圖的頂點集

定義＜課程、教師、班級＞關(guān)系為 RLSC，RLSC= L×S×C，RLSC中所有元組組成的集合為GLSC，為二分圖左側(cè)的頂點集合；定義＜時間、教室＞關(guān)系為 RTR，RTR= T×R，RTR中所有元組組成的集合為GTR，為二分圖右側(cè)的頂點集合；|GTR|＞＞|GLSC|。

（2）二分圖的邊集

在安排教室的時候，要滿足兩個條件：一是要滿足課程對教室類型的要求，二是要滿足班級人數(shù)對教室容量的要求。因此，GLSC不是滿映射于 GTR，只有滿足上述兩個條件的節(jié)點才可進(jìn)行連接。

（3）二分圖中邊的權(quán)值

對每條邊上的權(quán)值，可依據(jù)具體課程的時間期望度來構(gòu)造。例如，較難掌握的課程（如高等數(shù)學(xué)）最好安排在上午第一大節(jié)，那么GLSC中所有的高等數(shù)學(xué)課程與GTR中時間段為上午第一大節(jié)的所有節(jié)點連線的邊的權(quán)值要盡量小。通過對權(quán)值的設(shè)置，才能讓螞蟻排出較高質(zhì)量的課程。

為了克服基本蟻群算法的不足，結(jié)合排課問題的特點，本文采用改進(jìn)的蟻群算法——最大-最小螞蟻系統(tǒng)（Max-Min Ant System, MMAS）。改進(jìn)的蟻群算法求解排課問題的步驟如下：

（1）初始化參數(shù)，nc=0，每條邊的信息量ij(0)=c；

（2）把m只螞蟻放在二分圖左側(cè)的頂點集合GLSC中，為每只螞蟻建立禁忌表tabuk以及允許選擇的RTR表allowedk；

（3）計算螞蟻k在當(dāng)前點i（i點位于集合GLSC中）的轉(zhuǎn)移概率，通過計算結(jié)果選擇下一步將轉(zhuǎn)移到的位置j點（j點位于集合GTR中）；

（4）把j點從allowedk表中刪除，同時把j點放入tabuk表中；

（5）判斷集合GLSC中是否還有節(jié)點未與集合GTR中節(jié)點匹配，若有，i加1，返回第（3）步，反之，表示螞蟻k已完成一次周游，執(zhí)行下一步；

（6）若k＜m，表明還有螞蟻未完成周游，k加1，返回第（3）步，否則執(zhí)行下一步；

（7）比較m只螞蟻周游的代價大小，找出最小代價路徑的螞蟻；

（8）對對優(yōu)路徑上的信息素進(jìn)行更新；

（9）判斷nc是否達(dá)到最大迭代次數(shù)，若是，終止循環(huán)，求得最優(yōu)路線，否則nc加1，返回第（2）步。

2.3 遺傳-蟻群混合算法

遺傳算法、蟻群算法作為兩大仿生優(yōu)化算法，有其各自的優(yōu)點和不足。遺傳算法具有在大范圍內(nèi)快速全局搜索的能力，但對系統(tǒng)中的反饋信息利用不夠，往往求解到一定范圍時就開始做大量無用的冗余迭代，導(dǎo)致求精確解效率降低。蟻群算法原理是一種正反饋機制，具有更好的分布并行計算能力以及全局優(yōu)化能力，但在搜索初期由于信息素的匱乏，導(dǎo)致求解速度過慢。

因此本文將遺傳算法與蟻群算法融合，首先利用遺傳算法生成信息素分布，再利用蟻群算法求精確解，通過兩者的優(yōu)勢互補，來獲得良好的優(yōu)化性能和時間性能。

在本文的遺傳-蟻群混合算法中，設(shè)置遺傳算法的終止條件為：算法運行10次，每次迭代100代，取得的最優(yōu)解作為蟻群算法的初始解；或者運算過程中，運算結(jié)果的差值小于0.005的情況連續(xù)出現(xiàn)兩次，則終止運算，直接進(jìn)入蟻群算法。設(shè)置蟻群算法的終止條件為：最大迭代次數(shù)取值 100，當(dāng)算法達(dá)到最大迭代次數(shù)時，就停止運算。

遺傳-蟻群混合算法求解排課問題的步驟如下：

（1）遺傳算法參數(shù)初始化；

（2）隨機生成初始種群P(0)，設(shè)置迭代次數(shù)nc=0；

（3）計算各個體的適應(yīng)度函數(shù)值；

（4）選擇、交叉、變異操作；

（5）進(jìn)化代數(shù)nc=nc+l；

（6）判斷是否滿足結(jié)束條件，滿足，執(zhí)行下一步，不滿足，返回第（3）步；

（7）把遺傳算法生成的較優(yōu)解轉(zhuǎn)化為蟻群算法的初始信息素；

（8）蟻群算法參數(shù)初始化，迭代次數(shù)gen=0；

（9）把m只螞蟻放在二分圖左側(cè)的頂點集合GLSC中；

（10）對每只螞蟻根據(jù)轉(zhuǎn)移概率和排課約束條件進(jìn)行路徑選擇；

（11）記錄m條路線，完成一次迭代；

（12）計算m條路徑長度，記錄當(dāng)前最優(yōu)路徑值；

（13）對最優(yōu)路徑上的邊的信息量進(jìn)行更新，其余邊的信息量進(jìn)行揮發(fā)；

（14）判斷是否滿足終止條件，如果滿足則停止運算，求出目前最優(yōu)路徑的目標(biāo)值，否則gen=gen+1，返回第（9）步，開始新一輪迭代。

3 實驗結(jié)果及分析

使用C語言進(jìn)行編程，在主頻3.0GHz(2G RAM)的計算機上進(jìn)行試驗，選取一個學(xué)院班級的排課任務(wù)實例進(jìn)行測試。該學(xué)院有7個專業(yè)，28個班級，約1000名學(xué)生，87名教師，254個排課單元，29間教室，其中為10名教師設(shè)置了對排課的特殊要求。

為了驗證遺傳-蟻群混合算法在實際排課中的效果，在排課單元為100、400和800的情況下，對改進(jìn)的遺傳算法、改進(jìn)的蟻群算法和遺傳-蟻群混合算法的運算時間和適應(yīng)度進(jìn)行比較。

遺傳算法參數(shù)設(shè)置為：M=40，gen=100，交叉概率Pc=0.8，變異概率Pm=0.002；蟻群算法參數(shù)設(shè)置如下：m=5， =1，=5，=0.35，Q=10， =1000， =0.001，ij=1/(cij-c)，gen=100。

三種算法各測10組數(shù)據(jù)后取平均值，得到平均運算時間結(jié)果如表1所示，得到平均適應(yīng)度結(jié)果如表2所示：

表1 三種排課算法平均運算時間比較

表2 三種排課算法平均適應(yīng)度比較

由表1和表2可以看出，遺傳-蟻群混合算法的運算時間比改進(jìn)遺傳算法稍長，比改進(jìn)蟻群算法稍短，但遺傳-蟻群混合算法的適應(yīng)度卻遠(yuǎn)高于后兩種算法?？梢姡瑢⑦z傳算法與蟻群算法融合解決排課問題，具有良好的優(yōu)化性能與時間性能。

[1] 林瑞金,卓清寅.基于遺傳算法的高校排課系統(tǒng)設(shè)計與實現(xiàn)[J].荊楚理工學(xué)院學(xué)報,2010,25(9):27-29.

[2] 滕姿,鄧輝文,等.基于遺傳算法的排課系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機應(yīng)用,2007(S2):199-201,204.

[3] 李志娟,王冠.高校自動排課算法的研究與設(shè)計[J].計算機與數(shù)字工程,2008,36(5):199-202.

[4] 沈麗容,陳明磊.基于遺傳算法的高校排課系統(tǒng)研究[J].計算機與信息技術(shù),2006(11): 20-23.

[5] 王小平,曹立明.遺傳算法——理論、應(yīng)用與軟件實現(xiàn)[M].西安交通大學(xué)出版社,2002.