仿真的多目標優(yōu)化(蟻群算法在旅行商問題中的應用)

1、蟻群算法在旅行商問題中的應用（多目標優(yōu)化模型）蟻群算法在旅行商問題中的應用摘要本文將對蟻群算法的仿真學原理進行概要介紹和對蟻群算法產生、發(fā)展、優(yōu)化進行介紹以及闡述蟻群算法的幾點重要基本規(guī)則，并對蟻群算法的優(yōu)缺點進行討論。蟻群算法是受自然界中蟻群搜索食物行為啟發(fā)而提出的一種智能多目標優(yōu)化算法，通過介紹蟻群覓食過程中基于信息素的最短路徑的搜索策略，給出基于MATLAB的蟻群算法在旅行商問題中的應用。關鍵字：蟻群算法；旅行商問題；仿真；多目標優(yōu)化一、 問題重述旅行商問題(TSP)是一個經典的組合優(yōu)化問題。TSP可以描述為：一個商品推銷員要去若干個城市推銷商品， 該推銷員從一個城市出發(fā)， 需要經過所有

2、城市后，回到出發(fā)地。應如何選擇行進路線， 以使總的行程最短。從圖論的角度來看， 該問題實質是在一個帶權完全無向圖中， 找一個權值最小的Hamilton回路。由于該問題的可行解是所有頂點的全排列， 隨著頂點數(shù)的增加， 會產生組合爆炸， 它是一個N P完全問題。 隨著問題規(guī)模的增大，人們對復雜事物和復雜系統(tǒng)建立數(shù)學模型并進行求解的能力是有限的，目標函數(shù)和約束條件往往不能以明確的函數(shù)關系表達，或因函數(shù)帶有隨機參、變量，導致基于數(shù)學模型的優(yōu)化方法在應用于實際生產時，有其局限性甚至不適用。基于仿真的優(yōu)化(Simulation Based Optimization，SBO)方法正是在這樣的背景下發(fā)展起來的

