1、學 號： 能力拓展訓練題 目基于蟻群算法解決tsp問題學 院計算機科學與技術學院專 業班 級姓 名指導教師20112012學年 第2學期目錄一.介紹- 2 -二 詳細設計說明- 3 -2.1模塊描述- 3 -2.2性能- 3 -2.3算法- 3 -2.4流程邏輯-7-2.5接口- 8 -三 程序- 9 -四.結果- 20 -五.程序設計心得與體會- 21 -六.參考文獻- 22 -基于蟻群算法解決tsp問題摘 要：TSP問題是典型的NP - hard組合優化問題,蟻群算法是一種求解此類問題的優化算法,通過模擬螞蟻覓食行為來解決NP問題。文章使用蟻群算法求解TSP問題,并結合TSP問題的特點選擇

2、了一種合適的蟻群更新策略。關鍵詞：TSP問題,蟻群算法,群集智能,信息素一、介紹 旅行商問題( Traveling Salesman Problem, 簡稱TSP)是一個經典的NP難題,也是組合優化中研究最多的問題之一,它解決如何找到一條從一個城市出發經過若干個城市后又返回原城市的最短路徑。城市管道鋪設優化、物流業的車輛調度、制造業中的切割路徑優化等,現實生活中的優化問題都可以歸結為TSP問題進行求解。尋找一種有效的解決該問題的算法,具有重要的現實意義。蟻群算法是DorigoM等提出的,該算法采用了分布式并行計算機制,易于與其他方法結合,而且具有強的魯棒性,是求解TSP問題的一種理想方法。算法

3、的主要思想為:模擬螞蟻覓食行為。螞蟻在運行過程中會釋放一種特殊的分泌物- 信息素來尋找路徑。信息素會隨著時間消減,后面的螞蟻選擇信息素多的路徑,這樣便形成了一個正反饋機制。在整個尋徑過程中,雖然單只螞蟻的選擇能力有限,但它們的行為具有非常高的自組織性,相互之間交換路徑,最終尋找到最優路徑。二、詳細設計說明2.1模塊描述本程序共有void addcity(); void Clear(); void UpdateResult(); void move(); void move2last(); void shucout()；void project:initmap()；void project:Ge

4、tAnt()；void project:StartSearch() ；void project:UpdateTrial() 。子程序模塊和int main()一個主程序。void shucout()顯示歡迎信息模塊 void ant:move2last() 只剩下一個城市沒走過時才調用，直接移動到最后一個城市void ant:Clear() 清空數據，螞蟻周游完各個城市后，要重新開始周游各個城市時調用 void ant:addcity(int city) 增加一個城市到走過的城市數組中，并改變沒走過的城市數組中的標志 void ant:UpdateResult() 計算周游完城市后，走過的路徑

5、長度 void ant:move() 移動到下一個城市 void project:initmap() 初始化 void project:GetAnt() 初始化隨機種子 void project:StartSearch() 開始尋找最好的解決方法void project:UpdateTrial() 更新環境信息素 ，每只螞蟻周游完城市后才更新 2.2性能本程序按原理來說迭代次數越大，程序得出的結果越精確，但當數值超過1000以后，結果基本不變。要求城市數量 / 螞蟻數量 = 1.5左右 dbMin=100000000.0; 疊迭中的最小路徑長度。2.3算法本程序是基于蟻群算法求解問題，設為城市

6、，之間的幾何距離，。設 表示時刻位于城市的螞蟻的個數，螞蟻總數，表示時刻在 連線上殘留的信息量，初始時刻各條路徑上的信息量為（為常數）。用參數表示信息量的保留度，則經過個時刻后，路徑 上的信息量根據下式作調整： 表示第只螞蟻在本次循環中留在路徑 上的信息量，表示本次循環所有經過的螞蟻留在 上的信息量。 定義。螞蟻（，）在運動過程中，表示在時刻螞蟻由位置轉移到位置的概率： 我們用tabuN_CITY_COUNT記錄螞蟻目前已經走過的城市集合，AllowedCityN_CITY_COUNT表示螞蟻下一步允許選擇的城市集合，它等于全部的城市集合除去第只螞蟻已走過的集合tabuN_CITY_COUNT

