電子發燒友App
控制蟻群算法走向的關鍵是信息素，信息素類似遺傳算法的適應性函數，類似退火算法的評價函數，影響著其中一只螞蟻的下一步的選擇。
螞蟻：類似遺傳算法的染色體，就是一條解，在tsp問題中螞蟻的路徑就是tsp的解。
信息素：評價函數，與路徑成反比
螞蟻數量：一次迭代有多少只螞蟻在跑（注意不是一起跑，而是先后放上一只螞蟻）
迭代次數T：所有螞蟻跑完視為一次迭代周期。
程序流程：
1，隨機生成距離矩陣
進入循環while（t
{
2，信息素遞減（只有較近的信息素才能影響這一步）
3，對于每一只螞蟻，隨機生成起點，標記起點為訪問過
進入循環（尋找城市數量-1次）（起點已經有了）
{
4，尋找周圍城市的最大信息素
5，隨機生成0~1的數如果小于bugp（螞蟻正常選擇）則從最大信息素城市中找一個作為下一個
否則（螞蟻犯錯誤了，有木有感覺像退火算法里的允許犯錯的那個函數）隨機生成一個未訪問過的點作為下一個（因為至少你要保證可行吧）
6，標記這個點被訪問過
}
修改信息素，修改方式為原來信息素+Q/這條路徑長度（Q為1個常數）
t++;
}
輸出最優解。
［objc］ view plain copy#include 《stdio.h>
#include
#include
#include
#include
#define T 1000//最大迭代次數
#define n 1000//螞蟻數量
#define cities 10//城市數量
#define bugp 0.9//每一次選擇操作的出錯概率
#define alpha 0.1//每一次信息素的消失速率
#define Q 1
int start;
int biggest［cities］，biggestsum;//儲存信息素最多時所對應的點（畢竟信息素最大值所對應的邊不止一條，biggest記錄下那些邊的對應的終點，biggestsum為biggest的元素個數）
int distance［cities］［cities］;//城市的距離矩陣
double phe［cities］［cities］;//邊所對應的信息素濃度（之所以選擇邊是因為點容易受到周圍優秀的點的影響）
int ant;//螞蟻當前所在點
int bugsum，bugTry［cities］;//出錯時可供選擇的城市數量和城市下標
int visit［cities］;//用來標記城市是否已經經過
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;//每一個螞蟻隨機在起點
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］;//記錄下起點
memset（visit，0，sizeof（visit））;//清零標記數組
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］;//尋找周圍最大的信息素的那條邊（其實是為了找到那個p點）
for （p=0;p
{
if （（max==phe［ant］［p］）&&（！visit［p］））
biggest［biggestsum++］=p;//記錄下信息素濃度最大的點（注意一般不止一個點）
}
for （p=0;p
if （！visit［p］）
bugTry［bugsum++］=p;//記錄下總共可供選擇的點
d=rand（）%100;
d=d/100;
if （d
ant=biggest［rand（）%biggestsum］;//選擇信息素最大的點
else//如果螞蟻選擇錯誤
ant=bugTry［rand（）%bugsum］;//只選擇成立的點（未必最優）
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］;//注意要回到起點
for （j=1;j
{
n1=path［i］［j-1］;
n2=path［i］［j］;
phe［n1］［n2］=phe［n1］［n2］+Q/sumdistance;//更新信息素，注意因為信息素還要再次遞減，所以就好比2進制的權，越靠近話語權越重
}
n1=path［i］［cities-1］;
n2=path［i］［0］;
phe［n1］［n2］=phe［n1］［n2］+Q/sumdistance;
}
t++;//這樣迭代次數+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個螞蟻是最優的
printf（“%d\n”，path［r］［0］）;
return 0;
}
總結：蟻群算法的關鍵在于信息素，而影響信息素的因素只有兩個：螞蟻選擇這條路徑的數量和時間的流逝（越往后，越是之前的信息素影響就越弱）。
同時注意雖然現實中螞蟻是同時去找食物，但是在蟻群算法中螞蟻出發卻是有先后之分的，而所有的螞蟻走完就視為一次迭代。
?
工商網監
評論