【2019年整理】基于蟻群算法解決旅行商問題

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

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

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

4、): voidproject： :StartSearchO； voidproject： ：UpdateTrial ()。I 0 子程序模塊和int main()個主程序。void shucout ()顯示歡迎信息模塊voidant：:move21ast ()只剩下一個城市沒走過時才調(diào)用，直接移動到最后一個城市voidant：:Clear ()清空數(shù)據(jù)，螞蟻周游完各個城市后，要重新開始周游各個城市時調(diào)用voidant：dddcity(intcity)增加一個城市到走過的城市數(shù)組中，并改變沒走過的城市數(shù)組中的標(biāo)志void ant： ：UpdateResult()訃算周游完城市后，走過的路徑長度vo

5、id ant： :move()移動到下一個城市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;疊迭中的最小路徑長度。2.3算法本程序是基于蟻群算法求解TSP問題，設(shè)為城市j, _

6、/之間的兒何距M）表示/時刻位于城市，的螞蟻的個數(shù)，螞蟻總數(shù)加=，（/）表示/時/-I刻在i丿連線上殘留的信息量，初始時刻各條路徑上的信息量為可（0） = c （c為常數(shù)）。用參數(shù) P表示信息量的保留度，則經(jīng)過 H個時刻后，路徑 i丿上的信息量根據(jù)下式作調(diào)整：%(/M) = 0 (/) + %陽m吋表示第k只螞蟻在本次循環(huán)中留在路徑丿上的信息量，表示本次循環(huán)所有經(jīng)過的螞蟻留在i丿上的信息量。2 當(dāng)?shù)趉只螞蟻經(jīng)過i j時琲=乙0當(dāng)不經(jīng)過時定義 =1/切。螞蟻k （k=l, 2 ,，加）在運動過程中，尤表示在/時刻螞蟻k山位置i轉(zhuǎn)移到位置j的概率：T初WPij=7的0j e allowedk其他我

7、們用tabuN_CITY_COUNT記錄螞蟻k LI前已經(jīng)走過的城市集合，AllowedCity N_CITY_COUNT表示螞蟻k下一步允許選擇的城市集合，它等于全部的城市集 合除去第k只螞蟻已走過的集合tabuN_CITY.COUNTo 定義厶為第k只螞蟻在本次循環(huán)中走過的路徑和。 用蟻群算法解決TS P問題是一個遞推過程，當(dāng)=0時，將螞蟻放在各城市， 設(shè)定每條路徑上的信息量初值r(/(O) = C ,每只螞蟻根據(jù)公式?jīng)Q定的概率從城 市j到城市丿。(/)表示曾經(jīng)有多少螞蟻經(jīng)過路徑(/,;):伽說明較近的城市有 更大的可能性被選中。a.p用來控制兩者對螞蟻選擇的影響力程度。經(jīng)過一個 循環(huán)后，

8、根據(jù)公式；計算更新每條路徑的信息量 可。將所有的 皿“&伙=1,2,，加)復(fù)原，最后求出本次循環(huán)的最短路徑min厶*。這個過程不斷 重復(fù)，直到所有的螞蟻都選擇同樣的路徑，或者循環(huán)次數(shù)達(dá)到預(yù)先設(shè)定的最高 次數(shù)NC解決個城市的TS P問題算法設(shè)計如下：初始化：設(shè)定r = 0 ,循環(huán)計數(shù)器NC = O ,對每條路徑設(shè)定初始信息量 r,?(O) = C, Ar- = 0將加只螞蟻放在n個城市上(為了使問題簡化，設(shè)定m = n o(2)設(shè)定加“集合的索引5 = 1,對斤從1到加，把第k只螞蟻放在起始位置 ,對應(yīng)的設(shè)定集合重復(fù)下面的步驟，直到集合滿為止(這一步將重復(fù)“-1次)：設(shè)定$ = s + l ；對

9、k從1到加，根據(jù)公式確定的概率，選擇下一步移動的口標(biāo)城市J 在時間/時，第k只螞蟻所在的城市是i = tabuk(5-1);將第k只螞蟻移到城市八把j加入到集合tahuk (s)中。(4)對k從1到加：將第R只螞蟻從tabuk(”)移動到tabuk(1)；計算笫k只螞蟻所走過的路程和厶，并更新最小路徑min Lk ；二當(dāng)?shù)趉只螞蟻經(jīng)過i j時對每條路徑(/,;): Ar* = Lr0當(dāng)不經(jīng)過時=+時；(5) 對每條路徑(/, J)根據(jù)T-.(/ + ) = 0竊(/) + 兀計算Tjj (r + /?)；設(shè)定/=?+“；設(shè)定 NC = NC + 1；對每條路徑設(shè)定勺=0。(6) 如果 NCvN

