蟻群算法課程設(shè)計(jì)報(bào)告

精選優(yōu)質(zhì)文檔-----傾情為你奉上精選優(yōu)質(zhì)文檔-----傾情為你奉上專心---專注---專業(yè)專心---專注---專業(yè)精選優(yōu)質(zhì)文檔-----傾情為你奉上專心---專注---專業(yè)計(jì)算機(jī)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)《程序設(shè)計(jì)綜合課程設(shè)計(jì)》報(bào)告（2010/2011學(xué)年第一學(xué)期）學(xué)生姓名：學(xué)生班級(jí)：學(xué)生學(xué)號(hào)：指導(dǎo)教師：2011年1月8日

蟻群算法蟻群算法

蟻群算法求解ＴＳＰ問(wèn)題

目錄TOC\o"1-3"\h\u第一章課程設(shè)計(jì)目的和要求1.1程序設(shè)計(jì)目的學(xué)習(xí)C++程序設(shè)計(jì)不能滿足于“懂得了”，滿足于了解了語(yǔ)法和能看懂書(shū)上的程序，而應(yīng)當(dāng)掌握程序設(shè)計(jì)的全過(guò)程，即能獨(dú)立編寫(xiě)出源程序，獨(dú)立上機(jī)調(diào)試程序，獨(dú)立運(yùn)行程序和分析結(jié)果。設(shè)計(jì)C++的初衷是為了方便開(kāi)發(fā)大型程序，雖然現(xiàn)在還沒(méi)接觸大型程序，更不可能編寫(xiě)出能供實(shí)際應(yīng)用的大型程序，而只能接觸比較簡(jiǎn)單的程序。但通過(guò)學(xué)習(xí)C++課程，對(duì)C++有比較全面的、然而是初步的認(rèn)識(shí)，為今后進(jìn)一步學(xué)習(xí)和應(yīng)用C++打下良好的基礎(chǔ)。學(xué)習(xí)程序設(shè)計(jì)的目的是：=1\*GB2⑴加深對(duì)講授內(nèi)容的理解，尤其是一些語(yǔ)法的規(guī)定，光靠課堂講授，既枯燥無(wú)味又難以記憶，但它們是很重要的，通過(guò)設(shè)計(jì)來(lái)掌握語(yǔ)法規(guī)則是有效的方法。=2\*GB2⑵在程序設(shè)計(jì)中，可以了解運(yùn)行一個(gè)C++程序需要哪些必要的外部條件（例如硬件配置、軟件配置。=3\*GB2⑶學(xué)會(huì)上機(jī)調(diào)試程序。也就是善于發(fā)現(xiàn)程序中的錯(cuò)誤，并且很快地排除這些錯(cuò)誤，使程序能正常運(yùn)行。1.2程序設(shè)計(jì)要求利用蟻群算法求解TSP問(wèn)題。程序中給出51個(gè)城市的坐標(biāo)為：X軸：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.Ｙ軸：52,49,64,26,30,47,63,62,33,21,41,32,25,42,16,41,23,33,13,58,42,57,57,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.=1\*GB2⑴求出最短的旅行距離。=2\*GB2⑵求出如何旅行城市，求出每個(gè)城市是第幾個(gè)旅行能使旅行距離最優(yōu)。