7、。 定義為第只螞蟻在本次循環中走過的路徑和。 用蟻群算法解決問題是一個遞推過程 ，當時，將螞蟻放在各城市，設定每條路徑上的信息量初值，每只螞蟻根據公式決定的概率從城市到城市。表示曾經有多少螞蟻經過路徑；說明較近的城市有更大的可能性被選中。用來控制兩者對螞蟻選擇的影響力程度。經過一個循環后，根據公式；計算更新每條路徑的信息量。將所有的復原，最后求出本次循環的最短路徑。這個過程不斷重復，直到所有的螞蟻都選擇同樣的路徑，或者循環次數達到預先設定的最高次數。解決個城市的問題算法設計如下：初始化：設定，循環計數器，對每條路徑設定初始信息量,將只螞蟻放在個城市上（為了使問題簡化，設定。設定集合的索引，對從

8、到，把第只螞蟻放在起始位置，對應的設定集合重復下面的步驟，直到集合滿為止（這一步將重復次）：設定；對從到，根據公式確定的概率，選擇下一步移動的目標城市在時間時，第只螞蟻所在的城市是;將第只螞蟻移到城市；把加入到集合中。對從到：將第只螞蟻從移動到；計算第只螞蟻所走過的路程和，并更新最小路徑；對每條路徑：； 對每條路徑根據計算；設定；設定；對每條路徑，設定。如果，則清空所有的集合轉到第二步；否則，得出最短的路徑。在這兒我們用的是算法，這種算法，每當結束一個循環后，根據公式 計算。2.4流程邏輯開始初始化設定集合,對每只螞蟻=計算螞蟻所走過的路程和更新最小路徑對每條路徑計算設定acbacbNY清空所

9、有的集合得出最短路徑N集合滿Y結束圖12.5接口程序中的子函數：void addcity(int city); void Clear(); void UpdateResult(); void move(); void move2last(); void shucout();void UpdateTrial(); void initmap(); void GetAnt(); void StartSearch(); 三程序#include <iostream>#include <math.h> #include <time.h> using namespace

10、std; const int N_ANT_COUNT = 34; /螞蟻數量，一般取值原則為：城市數量 / 螞蟻數量 = 1.5左右 const int N_CITY_COUNT = 51; /城市數量 int N_IT_COUNT; /= 5000; /迭代次數，就是搜索次數 const double DB_Q=100; /總的信息素 const double DB_ALPHA=1; /信息素重要程度 const double DB_BETA=3; /這個數越大，則螞蟻往信息素大的地方走的概率就越大 const double DB_ROU=0.5; /環境信息素揮發速度 int bestto

11、urN_CITY_COUNT;/最佳路徑列表 /獲得指定范圍內的一個隨機數 double rnd(int low,double uper) double p=(rand()/(double)RAND_MAX)*(uper)-(low)+(low); return (p); ; /獲得指定上限范圍內的一個隨機數 int rnd(int uper) return (rand()%uper); ; /tsp地圖信息，包含了信息素，城市距離，和信息素變化矩陣 class GInfo public: double m_dDeltTrialN_CITY_COUNTN_CITY_COUNT; /臨時保存信息

12、素，更新環境信息素的時候使用，每只螞蟻周游完各個城市后開始計算 double m_dTrialN_CITY_COUNTN_CITY_COUNT; /城市間的信息素，就是環境信息素 double distanceN_CITY_COUNTN_CITY_COUNT; /城市間距離 ; GInfo Map; /定義螞蟻類 class ant private: int ChooseNextCity(); /選擇下一個城市 double probN_CITY_COUNT; /臨時變量數組，選擇下一個城市的時候，保存各個城市被選中的概率值 int m_nCityCount; /記錄螞蟻已經走過的城市數目 i

13、nt AllowedCityN_CITY_COUNT;/沒有走過的城市，數組索引對應城市編號 public: double m_dLength; double m_dShortest; int tabuN_CITY_COUNT; /記錄走過的城市，里面存的是城市的編號，數組索引表示走的順序。 public: ant(); void addcity(int city); void Clear(); void UpdateResult(); void move(); void move2last(); void shucout(); /只剩下一個城市沒走過時才調用，直接移動到最后一個城市 void

