基于圖著色問(wèn)題的群集智能算法研究.pdf

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

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

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