基于圖著色問題的群集智能算法研究.pdf

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

2、色問問提供了一個(gè)很好的選擇。
　　 在閱讀大量相關(guān)文獻(xiàn)的基礎(chǔ)上，本文針對基于圖著色問問的群集智能算法研究開展了一系列的工作，具體如下：
　　 介紹了圖著色和群集智能算法的基本理論，綜述了圖著色問問和群集智能算法的國內(nèi)外研究現(xiàn)狀，以及群集智能算法的特點(diǎn)和應(yīng)用。
　　 在系統(tǒng)分析了幾種傳統(tǒng)的群集智能算法用于圖的正常頂點(diǎn)著色的基礎(chǔ)上，對基于群集智能算法圖著色問問的求解過程進(jìn)行了深入的理論分析。針對遺傳算法和模擬退火算法

3、有較強(qiáng)的全局優(yōu)化能力，但局部搜索能力較差，而蟻群算法具有較強(qiáng)的局部搜索能力，因此將遺傳算法、模擬退火算法和蟻群算法相互結(jié)合，優(yōu)勢互補(bǔ)。
　　 提出了求解圖著色問問的兩類算法：蟻群單親遺傳算法和蟻群退火算法，提出的算法有效地克服了傳統(tǒng)的群集智能算法的缺點(diǎn)。
　　 運(yùn)用Matlab 7.0對提出的兩類新算法：蟻群單親遺傳算法和蟻群退火算法進(jìn)行了大量的仿真實(shí)驗(yàn)，結(jié)果表明，和傳統(tǒng)的智能算法相比，提出的算法具有更強(qiáng)的尋優(yōu)能力和魯棒