蟻群算法實現(xiàn)TSP

優(yōu)選文檔蟻群算法求解TSP問題目錄蟻群算法求解TSP問題3綱要：3優(yōu)選文檔優(yōu)選文檔要點(diǎn)詞：3一、序言3二、蟻群算法原理4三、蟻群算法解決TSP問題6四、解決n個城市的TSP問題的算法步驟8五、仿真結(jié)果9參照文件:10附錄10優(yōu)選文檔優(yōu)選文檔蟻群算法求解TSP問題綱要：蟻群算法是經(jīng)過螞蟻覓食而發(fā)展出的一種新的啟示算法，該算法已經(jīng)成功的解決了諸如TSP問題。本文簡要學(xué)習(xí)商議了螞蟻算法和TSP問題的基本內(nèi)容，試一試經(jīng)過matlab仿真解決一個實例問題。要點(diǎn)詞：蟻群算法；TSP問題；matlab。一、序言TSP(TravellingSalesmanProble)又稱貨郎擔(dān)或巡回售貨員問題。TSP問題可以描述為：有N個城市，一售貨員從初步城市出發(fā)，接見全部的城市一次，最后回到初步城市，求最短路徑。TSP問題除了擁有明顯的實質(zhì)意義外，有好多問題都可以概括為TSP問題。目前針對這一問題已有好多解法，如窮舉搜尋法(ExhaustiveSearchMetho)d,貪心法(GreedyMethod),動向規(guī)劃法(DynamicProgrammingMethod)分支界定法(Branch-And-Bound)，遺傳算法(GeneticAgorithm)模擬退火法(simulatedannealing禁忌搜尋。本文介紹了一種求解TSP問題的算法一蟻群算法，并經(jīng)過matlab仿真求解31個省會城市之間的最短距離，經(jīng)過仿真試驗，證明是一種解決TSP問題有效的方法。20世紀(jì)90年代，意大利學(xué)者M(jìn).Dorigo等人在新式算法研究的過程中，經(jīng)過模擬自然界螞蟻的覓食過程：即經(jīng)過信息素(pheromon?的相互交流從而找到由蟻巢至食品的最短路徑，提出了一種基于信息正反響原理的新式模擬進(jìn)化算法——蟻群算法(AntColonyalgorithm)。蟻群算法是繼遺傳算法、人工神經(jīng)網(wǎng)絡(luò)等算法此后的又一種啟示式算法，它優(yōu)選文檔優(yōu)選文檔的基本源理借鑒了這樣一個客觀事實：螞蟻由自組織的合作能力所產(chǎn)生的集體智能來搜尋路徑，它被認(rèn)為是用于解決組合優(yōu)化問題的又一種新方法。蟻群算法是一種適應(yīng)性好、魯棒性強(qiáng),擁有正反響結(jié)構(gòu)的并行算法。這些初步研究已顯示出蟻群算法在求解復(fù)雜優(yōu)化問題（特別是失散優(yōu)化問題）方面的一些優(yōu)越性,證明它是一種很有發(fā)展遠(yuǎn)景的方法。螞蟻算法在各個領(lǐng)域的應(yīng)用,說明該算法有著廣泛的適應(yīng)性,但由于該算法出現(xiàn)的較晚,對其研究還處于起步階段,遠(yuǎn)不如遺傳算法、人工神經(jīng)網(wǎng)絡(luò)和模擬退火算法那樣成熟。二、蟻群算法原理蟻群算法的基本源理本源于自然界螞蟻覓食的最短路徑原理，依照昆蟲學(xué)家的觀察，發(fā)現(xiàn)自然界的螞蟻誠然視覺不發(fā)達(dá)，但它可以在沒有任何提示的狀況下找到從食品源到巢穴的最短路徑，而且能在環(huán)境發(fā)生變化（如原有路徑上有了阻擋物）后，自適應(yīng)地搜尋新的最正確路徑。螞蟻是如何做到這一點(diǎn)的呢？原來，單個的螞蟻為了防備自己迷路，它在爬行時，同時也會釋放一種特別的分泌物——信息素（Pheromone,而且它也能覺察到必然范圍內(nèi)的其他螞蟻所分泌的信息素，并由此影響它自己的行為。當(dāng)一條路上的信息素越來越多（自然，隨著時間的推移會逐漸減弱），此后的螞蟻選擇這條路徑的概率也就越來越大，從而進(jìn)一步增加了該路徑的信息素濃度，這種選擇過程稱為螞蟻的自催化過程，其原理是一種正反響體系。這里我們可以用一個圖來說明螞蟻覓食的最短路徑選擇原理，如圖2-1所示。優(yōu)選文檔優(yōu)選文檔AAb)C)圖2-1蟻群覓食原理如圖2-1（a所示，我們假設(shè)A點(diǎn)是食品，而E點(diǎn)是螞蟻的巢穴，當(dāng)A、E兩點(diǎn)間沒有任何阻擋物阻截時，螞蟻不存在路徑選擇的問題，這種狀況最簡單：由于兩點(diǎn)間直線距離最短，螞蟻們搬運(yùn)食品時，會以直線的形式往返爬行。但在圖2-1（b）中的狀況有所變化，若某時刻忽然有一個阻擋物出現(xiàn)在螞蟻經(jīng)過的路徑中，原有的路徑被切斷，那么從A點(diǎn)到E點(diǎn)的螞蟻就必定在B點(diǎn)決定應(yīng)該往左還是往右走，而從E點(diǎn)到A點(diǎn)的螞蟻也必定在D點(diǎn)決定選擇走哪條路徑；這種決定會碰到各條路徑上過去螞蟻留下的信息素濃度（即殘留信息素濃度）的影響。若是往右走的路徑上的信息素濃度比較大，那么右邊的路徑被螞蟻選中的可能性也就大一些；但是對阻擋出現(xiàn)后第一個到達(dá)B點(diǎn)或D點(diǎn)的螞蟻而言，由于沒有信息素的影響，因此它們選擇向左也許向右的可能性是同樣的，（b）圖所表示的正是此時的狀況。若以從A點(diǎn)到E點(diǎn)的螞蟻為例進(jìn)行說明（對于從E點(diǎn)到A點(diǎn)的螞蟻而言，過程也基本是同樣的），由于路徑BCD比路徑BHD要短，因此選擇BCD路徑的第一只螞蟻要比選擇BHD的第一只螞蟻早到達(dá)D點(diǎn)；此時，從D點(diǎn)向B點(diǎn)看，路徑DCB上的信息素濃度要比優(yōu)選文檔優(yōu)選文檔路徑DHB上的信息素濃度大。因此從下一時刻開始，從E點(diǎn)經(jīng)D點(diǎn)到A點(diǎn)的螞蟻，它們選擇DCB路徑的可能性要比選擇DHB路徑的可能性大得多，從而使路徑BCD（或DCB）上信息素濃度與路徑BHD（或DHB）上信息素濃度的差變大；而信息素濃度差變大的結(jié)果是選擇路徑BCD（或DCB）的螞蟻進(jìn)一步增加，這又以致信息素濃度差進(jìn)一步加大。如圖2-1（c）所示，隨著時間的推移，幾乎全部的螞蟻都會選擇路徑BCD搬運(yùn)食品，而我們同時也會發(fā)現(xiàn)：BCD路徑也正是事實上的最短路徑。這種蟻群尋徑的原理可簡單理解為：對于單個的螞蟻來說，它并沒有要搜尋到最短路徑的主觀上的故意；但對于整個蟻群系統(tǒng)來說，它們又確實達(dá)到了搜尋到最短路徑的客觀上的收效。在自然界中，蟻群的這種搜尋路徑的過程表現(xiàn)為一種正反響的過程，與蟻群算法中人工蟻群的尋優(yōu)算法極為一致。比方，我們把只具備了簡單功能的工作單元視為“螞蟻”，那么上述搜尋路徑的過程可以用于講解蟻群算法中人工蟻群的尋優(yōu)過程。三、蟻群算法解決TSP問題我們來介紹一下如何用蟻群算法求解n個城市的TSP設(shè)d為城市i，jij之間的幾何距離，dij=Xi_xjy^yj1/2。設(shè)bt表示t時刻位于n城市i的螞蟻的個數(shù)，螞蟻總數(shù)bt，ijt表示t時刻在ij連線上im殘留的信息量，初始時刻各條路徑上的信息量為?jj0=C（C為常數(shù)）。用參優(yōu)選文檔優(yōu)選文檔數(shù)「表示信息量的保留度，則經(jīng)過n個時刻后，路徑ij上的信息量依照下式作調(diào)整:_.k=ZAE..ijjk=1-jk表示第k只螞蟻在本次循環(huán)中留在路徑ij上的信息量，■"■.ij表示本次循環(huán)全部經(jīng)過的螞蟻留在ij上的信息量。k—當(dāng)?shù)趉只螞蟻經(jīng)過ij時j=*Lk⑶o當(dāng)不經(jīng)過時定義..=1/dm。螞蟻k(k=l,2,m)在運(yùn)動過程中，pj表示在t時刻螞蟻k由地址1轉(zhuǎn)移到地址j的概率:jj:jalloweck丿工宀卩(t)一ISISI=sallowed0其他我們用tabUk(k=1,2,,m)記錄螞蟻k目前已經(jīng)走過的城市會集，allowdk表示螞蟻k下一步贊同選擇的城市會集，它等于全部的城市會集除去第k只螞蟻已走過的會集tabuk。定義Lk為第k只螞蟻在本次循環(huán)中走過的路徑和。用蟻群算法解決TSP問題是一個遞推過程，當(dāng)t=0時，將螞蟻放在各城市，設(shè)定每條路徑上的信息量初值.j0二C,每只螞蟻依照公式⑷決定的概率從城市i到城市j。.jt表示從前有多少螞蟻經(jīng)過路徑(i,j);j說明較近的城市有更大的可能性被選中。a，用來控制兩者對螞蟻選擇的影響力程優(yōu)選文檔優(yōu)選文檔度。經(jīng)過一個循環(huán)后，依照公式⑴⑵⑶計算更新每條路徑的信息量jt0將所.有的tabUkk=1,2,m復(fù)原，最后求出本次循環(huán)的最短路徑minLk。這個過程不斷重復(fù)，直到全部的螞蟻都選擇同樣的路徑，也許循環(huán)次數(shù)達(dá)到起初設(shè)定的最高次數(shù)NCmax0四、解決n個城市的TSP問題的算法步驟1.初始化：設(shè)定t=0，循環(huán)計數(shù)器nc=0，對每條路徑設(shè)定初始信息量.耳0=C,［耳=0將m只螞蟻放在n個城市上（為了使問題簡化，設(shè)定m=n。2.設(shè)定taub會集的索引s=l對k從1到m把第k只螞蟻放在初步地址，對應(yīng)的設(shè)定會集tabuks3.重復(fù)下面的步驟，直到會集tabu滿為止（這一步將重復(fù)n—1次）：設(shè)定s=s+1;對k從1到m依照公式⑷確定的概率，選擇下一步搬動的目標(biāo)城市j｛在時間t時，第k只螞蟻所在的城市是tabuJsT”；將第k只螞蟻移到城市j把j加入到會集tabuks中。4.對k從1到m:將第k只螞蟻從tabUkn搬動到tabUk1；計算第k只螞蟻所走過的路程和Lk，并更新最小路徑minLk;對每條路徑1,jQ