3、。本文將使用一種近似算法或啟發(fā)式算法蟻族算法。1、蟻群算法的提出蟻群算法(Ant Colony Optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。 2、蟻群算法的仿生學原理蟻群算法最初是通過對螞蟻群落的觀察，受蟻群行為特 征啟發(fā)而得出的。螞蟻是一種群居昆蟲，在覓食、清理巢穴 征啟發(fā)而得出的。螞蟻是一種群居昆蟲，在覓食、 等活動中，彼此依賴、相互協(xié)作共同完成特定的任務。 等活動中，彼此依賴、相互協(xié)作共同完成特定的任務。就個 體來講，單個螞蟻的智

4、力和體力是極其有限的， 體來講，單個螞蟻的智力和體力是極其有限的，服務于整個 群落的生存與發(fā)展；就群體來講，蟻群在行為上的分工協(xié)作、 群落的生存與發(fā)展；就群體來講，蟻群在行為上的分工協(xié)作、 在完成任務過程中所體現(xiàn)的自組織特征等反應出蟻群具有較 高的智能和自我管理能力，具有很高層次組織性， 高的智能和自我管理能力，具有很高層次組織性，這使得蟻 群能夠完成一些復雜的任務。 群能夠完成一些復雜的任務。蟻群的行為是整體協(xié)作，相互分工，蟻群的行為是整體協(xié)作，相互分工，以一個整體去解決一 些對單個螞蟻看上去是不可能完成的任務。 些對單個螞蟻看上去是不可能完成的任務。就目前來講，蟻群至少有三個方面的行為特征

5、對算法研究有很好的啟發(fā)意義，分別是覓食行為、任務分配、死蟻堆積閣。蟻群的覓食行為指螞蟻從巢穴出發(fā)尋找食物并且將食物搬回巢穴的行為.當螞蟻出外尋找食物時，會在自己走過的路 徑上釋放一種稱為信息家的物質，徑上釋放一種稱為信息家的物質，后續(xù)的螞蟻一般更愿意走 那些信息素強度更高的路徑。這樣，那些信息素強度更高的路徑。這樣，較短路徑上單位時間內通過的螞蟻數(shù)目較多，留下的信息素也較多(濃度更高) 通過的螞蟻數(shù)目較多，留下的信息素也較多(濃度更高)，對螞蟻產生了更強的吸引，使得更多的螞蟻走較短的路徑。 媽蟻產生了更強的吸引，使得更多的螞蟻走較短的路徑。這 就形成了一個正反饋機制， 就形成了一個正反饋機制，

6、使得最終所有的螞蟻都走蟻穴到 食物源的最短路徑. 食物源的最短路徑. 3、蟻群算法實現(xiàn)的重要規(guī)則（1）范圍螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個方格世界，并且能移動的距離也在這個范圍之內。（2）環(huán)境螞蟻所在的環(huán)境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。（3）覓食規(guī)則在每只螞蟻能感知的范圍內尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在能感知的

7、范圍內哪一點的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻都會以小概率犯錯誤，從而并不是往信息素最多的點移動。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應，而對食物信息素沒反應。（4）移動規(guī)則每只螞蟻都朝向信息素最多的方向移，并且，當周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，并且，在運動的方向有一個隨機的小的擾動。為了防止螞蟻原地轉圈，它會記住最近剛走過了哪些點，如果發(fā)現(xiàn)要走的下一點已經在最近走過了，它就會盡量避開。（5）避障規(guī)則：如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，并且有信息素指引的話，它會按照覓食的規(guī)則行為。（6）播撒

8、信息素規(guī)則：每只螞蟻在剛找到食物或者窩的時候撒發(fā)的信息素最多，并隨著它走遠的距離，播撒的信息素越來越少。根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個紐帶，實際上把各個螞蟻之間關聯(lián)起來了。比如，當一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當其它的螞蟻經過它附近的時候，就會感覺到信息素的存在，進而根據(jù)信息素的指引找到了食物。二、問題分析旅行商問題的各個城市間的距離可以用代價矩陣來表示，就是鄰接矩陣表示法。如果，則。先說明旅行商問題具有最優(yōu)解結構。設是從s出發(fā)的一條路徑長度最短的簡單回路，假設從s到下一個城市已經求出，則

9、問題轉化為求到S的最短路徑，顯然一定構成一條從到S的最短路徑，如果不然，設是一條從到S的最短路徑且經過n-1個城市，則將是從S出發(fā)的路徑長度最短的簡單回路且比要短，從而導致矛盾。所以，旅行商問題一定滿足最優(yōu)性原理。四、符號說明序號符號12345678910C:NC_max：m：Alpha：Beta：Rho:Q:R_best:L_best：n個城市的坐標，n2的矩陣最大迭代次數(shù)各班人數(shù)各專業(yè)所分配的名額數(shù)螞蟻個數(shù)表征信息素重要程度的參數(shù)表征啟發(fā)式因子重要程度的參數(shù)信息素蒸發(fā)系數(shù)信息素增加強度系數(shù)各代最佳路線各代最佳路線的長度五、模型的建立與求解1.旅行商模型：為一個帶權圖,為頂點集,為邊集。為頂

10、點i到頂點j 的距離， 其中且，同時則經典TSP的數(shù)學模型為： 其中是圖s 的頂點數(shù)。（1）為ctsp的目標函數(shù),求經過所有頂點的回路的最小距離。（2）-（4）限定回路上每個頂點僅有一條入邊和一條出邊。( 5 ) 限定在回路中不出現(xiàn)子回路。模型實質上是在一個帶權圖中求一條H a m i l t o n回路。若對所有i，j,k V， 不等式均成立， 則稱該問題是滿足三角不等式的。2.螞蟻算法求解TSP 問題的具體過程如下：（1）首先初始化，設迭代次數(shù)為NC。初始化NC=0，各初始化； （2）將m 個螞蟻置于n 個頂點上；（3）構造解。每個螞蟻按照狀態(tài)變化規(guī)則逐步地構造一個解，即生成一條線路。螞蟻

11、任務是訪問所有的城市后回到起點，生成一條回路。設螞蟻k當前所在的頂點為i，那么，螞蟻k 由點i 向點j 移動要遵循（1）式的狀態(tài)變化規(guī)則而不斷遷移，按不同概率來選擇下一點。（1）式中，表示螞蟻k 當前能選擇的城市集合，為禁忌表，它記錄螞蟻k已路過的城市，用來說明人工螞蟻的記憶性 ；式中相當于真實螞蟻沿途散播的信息素，是一個正實數(shù)，與圖G中弧（i，j）關聯(lián)，其值在運行時不斷改變，用于表示螞蟻從點i向點j移動的動力；用于評價螞蟻從點i 向點j 移動的啟發(fā)函數(shù)，其值通常用距離的倒數(shù)來求得，即。體現(xiàn)了信息素和啟發(fā)信息對螞蟻決策的影響。取值為1；參數(shù)描述啟發(fā)函數(shù)的重要性；參數(shù)決定利用和開發(fā)的相對重要性，

12、利用（Exploitation）是指走最好的路，開發(fā)（Exploration）是指按濃度高概率高的原則選路V，這樣可以保證選擇路徑的多樣性；q 是在0，1 取的隨機數(shù)，當時，按（1）式選最好的路，否則按（2）式的概率進行選路：（4）局部更新信息素值。應用局部信息素更新規(guī)則來改變信息素值。在構造解時，螞蟻k 對其走過的每條弧用：局部信息素更新規(guī)則來改變弧上關聯(lián)的信息素值，其中是信息素揮發(fā)參數(shù)。（5）若所有的m個螞蟻都構造完解，則轉（6） ；否則轉（3） ；（6）全局更新信息素值。應用全局信息素更新規(guī)則來改變信息素值。當所有m 個螞蟻生成了m 個解，其中有一條最短路徑是本代最優(yōu)解，將屬于這條路線上

13、的所有弧相關聯(lián)的信息素值按下式更新：其中是揮發(fā)參數(shù)；是目前得到的全局最優(yōu)解的路線長度。全局信息素更新的目的是在最短路線上注入額外的信息素，即只有屬于最短路線的弧上的信息素才能得到加強，這是一個正反饋的過程，也是一個強化學習的過程。在圖中各弧上，伴隨著信息素的揮發(fā)，全局最短路線上各弧的信息素值得到增加；（7）終止。若終止條件滿足，則結束；否則NC=NC+1，轉（2）進行下一代進化。終止條件可指定進化的代數(shù)，也可限定運行時間，或設定最短路長的下限。例：一個商品推銷員要去若干個城市推銷商品， 該推銷員從一個城市出發(fā)， 需要經過所有城市后，回到出發(fā)地。應如何選擇行進路線， 以使總的行程最短。城市坐標城

14、市坐標123456789行值304639177 712 488 326 238 196 312 列植312315244399535556229104790城市坐標101112131415161718行值386 107 562 788 381 332 715 918 161 列植570970756491676695678179370城市坐標192021222324252627行值780 676 329 263 429 507 394439935列植212578838931908367643201240城市坐標28293031行值140545778370列植550357826975應用上面的步鄹可

15、以解出最短路徑出來，相應的程序見附件，結果為：最短路徑圖每次循環(huán)最短路徑長度和平均路徑長度圖得出：15-14-25-10-6-28-18-3-7-1-26-8-19-17-27-13-4-2-29-24-5-20-16 22-11-21-9的和最短路徑線路 六、模型評價蟻群算法（ACA） 不僅利用了正反饋原理, 在一定程度上可以加快進化過程, 而且是一種本質并行的算法, 個體之間不斷進行信息交流和傳遞, 有利于發(fā)現(xiàn)較好解.單個個體容易收斂于局部最優(yōu), 但多個個體通過合作, 很快收斂于解空間的某一子集, 有利于對解空間的進一步探索, 從而不易陷入局部最優(yōu)。但是ACA也具有速度慢、易陷入局部最優(yōu)等

16、缺點。蟻群中多個個體的運動是隨機的, 當群體規(guī)模較大時, 要找出一條較好的路徑需要較長的搜索時間。七、參考文獻1 陳文蘭,戴樹貴.旅行商問題算法研究綜述.滁州學院學報,2006年，第8卷：1-62 尹曉峰,劉春煌,張睢皎. 基于MATLAB的混合型蟻群算法求解車輛路徑問題鐵道部科學研究院電子所,2005年，第14卷：32-423 薛定宇,陳陽泉.高等應用數(shù)學問題的MATLAB求解.北京：清華大學出版社，2011，197-2094 司守奎.數(shù)學建模算法.大連：海軍航空工程學院出版社，2007，395-411八、附件蟻群算法求解旅行商問題的matlab程序：clear；clc；%初始化蟻群m=31

17、;%蟻群中螞蟻的數(shù)量，當m接近或等于城市個數(shù)n時，本算法可以在最少的迭代次數(shù)內找到最優(yōu)解C=304 312;639 315;177 244;712 399;488 535;326 556;238 229;196 104;312 790;386 570;107 970;562 756;788 491;381 676;332 695;715 678;918 179;161 370;780 212;676 578;329 838;263 931;429 908;507 367;394 643;439 201;935 240;140 550;545 357;778 826;370 975;%城市的坐標

18、矩陣Nc_max=200;%最大循環(huán)次數(shù)，即算法迭代的次數(shù)，亦即螞蟻出動的撥數(shù)（每撥螞蟻的數(shù)量當然都是m）alpha=1;%螞蟻在運動過程中所積累信息（即信息素）在螞蟻選擇路徑時的相對重要程度，alpha過大時，算法迭代到一定代數(shù)后將出現(xiàn)停滯現(xiàn)象beta=5;%啟發(fā)式因子在螞蟻選擇路徑時的相對重要程度rho=0.5;%0rho1,表示路徑上信息素的衰減系數(shù)（亦稱揮發(fā)系數(shù)、蒸發(fā)系數(shù)），1-rho表示信息素的持久性系數(shù)Q=100;%螞蟻釋放的信息素量，對本算法的性能影響不大%變量初始化n=size(C,1);%表示TSP問題的規(guī)模，亦即城市的數(shù)量D=ones(n,n);%表示城市完全地圖的賦權鄰接

19、矩陣，記錄城市之間的距離for i=1:nfor j=1:nif ijD(i,j)=sqrt(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)2);endD(j,i)=D(i,j);endendeta=1./D;%啟發(fā)式因子，這里設為城市之間距離的倒數(shù)pheromone=ones(n,n);%信息素矩陣,這里假設任何兩個城市之間路徑上的初始信息素都為1tabu_list=zeros(m,n);%禁忌表，記錄螞蟻已經走過的城市，螞蟻在本次循環(huán)中不能再經過這些城市。當本次循環(huán)結束后，禁忌表被用來計算螞蟻當前所建立的解決方案，即經過的路徑和路徑的長度Nc=0;%循環(huán)次數(shù)計數(shù)器routh_b

