改進(jìn)的ACO和PSO算法在TSP中的應(yīng)用.pdf

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

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

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

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