當(dāng)?shù)趉只螞蟻經(jīng)過1j時ATij二L當(dāng)不經(jīng)過時ijijij5.對每條路徑(i,j)依照.耳(tn)ij■(t).*<ij計算■ijt'n；設(shè)定t=t+n;設(shè)定NC=NC+1;對每條路徑i,j設(shè)定△兀=06.若是NCVNC，則清空全部的會集tabu轉(zhuǎn)到第二步；否則，得出最短的路徑。優(yōu)選文檔優(yōu)選文檔算法的流程以以下圖五、仿真結(jié)果城市TSIP10001500200025Q030Q035Q040004500第200步最短距禽為157086818優(yōu)選文檔優(yōu)選文檔參照文件：[1]黃麗韶，朱喜基.基于MATLAB的蟻群算法求解旅行商問題[J].計算機(jī)世界.李志偉.基于群集智能的蟻群優(yōu)化算法研究[J].計算機(jī)工程與設(shè)計，2003，08.王源?螞蟻算法求解TSP問題.楊殿生?TSP問題的蟻群算法求解?鄂州大學(xué)報?⑸尹曉峰，劉春煌.基于MATLAB的混雜型蟻群算法求解旅行商問題[J].鐵路計算機(jī)應(yīng)用,2005,09.附錄附錄一：Matlab實現(xiàn)程序以下：%一始化變量clear;Alpha=1;%信息素重要程度的參數(shù)（對路徑選擇有很大影響）Beta=5;%啟示式因子重要程度的參數(shù)（對路徑選擇有很大影響）Rho=0.95;%信息素蒸發(fā)系數(shù)優(yōu)選文檔優(yōu)選文檔NC_max=200;%最大迭代次數(shù)（循環(huán)多結(jié)果更優(yōu)適當(dāng)即可）Q=100;%信息素增加強(qiáng)度系數(shù)（對結(jié)果影響?。〤ityNum=31;%問題的規(guī)模(城市個數(shù))[dislist,Clist]=tsp(CityNum);m=CityNum;%螞蟻個數(shù)Eta=1./dislist;%Eta為啟示因子，這里設(shè)為距離的倒數(shù)Tau=ones(CityNum,CityNum);%Tau為信息素矩陣Tabu=zeros(m,CityNum);%儲藏并記錄路徑的生成NC=1;%迭代計數(shù)器R_best=zeros(NC_max,CityNum);%L_best=inf.*ones(NC_max,1);%figure(1);

