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

王麗紅　劉平　于光華

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

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

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

排課問題描述

問題描述

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

約束條件

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

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

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

遺傳蟻群算法

算法基本思想

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

遺傳算法

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

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