基于蟻群算法的排課問題的研究.pdf

1、為了保證教學(xué)質(zhì)量，學(xué)校必須制定一套規(guī)范的教學(xué)計(jì)劃，而課表編排是教學(xué)計(jì)劃得以順利執(zhí)行的重要一環(huán)。隨著高校學(xué)生數(shù)量猛增，數(shù)據(jù)規(guī)模大、各種約束復(fù)雜，在教學(xué)資源一定的情況下排課越來(lái)越繁難。人工排課已經(jīng)難以完成課表編排的工作要求。因此，利用計(jì)算機(jī)解決排課問題成為當(dāng)務(wù)之急。 蟻群算法是近十幾年才提出來(lái)的一種新型模擬進(jìn)化算法，通過候選解組成的群體的進(jìn)化過程來(lái)尋求最優(yōu)解。該過程包括適應(yīng)階段和協(xié)作階段。在適應(yīng)階段，各候選解根據(jù)積累的信息不斷調(diào)整自

2、身結(jié)構(gòu)；在協(xié)作階段，候選解之間通過信息交流以期產(chǎn)生性能更好的解。蟻群算法通過正反饋和負(fù)反饋相結(jié)合的機(jī)制使算法朝著最優(yōu)解方向發(fā)展，又保持搜索范圍避免過早停滯。從而得到一定程度上的滿意解。 本文對(duì)基本蟻群算法的思想及原理進(jìn)行了分析，結(jié)合排課問題的自身特點(diǎn)提出一種適于排課問題的改進(jìn)的蟻群算法。在此，對(duì)排課問題進(jìn)行了抽象，將解決排課問題轉(zhuǎn)化為尋求二部圖的最大匹配問題，由于排課問題可以描述為圖結(jié)構(gòu)，這給蟻群算法介入排課問題提供了一個(gè)契機(jī)。

3、而如何滿足排課問題中的多種約束條件是排課問題的關(guān)鍵問題，在此算法中引入個(gè)體啟發(fā)信息等策略。考慮把這些約束具體抽象成一些合適的數(shù)字，適當(dāng)時(shí)候用這些數(shù)字來(lái)修正二部圖中邊上的權(quán)值，達(dá)到間接修改蟻群算法的期望啟發(fā)因子，配合蟻群尋求課表最優(yōu)解。 本文不僅在理論上論述了蟻群算法解決排課問題的方法，而且在此基礎(chǔ)上使用VB實(shí)現(xiàn)了一個(gè)基于蟻群算法解決排課問題的實(shí)驗(yàn)測(cè)試程序。測(cè)試結(jié)果表明蟻群算法能夠很好地解決排課問題，排出高質(zhì)量的課表。文中還通過采