各代最正確路線各代最正確路線的長度L_ave=zeros(NC_max,1);%各代路線的平均長度whileNC<=NC_max%停止條件之一：達(dá)到最大迭代次數(shù)%二將m只螞蟻放到CityNum個城市上Randpos=[];fori=1:(ceil(m/CityNum))Randpos=[Randpos,randperm(CityNum)];endTabu(:,1)=(Randpos(1,1:m))';%三m只螞蟻按概率函數(shù)選擇下一座城市，完成各自的遨游forj=2:CityNumfori=1:mvisited=Tabu(i,1:(j-1));%已接見的城市J=zeros(1,(CityNum-j+1));%待接見的城市P=J;%待接見城市的選擇概率分布Jc=1;fork=1:CityNumifisempty(find(visited==k,1))J(Jc)=k;Jc=Jc+1;endend%計算待選城市的概率分布fork=1:length(J)P(k)=(Tau(visited(end),J(k)FAIpha)*(Eta(visited(end),J(k)FBeta);endP=P/(sum(P));按概率原則采用下一個城市Pcum=cumsum(P);SeIect=find(Pcum>=rand);to_visit=J(SeIect(1));Tabu(i,j)=to_visit;endendifNC>=2Tabu(1,:)=R_best(NC-1,:);end%四記錄本次迭代最正確路線L=zeros(m,1);fori=1:mR=Tabu(i,:);L(i)=CalDist(dislist,R);endL_best(NC)=min(L);pos=find(L==L_best(NC));R_best(NC,:)=Tabu(pos(1),:);L_ave(NC)=mean(L);優(yōu)選文檔優(yōu)選文檔drawTSP(Clist,R_best(NC,:),L_best(NC),NC,0);NC=NC+1;%五更新信息素Delta_Tau=zeros(CityNum,CityNum);fori=1:mforj=1:(CityNum-1)Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);endDelta_Tau(Tabu(i,CityNum),Tabu(i,1))=Delta_Tau(Tabu(i,CityNum),Tabu(i,1))+Q/L(i);endTau=(1-Rho).*Tau+Delta_Tau;%六禁忌表清零Tabu=zeros(m,CityNum);%pause;tauji(NC)=Tau(1,2);end七輸出結(jié)果Pos=find(L_best==min(L_best));Shortest_Route=R_best(Pos(1),:);Shortest_Length=L_best(Pos(1));figure(2);plot([L_bestL_ave]);legend('最短距離’，平均距離');附錄二：function[DLn,cityn]=tsp(n)ifn==31city31=[13042312;36391315;41772244;37121399;34881535;33261556;32381229;41961004;優(yōu)選文檔優(yōu)選文檔4312790;4386570;30071970;25621756;27881491;23811676;1332695;37151678;39182179;40612370;37802212;36762578;40292838;42632931;34291908;35072367;33942643;34393201;29353240;31403550;25452357;27782826;23702975];%31d'=423.741byDBcitiesFogelfori=1:31forj=1:31DL31(i,j)=((city31(i,1)-city31(j,1)F2+(city31(i,2)-city31(j,2))A2)A0.5;endendDLn=DL31;cityn=city31;end附錄三：functionm=drawTSP(Clist,BSF,bsf