蟻群算法即相關(guān)代碼實現(xiàn)詳解—matlab之智能算法

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

一.算法背景

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

二.簡單說明

1）先看兩張圖

?

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

2）算法探究

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

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

??

相反選擇路徑B的概率為

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

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

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

%符號說明

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

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

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

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

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

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

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

%RouteOfBest表示各代的最佳路線

%LengthOfBest表示每次迭代的最佳路線的長度

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

%b表示期望因子，表示能見度的重要性

%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;%表示每條邊的能見度

SumOfCity=20;

>> SumOfant=40;

>> sight=1./length_address;

info_pre=ones（SumOfCity，SumOfCity）;

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

>> EachOfRoute=zeros（SumOfCity，SumOfCity）;

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

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

>> RouteOfBest=zeros（nc_max，SumOfCity）; %各代最佳路線

Length_best=inf.*ones（nc_max，1）; %各代最佳路線的長度

LengthOfAverage=zeros（nc_max，1）; %各代路線的平均長度

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

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

Randpos=［］; %隨即存取

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

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

Randpos=［Randpos，randperm（SumOfCity）］;

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

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

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

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

J=zeros（1，（SumOfCity-j+1））; %待訪問的城市

P=J;

%待訪問城市的選擇概率分布，用P表示

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

for k=1:SumOfCity

if length（find（CityOfVisited==k））==0 %開始時置0

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

end

end

%下面計算待選城市的概率分布

for k=1:length（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））;%按概率原則選取下一個城市

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

Select=find（Pcum>=rand）; %若計算的概率大于原來的就選擇這條路線

CityOfNextVisit=J（Select（1））;

EachOfRoute（i，j）=CityOfNextVisit;

end

end

if nc_now>=2

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

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

end%%第四步：記錄本次迭代最佳路線

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

for i=1:SumOfant

R=EachOfRoute（i，：）;

?

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

?