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

王麗紅　劉平　于光華

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

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

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

排課問題描述

問題描述

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

約束條件

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

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

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

遺傳蟻群算法

算法基本思想

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

遺傳算法

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

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