蟻群算法最優(yōu)路徑

機(jī)器人的路徑規(guī)劃---蟻群算法蟻群算法眾所周知，蟻群算法是優(yōu)化領(lǐng)域中新出現(xiàn)并逐漸引起重視的一種仿生進(jìn)化算法它是群體智能的典型實(shí)現(xiàn)，是一種基于種群尋優(yōu)的啟發(fā)式搜索算法。自從M.Dorigo等意大利學(xué)者在1991年首先提出蟻群算法(AntColonySystem,ACS)以來(lái)，這種新型的分布式智能模擬算法已逐漸引起人們的注意并得到廣泛的應(yīng)用。蟻群算法的特點(diǎn)主要表現(xiàn)在以下五個(gè)方面：螞蟻群體行為表現(xiàn)出正反饋過(guò)程。蟻群在尋優(yōu)的過(guò)程中會(huì)釋放一定量的信息素，蟻群的規(guī)模越大，釋放的信息素的量也就越大，而尋優(yōu)路徑上存在的信息素濃度越高，就會(huì)吸引更多的螞蟻，形成一種正反饋機(jī)制，然后通過(guò)反饋機(jī)制的調(diào)整，可對(duì)系統(tǒng)中的較優(yōu)解起到一個(gè)自增強(qiáng)的作用，從而使問(wèn)題的解向著全局最優(yōu)的方向演變，最終能有效地獲得全局相對(duì)較優(yōu)解。蟻群算法是一種本質(zhì)并行的算法。個(gè)體之間不斷進(jìn)行信息交流和傳遞.有利于最優(yōu)解的發(fā)現(xiàn)，并在很大程度上減少了陷于局部最優(yōu)的可能。蟻群算法易于與其他方法結(jié)合。蟻?zhàn)逅惴ㄍㄟ^(guò)與其他算法的結(jié)合，能夠揚(yáng)長(zhǎng)避短，提高算法的性能。蟻群算法提供的解具有全局性的特點(diǎn)。一群算法是一種群只能算法，每只螞蟻巡游的過(guò)程相對(duì)獨(dú)立，他們會(huì)在自己的活動(dòng)空間進(jìn)行搜索，螞蟻在尋優(yōu)過(guò)程中通過(guò)釋放信息素，相互影響，互相通信，保證了解的全局性。蟻群算法具有魯棒性。蟻?zhàn)逅惴ǖ臄?shù)學(xué)模型易于理解，可以廣泛應(yīng)用在很多復(fù)雜的優(yōu)化問(wèn)題中，蟻?zhàn)逅惴▍^(qū)別于傳統(tǒng)優(yōu)化算法的一個(gè)特點(diǎn)在于該算法不依賴(lài)于初始點(diǎn)的選擇，受初始點(diǎn)的影響相對(duì)較小，并且在整個(gè)算法過(guò)程中會(huì)自適應(yīng)的調(diào)整尋優(yōu)路徑。由此可見(jiàn)，在機(jī)器人尋找最優(yōu)路徑的過(guò)程中，采用蟻群算法實(shí)現(xiàn)路徑的規(guī)劃問(wèn)題，可以高效，準(zhǔn)確的找到最優(yōu)的路徑。移動(dòng)機(jī)器人的路徑規(guī)劃2.1環(huán)境信息處理假設(shè)機(jī)器人運(yùn)行環(huán)境為邊長(zhǎng)分別為x和Y的矩形區(qū)域，在矩形區(qū)域內(nèi)分布有n個(gè)異形障礙物，顯然對(duì)于該獲取的實(shí)際環(huán)境信息：首先，由于障礙物大小不一，而且形狀也各不相同，為了減少機(jī)器人處理地圖信息的負(fù)擔(dān)，需要對(duì)工作環(huán)境行一些必要的預(yù)處理；其次，在后續(xù)章節(jié)中，描述機(jī)器人的路徑規(guī)劃方法是基于把障礙物近似成質(zhì)點(diǎn)的基礎(chǔ)上進(jìn)行的，而要把障礙物近似成質(zhì)點(diǎn)也同樣需要對(duì)工作環(huán)境的信息進(jìn)行適當(dāng)預(yù)處理。環(huán)境信息預(yù)處理遵循以下原則：1）移動(dòng)機(jī)器人作二維平面運(yùn)動(dòng)，障礙物不考慮高度信息；2）小問(wèn)距障礙物作合并處理，即如果兩個(gè)障礙物相距太近，障礙物之間距離小于機(jī)器人通過(guò)的最小安全距離。則將兩個(gè)障礙物合并作為一個(gè)障礙物處理；3）作出障礙物的外接矩形，并對(duì)障礙物外接矩形進(jìn)行徑向擴(kuò)張且對(duì)環(huán)境邊界向內(nèi)作徑向擴(kuò)張，因此可把移動(dòng)機(jī)器人退化成運(yùn)動(dòng)質(zhì)點(diǎn)處理。2.2環(huán)境建模設(shè)機(jī)器人工作空間為二維結(jié)構(gòu)化空間記為RS，并且障礙物位置、大小已知。用尺寸相同的柵格對(duì)RS進(jìn)行劃分，柵格大小以機(jī)器人能在其內(nèi)自由運(yùn)動(dòng)為限，設(shè)機(jī)器人能自由運(yùn)動(dòng)的范圍為［0，R］。若某一柵格尺寸范圍內(nèi)不含任何障礙物，則稱(chēng)此柵格為自由柵格，反之稱(chēng)為障礙柵格。自由空間和障礙物均可表示成柵格塊的集合，我們將障礙物柵格集記為OS。柵格標(biāo)識(shí)可采用下述兩種方法：（1）直角坐標(biāo)法。以柵格陣左上角為坐標(biāo)原點(diǎn)，水平向右為x軸正方向，豎直向下為Y軸正方向，每一柵格區(qū)間對(duì)應(yīng)坐標(biāo)軸上的一個(gè)單位長(zhǎng)度。任一柵格均可用直角坐標(biāo)（x，y）唯一標(biāo)識(shí)。（2）序號(hào)法。按從左到右，從上到下的順序，從柵格陣左上角第一個(gè)柵格開(kāi)始，給每一個(gè)柵格一個(gè)序號(hào)n（從0開(kāi)始計(jì)），則序號(hào)以與柵格塊一一對(duì)應(yīng)。2.3具體方法給定一個(gè)有彈個(gè)節(jié)點(diǎn)的城市道路網(wǎng)的路徑規(guī)劃問(wèn)題，我們可以把指定的起始點(diǎn)s假設(shè)為人工蟻群（以下簡(jiǎn)稱(chēng)為蟻群）的巢穴，把目標(biāo)點(diǎn)t假設(shè)為要尋找的食物，則此路徑規(guī)劃問(wèn)題就可以轉(zhuǎn)化為蟻群尋找食物的路徑尋優(yōu)問(wèn)題。假定人工螞蟻(以下簡(jiǎn)稱(chēng)為螞蟻)的數(shù)量為m只，則每只螞蟻的行為要符合以下的規(guī)則：能夠釋放出兩種類(lèi)型的信息素：“食物”信息素和“巢穴”信息素；根據(jù)與當(dāng)前節(jié)點(diǎn)相連接的各個(gè)路徑上的信息素濃度和路徑長(zhǎng)度，以相應(yīng)的概率來(lái)隨機(jī)選擇下一個(gè)節(jié)點(diǎn)；不再選擇已經(jīng)走過(guò)的節(jié)點(diǎn)為下一個(gè)節(jié)點(diǎn)，這可以通過(guò)一個(gè)結(jié)構(gòu)數(shù)組來(lái)實(shí)現(xiàn)；在尋找食物時(shí)，通過(guò)“食物”信息素尋找下一個(gè)節(jié)點(diǎn)，同時(shí)釋放“巢穴”信息素；在尋找巢穴時(shí)，通過(guò)“巢穴”信息素尋找下一個(gè)節(jié)點(diǎn)，同時(shí)釋放“食物”信息素；按一定的路徑長(zhǎng)度釋放相應(yīng)的信息素濃度，并且所釋放的信息素濃度會(huì)隨著時(shí)間的推移而逐步減少；程序設(shè)計(jì)流程在主程序流程中，地圖數(shù)據(jù)庫(kù)是從實(shí)際地圖中抽象出來(lái)的城市道路網(wǎng)相關(guān)的數(shù)據(jù)信息，其中包括城市道路網(wǎng)的節(jié)點(diǎn)信息、道路信息和相應(yīng)道路的信息素信息，每部分信息都各自形成一個(gè)數(shù)據(jù)表。在節(jié)點(diǎn)表中，包括了各個(gè)節(jié)點(diǎn)的編號(hào)、對(duì)應(yīng)的地點(diǎn)名稱(chēng)和經(jīng)緯度坐標(biāo)等數(shù)據(jù)。在道路表中，包括了每條道路的起點(diǎn)和終點(diǎn)對(duì)應(yīng)的編號(hào)、道路的長(zhǎng)度、級(jí)別和所經(jīng)過(guò)的路線(xiàn)等數(shù)據(jù)。在信息素表中，包括了對(duì)應(yīng)道路上的“巢穴”信息素和“食物”信息素等數(shù)據(jù)。所需要輸入的參數(shù)包括：節(jié)點(diǎn)的數(shù)量n、起始節(jié)點(diǎn)的編號(hào)OriNode、目標(biāo)節(jié)點(diǎn)的編號(hào)DesNode、最大循環(huán)次數(shù)MaxCount.螞蟻的數(shù)量m、蒸發(fā)信息素的相對(duì)重要程度、每只螞蟻所釋放的信息素總量Q、信息素濃度的相對(duì)重要程度口、啟發(fā)式信息的相對(duì)重要程。所需要初始化的參數(shù)包括：“巢穴”信息素和“食物”信息素等值，每條道路對(duì)應(yīng)的“巢穴”信息素和“食物”信息素的值分別仞始化為1，這是為了在計(jì)算下一個(gè)節(jié)點(diǎn)的選擇概率時(shí)，分母不為0。在程序開(kāi)始時(shí)，首先連接地圖數(shù)據(jù)庫(kù)，然后輸入、初始化各個(gè)參數(shù)并開(kāi)始進(jìn)行循環(huán)。在每次循環(huán)中，每只螞蟻依次進(jìn)行尋食過(guò)程，如果有螞蟻找到了食物即找到了一條尋食路徑，將此路徑與本次循環(huán)中其它螞蟻找到的尋食路徑進(jìn)行比較，將最小的尋食路徑更新為最優(yōu)路徑，并判斷是否滿(mǎn)足所給定的精度，如果滿(mǎn)足則退出循環(huán)，否則進(jìn)行下一次循環(huán)。當(dāng)循環(huán)次數(shù)達(dá)到最大次數(shù)時(shí)，結(jié)束循環(huán)并判斷是否找到了最優(yōu)路徑，如果找到了最優(yōu)路徑，則輸出最優(yōu)路徑的路線(xiàn)及其權(quán)值，否則顯示沒(méi)有找到最優(yōu)路徑。最后，關(guān)閉地圖數(shù)據(jù)庫(kù)并結(jié)束程序。在每只螞蟻進(jìn)行尋食的過(guò)程中，首先判斷螞蟻是否正在尋找食物，如果是則進(jìn)行尋找食物的過(guò)程，否則進(jìn)行尋找巢穴的過(guò)程。在進(jìn)行尋找食物的過(guò)程中，首先從地圖數(shù)據(jù)庫(kù)的道路表中讀取與當(dāng)前節(jié)點(diǎn)所連接的節(jié)點(diǎn)數(shù)，以及每個(gè)節(jié)點(diǎn)的編號(hào)和權(quán)值。判斷每個(gè)節(jié)點(diǎn)是否已經(jīng)走過(guò)，如果此節(jié)點(diǎn)已經(jīng)走過(guò)，則讀取下一個(gè)節(jié)點(diǎn)。從地圖數(shù)據(jù)庫(kù)的信息素表中讀取對(duì)應(yīng)邊的“食物”信息素值，從當(dāng)前點(diǎn)到下一可行點(diǎn)的轉(zhuǎn)移是由基于信息量的狀態(tài)轉(zhuǎn)移概率和和距離啟發(fā)式信息概率綜合決定的，而這里采用的綜合決定方法是基于比例選擇策略即“輪盤(pán)賭”的方式。從地圖數(shù)據(jù)庫(kù)的道路表中讀取對(duì)應(yīng)邊的權(quán)值，并計(jì)算所走過(guò)路徑的權(quán)值。從地圖數(shù)據(jù)庫(kù)的信息素表中讀取對(duì)應(yīng)邊的“巢穴”信息素值，并重新計(jì)算對(duì)應(yīng)邊的“巢穴”信息素值。當(dāng)所得的值小于1時(shí)，將此值設(shè)置為1，這是為了保證下一回計(jì)算選擇概率時(shí)分母不為0。將重新計(jì)算的“巢穴”信息素值更新到信息素表中。判斷下一個(gè)目標(biāo)節(jié)點(diǎn)是否為食物，如果是的話(huà)，則保存各個(gè)記錄，如螞蟻所走過(guò)的節(jié)點(diǎn)、此螞蟻找到食物的次數(shù)以及整個(gè)路徑的總權(quán)值等數(shù)據(jù)，并為尋找巢穴做準(zhǔn)備，如清空內(nèi)存中的歷史數(shù)據(jù)，將食物作為起始節(jié)點(diǎn)等，否則設(shè)置下一個(gè)目標(biāo)節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)。在進(jìn)行尋找巢穴的過(guò)程中，大部分的操作都跟上面螞蟻進(jìn)行尋找食物的過(guò)程一樣，只不過(guò)將“食物”信息素和“巢穴”信息素進(jìn)行對(duì)調(diào)，在判斷下一個(gè)目標(biāo)節(jié)點(diǎn)是否為巢穴的時(shí)候，不需要保存各個(gè)記錄，只需為尋找食物做準(zhǔn)備，如清空內(nèi)存中的歷史數(shù)據(jù)，將巢穴作為起始節(jié)點(diǎn)，并將此螞蟻上次找到食物的路徑記錄。程序流程圖如下：

