劉海軍 蟻群算法原理及其應(yīng)用

蟻群算法原理及其應(yīng)用報告人：劉海軍報告內(nèi)容1ACO原理

2應(yīng)用實(shí)例TSPMacroDorigo蟻群算法原理在自然界中，螞蟻個體從洞穴出發(fā)尋找事物源，在找到事物之后返回蟻巢時，會在所經(jīng)過的路徑上留下一種稱為“信息素”的物質(zhì)。蟻群算法的信息交互主要是通過信息素來完成的。螞蟻在運(yùn)動的過程中，在沒有“視覺”的情況下，能夠感知這種物質(zhì)的存在和強(qiáng)度。初始階段，環(huán)境中沒有信息素的遺留，螞蟻尋找事物完全是隨機(jī)選擇路徑，隨后尋找該事物源的過程中就會受到先前螞蟻所殘留的信息素的影響，其表現(xiàn)為螞蟻在選擇路徑時趨向于選擇信息素濃度高的路徑，同時信息素是一種揮發(fā)性化學(xué)物，會隨著時間的推移慢慢的消逝。如果每只螞蟻在單位距離留下的信息素相同，那對于較短路徑上殘留的信息素濃度就相對較高，這被后來的螞蟻選擇的概率就大，從而導(dǎo)致這條短路徑上走的螞蟻就越多，而經(jīng)過的螞蟻越來，該路徑上殘留的信息素也將更多，這樣使得整個螞蟻的集體行為構(gòu)成了信息素的正反饋過程，從而找到比較短的路徑。蟻群算法抽象模型螞蟻在運(yùn)動過程中根據(jù)各條路徑上的信息量決定轉(zhuǎn)移方向，用禁忌表來記錄螞蟻所走過的結(jié)點(diǎn)，其在選擇過程中做動態(tài)調(diào)整。搜索過程中螞蟻根據(jù)各條路徑上的信息量和路徑的啟發(fā)信息來計算轉(zhuǎn)移概率。為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛘咄瓿梢淮嗡阉餮h(huán)后要對殘留信息進(jìn)行更新成立，因此引入信息素?fù)]發(fā)機(jī)制，模擬人腦的記憶，會隨時間的推移而逐漸淡化甚至忘記。

