求解排課問題的遺傳蟻群混合算法

◎王麗紅 劉平 于光華

求解排課問題的遺傳蟻群混合算法

◎王麗紅 劉平 于光華

針對排課問題，本文將遺傳算法和蟻群優(yōu)化算法融合，提出了一種遺傳蟻群混合的優(yōu)化算法。首先利用遺傳算法產(chǎn)生初始信息素的分布，在運(yùn)用蟻群算法求精確解。實(shí)驗(yàn)表明該算法取得了良好的適應(yīng)度值和時間性能。

排課問題涉及到教師、教室、班級、課程、時間等諸多因素，是一個處理起來相當(dāng)復(fù)雜的優(yōu)化決策問題。排課問題已被證明是一個NP完全問題，也是一個很有研究價值的實(shí)際問題。

文獻(xiàn)提出了一種新型的解決排課問題的離散粒子群算法，在三維空間中建立模型，并引入了沖突檢測及變異等操作。文獻(xiàn)提出了自適應(yīng)遺傳算法，該算法采用三維編碼方案，并在交叉概率和變異概率、適應(yīng)度函數(shù)、初始種群的生成等方面都進(jìn)行了設(shè)計和優(yōu)化。文獻(xiàn)應(yīng)用蟻群遺傳算法進(jìn)行排課研究。在本文將遺傳算法與蟻群算法融合來研究排課問題。

排課問題描述

問題描述

排課問題實(shí)際上是一個五維空間上的組合優(yōu)化求解問題。五維是指教室、教師、班級、課程、時間，要實(shí)現(xiàn)的目標(biāo)是上述五元素的最優(yōu)化配置，對于這一類組合優(yōu)化問題要尋求一種合理的近似最優(yōu)解。

約束條件

排課方案必須滿足兩大類約束：硬約束是衡量一個排課方案是否可行的標(biāo)準(zhǔn)，軟約束是衡量一個排課方案優(yōu)劣的標(biāo)準(zhǔn)，而反映一個排課方案優(yōu)劣的標(biāo)準(zhǔn)有多種情況。

硬約束是指在排課過程中必須遵守的規(guī)則，一般包含以下幾個方面：同一時間段內(nèi)，一位教師不能排一門以上的課程，不能占有一個以上的教室；同一時間段內(nèi)，一個班級不能上一門以上的課程；同一時間段內(nèi)，一個實(shí)驗(yàn)室不能排一門以上的課程；教室能夠容納上課班級的學(xué)生人數(shù)。

軟約束條件是指在排課方案中可以滿足但又可以不完全滿足的條件，根據(jù)各學(xué)院情況不同而有所差別，包含以下幾個方面：專業(yè)相關(guān)的重要課程盡量安排在較好的教學(xué)時間段；多學(xué)時的課程每周的安排要錯開（學(xué)時大于等于4課時，能夠盡量隔天排一次課）；一周內(nèi)每天課時盡量平均；教室利用率高，上課班級人數(shù)盡量接近教室可容鈉人數(shù)。

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

排課問題中設(shè)計的實(shí)體集合有教師、教室、班級、課程、時間，具體設(shè)定如下：教室集合表示第i個教室；教師集合表示第i位教師；班級集合表示第i個班級；課程集合表示第i門課程；時間集合表示第i個時間段。

遺傳蟻群算法

算法基本思想

遺傳算法在搜索初期具有較高向最優(yōu)解的收斂速度，但是達(dá)到一定時刻后不能有效利用系統(tǒng)中的反饋信息，使搜索具有盲目性，導(dǎo)致求解速度會明顯降低。由于信息素匱乏，蟻群算法在初期搜索速度緩慢，當(dāng)信息素累積到一定程度之后，蟻群算法求解效率會迅速提高。而遺傳蟻群混合算法的基本思想是，首先采用遺傳算法產(chǎn)生初始信息素的分布，當(dāng)遺傳算法達(dá)到一定迭代次數(shù)或群體中向最優(yōu)解的進(jìn)化速率低于一定程度時結(jié)束遺傳算法，應(yīng)用蟻群算進(jìn)行最優(yōu)解的求解。如圖1所示。

遺傳算法

編碼。針對排課問題的特點(diǎn)，使用三維數(shù)組對排課信息進(jìn)行保存，具有編碼和解碼都很直觀，方便沖突檢測，算法的復(fù)雜度低等優(yōu)點(diǎn)。

編碼和適應(yīng)度函數(shù)。對于適應(yīng)度函數(shù)，我們主要考慮軟約束：

i程，應(yīng)盡量隔一天以上再安排。若某門課程間隔 天上課效果的權(quán)值為該門課程的重要性權(quán)值為 ωi，優(yōu)化目標(biāo)：

遺傳操作。在標(biāo)準(zhǔn)遺傳算法中,交叉概率和變異概率是固定不變的。為了保持種群的多樣性，避免出現(xiàn)早熟和局部收斂現(xiàn)象，本文根據(jù)遺傳操作前后最優(yōu)染色體適應(yīng)度值的變化情況,對交叉概率和變異概率采用自適應(yīng)調(diào)整策略。

