蟻群算法即相關(guān)代碼實(shí)現(xiàn)詳解

一.算法背景

蟻群算法是近年來(lái)剛剛誕生的隨機(jī)優(yōu)化方法，它是一種源于大自然的新的仿生類(lèi)算法.由意大利學(xué)者Dorigo最早提出，螞蟻算法主要是通過(guò)螞蟻群體之間的信息傳遞而達(dá)到尋優(yōu)的目的，最初又稱(chēng)蟻群優(yōu)化方法（Ant Colony Optimization簡(jiǎn)稱(chēng)ACO）.由于模擬仿真中使用了人工螞蟻的概念，因此亦稱(chēng)螞蟻系統(tǒng).

二.簡(jiǎn)單說(shuō)明

1）先看兩張圖

?

圖1-1顯示了螞蟻從巢穴出去覓食的過(guò)程，起初在遇到障礙的時(shí)候，會(huì)以相同的概率選擇通過(guò)障礙的路徑（即選擇了兩條路徑假設(shè)為路徑1和2，且每條路徑上的螞蟻數(shù)量是相同的）.而在圖1-1（d）中，螞蟻們卻不再選擇路徑（2）），這就是蟻群算法的“雙橋模型”，這是什么原因呢？

2）算法探究

經(jīng)過(guò)探究，上述的實(shí)驗(yàn)反應(yīng)了螞蟻在群體行為中的一種信息正反饋現(xiàn)象.螞蟻個(gè)體間通過(guò)這種信息交流機(jī)制來(lái)搜索食物.而用來(lái)交流反饋的化學(xué)因素現(xiàn)在被我們稱(chēng)之為——————“信息素”.

然后建立相關(guān)“雙橋”實(shí)驗(yàn)的數(shù)學(xué)模型，首先，假設(shè)在對(duì)稱(chēng)橋的信息素的總數(shù)與過(guò)去一段時(shí)間內(nèi)經(jīng)過(guò)該橋的螞蟻數(shù)目成正比（即每只螞蟻都具有相同的信息素釋放能力）；其次，假設(shè)某時(shí)刻螞蟻按照橋上殘留信息量的多少來(lái)選擇其中的某條路徑，經(jīng)過(guò)該路徑的螞蟻數(shù)目越多，則該橋上的殘留信息素總量就越大.假設(shè)1-1圖中的兩條路徑分別為A和B，Am和Bm分別表示通過(guò)路徑A和B的螞蟻數(shù)目.則當(dāng)所有M（Am+Bm=M）只螞蟻通過(guò)障礙后，第（M+1）只螞蟻選擇路徑A的概率為

??

相反選擇路徑B的概率為

其中參數(shù)h（期望因子）和k（啟發(fā)因子）用來(lái)匹配真實(shí)實(shí)驗(yàn)數(shù)據(jù)，第（M+1）只螞蟻按照上述公式計(jì)算概率，然后生成一個(gè)區(qū)間在［0，1］上均勻分布的隨機(jī)數(shù)w，若w<=P（A），則選擇路徑A，否則選擇路徑B.

三.matlab相關(guān)代碼實(shí)現(xiàn)（以TSP旅行商問(wèn)題為例）

以下是解放軍信息工程大學(xué)一個(gè)老師編的matlab程序，網(wǎng)上有很多版本，已經(jīng)由本人添加注釋并修改過(guò)請(qǐng)尊重原作者勞動(dòng)，引用時(shí)請(qǐng)注明出處.

%符號(hào)說(shuō)明

%SumOfant表示螞蟻數(shù)量

%SumOfCity表示城市數(shù)量

%sight為距離的倒數(shù)，表示每條邊的能見(jiàn)度

%Q表示信息素增強(qiáng)的系數(shù)

%nc_now表示當(dāng)前的迭代次數(shù)

%nc_max表示自主設(shè)置的最大迭代次數(shù) 表示終止條件

%first_address表示測(cè)試數(shù)據(jù)中的城市坐標(biāo)

%RouteOfBest表示各代的最佳路線(xiàn)

%LengthOfBest表示每次迭代的最佳路線(xiàn)的長(zhǎng)度

%a表示啟發(fā)因子，表示信息素的相對(duì)重要程度

%b表示期望因子，表示能見(jiàn)度的重要性

