基于蟻群算法解決旅行商問題

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

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

3、的主要思想為:模擬螞蟻覓食行為。螞蟻在運(yùn)行過程中會(huì)釋放一種特殊的分泌物- 信息素來尋找路徑。信息素會(huì)隨著時(shí)間消減,后面的螞蟻選擇信息素多的路徑,這樣便形成了一個(gè)正反饋機(jī)制。在整個(gè)尋徑過程中,雖然單只螞蟻的選擇能力有限,但它們的行為具有非常高的自組織性,相互之間交換路徑,最終尋找到最優(yōu)路徑。二、詳細(xì)設(shè)計(jì)說明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()一個(gè)主程序。void shucout()顯示歡迎信息模塊 void ant:move2last() 只剩下一個(gè)城市沒走過時(shí)才調(diào)用，直接移動(dòng)到最后一個(gè)城市void ant:Clear() 清空數(shù)據(jù)，螞蟻周游完各個(gè)城市后，要重新開始周游各個(gè)城市時(shí)調(diào)用 void ant:addcity(int city) 增加一個(gè)城市到走過的城市數(shù)組中，并改變沒走過的城市數(shù)組中的標(biāo)志 void ant:UpdateResult() 計(jì)算周游完城市后，走過的路徑

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

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

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

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

9、有的集合得出最短路徑N集合滿Y結(jié)束圖12.5接口程序中的子函數(shù)：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; /螞蟻數(shù)量，一般取值原則為：城市數(shù)量 / 螞蟻數(shù)量 = 1.5左右 const int N_CITY_COUNT = 51; /城市數(shù)量 int N_IT_COUNT; /= 5000; /迭代次數(shù)，就是搜索次數(shù) const double DB_Q=100; /總的信息素 const double DB_ALPHA=1; /信息素重要程度 const double DB_BETA=3; /這個(gè)數(shù)越大，則螞蟻往信息素大的地方走的概率就越大 const double DB_ROU=0.5; /環(huán)境信息素?fù)]發(fā)速度 int bestto

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

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

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

14、 ant:move2last() for(int i=0;i<N_CITY_COUNT;i+) if (AllowedCityi=1) addcity(i); break; /清空數(shù)據(jù)，螞蟻周游完各個(gè)城市后，要重新開始周游各個(gè)城市時(shí)調(diào)用 void ant:Clear() m_dLength=0; for(int i=0; i<N_CITY_COUNT;i+) probi=0; AllowedCityi=1; i=tabuN_CITY_COUNT-1; /用最后一個(gè)城市作為出發(fā)城市 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; /增加一個(gè)城市到走過的城市數(shù)組中，并改變沒走過的城市數(shù)組中的標(biāo)志 void ant:addcity(int city) /add city to tabu; tabum_nCityCount=city; m_nCityCount+; AllowedCitycity=0; int ant:ChooseNextCity() /更新概率的路徑選擇 /選擇一條路徑,從 tabum_nCityCount-1到下一個(gè) int

16、 j=10000; double temp=0.0; int curCity=tabum_nCityCount-1; /當(dāng)前走到那個(gè)城市了 /先計(jì)算當(dāng)前城市和沒有走過的城市，兩兩之間的信息素的總和 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); /計(jì)算沒有走過的城市被選中的概率 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; /下面的操作實(shí)際上就是遺傳算法中的輪盤選擇 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的時(shí)候才會(huì)出現(xiàn) if (j = 10000) for (i=0;i<N_CITY_COUNT;i+) if (AllowedCityi = 1) j=i; break; return j; /計(jì)算周游完城市后，走過的路徑長(zhǎng)度 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、和開始城市間的距離 /移動(dòng)到下一個(gè)城市 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(); ;/更新環(huán)境信息素 /這里采用的是 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+) /計(jì)算每只螞蟻在兩兩城市間留下的信息素，螞蟻?zhàn)哌^的路徑越短，留下的信息素?cái)?shù)值越大 for (int j=0;j<N_CITY_COUNT-1;j+) /計(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; /最新的環(huán)境信息素 = 消失掉的信息素 + 新留下的信息素 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; /城市坐標(biāo)數(shù)據(jù)來自國(guó)際通用的數(shù)據(jù) 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; /計(jì)算兩兩城市間距離，需要進(jìn)行四舍五入取整 /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() /初始化隨機(jī)種子 srand(unsigned)time(NULL); /為每只螞蟻隨機(jī)分配一個(gè)出發(fā)城市 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; /本次疊迭中的最小路徑長(zhǎng)度 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(); /計(jì)算路徑

27、總長(zhǎng)度 /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(); /全部螞蟻遍歷各個(gè)城市后，更新環(huán)境信息素 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個(gè)城市X軸坐標(biāo)為：&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軸坐標(biāo)為："<<endl;cout<<"52,49,64,26,30,47,63,62,33,21"<<endl;cout<<"41,32,