蟻群算法在最短路中的應(yīng)用

《蟻群算法在最短路中的應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、下面的程序是蟻群算法在最短路中的應(yīng)用，稍加擴(kuò)展即可應(yīng)用于機(jī)器人路徑規(guī)劃function[ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q)%%---------------------------------------------------------------%?ACASP.m%?蟻群算法動(dòng)態(tài)尋路算法%?ChengAihua,PLAInformationEngineeringUniversity,ZhengZhou,China%?Email:aihuacheng@gm

2、ail.com%?Allrightsreserved%%---------------------------------------------------------------%?輸入?yún)?shù)列表%?G???????地形圖為01矩陣，如果為1表示障礙物%?Tau?????初始信息素矩陣（認(rèn)為前面的覓食活動(dòng)中有殘留的信息素）%?K???????迭代次數(shù)（指螞蟻出動(dòng)多少波）%?M???????螞蟻個(gè)數(shù)（每一波螞蟻有多少個(gè)）%?S???????起始點(diǎn)（最短路徑的起始點(diǎn)）%?E???????終止點(diǎn)（最短路徑的目的點(diǎn)）%?Alpha??

3、?表征信息素重要程度的參數(shù)%?Beta????表征啟發(fā)式因子重要程度的參數(shù)%?Rho?????信息素蒸發(fā)系數(shù)%?Q???????信息素增加強(qiáng)度系數(shù)%%?輸出參數(shù)列表%?ROUTES??每一代的每一只螞蟻的爬行路線%?PL??????每一代的每一只螞蟻的爬行路線長(zhǎng)度%?Tau?????輸出動(dòng)態(tài)修正過(guò)的信息素%%--------------------變量初始化----------------------------------%loadD=G2D(G);N=size(D,1);%N表示問(wèn)題的規(guī)模（象素個(gè)數(shù)）MM=size(G,1)

4、;a=1;%小方格象素的邊長(zhǎng)Ex=a*(mod(E,MM)-0.5);%終止點(diǎn)橫坐標(biāo)ifEx==-0.5???Ex=MM-0.5;endEy=a*(MM+0.5-ceil(E/MM));%終止點(diǎn)縱坐標(biāo)Eta=zeros(1,N);%啟發(fā)式信息，取為至目標(biāo)點(diǎn)的直線距離的倒數(shù)%下面構(gòu)造啟發(fā)式信息矩陣fori=1:N????ifix==-0.5???????ix=MM-0.5;???end???iy=a*(MM+0.5-ceil(i/MM));??????ifi~=E???????Eta(1,i)=1/((ix-Ex)^2+(iy-E

5、y)^2)^0.5;???else???????Eta(1,i)=100;???endendROUTES=cell(K,M);%用細(xì)胞結(jié)構(gòu)存儲(chǔ)每一代的每一只螞蟻的爬行路線PL=zeros(K,M);%用矩陣存儲(chǔ)每一代的每一只螞蟻的爬行路線長(zhǎng)度%%-----------啟動(dòng)K輪螞蟻覓食活動(dòng)，每輪派出M只螞蟻--------------------fork=1:K???disp(k);???form=1:M%%????第一步：狀態(tài)初始化???????W=S;%當(dāng)前節(jié)點(diǎn)初始化為起始點(diǎn)???????Path=S;%爬行路線初始化????

6、???PLkm=0;%爬行路線長(zhǎng)度初始化???????TABUkm=ones(1,N);%禁忌表初始化???????TABUkm(S)=0;%已經(jīng)在初始點(diǎn)了，因此要排除???????DD=D;%鄰接矩陣初始化%%????第二步：下一步可以前往的節(jié)點(diǎn)???????DW=DD(W,:);???????DW1=find(DW???????forj=1:length(DW1)???????????ifTABUkm(DW1(j))==0???????????????DW(j)=inf;???????????end???????end???

7、????LJD=find(DW???????Len_LJD=length(LJD);%可選節(jié)點(diǎn)的個(gè)數(shù)%%????覓食停止條件：螞蟻未遇到食物或者陷入死胡同???????whileW~=E&&Len_LJD>=1%%????????第三步：轉(zhuǎn)輪賭法選擇下一步怎么走???????????PP=zeros(1,Len_LJD);???????????fori=1:Len_LJD???????????????PP(i)=(Tau(W,LJD(i))^Alpha)*(Eta(LJD(i))^Beta);???????????end????

8、???????PP=PP/(sum(PP));%建立概率分布???????????Pcum=cumsum(PP);???????????Select=find(Pcum>=rand);%%????????第四步：狀態(tài)更新和記錄???????????Path=[P