10、Cmax，則清空所有的集合t tabu轉(zhuǎn)到第二步；否則，得出最短的路徑。在這兒我們用的是ant-cycle算法，這種算法，每當(dāng)結(jié)束一個循環(huán)后，根據(jù)公式計算廿。2.4流程邏輯b0Y清空所有的集合 tabu得出最短路徑Y(jié)圖12.5 接口程序中的子函數(shù)：void addcity(int city);void Clear ();void UpdateResult();void move ();void move21ast(); void shucout ();void UpdateTrial();void initmapO ;void GetAnt ();void StartSearch();三. 程

11、序include include Sinclude using namespace std;const int N.ANT.COUNT = 34; /螞蟻數(shù)雖，一般取值原則為：城市數(shù)址/螞蟻數(shù)雖=15左右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; /這個數(shù)越大.則螞蟻往信息素大的地方走的概率就越大const double DB_

12、ROU=0. 5: /環(huán)境信息素?fù)]發(fā)速度int besttour N.CITY.COUNT ;/最佳路徑列表/獲得抬定范困內(nèi)的一個隨機(jī)數(shù)double rnd(int low, double uper)double p=(rand()/(double)RAND_MAX)*(uper)-(low)+(low);return (p);/獲得抬定上限范困內(nèi)的一個隨機(jī)數(shù)int rnd(int uper)return (rand()%uper);/tsp地圖信息，包含了信息素.城市距離.和信息素變化矩陣class GInfopublic：double m_dDeltTrialN_CITY_COUNT N.

13、CITY.COUNT ; /臨時保存信息素.更新環(huán)境信息素的時候使用.每只螞蟻周游完備個城市后開始訃算double m_dTrialN_CITY_COUNT N.CITY.COUNT : /城市間的信息素，就是環(huán)境信息素double distanceN.CITY.COUNT N.CITY.COUNT : /城市間距離;GInfo Map;定義螞蟻類class antprivate： int ChooseNextCity 0 : 選擇下一個城市double probN_CITY_COUNT: /臨時變雖數(shù)組.選擇下一個城市的時候，保存各個城市被選中的概率值 int m.nCityCount; /

14、記錄媽蟻已經(jīng)走過的城市數(shù)目int AllowedCityN_CITY_COL-NT;/沒有走過的城市，數(shù)組索引對應(yīng)城市編號public：double m_dLength;double m_dShortest;int tabuN_CITY_COUXT; 記錄走過的城市.里面存的是城市的編號，數(shù)組索引表示走的順序。public：ant 0 ;void addcity(int city);void Clear();void UpdateResult():void move ();void move21ast();void shucout();/只剩下一個城市沒走過時才調(diào)用，直接移動到最后一個城市vo

15、id ant:move21ast()for(int i=0; iN_Cin_COUNT; i+)if (AllowedCityi=l)addcity(i);break;/清空數(shù)據(jù).螞蟻周游完幹個城市后.要重新開始周游各個城市時調(diào)用void ant:Clear 0m_dLength=O;for(int i=0; iN_CITY_COUNT;i卄)prob：i=0;AllowedCityi=l;i=tabuN_CITY_COUNT-l; 用最后一個城市作為出發(fā)城市m_nCityCount=0;addcity(i);/初始化ant: ant ()m_dLength=m_dShortest=0;m_n