%p表示信息素的蒸發(fā)系數(shù)，（1-p）表示信息素持久性系數(shù)

%length_address表示兩兩城市間的距離

for n=1:size（first_address）

for m=1:size（first_address）

length_address（n，m）=［（first_address（n，1）-first_address（m，1））^2+（first_address（n，2）-first_address（m，2））^2］^1/2;

end

end

sight=1./length_address;%表示每條邊的能見(jiàn)度

SumOfCity=20;

>> SumOfant=40;

>> sight=1./length_address;

info_pre=ones（SumOfCity，SumOfCity）;

%info_pre為信息素矩陣，可以理解為在螞蟻還沒(méi)有被放入城市前，每條道路上就已經(jīng)存在了一定含量的信息素（只是為了方便計(jì)算）

>> EachOfRoute=zeros（SumOfCity，SumOfCity）;

> %存儲(chǔ)并記錄每次迭代時(shí)每只螞蟻經(jīng)歷的路徑生成；

>> nc_now=1; nc_max=60; %迭代計(jì)數(shù)器，記錄迭代次數(shù)，此處設(shè)置為60次迭代

>> RouteOfBest=zeros（nc_max，SumOfCity）; %各代最佳路線(xiàn)

Length_best=inf.*ones（nc_max，1）; %各代最佳路線(xiàn)的長(zhǎng)度

LengthOfAverage=zeros（nc_max，1）; %各代路線(xiàn)的平均長(zhǎng)度

while nc_now<=nc_max%表示循環(huán)終止條件，迭代終止器

%%第二步：將m只螞蟻放到n個(gè)城市上

Randpos=［］; %隨即存取

for i=1：（ceil（SumOfant/SumOfCity））

%ceil為取整函數(shù)，表示每個(gè)城市放幾只螞蟻

Randpos=［Randpos，randperm（SumOfCity）］;

%randperm表示1-20隨機(jī)分配，也就是每只螞蟻的位置

end %表示每只螞蟻一開(kāi)始所被放置的位置%第三步：所有螞蟻按概率函數(shù)選擇下一座城市，完成各自的周游

for j=2:SumOfCity %每只螞蟻從第一個(gè)城市出發(fā)，開(kāi)始依次訪問(wèn)

for i=1:SumOfant CityOfVisited=EachOfRoute（i，1：（j-1））; %記錄已訪問(wèn)的城市，避免重復(fù)訪問(wèn)

J=zeros（1，（SumOfCity-j+1））; %待訪問(wèn)的城市

P=J;

%待訪問(wèn)城市的選擇概率分布，用P表示

Jc=1;%記錄已經(jīng)訪問(wèn)的城市數(shù)目

for k=1:SumOfCity

if length（find（CityOfVisited==k））==0 %開(kāi)始時(shí)置0

J（Jc）=k; Jc=Jc+1; %訪問(wèn)的城市個(gè)數(shù)自加1

end

end

%下面計(jì)算待選城市的概率分布

for k=1:length（J）%對(duì)每只螞蟻還沒(méi)有訪問(wèn)的城市依次計(jì)算概率

P（k）=（info_pre（CityOfVisited（end），J（k））^0.7）*（sight（CityOfVisited（end），J（k））^3.8）;%在這里設(shè)置啟發(fā)因子=0.7，期望因子=3.8 end P=P/（sum（P））;%按概率原則選取下一個(gè)城市

Pcum=cumsum（P）; %cumsum，元素累加即求和

Select=find（Pcum>=rand）; %若計(jì)算的概率大于原來(lái)的就選擇這條路線(xiàn)

CityOfNextVisit=J（Select（1））;

EachOfRoute（i，j）=CityOfNextVisit;

end

end

if nc_now>=2

EachOfRoute（1，：）=RouteOfBest（nc_now-1，：）;

%如果迭代次數(shù)大于2，則將前依次迭代的訪問(wèn)順序存入EachOfRoute

end%%第四步：記錄本次迭代最佳路線(xiàn)

L=zeros（SumOfant，1）; %開(kāi)始距離為0，m*1的列向量

for i=1:SumOfant

R=EachOfRoute（i，：）;

?

其中DrawRoute為自己寫(xiě)的一個(gè)畫(huà)圖函數(shù)，推薦程序如下

?