交叉概率調(diào)整策略：交叉操作前參與交叉的染色體中,最優(yōu)染色體的適應(yīng)度值為交叉后所得最優(yōu)染色體的適應(yīng)度值為原來交叉概率為 pc,則調(diào)整后交叉概率為

圖1 遺傳蟻群算法速度時間曲線圖

變異概率調(diào)整策略:變異操作前參與變異的染色體中,最優(yōu)染色體的適應(yīng)度值為變異后所得最優(yōu)染色體的適應(yīng)度值為原來變異概率為則調(diào)整后變異概率為:

蟻群優(yōu)化算法

信息素更新

排課問題即解決S × R →{L,T,C}的關(guān)系，為了將蟻群算法應(yīng)用到其中，將排課問題轉(zhuǎn)化為{S, R}與{L,T,C}構(gòu)成的二分圖的最大匹配問題。本文采用蟻周系統(tǒng)模型, 第K 只螞蟻完成一次周游后, 路徑(i, j)上的信息素增量定義為:

其中 LK為第K只螞蟻完成本次周游所經(jīng)歷的路徑長度，Q為常數(shù)。在每一只螞蟻完成一次周游后,路徑上新的信息量為:

目標(biāo)結(jié)點(diǎn)的選擇策略

在螞蟻周游過程中,螞蟻K由節(jié)點(diǎn)i選擇到節(jié)點(diǎn) j的概率為:

其中allowedk表示螞蟻K下一步允許選擇的節(jié)點(diǎn)。

求解排課問題的遺傳蟻群混合算法

下面詳細(xì)描述遺傳蟻群混合算法的執(zhí)行過程。

1.定義適應(yīng)度函數(shù)和目標(biāo)函數(shù)，設(shè)置遺傳算法控制參數(shù)。

2.隨機(jī)產(chǎn)生初始種群 P(g)，g=0。

3.計算 P(0)中每個個體的適應(yīng)度值。

4.進(jìn)行遺傳選擇、交叉、變異操作，直到滿足遺傳算法的結(jié)束條件:

(1)根據(jù)個體適應(yīng)度值及選擇策略確定 P(g)內(nèi)所選擇的個體。

(2)交叉操作：對所選擇的2個父體執(zhí)行交叉操作，并將所得 的2個后代插入P(g+1) 中，并計算個體適應(yīng)度值，同時記錄交叉操作前后最優(yōu)染色體的適應(yīng)度值1cf 、2cf 。

(3)變異操作:對所選擇的2個父體執(zhí)行變異操作，并將所得的2個后代插入P(g+1)中，并計算個體適應(yīng)度值，同時記錄變異操作前后最優(yōu)染色體的適應(yīng)度值1mf 、2mf 。

(4)根據(jù)遺傳操作前后最優(yōu)染色體的適應(yīng)度值調(diào)整交叉概率pc和變異概率 pm。

5.從 P(g)中選擇適應(yīng)能力強(qiáng)的部分個體放入優(yōu)化解集合。

6.對于優(yōu)化解集合中的每個優(yōu)化解，將遺傳算法的求解結(jié)果轉(zhuǎn)換成蟻群算法信息素初值設(shè)置。

7.初始化蟻群優(yōu)化算法控制參數(shù)，設(shè)置蟻群算法結(jié)束條件。

8.反復(fù)執(zhí)行下列操作，直至滿足蟻群算法結(jié)束條件：

(1)在二分圖頂點(diǎn)處放置 m 只螞蟻;

(2)計算螞蟻K由節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率，并根據(jù)計算結(jié)果選擇下一步轉(zhuǎn)移的節(jié)點(diǎn)j，將j在中刪除。

(3)判斷螞蟻K是否遍歷完所有的節(jié)點(diǎn)，若是，表示螞蟻K完成一次周游，執(zhí)行下一步；反之，返回(2)。

(4)判斷是否所有的螞蟻均完成周游，若是，執(zhí)行下一步；反之，返回(2)。

(5)計算所得 m種周游方案的適應(yīng)值,并從中選擇最佳方案的螞蟻。

(6)對信息素值進(jìn)行更新，返回(1)。

結(jié)果分析

算法用vc++實(shí)現(xiàn)，為驗(yàn)證遺傳蟻群混合算法在實(shí)際排課問題中的優(yōu)化效果，分別用遺傳算法、蟻群算法和遺傳蟻群混合算法進(jìn)行了模擬實(shí)驗(yàn)。三種算法所用的平均運(yùn)行時間對比圖如圖2所示。

圖2 三種算法運(yùn)行時間比較

三種算法平均適應(yīng)度值對比圖如圖3所示。

圖3 三種算法適應(yīng)度值比較

由模擬實(shí)驗(yàn)結(jié)果可知，遺傳蟻群混合算法的運(yùn)行時間要較遺傳算法、蟻群算法長一些， 但是適應(yīng)度要遠(yuǎn)遠(yuǎn)高于遺傳、蟻群算法，利用遺傳蟻群混合算法產(chǎn)生的排課方案能夠使得各門課時間段分布均勻，能夠滿足教學(xué)需要。

（作者單位：黑河學(xué)院計算機(jī)與信息工程學(xué)院）

黑龍江省大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項(xiàng)目《基于c/c++的智能排課軟件》，項(xiàng)目編號201513744024