信息素更新機(jī)制信息素根據(jù)下式進(jìn)行更新其中狀態(tài)轉(zhuǎn)移規(guī)則一只位于節(jié)點(diǎn)r的螞蟻通過應(yīng)用下式給出的規(guī)則選擇下一個將要移動到的城市s其中，S根據(jù)下列公式得到狀態(tài)轉(zhuǎn)移規(guī)則q是在[0,1]區(qū)間均勻分布的隨機(jī)數(shù)q0的大小決定了利用先驗知識與探索新路徑之間的相對重要性。上述狀態(tài)轉(zhuǎn)移規(guī)則被稱為偽隨機(jī)比例規(guī)則特點(diǎn)：傾向于選擇短的且有著大量信息素的邊作為移動方向蟻群算法的應(yīng)用：TSP問題TSP思路TSP思路代碼（1）：數(shù)據(jù)初始化m=31;C=[13042312;36391315;41772244;37121399;34881535;33261556;32381229;41961004;4312790;4386570;30071970;25621756;27881491;23811676;1332695;37151678;39182179;40612370;37802212;36762578;40292838;42632931;34291908;35072367;33942643;34393201;29353240;31403550;25452357;27782826;23702975];Nc_max=10;alpha=1;beta=5;rho=0.5;%0<rho<1,表示路徑上信息素的衰減系數(shù)Q=100;%螞蟻釋放的信息素量代碼（1）：數(shù)據(jù)初始化n=size(C,1);%表示TSP問題的規(guī)模，亦即城市的數(shù)量D=ones(n,n);%記錄城市之間的距離fori=1:nforj=1:nifi<jD(i,j)=sqrt((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2);endD(j,i)=D(i,j);endendeta=1./D;%啟發(fā)式因子，這里設(shè)為城市之間距離的倒數(shù)pheromone=ones(n,n);%信息素矩陣,這里假設(shè)任何兩個城市之間路徑上的初始信息素都為1tabu_list=zeros(m,n);%禁忌表，記錄螞蟻已經(jīng)走過的城市，螞蟻在本次循環(huán)中不能再經(jīng)過這些城市。%當(dāng)本次循環(huán)結(jié)束后，禁忌表被用來計算螞蟻當(dāng)前所建立的解決方案，即經(jīng)過的路徑和路徑的長度Nc=0;%循環(huán)次數(shù)計數(shù)器routh_best=zeros(Nc_max,n);%各次循環(huán)的最短路徑length_best=ones(Nc_max,1);%各次循環(huán)最短路徑的長度代碼（2）：形成初始解whileNc<Nc_max%將m只螞蟻放在n個城市上

rand_position=[];%[]為空矩陣

fori=1:ceil(m/n)%ceil數(shù)值函數(shù)功能為朝向無窮大方向取整

rand_position=[rand_position,randperm(n)];%p=randperm(n)返回1:n的一個隨機(jī)排列

endtabu_list(:,1)=(rand_position(1:m))';%將螞蟻放在城市上之后的禁忌表.%m只螞蟻按概率函數(shù)選擇下一座城市，在本次循環(huán)中完成各自的周游

forj=2:nfori=1:mcity_visited=tabu_list(i,1:(j-1));%已訪問的城市

city_remained=zeros(1,(n-j+1));%待訪問的城市

probability=city_remained;%待訪問城市的訪問概率

cr=1;fork=1:n%for循環(huán)用于求待訪問的城市。比如如果城市個數(shù)是5，而已訪問的城市city_visited=[24],則經(jīng)過此for循環(huán)后city_remanied=[135]iflength(find(city_visited==k))==0%find邏輯函數(shù)功能是找出非零元素的索引號

city_remained(cr)=k;cr=cr+1;endend

代碼（2）：形成初始解%狀態(tài)轉(zhuǎn)移規(guī)則****************************************

q0=0.5;ifrand>q0fork=1:length(city_remained)probability(k)=(pheromone(city_visited(end),city_remained(k)))^alpha*(eta(city_visited(end),city_remained(k)))^beta;%end函數(shù)終止代碼塊或為數(shù)組的最后一個元素的索引

position=find(probability==max(probability));to_visit=city_remained(position(1));endelsefork=1:length(city_remained)probability(k)=(pheromone(city_visited(end),city_remained(k)))^alpha*(eta(city_visited(end),city_remained(k)))^beta;endprobability=probability/sum(probability);pcum=cumsum(probability);%cumsum累積求和

select=find(pcum>=rand);to_visit=city_remained(select(1));endtabu_list(i,j)=to_visit;%**************************************************************endendifNc>0tabu_list(1,:)=routh_best(Nc,:);%將上一代的最優(yōu)路徑（最優(yōu)解）保留下來，保證上一代中的最適應(yīng)個體的信息不會丟失

end

代碼（2）：形成初始解%記錄本次循環(huán)的最佳路線

total_length=zeros(m,1);%m只螞蟻在本次循環(huán)中分別所走過的路徑長度

fori=1:mr=tabu_list(i,:);%取出第i只螞蟻在本次循環(huán)中所走的路徑

forj=1:(n-1)total_length(i)=total_length(i)+D(r(j),r(j+1));%第i只螞蟻本次循環(huán)中從起點(diǎn)城市到終點(diǎn)城市所走過的路徑長度

endtotal_length(i)=total_length(i)+D(r(1),r(n));%最終得到第i只螞蟻在本次循環(huán)中所走過的路徑長度

endlength_best(Nc+1)=min(total_length);%把m只螞蟻在本次循環(huán)中所走路徑長度的最小值作為本次循環(huán)中最短路徑的長度

position=find(total_length==length_best(Nc+1));%找到最短路徑的位置，即最短路徑是第幾只螞蟻或哪幾只螞蟻?zhàn)叱鰜淼?/p>

routh_best(Nc+1,:)=tabu_list(position(1),:);%把第一個走出最短路徑的螞蟻在本次循環(huán)中所走的路徑作為本次循環(huán)中的最優(yōu)路徑

Nc=Nc+1代碼（3）更新信息素delta_pheromone=zeros(n,n);fori=1:mforj=1:(n-1)delta_pheromone(tabu_list(i,j),tabu_list(i,j+1))=delta_pheromone(tabu_list(i,j),tabu_list(i,j+1))+Q/total_length(i);%total_length(i)為第i只螞蟻在本次循環(huán)中所走過的路徑長度（蟻周系統(tǒng)區(qū)別于蟻密系統(tǒng)和蟻量系統(tǒng)的地方）

enddelta_pheromone(tabu_list(i,n),tabu_list(i,1))=delta_pheromone(tabu_list(i,n),tabu_list(i,1))+Q/total_length(i);%至此把第i只螞蟻在本次循環(huán)中在所有路徑上釋放的信息素已經(jīng)累加上去

end%至此把m只螞蟻在本次循環(huán)中在所有路徑上釋放的信息素已經(jīng)累加上去

pheromone=(1-rho).*pheromone+delta_pheromone;%本次循環(huán)后所有路徑上的信息素

tabu_list=zeros(m,n);%禁忌表清零，準(zhǔn)備下一次循環(huán)，螞蟻在下一次循環(huán)中又可以自由地進(jìn)行選擇end代碼（4）輸出結(jié)果position=find(length_best==min(length_best));%min找出數(shù)組中的最小元素shortest_path=routh_best(position(1),:);shortest_length=length_best(position(1));代碼（5）繪制圖形%繪制最短路徑figure(1)%figure圖形窗口控制函數(shù)功能為建立圖形在句柄圖形對象函數(shù)中為建立圖形窗口set(gcf,'Name','AntColonyOptimization——Figureofshortest_path','Color','r')%set句柄圖形對象函數(shù)功能為設(shè)置對象N=length(shortest_path);%length求向量的長度scatter(C(:,1),C(:,2),50,'filled');%繪制散點(diǎn)圖scat