14、 ant:move2last() for(int i=0;i<N_CITY_COUNT;i+) if (AllowedCityi=1) addcity(i); break; /清空數據，螞蟻周游完各個城市后，要重新開始周游各個城市時調用 void ant:Clear() m_dLength=0; for(int i=0; i<N_CITY_COUNT;i+) probi=0; AllowedCityi=1; i=tabuN_CITY_COUNT-1; /用最后一個城市作為出發城市 m_nCityCount=0; addcity(i); /初始化 ant:ant() m_dLengt

15、h=m_dShortest=0; m_nCityCount=0; for(int i=0;i<N_CITY_COUNT;i+) AllowedCityi=1; probi=0; /增加一個城市到走過的城市數組中，并改變沒走過的城市數組中的標志 void ant:addcity(int city) /add city to tabu; tabum_nCityCount=city; m_nCityCount+; AllowedCitycity=0; int ant:ChooseNextCity() /更新概率的路徑選擇 /選擇一條路徑,從 tabum_nCityCount-1到下一個 int

16、 j=10000; double temp=0.0; int curCity=tabum_nCityCount-1; /當前走到那個城市了 /先計算當前城市和沒有走過的城市，兩兩之間的信息素的總和 for (int i=0;i<N_CITY_COUNT;i+) if (AllowedCityi = 1) temp=temp+pow(1.0/Map.distancecurCityi),DB_BETA)*pow(Map.m_dTrialcurCityi),DB_ALPHA); /計算沒有走過的城市被選中的概率 double sel=0; for (i=0;i<N_CITY_COUNT;

17、i+) if (AllowedCityi = 1) probi=pow(1.0/Map.distancecurCityi),DB_BETA)*pow(Map.m_dTrialcurCityi),DB_ALPHA)/temp; sel+=probi; else probi=0; /下面的操作實際上就是遺傳算法中的輪盤選擇 double mRate=rnd(0,sel); double mSelect=0; for ( i=0;i<N_CITY_COUNT;i+) if (AllowedCityi = 1) mSelect+=probi ; if (mSelect>=mRate) j=

18、i; break; /這種情況只有在temp=0.0的時候才會出現 if (j = 10000) for (i=0;i<N_CITY_COUNT;i+) if (AllowedCityi = 1) j=i; break; return j; /計算周游完城市后，走過的路徑長度 void ant:UpdateResult() / 修正旅行距離for(int i=0;i<N_CITY_COUNT-1;i+) m_dLength+=Map.distancetabuitabui+1; m_dLength+=Map.distancetabuN_CITY_COUNT-1tabu0; /最后城市

19、和開始城市間的距離 /移動到下一個城市 void ant:move() /the ant move to next town and add town ID to tabu. int n=ChooseNextCity(); addcity(n); class project public: double m_dLength; ant antsN_ANT_COUNT; public: project(); void UpdateTrial(); void initmap(); void GetAnt(); void StartSearch(); ;/更新環境信息素 /這里采用的是 ANT-CYC

20、LE 模式，即每只螞蟻周游完城市后才更新 void project:UpdateTrial() /calculate the changes of trial information int m=0; int n=0; for(int i=0;i<N_ANT_COUNT;i+) /計算每只螞蟻在兩兩城市間留下的信息素，螞蟻走過的路徑越短，留下的信息素數值越大 for (int j=0;j<N_CITY_COUNT-1;j+) /計算兩兩城市間的信息素 m=antsi.tabuj; n =antsi.tabuj+1; Map.m_dDeltTrialmn+=DB_Q/antsi.m_

21、dLength; Map.m_dDeltTrialnm+=DB_Q/antsi.m_dLength; /最后城市到開始城市間的信息素 m=antsi.tabuN_CITY_COUNT-1; n =antsi.tabu0; Map.m_dDeltTrialmn+=DB_Q/antsi.m_dLength; Map.m_dDeltTrialnm+=DB_Q/antsi.m_dLength; /最新的環境信息素 = 消失掉的信息素 + 新留下的信息素 for (int a=0;a<N_CITY_COUNT;a+) for (int j=0;j<N_CITY_COUNT;j+) Map.m

