第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中螞蟻在兩個位置節(jié)點間每移動一次后即更新信息素，而在Antcycle中當(dāng)所有的螞蟻都完成了自己的行程后才對信息素進(jìn)行更新，而且每只螞蟻所釋放的信息素被表達(dá)為反映相應(yīng)行程質(zhì)量的函數(shù)。

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

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

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

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

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

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

假定障礙物的周圍有兩條道路可以從螞蟻的巢穴到達(dá)食物源（如圖19-1所示）：Nest-ABD-Food和Nest-ACD-Food，分別具有長度4和6.螞蟻在單位時間內(nèi)可移動一個單位長度的距離。開始時所有道路上都未留有任何信息素。第十九章MATLAB優(yōu)化算法案例分析與應(yīng)用19.2蟻群算法的基本原理蟻群算法基本算法如下。設(shè)有m只螞蟻，每只螞蟻有以下特征：它根據(jù)以城市距離和鏈接邊上外激素的數(shù)量為變量的改了吧函數(shù)選擇下一個城市（設(shè)為t時刻上外激素的強(qiáng)度）。規(guī)定螞蟻走合法路線，除非周游完成，不允許轉(zhuǎn)到已訪問城市，由禁忌表控制（設(shè)表示第k只螞蟻的禁忌表，表示禁忌表中第s個元素）。它完成周游后，螞蟻在它每一條訪問的邊上留下外激素。設(shè)是在t時刻城市I的螞蟻數(shù)，設(shè)為全部螞蟻數(shù)。每只簡單螞蟻有以下特征：（1）它根據(jù)以城市距離和鏈接邊上激素的數(shù)量為變量的概率函數(shù)選擇下一個城市（設(shè)為t時刻上外激素的強(qiáng)度）。（2）規(guī)定螞蟻走合法路線，除非周游結(jié)束，不允許轉(zhuǎn)到已訪問城市，由禁忌表控制（設(shè)表示第k只螞蟻的禁忌表，表示禁忌表中第s個元素）。（3）完成周游后，螞蟻在它每一條訪問的邊上留下外激素。第十九章MATLAB優(yōu)化算法案例分析與應(yīng)用19.2蟻群算法的基本原理在Ant-quantitysystem模型中：在Ant-densitysystem模型中：它們的區(qū)別在于：后兩種模型中，利用的是局部信息，而前者利用的是整體信息，在求解TSP問題時，性能較好，因為通常采用它為基本模型。第十九章MATLAB優(yōu)化算法案例分析與應(yīng)用19.2蟻群算法的基本原理旅行商問題的蟻群算法的基本步驟第十九章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)化算法利用了本身信息、個體極值信息和全局極值3個信息，來指導(dǎo)粒子下一步迭代位置。蟻群算法利用正反饋原理和某種啟發(fā)式算法的有機(jī)結(jié)合，容易出現(xiàn)早熟現(xiàn)象以及陷入局部最優(yōu)解?；旌系乃悸肥亲屛浵佉簿哂小傲Ｗ印钡奶匦?，首先螞蟻按照蟻群算法，完成一次遍歷后，再讓螞蟻根據(jù)局部最優(yōu)解和全局最優(yōu)解進(jìn)行調(diào)整。

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

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

，找出全局極值和全局極值位置。第十九章MATLAB優(yōu)化算法案例分析與應(yīng)用19.4基于ACO_PSO的TSP求解解TSP問題的AC0_PSO混合算法步驟如下：（5）計算各螞蟻的路徑長度；記錄當(dāng)前的最好解。（6）按更新方程修改軌跡強(qiáng)度。（7）對各邊弧，置，。（8）若小于預(yù)定的迭代次數(shù)且無退化行為（即找到的都是相同的解）則轉(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);%計算新路徑長度之和ltsp1(i)=ca_tsp(n,path1(i,:),dij);%求個體極值

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)化算