多目標(biāo)蟻群算法及其實(shí)現(xiàn)

1、多目標(biāo)蟻群算法及其實(shí)現(xiàn)李首帥(2012101020019)指導(dǎo)老師：張勇【摘要】多目標(biāo)優(yōu)化問題對(duì)于現(xiàn)階段來說，是十分熱門的。本文將對(duì)多目標(biāo)規(guī)劃當(dāng)中的旅行商問題，通過基于 MATLAB的蟻群算法來解決，對(duì)多目標(biāo)問題進(jìn)行局部優(yōu)化。【關(guān)鍵詞】旅行商問題；蟻群算法；MATLAB一、背景介紹旅行商問題是物流領(lǐng)域當(dāng)中的典型問題，它的求解十分重要。蟻群算法是受自然界中真實(shí)蟻群的集體行為的啟發(fā)而提出的一種基于群體的模擬進(jìn)化算法，屬于隨機(jī)搜索算法。M.Dorigo等人充分利用了蟻群搜索食物的過程與旅行商問題(TSP)之間的相似性，通過人工模擬蟻群搜索食物的行為(即螞蟻個(gè)體之間通過間接通訊與相互協(xié)作最終找到從蟻穴

2、到食物 源的最短路徑)來求解TSP問題。為區(qū)別于真實(shí)蟻群，稱算法中的螞蟻為“人工螞蟻” 。人們 經(jīng)過大量研究發(fā)現(xiàn)，螞蟻個(gè)體之間是通過一種稱之為信息素(pheromone)的物質(zhì)進(jìn)行信息傳遞,從而能相互協(xié)作，完成復(fù)雜的任務(wù)。蟻群之所以表現(xiàn)出復(fù)雜有序的行為，個(gè)體之間的信息交流與相互協(xié)作起著重要的作用。螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下該種物質(zhì),而且能夠感知這種物質(zhì)的存在及其強(qiáng)度，并以此指導(dǎo)自己的運(yùn)動(dòng)方向。 螞蟻傾向于朝著該物質(zhì)強(qiáng)度高的方向移動(dòng)。因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋 現(xiàn)象：某一路徑上走過的螞蟻越多 ，則后來者選擇該路徑的概率就越大。螞蟻個(gè)體之間就是通過

3、這種信息的交流達(dá)到搜索食物的目的。二、蟻群算法原理介紹1. 蟻群在路徑上釋放信息素；2. 碰到還沒走過的路口，就隨機(jī)挑選一條路走。同時(shí)釋放與路徑長度有關(guān)的信息素；3信息素濃度與路長成反比；4. 最優(yōu)路徑上的信息濃度越來越大；5. 最終蟻群找到最優(yōu)路徑。其實(shí)自然界中，蟻群這種尋找路徑的過程表現(xiàn)是一種正反饋的過程，與人工蟻群的優(yōu)化算法很相近。所以我們簡單功能的工作單元視為螞蟻，則上述的搜尋路徑過程可以用來解釋人工蟻群搜尋過程。人工蟻群和自然界蟻群各具特點(diǎn)。人工蟻群具有一定的記憶能力。它能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)；另外,人工蟻群在選擇下一條路徑的時(shí)候并不是完全盲目的，而是按一定的算法規(guī)律有意識(shí)地尋找最