16、CityCount=0;for(int i=O;iN_CITY_COUNT;i+)AllowedCityi=l;probCi=0;/增加一個城市到走過的城市數(shù)組中，并改變沒走過的城市數(shù)組中的標(biāo)，忐void ant:addcity(int city)/add city to tabu;tabulm_nCityCount=city;m_nCityCount+;AllowedCitycity=0;int ant：:ChooseNextCity()/見新概率的路徑選擇/選擇一條路徑，從t abu m_nC i t y Count -1 到下一個int j=10000;double temp=00;in

17、t curCity=tabum_nCityCount-l : /T前走到那個城市了/先訃算、l前城市和沒有走過的城市兩兩之間的信息素的總和for (int i=0;iN_CITY_COUNT;i卄)if (AllowedCityfi = 1)temp=temp+pow(.(1. 0 Map distancecxirCityZ i) DB_BETA)*pow( (Map. m_dTrial EcurCity i2), DB_ALPHA)；/計算沒有走過的城市被選中的概率double sel=0;for (i=0;iN_CITY_COUNT;i卄)if (AllowedCityi = 1)prob

18、li=pow( (1.O/Map distancecurCityi), DB_BETA)*pow(Map. mdTrialtcurCity i), DB_ALPHA)/temp;sel+二probi;else prob：i=0;下面的操作實際上就是遺傳算法中的輪盤選擇double niRatendCO, sei):double mSelect=0;for ( i=0; i=mRate)j=i；break;/這種情況只有在temp=0. 0的時候才會出現(xiàn)if (j 10000) for (i=0;iN_CITY_COUNT;i卄)if (AllowedCityi = 1) break;retur

19、n j;計算周游完城市后，走過的路徑長度void ant:UpdateResult 0/修正旅行距離for(int i=0; iN_Cin_COUNT-l; i)m_dLength+=Map distanceItabuli tabui+l;m_dLength+=Map. distanceItabuN_CITY_COUNT1 ltabu0 ; /最后城市和開始城市間的距離/移動到下一個城市void ant：:move()/the ant move to next town and add town ID to tabu int n=ChooseNextCity0;addcity(n);class

20、 projectpublic：double m_dLength;ant antsN_ANT_COUNT;public：project 0;void UpdateTnal ();void initmap();void GetAnt 0;void StartSearch();；/HI新環(huán)境信息素/這里采用的是ANT-CYCLE模式，即每只螞蟻周游完城市后才更新void project：:UpdateTnal()/calculate the changes of trial informationint m=0;int n=0;for(int i=O;iN_ANT_COUNT;i-) /計算每只螞蟻

21、在兩兩城市間留下的信息素.螞蟻走過的路徑越短，留下的信息素數(shù)值越大for (int j=0;jN_CITY_COUNT-l;j-+) /il算兩兩城市間的信息素m=antsi tabuj;n =antsi. tabuj+l:Map. mdDeltTrialmln*=DB_Q/antsi. m_dLength;Map. m_dDeltTrial LnmpDB_Q/arrtsi m_dLength;/最后城市到開始城市間的信息素m=antsi. tabuN_CITY_COUNT-l;n =antsitabulO;Map. m_dDeltTrial Lm InDBQ/antsi. m_dLength

22、;Map. m_dDeltTrialLnIm -DBQ/antsi. m_dLength;/最新的環(huán)境信息素=消失掉的信息素十新留下的信息素for (int a=0;aN_CITY_COUNT;a+)for (int j=0;jN_CITY_COUNT;j+TMap. m_dTrialaj = (DB_R0U*Map. m_dTrialaj*Map. mdDeltTrialaj);Map. m_dDeltTrialCaj=0;/初始化void project：:mitmapOfor(int i=0: iN_Cin_COUNT; i+)for (int j=0;jN_CITY_COUNT;j卄)

23、Map. m.dTrialij=l;Map. m_dDeltTrialli:j=0；project:project()/initial mapinitmapO ;m_dLength=10e9;struct cityint num;int x;int y； ccN_CITY_COUNT;/城市坐標(biāo)數(shù)據(jù)來自國際通用的數(shù)據(jù)eil51.tspint 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, 3& 46, 61,

24、 62, 63, 32, 45, 59, 5,10,21,5, 30, 39, 32, 25, 25, 4& 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, 57, 52, 3& 68, 1& 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;iN_CITY_COUNT;i卄) cc