程序設(shè)計(jì)內(nèi)容2.1關(guān)于蟻群智能和ＴＳＰ昆蟲(chóng)學(xué)家們?cè)谘芯款愃莆浵佭@樣的視盲動(dòng)物如何沿最佳路線從其巢穴打達(dá)食物源的過(guò)程中發(fā)現(xiàn)，螞蟻與螞蟻之間最重要的通信媒介就是他們?cè)谝苿?dòng)過(guò)程中所釋放的特有的分泌物——信息素，當(dāng)一個(gè)孤立的螞蟻隨機(jī)移動(dòng)時(shí)，它能檢測(cè)到其他同伴所釋放的信息素，并沿著該路線移動(dòng)，同時(shí)又釋放自身的信息素，從而增強(qiáng)了該路線上的信息素?cái)?shù)量，隨著越來(lái)越多的螞蟻通過(guò)該路線，一條最佳的路徑就會(huì)逐漸形成。已經(jīng)總結(jié)出來(lái)螞蟻行為具有以下如下一些顯著特征：=1\*GB2⑴能夠察覺(jué)前方小范圍區(qū)域內(nèi)的狀況，并判斷是否有食物或其他同類的信息素軌跡；=2\*GB2⑵能夠釋放出兩種類型的信息素：“食物”信息素和“巢穴”信息素；=3\*GB2⑶僅當(dāng)攜帶食物或是將食物帶回到巢穴時(shí)才會(huì)釋放信息素；=4\*GB2⑷所釋放的信息素?cái)?shù)量會(huì)隨著其不斷移動(dòng)而逐步減少。并且螞蟻的運(yùn)動(dòng)還遵循以下簡(jiǎn)單規(guī)則：=1\*GB2⑴按隨機(jī)方向離開(kāi)巢穴，僅受其巢穴周圍的信息素影響；=2\*GB2⑵按隨機(jī)方向移動(dòng)，僅受其周圍“食物”信息素的影響；當(dāng)察覺(jué)到“食物”信息素軌跡時(shí)，將沿著強(qiáng)度最大的軌跡運(yùn)動(dòng)；=3\*GB2⑶一旦找到食物，將取走部分，并開(kāi)始釋放“食物”信息素；=4\*GB2⑷移動(dòng)過(guò)程中，將受到“巢穴”信息素的影響；=5\*GB2⑸一旦回到巢穴，將放下食物，并開(kāi)始釋放“巢穴”信息素。自然界中的螞蟻沒(méi)有視覺(jué)，既不知道像何處去尋找和獲得食物，也不知道發(fā)現(xiàn)食物后如何返回巢穴，它們僅僅依靠于同類散發(fā)在周圍環(huán)境中的特殊物質(zhì)——信息素的軌跡，從而決定自己何去何從。螞蟻還是有能力找到從其巢穴到食物源的最佳路徑，甚至在該路線上放置障礙物之后，它們讓然能很快重新找到新的最佳路徑。蟻群算法就是模擬螞蟻的這種特性，來(lái)找到優(yōu)化最佳的路徑．（如圖2-1）螞蟻在相同的時(shí)間區(qū)間內(nèi)，短的路線會(huì)有更多的機(jī)會(huì)被選擇。食物食物２１１２１１障礙物障礙物２１２１巢穴巢穴圖2-1TSP問(wèn)題可以描述為：有N個(gè)城市，一售貨員從起始城市出發(fā)，訪問(wèn)所有的城市一次，最后回到起始城市，求最短路徑。TSP問(wèn)題除了具有明顯的實(shí)際意義外，有許多問(wèn)題都可以歸結(jié)為T(mén)SP問(wèn)題。2.2解決的問(wèn)題用蟻群算法來(lái)解決在旅行商旅中有51個(gè)城市的最優(yōu)路徑，并求出如何行走才是距離最短和城市走的順序。第三章詳細(xì)設(shè)計(jì)說(shuō)明3.1模塊描述本程序共有voidaddcity();voidClear();voidUpdateResult();voidmove();voidmove2last();voidshucout()；voidproject::initmap()；voidproject::GetAnt()；voidproject::StartSearch()；voidproject::UpdateTrial()。１０子程序模塊和intmain()一個(gè)主程序。voidshucout()顯示歡迎信息模塊voidant::move2last()只剩下一個(gè)城市沒(méi)走過(guò)時(shí)才調(diào)用，直接移動(dòng)到最后一個(gè)城市voidant::Clear()清空數(shù)據(jù)，螞蟻周游完各個(gè)城市后，要重新開(kāi)始周游各個(gè)城市時(shí)調(diào)用voidant::addcity(intcity)增加一個(gè)城市到走過(guò)的城市數(shù)組中，并改變沒(méi)走過(guò)的城市數(shù)組中的標(biāo)志voidant::UpdateResult()計(jì)算周游完城市后，走過(guò)的路徑長(zhǎng)度voidant::move()移動(dòng)到下一個(gè)城市voidproject::initmap()初始化voidproject::GetAnt()初始化隨機(jī)種子voidproject::StartSearch()開(kāi)始尋找最好的解決方法voidproject::UpdateTrial()更新環(huán)境信息素，每只螞蟻周游完城市后才更新3.2性能本程序按原理來(lái)說(shuō)迭代次數(shù)越大，程序得出的結(jié)果越精確，但當(dāng)數(shù)值超過(guò)1000以后，結(jié)果基本不變。要求城市數(shù)量/螞蟻數(shù)量=1.5左右dbMin=.0;疊迭中的最小路徑長(zhǎng)度。3.3輸入項(xiàng)和輸出項(xiàng)本程序的需要輸入項(xiàng)有：需要輸入迭代次數(shù)，就是搜索次數(shù)N_IT_COUNT螞蟻數(shù)量N_ANT_COUNT=34（一般取值原則為：城市數(shù)量/螞蟻數(shù)量=1.5左右）城市數(shù)量N_CITY_COUNT=51;總的信息素DB_Q=100;信息素重要程度DB_ALPHA=1;引導(dǎo)螞蟻往信息素大的地方走的數(shù)DB_BETA=3;環(huán)境信息素?fù)]發(fā)速度DB_ROU=0.5。城市坐標(biāo)數(shù)據(jù)intx_Ary[51]={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};inty_Ary[51]={52,49,64,26,30,47,63,62,33,21,41,32,25,42,16,41,23,33,13,58,42,57,57,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};輸出項(xiàng)：優(yōu)化后旅行的最短距離（圖3-1）圖3-1每個(gè)城市走的順序（圖3-2）圖3-23.4算法本程序是基于蟻群算法求解ＴＳＰ問(wèn)題，設(shè)為城市，之間的幾何距離，。設(shè)表示時(shí)刻位于城市的螞蟻的個(gè)數(shù)，螞蟻總數(shù)，表示時(shí)刻在連線上殘留的信息量，初始時(shí)刻各條路徑上的信息量為（為常數(shù)）。用參數(shù)表示信息量的保留度，則經(jīng)過(guò)個(gè)時(shí)刻后，路徑上的信息量根據(jù)下式作調(diào)整：=1\*GB3①=2\*GB3②表示第只螞蟻在本次循環(huán)中留在路徑上的信息量，表示本次循環(huán)所有經(jīng)過(guò)的螞蟻留在上的信息量。＝=3\*GB3③定義。螞蟻（＝１，２，…，）在運(yùn)動(dòng)過(guò)程中，表示在時(shí)刻螞蟻由位置轉(zhuǎn)移到位置的概率：＝=4\*GB3④我們用tabu[N_CITY_COUNT]記錄螞蟻目前已經(jīng)走過(guò)的城市集合，AllowedCity[N_CITY_COUNT]表示螞蟻下一步允許選擇的城市集合，它等于全部的城市集合除去第只螞蟻已走過(guò)的集合tabu[N_CITY_COUNT]。定義為第只螞蟻在本次循環(huán)中走過(guò)的路徑和。用蟻群算法解決ＴＳＰ問(wèn)題是一個(gè)遞推過(guò)程，當(dāng)時(shí)，將螞蟻放在各城市，設(shè)定每條路徑上的信息量初值，每只螞蟻根據(jù)公式=4\*GB3④決定的概率從城市到城市。表示曾經(jīng)有多少螞蟻經(jīng)過(guò)路徑；說(shuō)明較近的城市有更大的可能性被選中。用來(lái)控制兩者對(duì)螞蟻選擇的影響力程度。經(jīng)過(guò)一個(gè)循環(huán)后，根據(jù)公式=1\*GB3①；=2\*GB3②；=3\*GB3③計(jì)算更新每條路徑的信息量。將所有的復(fù)原，最后求出本次循環(huán)的最短路徑。這個(gè)過(guò)程不斷重復(fù)，直到所有的螞蟻都選擇同樣的路徑，或者循環(huán)次數(shù)達(dá)到預(yù)先設(shè)定的最高次數(shù)。解決個(gè)城市的ＴＳＰ問(wèn)題算法設(shè)計(jì)如下：=1\*GB2⑴初始化：設(shè)定，循環(huán)計(jì)數(shù)器，對(duì)每條路徑設(shè)定初始信息量,將只螞蟻放在個(gè)城市上（為了使問(wèn)題簡(jiǎn)化，設(shè)定）。=2\*GB2⑵設(shè)定集合的索引，對(duì)從１到，把第只螞蟻放在起始位置，對(duì)應(yīng)的設(shè)定集合=3\*GB2⑶重復(fù)下面的步驟，直到集合滿為止（這一步將重復(fù)次）：設(shè)定；對(duì)從１到，根據(jù)公式=4\*GB3④確定的概率，選擇下一步移動(dòng)的目標(biāo)城市｛在時(shí)間時(shí)，第只螞蟻所在的城市是};將第只螞蟻移到城市；把加入到集合中。=4\*GB2⑷對(duì)從１到：將第只螞蟻從移動(dòng)到；計(jì)算第ｋ只螞蟻所走過(guò)的路程和，并更新最小路徑；對(duì)每條路徑：＝；=5\*GB3⑤=5\*GB2⑸對(duì)每條路徑根據(jù)計(jì)算；設(shè)定；設(shè)定；對(duì)每條路徑，設(shè)定。=6\*GB2⑹如果，則清空所有的集合ｔ轉(zhuǎn)到第二步；否則，得出最短的路徑。在這兒我們用的是算法，這種算法，每當(dāng)結(jié)束一個(gè)循環(huán)后，根據(jù)公式=3\*GB3③計(jì)算。3.5流程邏輯開(kāi)始開(kāi)始初始化初始化設(shè)定設(shè)定集合,對(duì)每只螞蟻對(duì)每只螞蟻=計(jì)算螞蟻所走過(guò)的路程和計(jì)算螞蟻所走過(guò)的路程和更新最小路徑ｍｉｎ更新最小路徑ｍｉｎ對(duì)每條路徑計(jì)算對(duì)每條路徑計(jì)算設(shè)定ＮＣ＝ＮＣ＋１設(shè)定ＮＣ＝ＮＣ＋１acacbbacbacb NNYY清空所有的集合清空所有的集合得出最短路徑得出最短路徑N集合N集合滿YY結(jié)束結(jié)束圖3-53.6接口程序中的子函數(shù)：voidaddcity(intcity);voidClear();voidUpdateResult();voidmove();voidmove2last();voidshucout();voidUpdateTrial();voidinitmap();voidGetAnt();voidStartSearch();子函數(shù)的接口voidant::Clear()voidant::move2last()voidant::Clear()voidant::move2last()voidaddcity(ivoidaddcity(i)voidaddcity(i)圖3-2圖3-2圖3-1圖3-1voidproject::GetAnt()voidant::move()voidproject::GetAnt()voidant::move()voidaddcity(ivoidaddcity(i)voidaddcity(i)圖3-4圖3-3圖3-4圖3-3主函數(shù)voidproject::StartSearch()主函數(shù)voidproject::StartSearch()voidshucout();voidant::move()voidshucout();voidant::move()projectTSPvoidant::move2last()projectTSPvoidant::move2last()TSP.GetAnt()voidUpdateTrial();TSP.GetAnt()voidUpdateTrial();TSP.StartSearch()TSP.StartSearch()voidClear();voidClear();圖3-6圖3-5圖3-6圖3-53.7數(shù)據(jù)存儲(chǔ)說(shuō)明本程序沒(méi)有數(shù)據(jù)存儲(chǔ)，每次需要換疊代數(shù)時(shí)重新運(yùn)行本程序。3.8注釋設(shè)計(jì)注釋可以讓程序更具有可讀性，本程序在每個(gè)數(shù)據(jù)類型后都有注釋（如圖3-1）；在每個(gè)不易理解的語(yǔ)句中也有注釋設(shè)計(jì)（如圖3-2，3-3）；在每個(gè)子程序中都加入注釋（如圖3-4,3-5）圖3-1圖3-2圖3-3圖3-4圖3-53.9限制條件在操作系統(tǒng)和條件下運(yùn)行本程序。3.10測(cè)試計(jì)劃打開(kāi)程序后會(huì)出現(xiàn)一個(gè)歡迎界面，輸入迭代次數(shù)后運(yùn)行程序。先令城市數(shù)分別為1,2,3然后得到的結(jié)果與。進(jìn)行比較，求出最優(yōu)接合最優(yōu)路線，進(jìn)行比較。來(lái)測(cè)試程序運(yùn)行結(jié)果的對(duì)錯(cuò)。

程序使用說(shuō)明本程序操作簡(jiǎn)單易于上手，已經(jīng)給出51坐城市坐標(biāo)求最優(yōu)距離，和每個(gè)城市旅行的順序。只需要要輸入迭代數(shù)。歡迎界面，輸入迭代次數(shù)。圖4-１當(dāng)次數(shù)為時(shí)：圖4-2圖4-3圖4-4圖4-5圖4-6圖4-7圖4-8圖4-9圖4-10最后運(yùn)行結(jié)果：圖4-11Theshortesttoursis:430.．下面的數(shù)字是51個(gè)城市所旅行的順序，只要按照程序給出的城市順序數(shù)進(jìn)行旅行，所走的距離是最優(yōu)的為430．如果想更換螞蟻數(shù)量和城市數(shù)量（圖4-12）以及城市的坐標(biāo)（圖4-13）只需把源代碼中數(shù)和坐標(biāo)更改就可以。圖4-12圖4-13

第五章程序設(shè)計(jì)心得與體會(huì)通過(guò)一個(gè)學(xué)期對(duì)《程序設(shè)計(jì)》的學(xué)習(xí)，對(duì)于的基本的理論知識(shí)有了點(diǎn)了解，初步形成了基本的語(yǔ)言程序設(shè)計(jì)的思想，但對(duì)于大型程序的編程還是不了解。在為期三周的課程設(shè)計(jì)，檢查這一個(gè)學(xué)期來(lái)計(jì)算機(jī)語(yǔ)言的學(xué)習(xí)成果，也是為了讓我們進(jìn)一步掌握和熟練地運(yùn)用它，與此同時(shí)，也能夠讓我們認(rèn)清自己在學(xué)習(xí)方面的不足之處和薄弱環(huán)節(jié)，并加以彌補(bǔ)和鞏固。通過(guò)對(duì)蟻群算法ＴＳＰ程序設(shè)計(jì)，不僅讓我鞏固了知識(shí)而且還讓我了解了關(guān)于蟻群算法的很多知識(shí)，著對(duì)于我來(lái)說(shuō)，是不小的收獲，以前根本就不知道蟻群算法，現(xiàn)在有了基本的了解，感覺(jué)自己收獲不少。經(jīng)過(guò)這次設(shè)計(jì)我體會(huì)頗多，我懂得了用MicrosoftVisualC++6.0對(duì)程序進(jìn)行調(diào)試，糾正錯(cuò)誤，我加強(qiáng)了對(duì)程序設(shè)計(jì)這門(mén)課程的認(rèn)識(shí)，并且復(fù)習(xí)了自己以前學(xué)習(xí)到的知識(shí)，自己的邏輯思考能力也提高不少。這些都使得我對(duì)計(jì)算機(jī)語(yǔ)言的學(xué)習(xí)有了更深入的認(rèn)識(shí)！總之，通過(guò)這次課程設(shè)計(jì)，我收獲頗豐，相信會(huì)為自己以后的學(xué)習(xí)和工作帶來(lái)很大的好處。最重要的還是激發(fā)了我編程和對(duì)算法的興趣和熱情，讓我從一個(gè)只懂理論變成了能做一些小型程序。整體地評(píng)價(jià)這次課程設(shè)計(jì)，我認(rèn)為收獲很大，正如上面所說(shuō)的那樣，通過(guò)課程設(shè)計(jì)，既復(fù)習(xí)了以前的舊知識(shí)，又學(xué)到了一些新的知識(shí)。像應(yīng)用程序的設(shè)計(jì)和創(chuàng)建，經(jīng)歷了平時(shí)在課堂和考試中不會(huì)出現(xiàn)的難題和考驗(yàn)。而這些問(wèn)題，又都是課本上很少提到的、更深一層的實(shí)踐與知識(shí)相結(jié)合的問(wèn)題，這并不是我們平時(shí)只靠課本，就可以輕易解決的。所以，鍛煉了我們面對(duì)難題，學(xué)會(huì)用已掌握的知識(shí)去解決具體問(wèn)題的能力，進(jìn)一步培養(yǎng)了獨(dú)立思考問(wèn)題和解決問(wèn)題的能力。特別是學(xué)會(huì)了在Visual中如何調(diào)試程序的方法。當(dāng)然，老師的指導(dǎo)和同學(xué)的幫助也是不可忽視的，他們給了我許多提示和幫助，教會(huì)了我編譯復(fù)雜程序的方法?？偠灾@次程序設(shè)計(jì)實(shí)踐讓我收獲很大。

附錄一：參考文獻(xiàn)=1\*GB2⑴譚浩強(qiáng)著程序設(shè)計(jì).北京：清華大學(xué)出版社；1999=2\*GB2⑵譚浩強(qiáng)著程序設(shè)計(jì)題解與上機(jī)指導(dǎo).北京：清華大學(xué)出版社；1999=3\*GB2⑶馬良朱剛寧愛(ài)兵著蟻群優(yōu)化算法；2008=4\*GB2⑷蟻群算法貼吧。

附錄二：程序清單//ANT.cpp:定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。//城市坐標(biāo)數(shù)據(jù)直接寫(xiě)在代碼里面，使用的是eil51.tsp中的數(shù)據(jù)#include<iostream>#include<math.h>#include<time.h>usingnamespacestd;constintN_ANT_COUNT=34;//螞蟻數(shù)量，一般取值原則為：城市數(shù)量/螞蟻數(shù)量=1.5左右constintN_CITY_COUNT=51;//城市數(shù)量intN_IT_COUNT;//=5000;//迭代次數(shù)，就是搜索次數(shù)constdoubleDB_Q=100;//總的信息素constdoubleDB_ALPHA=1;//信息素重要程度constdoubleDB_BETA=3;//這個(gè)數(shù)越大，則螞蟻往信息素大的地方走的概率就越大constdoubleDB_ROU=0.5;//環(huán)境信息素?fù)]發(fā)速度intbesttour[N_CITY_COUNT];//最佳路徑列表//獲得指定范圍內(nèi)的一個(gè)隨機(jī)數(shù)doublernd(intlow,doubleuper){doublep=(rand()/(double)RAND_MAX)*((uper)-(low))+(low);return(p);};//獲得指定上限范圍內(nèi)的一個(gè)隨機(jī)數(shù)intrnd(intuper){return(rand()%uper);};//tsp地圖信息，包含了信息素，城市距離，和信息素變化矩陣classGInfo{public:doublem_dDeltTrial[N_CITY_COUNT][N_CITY_COUNT];//臨時(shí)保存信息素，更新環(huán)境信息素的時(shí)候使用，每只螞蟻周游完各個(gè)城市后開(kāi)始計(jì)算doublem_dTrial[N_CITY_COUNT][N_CITY_COUNT];//城市間的信息素，就是環(huán)境信息素doubledistance[N_CITY_COUNT][N_CITY_COUNT];//城市間距離};GInfoMap;//定義螞蟻類classant{private:intChooseNextCity();//選擇下一個(gè)城市doubleprob[N_CITY_COUNT];//臨時(shí)變量數(shù)組，選擇下一個(gè)城市的時(shí)候，保存各個(gè)城市被選中的概率值intm_nCityCount;//記錄螞蟻已經(jīng)走過(guò)的城市數(shù)目intAllowedCity[N_CITY_COUNT];//沒(méi)有走過(guò)的城市，數(shù)組索引對(duì)應(yīng)城市編號(hào)public:doublem_dLength;doublem_dShortest;inttabu[N_CITY_COUNT];//記錄走過(guò)的城市，里面存的是城市的編號(hào)，數(shù)組索引表示走的順序。public:ant();voidaddcity(intcity);voidClear();voidUpdateResult();voidmove();voidmove2last();voidshucout();};//只剩下一個(gè)城市沒(méi)走過(guò)時(shí)才調(diào)用，直接移動(dòng)到最后一個(gè)城市voidant::move2last(){for(inti=0;i<N_CITY_COUNT;i++){if(AllowedCity[i]==1){addcity(i);break;}}}//清空數(shù)據(jù)，螞蟻周游完各個(gè)城市后，要重新開(kāi)始周游各個(gè)城市時(shí)調(diào)用voidant::Clear(){m_dLength=0;for(inti=0;i<N_CITY_COUNT;i++){prob[i]=0;AllowedCity[i]=1;}i=tabu[N_CITY_COUNT-1];//用最后一個(gè)城市作為出發(fā)城市m_nCityCount=0;addcity(i);}//初始化ant::ant(){m_dLength=m_dShortest=0;m_nCityCount=0;for(inti=0;i<N_CITY_COUNT;i++){AllowedCity[i]=1;prob[i]=0;}}//增加一個(gè)城市到走過(guò)的城市數(shù)組中，并改變沒(méi)走過(guò)的城市數(shù)組中的標(biāo)志voidant::addcity(intcity){//addcitytotabu;tabu[m_nCityCount]=city;m_nCityCount++;AllowedCity[city]=0;}intant::ChooseNextCity(){//更新概率的路徑選擇//選擇一條路徑,從tabu[m_nCityCount-1]到下一個(gè)intj=10000;doubletemp=0.0;intcurCity=tabu[m_nCityCount-1];//當(dāng)前走到那個(gè)城市了//先計(jì)算當(dāng)前城市和沒(méi)有走過(guò)的城市，兩兩之間的信息素的總和for(inti=0;i<N_CITY_COUNT;i++){if(AllowedCity[i]==1){temp=temp+pow((1.0/Map.distance[curCity][i]),DB_BETA)*pow((Map.m_dTrial[curCity][i]),DB_ALPHA);}}//計(jì)算沒(méi)有走過(guò)的城市被選中的概率doublesel=0;for(i=0;i<N_CITY_COUNT;i++){if(AllowedCity[i]==1){prob[i]=pow((1.0/Map.distance[curCity][i]),DB_BETA)*pow((Map.m_dTrial[curCity][i]),DB_ALPHA)/temp;sel+=prob[i];}else{prob[i]=0;}}//下面的操作實(shí)際上就是遺傳算法中的輪盤(pán)選擇doublemRate=rnd(0,sel);doublemSelect=0;for(i=0;i<N_CITY_COUNT;i++){if(AllowedCity[i]==1){mSelect+=prob[i];}if(mSelect>=mRate){j=i;break;}}//這種情況只有在temp=0.0的時(shí)候才會(huì)出現(xiàn)if(j==10000){for(i=0;i<N_CITY_COUNT;i++){if(AllowedCity[i]==1){j=i;break;}}}returnj;}//計(jì)算周游完城市后，走過(guò)的路徑長(zhǎng)度voidant::UpdateResult(){//修正旅行距離for(inti=0;i<N_CITY_COUNT-1;i++){m_dLength+=Map.distance[tabu[i]][tabu[i+1]];}m_dLength+=Map.distance[tabu[N_CITY_COUNT-1]][tabu[0]];//最后城市和開(kāi)始城市間的距離}//移動(dòng)到下一個(gè)城市voidant::move(){//theantmovetonexttownandaddtownIDn=ChooseNextCity();addcity(n);}classproject{public:doublem_dLength;antants[N_ANT_COUNT];public:project();voidUpdateTrial();voidinitmap();voidGetAnt();voidStartSearch();};//更新環(huán)境信息素//這里采用的是ANT-CYCLE模式，即每只螞蟻周游完城市后才更新voidproject::UpdateTrial(){//calculatethechangesoftrialinformationintm=0;intn=0;for(inti=0;i<N_ANT_COUNT;i++)//計(jì)算每只螞蟻在兩兩城市間留下的信息素，螞蟻?zhàn)哌^(guò)的路徑越短，留下的信息素?cái)?shù)值越大{for(intj=0;j<N_CITY_COUNT-1;j++)//計(jì)算兩兩城市間的信息素{m=ants[i].tabu[j];n=ants[i].tabu[j+1];Map.m_dDeltTrial[m][n]+=DB_Q/ants[i].m_dLength;Map.m_dDeltTrial[n][m]+=DB_Q/ants[i].m_dLength;}//最后城市到開(kāi)始城市間的信息素m=ants[i].tabu[N_CITY_COUNT-1];n=ants[i].tabu[0];Map.m_dDeltTrial[m][n]+=DB_Q/ants[i].m_dLength;Map.m_dDeltTrial[n][m]+=DB_Q/ants[i].m_dLength;}//最新的環(huán)境信息素=消失掉的信息素+新留下的信息素for(inta=0;a<N_CITY_COUNT;a++){for(intj=0;j<N_CITY_COUNT;j++){Map.m_dTrial[a][j]=(DB_ROU*Map.m_dTrial[a][j]+Map.m_dDeltTrial[a][j]);Map.m_dDeltTrial[a][j]=0;}}}//初始化voidproject::initmap(){for(inti=0;i<N_CITY_COUNT;i++){for(intj=0;j<N_CITY_COUNT;j++){Map.m_dTrial[i][j]=1;Map.m_dDeltTrial[i][j]=0;}}}project::project(){//initialmapinitmap();m_dLength=10e9;structcity{intnum;intx;inty;} cc[N_CITY_COUNT];//城市坐標(biāo)數(shù)據(jù)來(lái)自國(guó)際通用的數(shù)據(jù)eil51.tspintx_Ary[51]={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};inty_Ary[51]={52,49,64,26,30,47,63,62,33,21,41,32,25,42,16,41,23,33,13,58,42,57,57,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(inti=0;i<N_CITY_COUNT;i++){cc[i].x=x_Ary[i];cc[i].y=y_Ary[i];cc[i].num=i;}//計(jì)算兩兩城市間距離，需要進(jìn)行四舍五入取整//eil51.tsp的最短路徑426，是按四舍五入取整后的距離算出來(lái)的。for(intb=0;b<N_CITY_COUNT;b++){for(intj=0;j<N_CITY_COUNT;j++){Map.distance[b][j]=(int)(sqrt(pow((cc[b].x-cc[j].x),2)+pow((cc[b].y-cc[j].y),2))+0.5);}}}voidproject::GetAnt(){//初始化隨機(jī)種子srand((unsigned)time(NULL));//為每只螞蟻隨機(jī)分配一個(gè)出發(fā)城市intcity=0;for(inti=0;i<N_ANT_COUNT;i++){city=rnd(N_CITY_COUNT);ants[i].addcity(city);}}voidproject::StartSearch(){//begintofindbestsolutionintmax=0;//everyanttourstimesdoubletemp;inttemptour[N_CITY_COUNT];doubledbMin=0.0;while(max<N_IT_COUNT){dbMin=.0;//本次疊迭中的最小路徑長(zhǎng)度f(wàn)or(intj=0;j<N_ANT_COUNT;j++){for(inti=0;i<N_CITY_COUNT-1;i++){ants[j].move();}}for(intc=0;c<N_ANT_COUNT;c++){ants[c].move2last();ants[c].UpdateResult();//計(jì)算路徑總長(zhǎng)度}//findoutthebestsolutionofthestepandputitintotemptemp=ants[0].m_dLength;for(intt=0;t<N_CITY_COUNT;t++){temptour[t]=ants[0].tabu[t];}for(intd=0;d<N_ANT_COUNT;d++){if(temp>ants[d].m_dLength){temp=ants[d].m_dLength;for(intt=0;t<N_CITY_COUNT;t++){temptour[t]=ants[d].tabu[t];}}if(dbMin>ants[j].m_dLength){dbMin=ants[