4、短路徑。而自然界蟻群不具有記憶的能力，它們的選路憑借外激素，或者道路的殘留信息來選擇，更多地體現(xiàn)正反饋的過程。 人工蟻群和自然界蟻群的相似之處在于兩者優(yōu)先選擇的都是含 “外激素”濃度較大的路徑；兩者的工作單元(螞蟻)都是通過在其所 經(jīng)過的路徑上留下一定信息的方法進(jìn)行間接的信息傳遞。三、基于MATLAB勺蟻群算法求解旅行商問題TSP問題描述如下：設(shè)有n個(gè)城市C= (1, 2,.,n)，任意兩個(gè)城市i , j之間的距離為d,求一條經(jīng)過每個(gè)城市的路徑n = ( n (1) , n (2), . , n (n),使得距離最小。第一步：初始化將m只螞蟻隨機(jī)放到n個(gè)城市，每只螞蟻的禁忌表為螞蟻當(dāng)前所在城市

5、，各邊信息初始化為c。禁忌表體現(xiàn)了人工螞蟻的記憶性，使得螞蟻不會(huì)走重復(fù)道路，提高了效率。第二步：構(gòu)造路徑在t時(shí)刻，螞蟻k從城市i轉(zhuǎn)移到城市j的概率為：b(i,j 滬(i, j 少 如果 |pk(i,j)C旳押,s(i,s爐,如果嚴(yán)山i 0其中，Tabuk是保存了每只螞蟻 k已經(jīng)到訪過的城市集合，Jk=N-TabUk,a, B是系統(tǒng)參數(shù)，分別表示信息素、距離對(duì)螞蟻的選擇路徑的影響程度。t (i,j)表示邊L(i,j) 上的信息度強(qiáng)度。：i, j表示由i到j(luò)的期望程度，一般為 1/dij。a =0的時(shí)候，為最鄰近城市選取概率最大。3 =0的時(shí)候，螞蟻完全只根據(jù)信息濃度確定路徑。第三步：更新信息在所

6、有螞蟻找到一條合法的路徑后對(duì)信息進(jìn)行更新。ij t 1 = 1 - p ij t 廠二t,t 1mQ-ij t,t 1 Lk,若螞蟻經(jīng)過i,j0,否則其中p為信息素的揮發(fā)速率，小于1的正數(shù)，可取0.5。'：ij表示螞蟻在本次運(yùn)行中留在路徑L(i , j)上的信息速度。./. ,.kij表示螞蟻k放置在邊上L(i , j)的信息速度。Q表示螞蟻所留軌跡為正常數(shù) （10,10000）。Lk表示第k只螞蟻在本次周游中所走過的路徑長度和。第四步：輸出結(jié)果若迭代次數(shù)小于預(yù)定的迭代次數(shù)，且無退化行為（找到的都是相同的解）則轉(zhuǎn)步驟二， 否則輸出目前的最優(yōu)解。四、數(shù)據(jù)實(shí)驗(yàn)及結(jié)果通過計(jì)算機(jī)仿真， 令參數(shù)

7、為m=31,a =1, 3 =5, p =0.5,NC_max=200,Q=100,城市的數(shù)目為31。如圖所示：五、結(jié)論本文設(shè)計(jì)了一種基于 MATLAB實(shí)現(xiàn)的蟻群算法，用以求解組合優(yōu)化難題中的典型代表旅 行商問題。對(duì)31個(gè)城市旅行商問題進(jìn)行了測(cè)試，所得結(jié)果能達(dá)到優(yōu)化作用，實(shí)現(xiàn)了本文的 研究目標(biāo)?？梢园l(fā)現(xiàn)蟻群算法的優(yōu)點(diǎn)：不依賴于所求問題的具體數(shù)學(xué)表達(dá)式描述，具有很強(qiáng)的找到全局最優(yōu)解的優(yōu)化能力，正反饋、較強(qiáng)的魯棒性、全局性、普遍性，優(yōu)良的分布式并行計(jì)算 機(jī)制，易于與其他方法相結(jié)合。缺點(diǎn)：模型普適性不強(qiáng)，不能直接應(yīng)用于實(shí)際優(yōu)化問題，局 部搜索能力較弱，易出現(xiàn)停滯和局部收斂、收斂速度慢等問題，長時(shí)間花費(fèi)在解的構(gòu)造上， 導(dǎo)致搜索時(shí)間過長，算法最先基于離散問題，不能直接解決連續(xù)優(yōu)化問題。由于蟻群算法對(duì)圖的對(duì)稱性以