蟻群算法解決tsp問題

控制蟻群算法走向的關(guān)鍵是信息素，信息素類似遺傳算法的適應(yīng)性函數(shù)，類似退火算法的評價函數(shù)，影響著其中一只螞蟻的下一步的選擇。

螞蟻：類似遺傳算法的染色體，就是一條解，在tsp問題中螞蟻的路徑就是tsp的解。

信息素：評價函數(shù)，與路徑成反比

螞蟻數(shù)量：一次迭代有多少只螞蟻在跑（注意不是一起跑，而是先后放上一只螞蟻）

迭代次數(shù)T：所有螞蟻跑完視為一次迭代周期。

程序流程：

1，隨機(jī)生成距離矩陣

進(jìn)入循環(huán)while（t

{

2，信息素遞減（只有較近的信息素才能影響這一步）

3，對于每一只螞蟻，隨機(jī)生成起點(diǎn)，標(biāo)記起點(diǎn)為訪問過

進(jìn)入循環(huán)（尋找城市數(shù)量-1次）（起點(diǎn)已經(jīng)有了）

{

4，尋找周圍城市的最大信息素

5，隨機(jī)生成0~1的數(shù)如果小于bugp（螞蟻正常選擇）則從最大信息素城市中找一個作為下一個

否則（螞蟻犯錯誤了，有木有感覺像退火算法里的允許犯錯的那個函數(shù)）隨機(jī)生成一個未訪問過的點(diǎn)作為下一個（因?yàn)橹辽倌阋ＷC可行吧）

6，標(biāo)記這個點(diǎn)被訪問過

}

修改信息素，修改方式為原來信息素+Q/這條路徑長度（Q為1個常數(shù)）

t++;

}

輸出最優(yōu)解。

［objc］ view plain copy#include 《stdio.h>

#include

#include

#include

#include

#define T 1000//最大迭代次數(shù)

#define n 1000//螞蟻數(shù)量

#define cities 10//城市數(shù)量

#define bugp 0.9//每一次選擇操作的出錯概率

#define alpha 0.1//每一次信息素的消失速率

#define Q 1

int start;

int biggest［cities］，biggestsum;//儲存信息素最多時所對應(yīng)的點(diǎn)（畢竟信息素最大值所對應(yīng)的邊不止一條，biggest記錄下那些邊的對應(yīng)的終點(diǎn)，biggestsum為biggest的元素個數(shù)）

int distance［cities］［cities］;//城市的距離矩陣

double phe［cities］［cities］;//邊所對應(yīng)的信息素濃度（之所以選擇邊是因?yàn)辄c(diǎn)容易受到周圍優(yōu)秀的點(diǎn)的影響）

int ant;//螞蟻當(dāng)前所在點(diǎn)

int bugsum，bugTry［cities］;//出錯時可供選擇的城市數(shù)量和城市下標(biāo)

int visit［cities］;//用來標(biāo)記城市是否已經(jīng)經(jīng)過

int path［n］［cities+1］;//記錄每一個螞蟻所走過的城市

void initdistance（）

{

int i，j;

memset（distance，0，sizeof（distance））;

srand（time（NULL））;

for （i=0;i

for （j=i+1;j

{

distance［i］［j］=rand（）%100;

distance［j］［i］=distance［i］［j］;

}

printf（“城市的距離矩陣如下：\n”）;

for （i=0;i

{

for （j=0;j

printf（“%4d”，distance［i］［j］）;

printf（“\n”）;

}

}

int main（）

{

int i，j，k，p，t，n1，n2，r;

double d;

double max;//記錄下最大信息素濃度

double sumdistance;

initdistance（）;//初始化城市矩陣

t=0;

for （i=0;i

for （j=0;j

phe［i］［j］=1;//初始化每一條邊的信息素濃度

srand（time（NULL））;

for （i=0;i

path［i］［0］=rand（）%cities;//每一個螞蟻隨機(jī)在起點(diǎn)

while（t《T）

{

for （i=0;i

for （j=0;j

phe［i］［j］=phe［i］［j］*alpha;//每一次信息素逐漸消逝

for （i=0;i

{

start=path［i］［0］;//記錄下起點(diǎn)

memset（visit，0，sizeof（visit））;//清零標(biāo)記數(shù)組

visit［start］=1;

ant=start;

for （j=1;j

{

bugsum=biggestsum=max=0;

for （p=0;p

if （！visit［p］）

max=max>phe［ant］［p］？max:phe［ant］［p］;//尋找周圍最大的信息素的那條邊（其實(shí)是為了找到那個p點(diǎn)）

for （p=0;p

{

if （（max==phe［ant］［p］）&&（！visit［p］））

biggest［biggestsum++］=p;//記錄下信息素濃度最大的點(diǎn)（注意一般不止一個點(diǎn)）

}

for （p=0;p

if （！visit［p］）

bugTry［bugsum++］=p;//記錄下總共可供選擇的點(diǎn)

d=rand（）%100;

d=d/100;

if （d

ant=biggest［rand（）%biggestsum］;//選擇信息素最大的點(diǎn)

else//如果螞蟻選擇錯誤

ant=bugTry［rand（）%bugsum］;//只選擇成立的點(diǎn)（未必最優(yōu)）

visit［ant］=1;

path［i］［j］=ant;

}

}

//上面是每一只螞蟻的選擇，而一次全部選擇后，更新信息素

for （i=0;i

{

sumdistance=0;

for （j=1;j

{

n1=path［i］［j-1］;

n2=path［i］［j］;

sumdistance=sumdistance+distance［n1］［n2］;

}

n1=path［i］［cities-1］;

n2=path［i］［0］;

sumdistance=sumdistance+distance［n1］［n2］;//注意要回到起點(diǎn)

for （j=1;j

{

n1=path［i］［j-1］;

n2=path［i］［j］;

phe［n1］［n2］=phe［n1］［n2］+Q/sumdistance;//更新信息素，注意因?yàn)樾畔⑺剡€要再次遞減，所以就好比2進(jìn)制的權(quán)，越靠近話語權(quán)越重

}

n1=path［i］［cities-1］;

n2=path［i］［0］;

phe［n1］［n2］=phe［n1］［n2］+Q/sumdistance;

}

t++;//這樣迭代次數(shù)+1

}

max=999999;

for （i=0;i

{

sumdistance=0;

for （j=1;j

{

n1=path［i］［j-1］;

n2=path［i］［j］;

sumdistance=sumdistance+distance［n1］［n2］;

}

n1=path［i］［cities-1］;

n2=path［i］［0］;

sumdistance=sumdistance+distance［n1］［n2］;

if （sumdistance

{

max=sumdistance;

r=i;

}

}

printf（“最短路徑為：%.4f\n”，max）;

printf（“路徑為：\n”）;

for （i=0;i

printf（“%d ”，path［r］［i］）;//第r個螞蟻是最優(yōu)的

printf（“%d\n”，path［r］［0］）;

return 0;

}

總結(jié)：蟻群算法的關(guān)鍵在于信息素，而影響信息素的因素只有兩個：螞蟻選擇這條路徑的數(shù)量和時間的流逝（越往后，越是之前的信息素影響就越弱）。

同時注意雖然現(xiàn)實(shí)中螞蟻是同時去找食物，但是在蟻群算法中螞蟻出發(fā)卻是有先后之分的，而所有的螞蟻?zhàn)咄昃鸵暈橐淮蔚?br /> ?