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

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

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

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

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

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

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

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

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

蟻群算法利用了信息素進行傳遞信息，而粒子群優化算法利用了本身信息、個體極值信息和全局極值3個信息，來指導粒子下一步迭代位置。蟻群算法利用正反饋原理和某種啟發式算法的有機結合，容易出現早熟現象以及陷入局部最優解。混合的思路是讓螞蟻也具有“粒子”的特性，首先螞蟻按照蟻群算法，完成一次遍歷后，再讓螞蟻根據局部最優解和全局最優解進行調整。

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

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

，找出全局極值和全局極值位置。第十九章MATLAB優化算法案例分析與應用19.4基于ACO_PSO的TSP求解解TSP問題的AC0_PSO混合算法步驟如下：（5）計算各螞蟻的路徑長度；記錄當前的最好解。（6）按更新方程修改軌跡強度。（7）對各邊弧，置，。（8）若小于預定的迭代次數且無退化行為（即找到的都是相同的解）則轉步驟2。（9）輸出目前最好解。第十九章MATLAB優化算法案例分析與應用19.4基于ACO_PSO的TSP求解圖19-5城市信息圖第十九章MATLAB優化算法案例分析與應用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優化算法案例分析與應用19.4基于ACO_PSO的TSP求解圖19-6交叉變異1函數輸出結果圖第十九章MATLAB優化算