遺傳-蟻群混合算法解決高校排課問(wèn)題的研究

葉 靖 喻 昕

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

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

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

1 排課問(wèn)題描述

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

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

（1）同一教師在同一時(shí)段只能安排在一個(gè)教室授課；

（2）同一個(gè)班級(jí)在同一時(shí)段只能在一個(gè)教室上課；

（3）同一教室在同一時(shí)段只能安排一門(mén)課程；

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

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

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

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

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

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

2 用遺傳-蟻群混合算法解決排課問(wèn)題

2.1 遺傳算法

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

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

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

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

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

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

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

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

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

2.1.1 編碼

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

教師ID 班級(jí)ID 課程ID 教室 上課時(shí)間

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

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

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

2.1.3 種群操作

（1）初始化種群

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

（2）選擇操作

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

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

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

M=fi/∑fi/n

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

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

（3）交叉操作

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

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

（4）變異操作

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

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

3692 1802101 110075 010205 21

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

3692 1802101 110075 010205 41

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

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

2.2 蟻群算法

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

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

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

其中：N ——圖的頂點(diǎn)集合；

S ——邊的集合；

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

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

（1）二分圖的頂點(diǎn)集

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

（2）二分圖的邊集

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

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

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

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

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

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

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

（4）把j點(diǎn)從allowedk表中刪除，同時(shí)把j點(diǎn)放入tabuk表中；

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

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

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

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

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

2.3 遺傳-蟻群混合算法

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

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

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

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

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

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

（3）計(jì)算各個(gè)體的適應(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è)的頂點(diǎn)集合GLSC中；

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

為了驗(yàn)證遺傳-蟻群混合算法在實(shí)際排課中的效果，在排課單元為100、400和800的情況下，對(duì)改進(jìn)的遺傳算法、改進(jìn)的蟻群算法和遺傳-蟻群混合算法的運(yùn)算時(shí)間和適應(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。

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

表1 三種排課算法平均運(yùn)算時(shí)間比較

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

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

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

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

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

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

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