22、_dTrialaj=(DB_ROU*Map.m_dTrialaj+Map.m_dDeltTrialaj ); Map.m_dDeltTrialaj=0; /初始化 void project:initmap() for(int i=0;i<N_CITY_COUNT;i+) for (int j=0;j<N_CITY_COUNT;j+) Map.m_dTrialij=1; Map.m_dDeltTrialij=0; project:project() /initial map initmap(); m_dLength=10e9; struct city int num; int x;

23、int y; ccN_CITY_COUNT; /城市坐標數據來自國際通用的數據 eil51.tsp int x_Ary51= 37,49,52,20,40,21,17,31,52,51, 42,31,5,12,36,52,27,17,13,57, 62,42,16,8,7,27,30,43,58,58, 37,38,46,61,62,63,32,45,59,5, 10,21,5,30,39,32,25,25,48,56, 30 ; int y_Ary51= 52,49,64,26,30,47,63,62,33,21, 41,32,25,42,16,41,23,33,13,58, 42,57,5

24、7,52,38,68,48,67,48,27, 69,46,10,33,63,69,22,35,15,6, 17,10,64,15,10,39,32,55,28,37, 40 ; for (int i=0;i<N_CITY_COUNT;i+) cci.x=x_Aryi; cci.y=y_Aryi; cci.num=i; /計算兩兩城市間距離，需要進行四舍五入取整 /eil51.tsp的最短路徑426，是按四舍五入取整后的距離算出來的。 for(int b=0;b<N_CITY_COUNT;b+) for (int j=0;j<N_CITY_COUNT;j+) Map.dist

25、ancebj=(int)(sqrt(pow(ccb.x-ccj.x),2)+pow(ccb.y-ccj.y),2)+0.5); void project:GetAnt() /初始化隨機種子 srand(unsigned)time(NULL); /為每只螞蟻隨機分配一個出發城市 int city=0; for (int i=0;i<N_ANT_COUNT;i+) city=rnd(N_CITY_COUNT); antsi.addcity(city); void project:StartSearch() /begin to find best solution int max=0;/eve

26、ry ant tours times double temp; int temptourN_CITY_COUNT; double dbMin=0.0; while (max < N_IT_COUNT) dbMin=100000000.0; /本次疊迭中的最小路徑長度 for(int j=0;j<N_ANT_COUNT;j+) for (int i=0;i<N_CITY_COUNT-1;i+) antsj.move(); for(int c=0;c<N_ANT_COUNT;c+) antsc.move2last(); antsc.UpdateResult(); /計算路徑

27、總長度 /find out the best solution of the step and put it into temp temp=ants0.m_dLength; for (int t=0;t<N_CITY_COUNT;t+) temptourt=ants0.tabut; for(int d=0;d<N_ANT_COUNT;d+) if (temp>antsd.m_dLength) temp=antsd.m_dLength; for (int t=0;t<N_CITY_COUNT;t+) temptourt=antsd.tabut; if (dbMin>

28、antsj.m_dLength) dbMin=antsj.m_dLength; if (temp<m_dLength) m_dLength=temp; for (int t=0;t<N_CITY_COUNT;t+) besttourt=temptourt; printf("%d : %.0fn",max,m_dLength); UpdateTrial(); /全部螞蟻遍歷各個城市后，更新環境信息素 for(int e=0;e<N_ANT_COUNT;e+) /再搜索一次 antse.Clear(); max+; printf("The short

29、est toure is : %fn",m_dLength); for (int t=0;t<N_CITY_COUNT;t+) printf(" %d ",besttourt); void shucout()cout<<"*本程序是利用蟻群算法求解TSP問題，即最旅游城市中的最段距離和行走路線*"<<endl<<endl<<endl<<endl<<endl<<endl<<endl;cout<<"51個城市X軸坐標為：&qu

30、ot;<<endl;cout<<"37,49,52,20,40,21,17,31,52,51, "<<endl;cout<<"42,31,5,12,36,52,27,17,13,57, "<<endl;cout<<"62,42,16,8,7,27,30,43,58,58, "<<endl;cout<<"37,38,46,61,62,63,32,45,59,5,"<<endl;cout<<"10,21,5,30,39,32,25,25,48,56, "<<endl;cout<<"30 "<<endl;cout<<"城市Y軸坐標為："<<endl;cout<<"52,49,64,26,30,47,63,62,33,21"<<endl;cout<<"41,32,