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

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

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

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