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

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

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

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