Matlab仿真4.1參數(shù)介紹地圖數(shù)據(jù)庫(kù)是從實(shí)際地圖中抽象出來(lái)的城市道路網(wǎng)相關(guān)的數(shù)據(jù)信息，其中包括城市道路網(wǎng)的節(jié)點(diǎn)信息、道路信息和相應(yīng)道路的信息素信息，每部分信息都各自形成一個(gè)數(shù)據(jù)表。在節(jié)點(diǎn)表中，包括了各個(gè)節(jié)點(diǎn)的編號(hào)、對(duì)應(yīng)的地點(diǎn)名稱(chēng)和經(jīng)緯度坐標(biāo)等數(shù)據(jù)。在道路表中，包括了每條道路的起點(diǎn)和終點(diǎn)對(duì)應(yīng)的編號(hào)、道路的長(zhǎng)度、級(jí)別和所經(jīng)過(guò)的路線(xiàn)等數(shù)據(jù)。在信息素表中，包括了對(duì)應(yīng)道路上的“巢穴”信息素和“食物”信息素等數(shù)據(jù)。本仿真系統(tǒng)的靜態(tài)地圖數(shù)據(jù)假設(shè)在機(jī)器人出發(fā)之前就已經(jīng)得到，而動(dòng)態(tài)地圖數(shù)據(jù)假設(shè)按一定的頻率可以得到。在機(jī)器人整個(gè)仿真系統(tǒng)中所需要輸入的參數(shù)包括：節(jié)點(diǎn)的數(shù)量櫛、起始節(jié)點(diǎn)的編號(hào)OriNode、目標(biāo)節(jié)點(diǎn)的編號(hào)DesNode、最大循環(huán)次數(shù)MaxCount、螞蟻的數(shù)量m、蒸發(fā)信息素的相對(duì)重要程度、每只螞蟻所釋放的信息素總量Q、信息素濃度的相對(duì)重要程度〃、啟發(fā)式信息的相對(duì)重要程。所需要初始化的參數(shù)包括：“巢穴”信息素和“食物”信息素等值，每條道路對(duì)應(yīng)的“巢穴”信息素和“食物”信息素的值分別初始化為1，這是為了在計(jì)算下一個(gè)節(jié)點(diǎn)的選擇概率時(shí)，分母不為0。4.2程序介紹4.2.1G2D.m用于把障礙物分布圖轉(zhuǎn)化為圖的賦權(quán)鄰接矩陣，地形圖矩陣是一個(gè)01矩陣，里面的所有元素要么為0，要么為1。為0即表示機(jī)器人可以到達(dá)的節(jié)點(diǎn)，為1即表示其對(duì)應(yīng)的柵格是障礙物。源程序如下：functionD=G2D(G)a=1;N=size(G,1);D=inf*ones(NA2,NA2);fori=1:(NA2)x=ceil(i/N-0.00001);y=mod(i,N);ify==0y=N;endx1=x-1;y1=y-1;ifx1>=1&&y1>=1j=(x1-1)*N+y1;D(i,j)=1.414*a;D(j,i)=1.414*a;endx2=x-1;y2=y;ifx2>=1j=(x2-1)*N+y2;D(i,j)=a;D(j,i)=a;endx3=x-1;y3=y+1;ifx3>=1&&x3<=Nj=(x3-1)*N+y3;D(i,j)=1.414*a;D(j,i)=1.414*a;endx4=x;y4=y-l;ify4>=lj=(x4-l)*N+y4;D(i,j)=a;D(j,i)=a;endx5=x;y5=y+l;ify5v=Nj=(x5-l)*N+y5;D(i,j)=a;D(j,i)=a;endx6=x+l;y6=y-l;ifx6v=N&&y6>=lj=(x6-l)*N+y6;D(i,j)=1.414*a;D(j,i)=1.414*a;endx7=x+l;y7=y;ifx7v=Nj=(x7-l)*N+y7;D(i,j)=a;D(j,i)=a;endx8=x+l;y8=y+l;ifx8v=N&&y8v=Nj=(x8-l)*N+y8;D(i,j)=1.414*a;D(j,i)=1.414*a;endendforx=l:Nfory=l:NifG(x,y)=lJ=(x-l)*N+y;D(:,J)=inf*ones(NA2,l);D(J,:)=inf*ones(l,NA2);endendendfori=l:(N-l)x=i*N+1;y=(i+1)*N;D(x,y)=inf;D(y,x)=inf;end4.2.2ACASP.m障礙物可以動(dòng)的情況設(shè)計(jì)的蟻群算法，其主要功能就是通過(guò)派遣若干批螞蟻，來(lái)搜索動(dòng)態(tài)環(huán)境下的最短路。程序內(nèi)部設(shè)計(jì)準(zhǔn)則完全按照前面的設(shè)計(jì)要求進(jìn)行，包括啟發(fā)式信息規(guī)則、信息素更新規(guī)則，等等。當(dāng)然，此程序可以單獨(dú)運(yùn)行，主要用于解決靜態(tài)環(huán)境下的螞蟻尋路問(wèn)題。程序把各批次所有螞蟻的行走路線(xiàn)都記錄下來(lái)，可以據(jù)此繪出螞蟻尋路的動(dòng)態(tài)圖形。源程序如下：function[ROUTES,PL,Tau]=Route(GTau,K,M,S,E,Alpha,Beta,Rho,Q)D=G2D(G);N=size(D,1);MM=size(G,1);a=1;Ex=a*(mod(E,MM)-0.5);ifEx==-0.5Ex=MM-0.5;endEy=a*(MM+0.5-ceil(E/MM));Eta=zeros(1,N);fori=1:Nix=a*(mod(i,MM)-0.5);ifix==-0.5ix=MM-0.5;endiy=a*(MM+0.5-ceil(i/MM));ifi?=EEta(1,i)=1/((ix-Ex)A2+(iy-Ey)A2)A0.5;elseEta(1,i)=100;endendROUTES=cell(K,M);PL=zeros(K,M);fork=1:Kdisp(k);form=1:MW=S;Path=S;PLkm=0;TABUkm=ones(1,N);TABUkm(S)=0;DD=D;DW=DD(W,:);DW1=find(DW<inf);forj=1:length(DW1)ifTABUkm(DW1(j))==0DW(j)=inf;endendLJD=find(DW<inf);Len_LJD=length(LJD);whileW?=E&&Len_LJD>=1PP=zeros(1,Len_LJD);fori=1:Len_LJDPP(i)=(Tau(W,LJD(i))AAlpha)*(Eta(LJD(i))ABeta);endPP=PP/(sum(PP));Pcum=cumsum(PP);Select=find(Pcum>=rand);to_visit=LJD(Select(1));Path=[Path,to_visit];PLkm=PLkm+DD(W,to_visit);W=to_visit;%movetothenextpointforkk=1:NifTABUkm(kk)==0DD(W,kk)=inf;DD(kk,W)=inf;endendTABUkm(W)=0;DW=DD(W,:);DW1=find(DW<inf);forj=1:length(DW1)ifTABUkm(DW1(j))==0DW(j)=inf;endendLJD=find(DW<inf);Len_LJD=length(LJD);endROUTES{k,m}=Path;ifPath(end)==EPL(k,m)=PLkm;elsePL(k,m)=inf;endendDelta_Tau=zeros(N,N);form=1:MifPL(k,m)<infROUT=ROUTES{k,m};TS=length(ROUT)-1;PL_km=PL(k,m);fors=1:TSx=ROUT(s);y=ROUT(s+1);Delta_Tau(x,y)=Delta_Tau(x,y)+Q/PL_km;Delta_Tau(y,x)=Delta_Tau(y,x)+Q/PL_km;endendendTau=(1-Rho).*Tau+Delta_Tau;%pheromoneevaporatessomeandaccumulatessomeendplotif=1;%controlparameter,determineifplotornotifplotif==1%plotconvergencecurvemeanPL=zeros(1,K);minPL=zeros(1,K);fori=1:KPLK=PL(i,:);Nonzero=find(PLK<inf);PLKPLK=PLK(Nonzero);meanPL(i)=mean(PLKPLK);minPL(i)=min(PLKPLK);endfigure(1)plot(minPL,'r');holdonplot(meanPL,'g');legend('最小路徑長(zhǎng)度','平均路徑長(zhǎng)度')；gridontitle('收斂曲線(xiàn)(平均路徑長(zhǎng)度和最小路徑長(zhǎng)度)');xlabel('迭代次數(shù)');ylabel('路徑長(zhǎng)度')；%PlotPassingGraphfigure(2)axis([0,MM,0,MM])fori=1:MMforj=1:MMifG(i,j)==1x1=j-1;y1=MM-i;x2=j;y2=MM-i;x3=j;y3=MM-i+1;x4=j-1;y4=MM-i+1;fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.2,0.2,0.2]);holdonelsex1=j-1;y1=MM-i;x2=j;y2=MM-i;x3=j;y3=MM-i+1;x4=j-1;y4=MM-i+1;fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1]);holdonendendendholdonROUT=ROUTES{K,M};LENROUT=length(ROUT);Rx=ROUT;Ry=ROUT;forii=1:LENROUTRx(ii)=a*(mod(ROUT(ii),MM)-0.5);ifRx(ii)==-0.5Rx(ii)=MM-0.5;endRy(ii)=a*(MM+0.5-ceil(ROUT(ii)/MM));endplot(Rx,Ry,'LineWidth',2)endtitle('ShortestPath');axis([0,MM,0,MM]);plotif2=1;%Plotrouteforeveryiterationifplotif2==1figure(3)axis([0,MM,0,MM])fori=1:MMforj=1:MMifG(i,j)==1x1=j-1;y1=MM-i;x2=j;y2=MM-i;x3=j;y3=MM-i+1;x4=j-1;y4=MM-i+1;fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.2,0.2,0.2]);holdonelsex1=j-1;y1=MM-i;x2=j;y2=MM-i;x3=j;y3=MM-i+