蟻群算法求解tsp問題

《蟻群算法求解tsp問題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、HUNANUNIVERSITY課程作業(yè)課程題目智能優(yōu)化算法學(xué)生姓名李小燕學(xué)生學(xué)號S131020016專業(yè)班級計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院名稱信息科學(xué)與工程學(xué)院指導(dǎo)老師楊圣洪2014年6月8日蟻群算法求解TSP問題摘要：蟻群算法是一種分布式內(nèi)在并行算法。單個(gè)螞蟻的搜索過程是彼此獨(dú)立的，易于局部最優(yōu)，通過個(gè)體間不斷的信息交流和傳遞有利于發(fā)現(xiàn)較好解；并且該算法是一種正反饋算法。路徑上的信息素濃度較高，將吸引更多的螞蟻沿這條路徑運(yùn)動，又使得信息素濃度增加，加快了算法的進(jìn)化過程。本文通過求解TSP問題，通過在特定情況下對路徑進(jìn)行逐步遍歷比較來降低陷入局部最優(yōu)解的可能性,找出最優(yōu)解

2、。關(guān)鍵詞：蟻群算法；TSP；信息素；遍歷1.引言TSP問題又稱最短路徑問題，還稱為旅行商問題，是一種比較經(jīng)典的NP難題，問題描述較簡單，而獲得最優(yōu)解卻十分困難。求解TSP問題不僅為其他算法提供了使用平臺，而且算法的優(yōu)劣性能也可通過其求得TSP問題的解集來驗(yàn)證。旅行商問題的經(jīng)典描述為：已知N個(gè)城市及相互間的距離，旅行商從某城市出發(fā)遍歷這N個(gè)城市后再回到原點(diǎn)，在旅行商每個(gè)城市都只訪問一次的前提下確定一條最短路徑。蟻群算法是一種基于種群的啟發(fā)式仿生進(jìn)化系統(tǒng)。該算法通過模擬自然界的螞蟻覓食過程對目標(biāo)進(jìn)行搜索，而在搜索過程中人工螞蟻會在其經(jīng)過的路徑上釋放信息素，蟻群依賴于

3、同類散發(fā)在周圍環(huán)境中的特殊物質(zhì)—信息素的軌跡來決定自己的去向。當(dāng)某些路徑上走過的螞蟻越來越多時(shí)，留下的信息素也會越來越多，以致后螞蟻選擇該路徑的概率也越來越高，從而更增加了該路徑的吸引強(qiáng)度，逐漸形成了一條它們自己事先并未意識到的最短路線。蟻群算法實(shí)現(xiàn)TSP過程為：將m只螞蟻放入到n個(gè)隨機(jī)選擇的城市中，那么每個(gè)螞蟻每步的行動是：根據(jù)一定的依據(jù)選擇下一個(gè)它還沒有訪問的城市；同時(shí)在完成一步（從一個(gè)城市到達(dá)另一個(gè)城市）或者一個(gè)循環(huán)（完成對所有n個(gè)城市的訪問）后，更新所有路徑上的信息素濃度。2.蟻群算法的數(shù)學(xué)模型（1）、基本參數(shù)、信息素濃度公式、擇路概率設(shè)螞蟻的數(shù)量為m，

4、城市的數(shù)量為n，城市i與城市j之間的距離為dij，t時(shí)刻城市i與城市j之間的信息素濃度為tij(t)，初始時(shí)刻，各個(gè)城市間連接路徑上的信息素濃度相同，不妨記為tij(0)=t0。螞蟻k(k=1,2,..,m)根據(jù)各城市間連接路徑上的信息素濃度，決定其下一個(gè)要訪問的城市，設(shè)Pijk(t)表示t時(shí)刻，螞蟻k從城市i到城市j的概率，其計(jì)算公式為如下：其中：hij(t)為啟發(fā)式函數(shù)，hij(t)=1/dij，表示螞蟻從城市i轉(zhuǎn)移到城市j的期望程序；allowk(k=1,2,…,m)表示螞蟻k待訪問的城市的集合，開始時(shí)allowk為其他n-1城市，隨著時(shí)間推進(jìn)，其中的元素

5、不斷減少，直至為空，表示所有城市訪問完，即遍歷所有城市。a為信息素的重要程度因子，其值越大，轉(zhuǎn)移中起的作用越大b為啟發(fā)函數(shù)的重要程度因子，其值越大，表示啟發(fā)函數(shù)在轉(zhuǎn)移中的作用越大，即螞蟻以較大的概率轉(zhuǎn)移到距離短的城市。螞蟻釋放的信息素會隨時(shí)間的推進(jìn)而減少，設(shè)參數(shù)r(0

6、濃度。（2）、Dtijk的計(jì)算方法Dtijk=其中：Q為常數(shù)，表示螞蟻循環(huán)一次釋放的信息素的總量；dij為第k只螞蟻經(jīng)過路徑的長度，Length；3.算法實(shí)現(xiàn)步驟1、初始化參數(shù)螞蟻數(shù)量m，信息素重要程度a，啟發(fā)函數(shù)重要程度b，信息素?fù)]發(fā)因子r，信息素釋放總量Q，最大迭代次數(shù)iter_max。獲取各城市之間的距離dij，為了保證啟發(fā)式函數(shù)hij=1/dij能順利進(jìn)行，對于i=j即自己到自己的距離不能給為0，而是給成一個(gè)很小的距離，如10-4或10-5。2、構(gòu)建解空間將各個(gè)螞蟻隨機(jī)地置于不同出發(fā)點(diǎn)，對每個(gè)螞蟻按歸照下式，確定下一城市。3、更新信息素計(jì)算各個(gè)螞蟻經(jīng)過的

7、路徑長度Lk，記錄當(dāng)前迭代次數(shù)中的最優(yōu)解(即最短路徑)，根據(jù)如下公式更新信息素：tij(t+1)=(1-r)tij(t)+Dtij，Dtij=Dtijk=4、判斷是否終止若沒有到最大次數(shù)，則清空螞蟻經(jīng)過路徑的記錄表，返回步驟2。4.相關(guān)實(shí)驗(yàn)4.1實(shí)驗(yàn)內(nèi)容1、訪問我國每個(gè)省會城市一次也僅一次的最短路徑，共有31個(gè)2、如果采用枚舉法，巡回路徑可能1.326′1032種。3、城市的坐標(biāo)citys，這是直角坐標(biāo)，根據(jù)二個(gè)城市的坐標(biāo)值，可以用D=可計(jì)算出任意二個(gè)城市間的距離。citys=1304231236391315417722443712139934881535332

8、615563238122