20、est=zeros(Nc_max,n);%各次循環(huán)的最短路徑length_best=ones(Nc_max,1);%各次循環(huán)最短路徑的長度length_average=ones(Nc_max,1);%各次循環(huán)所有路徑的平均長度while Ncq0for k=1:length(city_remained)probability(k)=(pheromone(city_visited(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(k)beta;position=find(probability=max(probabil

21、ity);to_visit=city_remained(position(1);endelsefor k=1:length(city_remained)probability(k)=(pheromone(city_visited(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(k)beta;endprobability=probability/sum(probability);pcum=cumsum(probability);select=find(pcum=rand);to_visit=city_remained

22、(select(1);endtabu_list(i,j)=to_visit;%*endendif Nc0tabu_list(1,:)=routh_best(Nc,:);%將上一代的最優(yōu)路徑（最優(yōu)解）保留下來，保證上一代中的最適應個體的信息不會丟失end%記錄本次循環(huán)的最佳路線total_length=zeros(m,1);%m只螞蟻在本次循環(huán)中分別所走過的路徑長度for i=1:mr=tabu_list(i,:);%取出第i只螞蟻在本次循環(huán)中所走的路徑for j=1:(n-1)total_length(i)=total_length(i)+D(r(j),r(j+1);%第i只螞蟻本次循環(huán)中從起

23、點城市到終點城市所走過的路徑長度endtotal_length(i)=total_length(i)+D(r(1),r(n);%最終得到第i只螞蟻在本次循環(huán)中所走過的路徑長度endlength_best(Nc+1)=min(total_length);%把m只螞蟻在本次循環(huán)中所走路徑長度的最小值作為本次循環(huán)中最短路徑的長度position=find(total_length=length_best(Nc+1);%找到最短路徑的位置，即最短路徑是第幾只螞蟻或哪幾只螞蟻走出來的routh_best(Nc+1,:)=tabu_list(position(1),:);%把第一個走出最短路徑的螞蟻在本次

24、循環(huán)中所走的路徑作為本次循環(huán)中的最優(yōu)路徑length_average(Nc+1)=mean(total_length);%計算本次循環(huán)中m只螞蟻所走路徑的平均長度Nc=Nc+1%更新信息素delta_pheromone=zeros(n,n);for i=1:mfor j=1:(n-1)delta_pheromone(tabu_list(i,j),tabu_list(i,j+1)=delta_pheromone(tabu_list(i,j),tabu_list(i,j+1)+Q/total_length(i);%total_length(i)為第i只螞蟻在本次循環(huán)中所走過的路徑長度（蟻周系統(tǒng)區(qū)別于蟻密系統(tǒng)和蟻量系統(tǒng)的地方）enddelta_pheromone(tabu_list(i,n),tabu_list(i,1)=delta_pheromone(tabu_list(i,n),tabu_list(i,1)+Q/total_length(i);%至此把第i只螞蟻在本次循環(huán)中在所有路徑上釋放的信息素已經累加上去end%至此把m只螞蟻在本次循環(huán)中在所有