求解TSP與背包問(wèn)題的蟻群算法.pdf

1、隨著人類社會(huì)的飛速發(fā)展，許多復(fù)雜性、非線性、龐大系統(tǒng)等方面的問(wèn)題大量呈現(xiàn)在人們的面前，傳統(tǒng)的優(yōu)化方法已經(jīng)逐漸陷入了困境。這時(shí)，自然界中那些群居的簡(jiǎn)單生物表現(xiàn)出來(lái)的復(fù)雜的群體智慧給了研究者們很大的啟發(fā)。這些生物群體中每一個(gè)個(gè)體的行為都很簡(jiǎn)單，沒(méi)有統(tǒng)一的指揮，但它們之間的有機(jī)協(xié)調(diào)和自組織能力，卻使得整個(gè)群體表現(xiàn)出高度的智慧，能夠完成非常復(fù)雜的任務(wù)。這種現(xiàn)象吸引了眾多學(xué)者的關(guān)注，去深入研究在現(xiàn)象背后存在的機(jī)理，并通過(guò)計(jì)算機(jī)模擬其中可循的規(guī)律，

2、用來(lái)指導(dǎo)和解決傳統(tǒng)方法難以解決的實(shí)際問(wèn)題。
　　 目前通過(guò)模擬生物群體的行為來(lái)解決優(yōu)化問(wèn)題已經(jīng)成為優(yōu)化領(lǐng)域新的研究熱點(diǎn)，并已經(jīng)在一些實(shí)際應(yīng)用領(lǐng)域取得突破性的進(jìn)展。其中有代表性的有蟻群算法、粒子群算法、模擬退火算法、遺傳算法等。由于這些方法概念簡(jiǎn)明、實(shí)現(xiàn)方便，尤其在解決復(fù)雜的組合優(yōu)化問(wèn)題方面具有很大的優(yōu)越性，迅速得到國(guó)際優(yōu)化計(jì)算領(lǐng)域的認(rèn)可，并在工程設(shè)計(jì)、生產(chǎn)優(yōu)化等應(yīng)用領(lǐng)域取得成功的應(yīng)用。
　　 本論文重點(diǎn)研究當(dāng)前應(yīng)用最廣泛

3、、最典型的群體智能優(yōu)化方法-蟻群優(yōu)化方法。論文針對(duì)基本蟻群算法收斂速度較慢和算法容易出現(xiàn)停滯現(xiàn)象的缺點(diǎn)，對(duì)蟻群算法進(jìn)行研究，提出了兩種改進(jìn)的蟻群優(yōu)化算法，并分別應(yīng)用于TSP和多維0-1背包問(wèn)題。論文的研究工作主要包括以下兩個(gè)方面：
　　 (1)改進(jìn)的蟻群算法應(yīng)用于TSP的研究。在對(duì)基本蟻群算法的基本原理、算法模型和實(shí)現(xiàn)過(guò)程的深入研究后，針對(duì)其存在的收斂速度慢，在搜索過(guò)程中很容易早熟從而陷入局部最優(yōu)的缺陷，提出了一種具有多段雜交和

4、局部變異特性的蟻群優(yōu)化算法。該算法結(jié)合遺傳算法和圖論中的最鄰近算法，并自適應(yīng)地初始化信息素和限定信息素的大小范圍。這種改進(jìn)有利于保持群體多樣性的特性，同時(shí)能有效抑制算法易于陷入局部最優(yōu)的缺陷，從而提高了解的全局搜索能力和解的質(zhì)量。
　　 (2)改進(jìn)的蟻群算法應(yīng)用于多維0-1背包問(wèn)題的研究。在對(duì)背包問(wèn)題的基本原理、算法模型和實(shí)現(xiàn)過(guò)程的深入研究后，針對(duì)其存在的搜索時(shí)間長(zhǎng)和容易陷入局部最優(yōu)解的缺點(diǎn)，提出一種改進(jìn)的求解多維0-1背包問(wèn)題