蟻群算法解決TSP問(wèn)題(共8頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上蟻群算法解決TSP問(wèn)題一、論述1、算法來(lái)源蟻群算法的基本原理來(lái)源于自然界螞蟻覓食的最短路徑原理，根據(jù)昆蟲(chóng)學(xué)家的觀察，發(fā)現(xiàn)自然界的螞蟻雖然視覺(jué)不發(fā)達(dá)，但它可以在沒(méi)有任何提示的情況下找到從食物源到巢穴的最短路徑，并且能在環(huán)境發(fā)生變化（如原有路徑上有了障礙物）后，自適應(yīng)地搜索新的最佳路徑。2、單個(gè)螞蟻尋找路徑正反饋：?jiǎn)蝹€(gè)的螞蟻為了避免自己迷路，它在爬行時(shí)，同時(shí)也會(huì)釋放一種特殊的分泌物信息素（Pheromone），而且它也能覺(jué)察到一定范圍內(nèi)的其它螞蟻所分泌的信息素，并由此影響它自己的行為。當(dāng)一條路上的信息素越來(lái)越多（當(dāng)然，隨著時(shí)間的推移會(huì)逐漸減弱），后來(lái)的螞蟻選擇這條路徑的概

2、率也就越來(lái)越大，從而進(jìn)一步增加了該路徑的信息素濃度，這種選擇過(guò)程稱(chēng)為螞蟻的自催化過(guò)程。多樣性：同時(shí)為了保證螞蟻在覓食的時(shí)候不至走進(jìn)死胡同而無(wú)限循環(huán)，螞蟻在尋找路徑的過(guò)程中，需要有一定的隨機(jī)性，雖然在覓食的過(guò)程中會(huì)根據(jù)信息素的濃度去覓食，但是有時(shí)候也有判斷不準(zhǔn)，環(huán)境影響等其他很多種情況，還有最終要的一點(diǎn)就是當(dāng)前信息素濃度大的路徑并不一定是最短的路徑，需要不斷的去修正，多樣性保證了系統(tǒng)的創(chuàng)新能力。正是這兩點(diǎn)小心翼翼的巧妙結(jié)合才使得蟻群的智能行為涌現(xiàn)出來(lái)。3、具體實(shí)現(xiàn)需要解決的兩個(gè)首要問(wèn)題（1）如何實(shí)現(xiàn)單個(gè)螞蟻尋路的過(guò)程（2）如何實(shí)現(xiàn)信息素濃度的更新二、具體實(shí)現(xiàn)代碼如下所示：cpp view pla

3、in copy 在CODE上查看代碼片派生到我的代碼片#include <iostream> #include <algorithm> #include <cstring> #include <windows.h> #include <stdio.h> #include <stdlib.h> #include <math.h> #include <time.h> using namespace std; /* int CityPos102= 87,7,91,38,83,46,71,44,64,60,

4、68,58,83,69, 87,76,74,78,71,71 ; /10個(gè)城市的坐標(biāo)*/ unsigned seed=(unsigned)time(0);/原型：void srand(unsigned seed); /30個(gè)城市的坐標(biāo) int CityPos302=87,7,91,38,83,46,71,44,64,60,68,58,83,69,87,76,74,78,71,71,58,69,54,62,51,67,37,84,41,94,2,99,7,64,22,60,25,62,18,54,4,50,13,40,18,40,24,42,25,38,41,26,45,21,44,35,58,

5、35,62,32; #define CITY_NUM 30 /城市數(shù)量 #define ANT_NUM 30 /蟻群數(shù)量 #define TMAC 1000 /迭代最大次數(shù) #define ROU 0.5 /誤差大小 #define ALPHA 1 / 信息素重要程度的參數(shù) #define BETA 4 / 啟發(fā)式因子重要程度的參數(shù) #define Q 100 /信息素殘留參數(shù) const int maxn = 100; double dismaxnmaxn; /距離 double infomaxnmaxn; /信息素矩陣 double ECITY_NUMCITY_NUM; /啟發(fā)因子矩陣 i

6、nt visCITY_NUMCITY_NUM; double Bestlength; double ansCITY_NUM; const double mmax = 10e9; /返回指定范圍內(nèi)的隨機(jī)整數(shù) int rnd(int nLow,int nUpper) return nLow+(nUpper-nLow)*rand()/(RAND_MAX+1); /返回指定范圍內(nèi)的隨機(jī)浮點(diǎn)數(shù) double rnd(double dbLow,double dbUpper) double dbTemp=rand()/(double)RAND_MAX+1.0); return dbLow+dbTemp*(d

7、bUpper-dbLow); /返回浮點(diǎn)數(shù)四舍五入取整后的浮點(diǎn)數(shù) double ROUND(double dbA) return (double)(int)(dbA+0.5); struct Ant int PathCITY_NUM; /螞蟻?zhàn)叩穆窂?double length; /路徑總長(zhǎng)度 int visCITY_NUM; /走過(guò)城市標(biāo)記 int cur_cityno; /當(dāng)前城市 int moved_cnt; /已走的數(shù)量 /初始化 void Init() memset(vis, 0, sizeof(vis); length = 0; cur_cityno = rnd(0, CITY_N

8、UM);/隨機(jī)選擇一個(gè)出發(fā)城市 Path0 = cur_cityno; viscur_cityno = 1; moved_cnt = 1; /printf("Init %d n", cur_cityno); /選擇下一個(gè)城市 /返回值 為城市編號(hào) int chooseNextCity() int nSelectedCity=-1; /返回結(jié)果，先暫時(shí)把其設(shè)置為-1 /計(jì)算當(dāng)前城市和沒(méi)去過(guò)的城市之間的信息素總和 double dbTotal=0.0; double probCITY_NUM; /保存各個(gè)城市被選中的概率 for(int i = 0; i < CITY_N

9、UM; i+) if (!visi) probi=pow(infocur_citynoi,ALPHA) *pow(1.0/discur_citynoi, BETA); dbTotal += probi; else probi = 0; /進(jìn)行輪盤(pán)選擇 double dbTemp=0.0; if (dbTotal > 0.0) /總的信息素值大于0 dbTemp = rnd(0.0, dbTotal); for (int i = 0; i < CITY_NUM; i+) if (!visi) dbTemp -= probi; if (dbTemp < 0.0) nSelecte

10、dCity = i; break; /如果城市間的信息素非常小 ( 小到比double能夠表示的最小的數(shù)字還要小 ) /出現(xiàn)這種情況，就把第一個(gè)沒(méi)去過(guò)的城市作為返回結(jié)果 if (nSelectedCity = -1) for (int i=0; i<CITY_NUM; i+) if (!visi) /城市沒(méi)去過(guò) nSelectedCity=i; break; return nSelectedCity; /螞蟻在城市間移動(dòng) void Move() int nCityno = chooseNextCity();/選擇下一個(gè)城市 Pathmoved_cnt = nCityno;/保存螞蟻?zhàn)叩穆?/p>

