第19章 基于AC0的TSP求解

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

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

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

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

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

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

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

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

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

蟻群算法利用了信息素進(jìn)行傳遞信息，而粒子群優(yōu)化算法利用了本身信息、個(gè)體極值信息和全局極值3個(gè)信息，來(lái)指導(dǎo)粒子下一步迭代位置。蟻群算法利用正反饋原理和某種啟發(fā)式算法的有機(jī)結(jié)合，容易出現(xiàn)早熟現(xiàn)象以及陷入局部最優(yōu)解。混合的思路是讓螞蟻也具有“粒子”的特性，首先螞蟻按照蟻群算法，完成一次遍歷后，再讓螞蟻根據(jù)局部最優(yōu)解和全局最優(yōu)解進(jìn)行調(diào)整。

調(diào)整思路如下：對(duì)于旅行商問(wèn)題，其當(dāng)前的位置是基本路徑，讓當(dāng)前解與個(gè)體極值和全局極值分別作交叉操作，產(chǎn)生的解為新的位置，再做變異操作。第十九章MATLAB優(yōu)化算法案例分析與應(yīng)用19.4基于ACO_PSO的TSP求解解TSP問(wèn)題的AC0_PSO混合算法步驟如下：（1）；（nc為迭代步數(shù)或搜索次數(shù)），初始化；產(chǎn)生大量的路徑（如100條），從中選擇比較優(yōu)的（30條）路徑，使這些路徑留下信息素，將m只螞蟻置于n個(gè)頂點(diǎn)上。（2）根據(jù)當(dāng)前位置計(jì)算適應(yīng)度值（各路徑的長(zhǎng)度），設(shè)置當(dāng)前適應(yīng)值為個(gè)體極值，當(dāng)前位置為個(gè)體極值位置，根據(jù)各個(gè)粒子的個(gè)體極值，找出全局極值和全局極值位置。（3）將各螞蟻的初始出發(fā)點(diǎn)置于當(dāng)前解集中；對(duì)每只螞蟻k，按照概率移至下一頂點(diǎn)j；將頂點(diǎn)j置于當(dāng)前解集。（4）對(duì)每只螞蟻進(jìn)行如下操作，第j只螞蟻路徑與交叉得到

，與交叉得到，以一定概率變異到，根據(jù)當(dāng)前位置計(jì)算路徑長(zhǎng)度，有新的目標(biāo)函數(shù)變好，接受新值；否則就拒絕，第j個(gè)粒子路徑仍為，重新找到各只螞蟻的個(gè)體極值和極值位置

，找出全局極值和全局極值位置。第十九章MATLAB優(yōu)化算法案例分析與應(yīng)用19.4基于ACO_PSO的TSP求解解TSP問(wèn)題的AC0_PSO混合算法步驟如下：（5）計(jì)算各螞蟻的路徑長(zhǎng)度；記錄當(dāng)前的最好解。（6）按更新方程修改軌跡強(qiáng)度。（7）對(duì)各邊弧，置，。（8）若小于預(yù)定的迭代次數(shù)且無(wú)退化行為（即找到的都是相同的解）則轉(zhuǎn)步驟2。（9）輸出目前最好解。第十九章MATLAB優(yōu)化算法案例分析與應(yīng)用19.4基于ACO_PSO的TSP求解圖19-5城市信息圖第十九章MATLAB優(yōu)化算法案例分析與應(yīng)用19.4基于ACO_PSO的TSP求解ltsp(i)=ca_tsp(n,path(i,:),dij);%交叉操作%四種交叉子程序分別為cross_tsp_a,cross_tsp_b,cross_tsp_c,cross_tsp_dpath1(i,:)=cross_tsp_a(path(i,:),gcbest,n);path1(i,:)=cross_tsp_a(path1(i,:),pcbest(i,:),n);%變異操作%四種變異子程序分別為mutation_a,mutation_b,mutation_c,mutation_dpath1(i,:)=mutation_a(path1(i,:),n);%計(jì)算新路徑長(zhǎng)度之和ltsp1(i)=ca_tsp(n,path1(i,:),dij);%求個(gè)體極值

ifltsp1(i)<ltsp(i)ltsp(i)=ltsp1(i);path(i,:)=path1(i,:);endifltsp(i)<plbest(i)plbest(i)=ltsp(i);pcbest(i,:)=path(i,:);end

第十九章MATLAB優(yōu)化算法案例分析與應(yīng)用19.4基于ACO_PSO的TSP求解圖19-6交叉變異1函數(shù)輸出結(jié)果圖第十九章MATLAB優(yōu)化算