25、i x=x_Aryi;cci. y=y_Aryi;cci num=i;計算兩兩城市間距離.需要進(jìn)行四舍五入取整/eil51. tsp的最短路徑426.是按四舍五入?yún)д蟮木嚯x算出來的。fordnt b=0: bN_Cin_COUNT;b+)for (int j=0;jN_CITY_COUNT;j+TMap. distance lb j = (int) (sqrt (pow(ccb. Xccj. x), 2)+pow(ccbj.廠ccj y), 2)+0. 5);void project：:GetAnt()/初始化隨機(jī)種子srand(unsigned)time(NULL);/為每只螞蟻隨機(jī)分配一

26、個出發(fā)城市int city=0;for (int i=0;iN_ANT_COUNT;i+)city=rnd(N_CITY_C0UNT);antsi addcity(city);void project：:StartSearchO/begin to find best solutionint max=0;/every ant tours timesdouble temp;int temptourN.CITY.COUNT:double dbMm=0. 0;while (max N.IT.COUNT)dbMin=100000000. 0; /本次疊迭中的最小路徑長度for(int j=0;jN_AN

27、T_COUNT;j+)for (int i=0;iN_CITY_COUNT-l:i+)antsj move ();for(int c=0:cN_ANT_C0UNT;c+)antsc move21ast();ants c. UpdateResult () ; /計算路徑總長度find out the best solution of the step and put it into temp temp二ants0 m_dLength;for (int t=0;tN_CITY_COUNT;t+)temptour 2t=ants10 tabu It;for(int d=0;dantsdj m_dLe

28、ngth)temp=antsdl m_dLength;for (int t=0;tantsj m_dLength)dbMin=antsj m_dLength;if (tempm_dLength)m_dLength=temp;for (int t=0:tN.CITY.COUNT;t+)besttour:t二temptourt;pnntf (%d :弔.Of n, max, m_dLength);UpdateTrialO; /全部螞蟻遍歷各個城市后，更新環(huán)境信息素for (int e=0; eN_ANT_COUNT; e+)/再搜索一次antse Clear ();maz十+;pnntf (The

29、 shortest toure is : %fn*, m_dLength):for (int t=0;tN_CITY_COUNT;t卄)printf(* %d , besttourt);void shucout()cout*木程序是利用蟻群算法求解TSP問題即最旅游城市中的般段距離和行走路線 *endK 7, 27, 30, 13, 58, 58, *endl;cout*37t 38, 46, 61, 62, 63, 32, 45, 59, 5, *endl;cout*10t 21, 5, 30, 39, 32, 25, 25,48, 56. *endl;cout*30 *endl;cout*

30、城市Y軸坐標(biāo)為：*endl;cout*52, 49, 64, 26, 30, 47, 63, 62, 33, 2Tendl;cout*41, 32, 25, 42, 16, 41, 23, 33, 13, 58endl;cout*42t 57, 57, 52, 38, 68, 48, 67, 4& 27*endl;cout*69, 46, 10, 33, 63, 69, 22, 35, 15, 6*endl;cout*17t 10,64,15, 10, 39, 32, 55, 2& 37endl;cout*，10*endl;cout請輸入迭代次數(shù)，就是捜索次數(shù)(次數(shù)越大越準(zhǔn)確最好在20006000) endl;cinN_IT_C0UNT;主程序入口int mam()shucout 0;project TSP;TSP. Get Ant ();TSP. StartSearch0;getchar0;return 0;四. 結(jié)果ss本程序是利用蟻群算送求解tsp間題 即最旅游城神的段距離和行走路線*51個城市X軸坐標(biāo)為；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,