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

◎王麗紅 劉平 于光華

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

◎王麗紅 劉平 于光華

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

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

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

排課問題描述

問題描述

排課問題實際上是一個五維空間上的組合優化求解問題。五維是指教室、教師、班級、課程、時間，要實現的目標是上述五元素的最優化配置，對于這一類組合優化問題要尋求一種合理的近似最優解。

約束條件

排課方案必須滿足兩大類約束：硬約束是衡量一個排課方案是否可行的標準，軟約束是衡量一個排課方案優劣的標準，而反映一個排課方案優劣的標準有多種情況。

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

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

排課問題數學模型

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

遺傳蟻群算法

算法基本思想

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

遺傳算法

編碼。針對排課問題的特點，使用三維數組對排課信息進行保存，具有編碼和解碼都很直觀，方便沖突檢測，算法的復雜度低等優點。

編碼和適應度函數。對于適應度函數，我們主要考慮軟約束：

i程，應盡量隔一天以上再安排。若某門課程間隔 天上課效果的權值為該門課程的重要性權值為 ωi，優化目標：

遺傳操作。在標準遺傳算法中,交叉概率和變異概率是固定不變的。為了保持種群的多樣性，避免出現早熟和局部收斂現象，本文根據遺傳操作前后最優染色體適應度值的變化情況,對交叉概率和變異概率采用自適應調整策略。

交叉概率調整策略：交叉操作前參與交叉的染色體中,最優染色體的適應度值為交叉后所得最優染色體的適應度值為原來交叉概率為 pc,則調整后交叉概率為

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

變異概率調整策略:變異操作前參與變異的染色體中,最優染色體的適應度值為變異后所得最優染色體的適應度值為原來變異概率為則調整后變異概率為:

蟻群優化算法

信息素更新

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

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

目標結點的選擇策略

在螞蟻周游過程中,螞蟻K由節點i選擇到節點 j的概率為:

其中allowedk表示螞蟻K下一步允許選擇的節點。

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

下面詳細描述遺傳蟻群混合算法的執行過程。

1.定義適應度函數和目標函數，設置遺傳算法控制參數。

2.隨機產生初始種群 P(g)，g=0。

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

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

(1)根據個體適應度值及選擇策略確定 P(g)內所選擇的個體。

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

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

(4)根據遺傳操作前后最優染色體的適應度值調整交叉概率pc和變異概率 pm。

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

6.對于優化解集合中的每個優化解，將遺傳算法的求解結果轉換成蟻群算法信息素初值設置。

7.初始化蟻群優化算法控制參數，設置蟻群算法結束條件。

8.反復執行下列操作，直至滿足蟻群算法結束條件：

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

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

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

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

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

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

結果分析

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

圖2 三種算法運行時間比較

三種算法平均適應度值對比圖如圖3所示。

圖3 三種算法適應度值比較

由模擬實驗結果可知，遺傳蟻群混合算法的運行時間要較遺傳算法、蟻群算法長一些， 但是適應度要遠遠高于遺傳、蟻群算法，利用遺傳蟻群混合算法產生的排課方案能夠使得各門課時間段分布均勻，能夠滿足教學需要。

（作者單位：黑河學院計算機與信息工程學院）

黑龍江省大學生創新創業訓練計劃項目《基于c/c++的智能排課軟件》，項目編號201513744024