第19章 基于AC0的TSP求解

第十九章MATLAB優(yōu)化算法案例分析與應用第19章基于AC0的TSP求解第十九章MATLAB優(yōu)化算法案例分析與應用19.1蟻群算法理論研究現(xiàn)狀

最初提出的AS有三種版本：Antdensity、Antquantity和Antcycle。在Antdensity和Antquantity中螞蟻在兩個位置節(jié)點間每移動一次后即更新信息素，而在Antcycle中當所有的螞蟻都完成了自己的行程后才對信息素進行更新，而且每只螞蟻所釋放的信息素被表達為反映相應行程質(zhì)量的函數(shù)。

通過與其他各種通用的啟發(fā)式算法相比，在不大于75城市的TSP中，這三種基本算法的求解能力還是比較理想的，但是當問題規(guī)模擴展時，AS的解題能力大幅度下降，因此，其后的ACO研究工作主要集中在AS性能的改進方面。

較早的一種改進方法是精英策略（ElitistStrategy），其思想是在算法開始后，即對所有已發(fā)現(xiàn)的最好路徑給予額外的增強，并將隨后與之對應的行程記為Tgb（全局最有行程）。

當進行信息素更新時，對這些行程予以加權，同時將經(jīng)過這些行程的螞蟻記為“精英”，從而增大較好行程的選擇機會。這種改進型算法能夠以更快的速度獲得更好的解，但是若選擇的精英過多則算法會由于較早的收斂于局部次優(yōu)解而導致搜索中的過早停滯。第十九章MATLAB優(yōu)化算法案例分析與應用19.2蟻群算法的基本原理

蟻群算法是一種新型的模擬進化算法，鑒于目前國內(nèi)尚缺乏這一方面的研究，其研究剛剛開始，遠未像遺傳算法、模擬退火算法等算法那樣行程系統(tǒng)的分析方法和堅實的數(shù)學基礎，有許多問題有待進一步研究，如算法的收斂性、理論依據(jù)等更多細致的工作還有待于進一步展開。

單只螞蟻的行為極其簡單，但由這樣的單個簡單個體所組成的蟻群群體卻表現(xiàn)出及其復雜的行為，如：在螞蟻運動路徑上突然出現(xiàn)障礙物時，螞蟻能夠很快重新找到最優(yōu)路徑。像螞蟻這類群居昆蟲，雖然沒有視覺，卻能找到由蟻穴到食物源的最短路徑，究其愿意，馬一個題之間通過一種稱之為信息素（pheromone）的物質(zhì)進行信息傳遞，從而能相互協(xié)作，完成復雜的任務。螞蟻之所以表現(xiàn)出復雜有序的行為，個體之間的信息交流和相互協(xié)作起著重要作用。

螞蟻在運動過程中，能夠在它所過的路徑上留下該物質(zhì)，并以此指導自己的運動方向。螞蟻傾向于朝著該物質(zhì)強度高的方向移動。因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后者選擇該路徑的概率約大。螞蟻個體之間就是通過這種信息的交流達到搜索實物的目的。這里，用一個形象化的圖示來說明螞蟻群體的路徑搜索原理和機制。第十九章MATLAB優(yōu)化算法案例分析與應用19.2蟻群算法的基本原理

假定障礙物的周圍有兩條道路可以從螞蟻的巢穴到達食物源（如圖19-1所示）：Nest-ABD-Food和Nest-ACD-Food，分別具有長度4和6.螞蟻在單位時間內(nèi)可移動一個單位長度的距離。開始時所有道路上都未留有任何信息素。第十九章MATLAB優(yōu)化算法案例分析與應用19.2蟻群算法的基本原理蟻群算法基本算法如下。設有m只螞蟻，每只螞蟻有以下特征：它根據(jù)以城市距離和鏈接邊上外激素的數(shù)量為變量的改了吧函數(shù)選擇下一個城市（設為t時刻上外激素的強度）。規(guī)定螞蟻走合法路線，除非周游完成，不允許轉(zhuǎn)到已訪問城市，由禁忌表控制（設表示第k只螞蟻的禁忌表，表示禁忌表中第s個元素）。它完成周游后，螞蟻在它每一條訪問的邊上留下外激素。設是在t時刻城市I的螞蟻數(shù)，設為全部螞蟻數(shù)。每只簡單螞蟻有以下特征：（1）它根據(jù)以城市距離和鏈接邊上激素的數(shù)量為變量的概率函數(shù)選擇下一個城市（設為t時刻上外激素的強度）。（2）規(guī)定螞蟻走合法路線，除非周游結(jié)束，不允許轉(zhuǎn)到已訪問城市，由禁忌表控制（設表示第k只螞蟻的禁忌表，表示禁忌表中第s個元素）。（3）完成周游后，螞蟻在它每一條訪問的邊上留下外激素。第十九章MATLAB優(yōu)化算法案例分析與應用19.2蟻群算法的基本原理在Ant-quantitysystem模型中：在Ant-densitysystem模型中：它們的區(qū)別在于：后兩種模型中，利用的是局部信息，而前者利用的是整體信息，在求解TSP問題時，性能較好，因為通常采用它為基本模型。第十九章MATLAB優(yōu)化算法案例分析與應用19.2蟻群算法的基本原理旅行商問題的蟻群算法的基本步驟第十九章MATLAB優(yōu)化算法案例分析與應用19.3基于ACO的TSP求解圖19-3原始城市位置第十九章MATLAB優(yōu)化算法案例分析與應用19.3基于ACO的TSP求解圖19-4ACO優(yōu)化的TSP求解第十九章MATLAB優(yōu)化算法案例分析與應用19.4基于ACO_PSO的TSP求解

蟻群算法利用了信息素進行傳遞信息，而粒子群優(yōu)化算法利用了本身信息、個體極值信息和全局極值3個信息，來指導粒子下一步迭代位置。蟻群算法利用正反饋原理和某種啟發(fā)式算法的有機結(jié)合，容易出現(xiàn)早熟現(xiàn)象以及陷入局部最優(yōu)解?；旌系?/p>