求解TSP與背包問題的蟻群算法.pdf

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

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

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

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