改進的ACO和PSO算法在TSP中的應用.pdf

1、蟻群優(yōu)化算法(AntColonyOptimization，ACO)和粒子群算法(ParticleSwarmOptimization，PSO)是兩種典型的群體智能算法。由于算法的高效性和易實現(xiàn)性，因此成為了眾學者的研究焦點。目前，這兩種算法已被應用到函數(shù)優(yōu)化和工程技術(shù)領(lǐng)域，并取得了較好的效果。另一方面，算法在許多領(lǐng)域的研究還處于起步階段，算法本身存在著一些不足之處。 旅行商問題(TravelingSalesmanProblem，T

2、SP)是一種經(jīng)典的、受到廣泛研究的組合優(yōu)化問題之一。迄今為止，已經(jīng)有多種不同的求解方法被提出。蟻群優(yōu)化算法和粒子群算法均被嘗試應用于旅行商問題的求解，并取得了較大進展。然而，與一些專門用于求解旅行商問題的啟發(fā)式方法相比，算法在所求解的質(zhì)量上仍存在一些不足。因此，如何對算法加以改進使其具有更好的性能具有重要的意義。 本文在前人工作的基礎上，對蟻群優(yōu)化算法、粒子群算法及其在旅行商問題中的應用進行了研究。主要工作如下： 1.針

3、對蟻群優(yōu)化算法容易陷入局部最優(yōu)的缺陷，提出了一種基于排列的動態(tài)自適應蟻群算法。首先，為了避免算法后期陷入停滯狀態(tài)，信息素的下界被設置為一個非零常數(shù)，根據(jù)蟻群中螞蟻獲得的解的質(zhì)量的優(yōu)劣，選出部分最優(yōu)秀的螞蟻按其解的優(yōu)劣程度酌量釋放信息素，以增強螞蟻后期探索最優(yōu)解的能力：其次，采用了一種更具智能性的行為選擇規(guī)則，使蟻群在搜索過程中可以動態(tài)調(diào)整探索和開發(fā)之間的平衡系數(shù)，有效抑制收斂過程中的早熟現(xiàn)象，提高算法的搜索能力。最后為了驗證所提出的方法

4、的有效性和可行性，對TSPLIB標準庫中的多個實例進行了測試，并給出了數(shù)值結(jié)果。 2.針對標準粒子群算法在求解旅行商問題過程中容易出現(xiàn)早熟和停滯現(xiàn)象的缺點，提出了一種改進的粒子群算法。首先，在初始解的選取過程中，利用改進的貪婪策略直接獲得一組高性能初始解以提高算法的搜索效率。其次，通過引入次優(yōu)吸引子，使粒子在搜索過程中可以更加充分地利用群體的信息來提高自身的性能，有效抑制收斂過程中的停滯現(xiàn)象，提高算法的搜索能力。為了驗證所提出的