電子發(fā)燒友App
控制蟻群算法走向的關(guān)鍵是信息素，信息素類似遺傳算法的適應(yīng)性函數(shù)，類似退火算法的評(píng)價(jià)函數(shù)，影響著其中一只螞蟻的下一步的選擇。
螞蟻：類似遺傳算法的染色體，就是一條解，在tsp問題中螞蟻的路徑就是tsp的解。
信息素：評(píng)價(jià)函數(shù)，與路徑成反比
螞蟻數(shù)量：一次迭代有多少只螞蟻在跑（注意不是一起跑，而是先后放上一只螞蟻）
迭代次數(shù)T：所有螞蟻跑完視為一次迭代周期。
程序流程：
1，隨機(jī)生成距離矩陣
進(jìn)入循環(huán)while（t
{
2，信息素遞減（只有較近的信息素才能影響這一步）
3，對(duì)于每一只螞蟻，隨機(jī)生成起點(diǎn)，標(biāo)記起點(diǎn)為訪問過
進(jìn)入循環(huán)（尋找城市數(shù)量-1次）（起點(diǎn)已經(jīng)有了）
{
4，尋找周圍城市的最大信息素
5，隨機(jī)生成0~1的數(shù)如果小于bugp（螞蟻正常選擇）則從最大信息素城市中找一個(gè)作為下一個(gè)
否則（螞蟻犯錯(cuò)誤了，有木有感覺像退火算法里的允許犯錯(cuò)的那個(gè)函數(shù)）隨機(jī)生成一個(gè)未訪問過的點(diǎn)作為下一個(gè)（因?yàn)橹辽倌阋ＷC可行吧）
6，標(biāo)記這個(gè)點(diǎn)被訪問過
}
修改信息素，修改方式為原來信息素+Q/這條路徑長(zhǎng)度（Q為1個(gè)常數(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//每一次選擇操作的出錯(cuò)概率
#define alpha 0.1//每一次信息素的消失速率
#define Q 1
int start;
int biggest［cities］，biggestsum;//儲(chǔ)存信息素最多時(shí)所對(duì)應(yīng)的點(diǎn)（畢竟信息素最大值所對(duì)應(yīng)的邊不止一條，biggest記錄下那些邊的對(duì)應(yīng)的終點(diǎn)，biggestsum為biggest的元素個(gè)數(shù)）
int distance［cities］［cities］;//城市的距離矩陣
double phe［cities］［cities］;//邊所對(duì)應(yīng)的信息素濃度（之所以選擇邊是因?yàn)辄c(diǎn)容易受到周圍優(yōu)秀的點(diǎn)的影響）
int ant;//螞蟻當(dāng)前所在點(diǎn)
int bugsum，bugTry［cities］;//出錯(cuò)時(shí)可供選擇的城市數(shù)量和城市下標(biāo)
int visit［cities］;//用來標(biāo)記城市是否已經(jīng)經(jīng)過
int path［n］［cities+1］;//記錄每一個(gè)螞蟻所走過的城市
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;//每一個(gè)螞蟻隨機(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í)是為了找到那個(gè)p點(diǎn)）
for （p=0;p
{
if （（max==phe［ant］［p］）&&（！visit［p］））
biggest［biggestsum++］=p;//記錄下信息素濃度最大的點(diǎn)（注意一般不止一個(gè)點(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//如果螞蟻選擇錯(cuò)誤
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個(gè)螞蟻是最優(yōu)的
printf（“%d\n”，path［r］［0］）;
return 0;
}
總結(jié)：蟻群算法的關(guān)鍵在于信息素，而影響信息素的因素只有兩個(gè)：螞蟻選擇這條路徑的數(shù)量和時(shí)間的流逝（越往后，越是之前的信息素影響就越弱）。
同時(shí)注意雖然現(xiàn)實(shí)中螞蟻是同時(shí)去找食物，但是在蟻群算法中螞蟻出發(fā)卻是有先后之分的，而所有的螞蟻?zhàn)咄昃鸵暈橐淮蔚?br /> ?
工商網(wǎng)監(jiān)
評(píng)論