11、徑 visnCityno = 1;/把這個(gè)城市設(shè)置成已經(jīng)去過(guò) cur_cityno = nCityno; /更新已走路徑長(zhǎng)度 length += disPathmoved_cnt-1Pathmoved_cnt; moved_cnt+; /螞蟻進(jìn)行搜索一次 void Search() Init(); /如果螞蟻去過(guò)的城市數(shù)量小于城市數(shù)量，就繼續(xù)移動(dòng) while(moved_cnt < CITY_NUM) Move(); length += disPathCITY_NUM-1Path0; ; struct TSP Ant antsANT_NUM; /定義一群螞蟻 Ant ant_best;

12、/保存最好結(jié)果的螞蟻 void Init() /初始化為最大值 ant_best.length = mmax; puts("al dis"); /計(jì)算兩兩城市間距離 for (int i = 0; i < CITY_NUM; i+) for (int j = 0; j < CITY_NUM; j+) double temp1=CityPosj0-CityPosi0; double temp2=CityPosj1-CityPosi1; disij = sqrt(temp1*temp1+temp2*temp2); /初始化環(huán)境信息素 puts("init

13、info"); for (int i=0; i<CITY_NUM; i+) for (int j=0; j<CITY_NUM; j+) infoij=1.0; /更新信息素,當(dāng)前每條路上的信息素等于過(guò)去保留的信息素 /加上每個(gè)螞蟻這次走過(guò)去剩下的信息素 void Updateinfo() /puts("update info"); double tmpinfoCITY_NUMCITY_NUM; memset(tmpinfo, 0, sizeof(tmpinfo); int m = 0; int n = 0; /遍歷每只螞蟻 for (int i = 0

14、; i < ANT_NUM; i+) /puts("*"); / for (int j = 0; j < CITY_NUM; j+) / printf("%d ", antsi.Pathj); / /puts(""); for (int j = 1; j < CITY_NUM; j+) m = antsi.Pathj; n = antsi.Pathj-1; /printf("%d %dn", m, n); tmpinfonm = tmpinfonm+Q/antsi.length; tmpinfom

15、n = tmpinfonm; /最后城市和開(kāi)始城市之間的信息素 n = antsi.Path0; tmpinfonm = tmpinfonm+Q/antsi.length; tmpinfomn = tmpinfonm; /更新環(huán)境信息素 for (int i = 0; i < CITY_NUM; i+) for (int j = 0; j < CITY_NUM; j+) /最新的環(huán)境信息素 = 留存的信息素 + 新留下的信息素 infoij = infoij*ROU + tmpinfoij; /尋找路徑，迭代TMAC次 void Search() for (int i = 0; i

16、 < TMAC; i+) printf("current iteration times %dn", i); for (int j = 0; j < ANT_NUM; j+) antsj.Search(); /保存最佳結(jié)果 for (int j = 0; j < ANT_NUM; j+) if (ant_best.length > antsj.length) ant_best = /更新環(huán)境信息素 Updateinfo(); printf("current minimum length %lfn", ant_best.length

17、); ; int main() /freopen("output.txt", "w", stdout); srand(seed); TSP tsp; /初始化蟻群 tsp.Init(); /開(kāi)始查找 tsp.Search(); puts("The Minimum length route is :n"); for (int i = 0; i < CITY_NUM; i+) if (i != 0 && i % 20 = 0) puts(""); printf("%d ", tsp.ant_best.Pathi); return 0; <strong> </strong> 運(yùn)算結(jié)果（1）選擇老師所給10個(gè)城市的數(shù)據(jù)，結(jié)果如下所示，經(jīng)過(guò)50次迭代就能得到最優(yōu)解，而且算法相當(dāng)穩(wěn)定，多次嘗試都是50次就能得到最優(yōu)解，相比于遺傳算法的500次迭代在時(shí)間上有了很大的改進(jìn)。（2）選擇老師所給的30個(gè)城市的數(shù)據(jù)，經(jīng)過(guò)1000次迭代過(guò)程能得到一個(gè)非常較優(yōu)的解，結(jié)果穩(wěn)