蟻群算法在圖著色中的研究.pdf

1、圖著色問題是一個被廣泛研究的組合優(yōu)化問題，也是科學計算和工程設計中一個重要和基本的問題。事實上，許多現(xiàn)實生活中的問題例如考試時間表問題和任務分配問題等都可以被模擬或拓展為圖著色問題。對于任意一個圖著色問題而言，沒有一種算法可以在多項式的時間內(nèi)找到它的解，因此圖著色問題是一個NP問題。目前，對包括旅行商問題在內(nèi)的許多組合優(yōu)化問題利用蟻群算法得到了成功解決并獲得了廣泛應用，因此，以種群進化理論為基礎的蟻群算法為求解圖著色問題提供了一個很好的

2、選擇。
　　在閱讀大量參考文獻的基礎上，本文針對基于圖著色問題的蟻群算法開展了一系列的研究，主要工作如下：
　?。?）對蟻群算法進行了分析和研究，總結(jié)出蟻群算法的工作原理，算法流程，蟻群算法的優(yōu)缺點以及蟻群算法的改進方向。
　　（2）分析了傳統(tǒng)的蟻群算法解決圖著色問題，并對蟻群算法求解圖著色問題的過程進行了深入的研究。針對蟻群算法存在早熟收斂等缺點，提出了穩(wěn)定策略蟻群算法，對蟻群算法的信息素的更新和信息素的調(diào)節(jié)方面進行

3、了改進，該穩(wěn)定策略是一種可以保持進化種群的穩(wěn)定而又不會陷入局部最優(yōu)的策略。
　?。?）蟻群算法的性能改進有一定的局限性，本文對遺傳算法進行了研究，提出了遺傳-蟻群混合算法?；旌纤惴饶馨l(fā)揮蟻群算法與遺傳算法在尋優(yōu)搜索的過程中各自的優(yōu)勢，又可以克服遺傳算法在搜索到一定階段時最優(yōu)解搜索效率低下的問題以及蟻群算法初始信息素量匱乏的問題，提高解決圖著色問題的效率。實驗結(jié)果顯示使用遺傳-蟻群混合算法求解圖著色問題的結(jié)果相對基本蟻群算法有所提