當前位置:首頁 » 操作系統 » 蟻群演算法求解tsp

蟻群演算法求解tsp

發布時間: 2023-02-01 07:04:03

① MATLAB 蟻群演算法求解TSP問題

n個城市,編號為1---n
for循環的次數是螞蟻重復城市的次數,比如5個螞蟻放到4個城市,需要重復兩遍才能放完螞蟻,每次循環產生n個1---n的隨機數,相當於隨機n個城市,產生城市序列
循環結束
Tabu一句表示將m個螞蟻隨機,每個螞蟻放到前面產生的城市序列中,每個螞蟻一個城市,需要m個,所以提取前面1:m個序列
'表示轉置,沒有多大用處,可能參與後面的計算方便。
我感覺如果m,n很大的話,你這樣做會產生很大的浪費,計算很多的隨機數,這樣的話更好,一句就得:(如果變數Randpos後面沒有用到的話,如果用到了,還要用你的程序)
Tabu=ceil(n*rand(1,m))'

② 蟻群演算法求解TSP問題遇到「索引超出矩陣維度。」的問題跪求大神能解答

你檢查一下坐標矩陣是否出現了重復數值。比如你給的例子中C矩陣的第二個和第三個數值就重復了。

③ 蟻群演算法

在螞蟻種群中,螞蟻間相互交流的方式是通過一種名為信息素的物質,它可以是螞蟻行動時留下的物質,可以被其他螞蟻所感知。

在尋找食物的過程中,如左圖所示,三角形ABC是等邊三角形,螞蟻窩在A點,C點有食物,A點的兩只螞蟻選擇了兩條路線前往C點,一條為AB->BC,另一條A->C,當走遠路的螞蟻,到達C點時,延AC邊上的螞蟻已經走了一個來回,路徑上信息素如右圖所示。後到會感知到邊AC上的信息素濃度更高一些,於是他也會選擇AC來行走,因為相同時間內,信息素濃度更高的說明,路程更短。

蟻群演算法便是基於這樣的一個思想來解決如TSP等優化問題,一下介紹便是拿TSP問題來介紹蟻群演算法

信息素用符號τ來表示,如下式,下標i,j表示從城市i到城市j這條道路上的信息素,上標0表示這是初次計算,也就是初始信息素,初始信息素都設置為1,或者一個較小的常數,表示每條道路上的信息素都相等,這樣通過運算螞蟻爬向各個城市的概率都相等

基於信息素,每隻螞蟻都有一個選擇道路的公式,如下式

其中

當所有螞蟻完成一次周遊後,各個路徑上的信息素進行一次更新

④ 請教,採用蟻群演算法求解TSP問題的oliver30最優路徑

給你產考產考//蟻群演算法關於簡單的TSP問題求解//#include#include#include#include#include#defineM13//螞蟻的數量#defineN144//城市的數量#defineR1000//迭代次數#defineIN1//初始化的信息素的量#defineMAX0x7fffffff//定義最大值structcoordinate{charcity[15];//城市名intx;//城市相對橫坐標inty;//城市相對縱坐標}coords[N];doublegraph[N][N];//儲存城市之間的距離的鄰接矩陣,自己到自己記作MAXdoublephe[N][N];//每條路徑上的信息素的量doubleadd[N][N];//代表相應路徑上的信息素的增量doubleyita[N][N];//啟發函數,yita[i][j]=1/graph[i][j]intvis[M][N];//標記已經走過的城市intmap[M][N];//map[K][N]記錄第K只螞蟻走的路線doublesolution[M];//記錄某次循環中每隻螞蟻走的路線的距離intbestway[N];//記錄最近的那條路線doublebestsolution=MAX;intNcMax;//代表迭代次數,理論上迭代次數越多所求的解更接近最優解,最具有說服力doublealpha,betra,rou,Q;voidInitialize();//信息初始化voidInputcoords(FILE*fp);//將文件中的坐標信息讀入voidGreateGraph();//根據坐標信息建圖doubleDistance(int*p);//計算螞蟻所走的路線的總長度voidResult();//將結果保存到out.txt中voidInitialize(){alpha=2;betra=2;rou=0.7;Q=5000;NcMax=R;return;}voidInputcoords(FILE*fp){inti;intnumber;if(fp==NULL){printf("Sorry,thefileisnotexist\n");exit(1);}else{for(i=0;idrand)break;}vis[k][j]=1;//將走過的城市標記起來map[k][s]=j;//記錄城市的順序}s++;}memset(add,0,sizeof(add));for(k=0;k20)//設立一個上界,防止啟發因子的作用被淹沒phe[i][j]=20;}}memset(vis,0,sizeof(vis));memset(map,-1,sizeof(map));}Result();printf("Resultissavedinout.txt\n");return0;}

⑤ TSP解決之道——蟻群演算法

蟻群演算法java實現以及TSP問題蟻群演算法求解

蟻群演算法原理與應用講解

蟻群演算法原理與應用1 -自然計算與群體智能

1、蟻群演算法(Ant Clony Optimization,ACO)是一種群智能演算法,它是由一群無智能或有輕微智能的個體(Agent)通過相互協作而表現出智能行為,從而為求解復雜問題提供了一個新的可能性。

2、是一種仿生學的演算法,是由自然界中螞蟻覓食的行為而啟發。(artificial ants;雙橋實驗)

3、運作機理:當一定路徑上通過的螞蟻越來越多時,其留下的信息素軌跡也越來越多,後來螞蟻選擇該路徑的概率也越高,從而更增加了該路徑的信息素強度,而強度大的信息素會吸引更多的螞蟻,從而形成一種正反饋機制。

4、蟻群演算法歐化過程中的兩個重要原則:

     a、螞蟻在眾多路徑中轉移路線的選擇規則。

     b、全局化信息素更新規則。信息素更新的實質就是人工螞蟻根據真實螞蟻在訪問過的邊上留下的信息素和蒸發的信息素來模擬真實信息素數量的變化,從而使得越好的解得到越多的增強。這就形成了一種自催化強化學習(Autocatalytic Reinforcement Learning)的正反饋機制。

1、描述:螞蟻數量m;城市之間的信息素矩陣pheromone;每次迭代的m個螞蟻的最短路徑    BestLength;最佳路徑BestTour。                                                                                                                                     每隻螞蟻都有 :禁忌表(Tabu)存儲已訪問過的城市,允許訪問的城市表(Allowed)存儲還可以訪問的城市,矩陣( Delta )來存儲它在一個循環(或者迭代)中給所經過的路徑釋放的信息素。

2、 狀態轉移概率 :在搜索過程中,螞蟻根據各條路徑上的信息量及路徑的啟發信息來計算狀態轉移概率。在t時刻螞蟻k由元素(城市)i轉移到元素(城市)j的狀態轉移概率:

τij (t) :時刻路徑(i, j)上的信息量。ηij=1/dij :啟發函數。

α為信息啟發式因子 ,表示軌跡的相對重要性,反映了螞蟻在運動過程中積累的信息在螞蟻運動時所起的作用,其值越大,則該螞蟻越傾向於選擇其它螞蟻經過的路徑,螞蟻之間的協作性越強;

β為期望啟發式因子 ,表示能見度的相對重要性,反映螞蟻在運動過程中啟發信息在螞蟻選擇路徑中的受重視程度,其值越大,則該狀態狀態轉移概率越接近於貪心規則;

3、 息素更新規則 :

ρ表示信息素揮發系數;Δτij(t)表示本次循環中路徑(i, j)上的信息素增量,初始時刻Δτij(t) =0。

4、三種信息增量計算方法:

區別:第一種利用了全局信息,在走一圈後更新。二、三中都利用的是局部信息。通常使用第一種。

5、TSP中流程圖

⑥ TSP中用蟻群演算法和遺傳演算法有區別么

TSP,只是一個普通但很經典的NP-C問題。具有大的難以想像的解空間。一般的branch-and-bound演算法是很難搞定的。於是,人們嘗試智能演算法,包括遺傳演算法,蟻群演算法,粒子群演算法等。遺傳演算法和蟻群演算法都是基於種群的。但是這兩個演算法有著本質區別。遺傳演算法的進化機制是基於個體競爭,而蟻群演算法的搜索機制則是螞蟻之間的信息素傳導機制下的群體合作。因此,蟻群演算法,粒子群演算法,人工魚群演算法等,被歸納為群智能演算法,成為了一個有別於遺傳演算法的另一個進化計算領域的分支。由於搜索機制的不同,這兩種演算法對於不同的問題,具有不同的效率。就拿標准遺傳演算法和標准蟻群演算法來說,應該是蟻群演算法更適合求解TSP。然而,無論是遺傳演算法還是蟻群演算法,都有大量的變種演算法或者稱為改進演算法,所以很難簡單的說誰更適合TSP。
記得採納啊

⑦ 蟻群演算法解決TSP問題,最優解是多少,參數如何選擇

概念:蟻群演算法(ant colony optimization, ACO),又稱螞蟻演算法,是一種用來在圖中尋找優化路徑的機率型演算法。它由Marco Dorigo於1992年在他的博士論文中提出,其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。蟻群演算法是一種模擬進化演算法,初步的研究表明該演算法具有許多優良的性質.針對PID控制器參數優化設計問題,將蟻群演算法設計的結果與遺傳演算法設計的結果進行了比較,數值模擬結果表明,蟻群演算法具有一種新的模擬進化優化方法的有效性和應用價值

其原理:為什麼小小的螞蟻能夠找到食物?他們具有智能么?設想,如果我們要為螞蟻設計一個人工智慧的程序,那麼這個程序要多麼復雜呢?首先,你要讓螞蟻能夠避開障礙物,就必須根據適當的地形給它編進指令讓他們能夠巧妙的避開障礙物,其次,要讓螞蟻找到食物,就需要讓他們遍歷空間上的所有點;再次,如果要讓螞蟻找到最短的路徑,那麼需要計算所有可能的路徑並且比較它們的大小,而且更重要的是,你要小心翼翼的編程,因為程序的錯誤也許會讓你前功盡棄。這是多麼不可思議的程序!太復雜了,恐怕沒人能夠完成這樣繁瑣冗餘的程序

應用范圍:螞蟻觀察到的范圍是一個方格世界,螞蟻有一個參數為速度半徑(一般是3),那麼它能觀察到的范圍就是3*3個方格世界,並且能移動的距離也在這個范圍之內

引申:跟著螞蟻的蹤跡,你找到了什麼?通過上面的原理敘述和實際操作,我們不難發現螞蟻之所以具有智能行為,完全歸功於它的簡單行為規則,而這些規則綜合起來具有下面兩個方面的特點: 1、多樣性 2、正反饋 多樣性保證了螞蟻在覓食的時候不置走進死胡同而無限循環,正反饋機制則保證了相對優良的信息能夠被保存下來。我們可以把多樣性看成是一種創造能力,而正反饋是一種學習強化能力。正反饋的力量也可以比喻成權威的意見,而多樣性是打破權威體現的創造性,正是這兩點小心翼翼的巧妙結合才使得智能行為涌現出來了。 引申來講,大自然的進化,社會的進步、人類的創新實際上都離不開這兩樣東西,多樣性保證了系統的創新能力,正反饋保證了優良特性能夠得到強化,兩者要恰到好處的結合。如果多樣性過剩,也就是系統過於活躍,這相當於螞蟻會過多的隨機運動,它就會陷入混沌狀態;而相反,多樣性不夠,正反饋機制過強,那麼系統就好比一潭死水。這在蟻群中來講就表現為,螞蟻的行為過於僵硬,當環境變化了,螞蟻群仍然不能適當的調整。 既然復雜性、智能行為是根據底層規則涌現的,既然底層規則具有多樣性和正反饋特點,那麼也許你會問這些規則是哪裡來的?多樣性和正反饋又是哪裡來的?我本人的意見:規則來源於大自然的進化。而大自然的進化根據剛才講的也體現為多樣性和正反饋的巧妙結合。而這樣的巧妙結合又是為什麼呢?為什麼在你眼前呈現的世界是如此栩栩如生呢?答案在於環境造就了這一切,之所以你看到栩栩如生的世界,是因為那些不能夠適應環境的多樣性與正反饋的結合都已經死掉了,被環境淘汰了! 蟻群演算法的實現 下面的程序開始運行之後,螞蟻們開始從窩里出動了,尋找食物;他們會順著屏幕爬滿整個畫面,直到找到食物再返回窩。 其中,『F』點表示食物,『H』表示窩,白色塊表示障礙物,『+』就是螞蟻了。

具體參考http://ke..com/view/539346.htm
希望對你有幫助,謝謝。

⑧ 在MATLAB中用蟻群演算法求解TSP問題,在經典的代碼中有Tabu(1,:)=R_best(NC-1,:)。不明白代碼的目的。

正在做。我是這樣理解的:
if NC >= 2
Tabu(1,:) = R_best(NC-1,:);
%把上一次迭代中最佳路線經歷的城市放到本次Tabu的第一行
%相當是加了一個約束條件,如果本次迭代的情況不好,至少不會按照不好的最優解去更新信息素,讓下次的情況更差
end

⑨ 蟻群演算法求解TSP問題的源程序及簡要說明

簡單蟻群演算法求解TSP的源程序(我幫你找的)

蟻群演算法是新興的仿生演算法,最初是由義大利學者Dorigo M於1991年首次提出,由於具有較強的魯棒性,優良的分布式計算機制和易於與其它方法結合等優點,成為人工智慧領域的一個研究熱點。本程序是實現簡單的蟻群演算法,TSP問題取的是att48,可從http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95獲取,程序運行時間可能會比較長,在我的這台CPU 1.6G+內存256M的機器上運行時間大概是13分鍾左右。我用的語言是MATLAB 7.1。此程序僅供學習所用,如有問題請反饋。謝謝。(註:程序沒有計算最後一個城市回來起點城市的距離)

function [y,val]=QACS
tic
load att48 att48;
MAXIT=300; % 最大循環次數
NC=48; % 城市個數
tao=ones(48,48);% 初始時刻各邊上的信息最為1
rho=0.2; % 揮發系數
alpha=1;
beta=2;
Q=100;
mant=20; % 螞蟻數量
iter=0; % 記錄迭代次數
for i=1:NC % 計算各城市間的距離
for j=1:NC
distance(i,j)=sqrt((att48(i,2)-att48(j,2))^2+(att48(i,3)-att48(j,3))^2);
end
end
bestroute=zeros(1,48); % 用來記錄最優路徑
routelength=inf; % 用來記錄當前找到的最優路徑長度
% for i=1:mant % 確定各螞蟻初始的位置
% end
for ite=1:MAXIT
for ka=1:mant %考查第K只螞蟻
deltatao=zeros(48,48); % 第K只螞蟻移動前各邊上的信息增量為零
[routek,lengthk]=travel(distance,tao,alpha,beta);
if lengthk<routelength % 找到一條更好的路徑
routelength=lengthk;
bestroute=routek;
end
for i=1:NC-1 % 第K只螞蟻在路徑上釋放的信息量
deltatao(routek(i),routek(i+1))=deltatao(routek(i),routek(i+1))+Q/lengthk;
end
deltatao(routek(48),1)=deltatao(routek(48),1)+Q/lengthk;
end
for i=1:NC-1
for j=i+1:NC
if deltatao(i,j)==0
deltatao(i,j)=deltatao(j,i);
end
end
end
tao=(1-rho).*tao+deltatao;
end
y=bestroute;
val=routelength;
toc

function [y,val]=travel(distance,tao,alpha,beta) % 某隻螞蟻找到的某條路徑
[m,n]=size(distance);
p=fix(m*rand)+1;
val=0; % 初始路徑長度設為 0
tabuk=[p]; % 假設該螞蟻都是從第 p 個城市出發的
for i=1:m-1
np=tabuk(length(tabuk)); % 螞蟻當前所在的城市號
p_sum=0;
for j=1:m
if isin(j,tabuk)
continue;
else
ada=1/distance(np,j);
p_sum=p_sum+tao(np,j)^alpha*ada^beta;
end
end
cp=zeros(1,m); % 轉移概率
for j=1:m
if isin(j,tabuk)
continue;
else
ada=1/distance(np,j);
cp(j)=tao(np,j)^alpha*ada^beta/p_sum;
end
end
NextCity=pchoice(cp);
tabuk=[tabuk,NextCity];
val=val+distance(np,NextCity);
end
y=tabuk;

function y=isin(x,A) % 判斷數 x 是否在向量 A 中,如在返回 1 ,否則返回 0
y=0;
for i=1:length(A)
if A(i)==x
y=1;
break;
end
end

function y=pchoice(A)
a=rand;
tempA=zeros(1,length(A)+1);
for i=1:length(A)
tempA(i+1)=tempA(i)+A(i);
end
for i=2:length(tempA)
if a<=tempA(i)
y=i-1;
break;
end
end

⑩ 蟻群演算法求解tsp問題能設置不限城市數量嗎

如果不限制城市數量,需要找到自適應的演算法參數。
如果可以找到自適應演算法參數的情況下,或者說能得到與城市數量相關的參數設置函數,不限定城市數量應該也是可以的。

熱點內容
我老爸的密碼是什麼 發布:2024-03-29 20:03:50 瀏覽:247
資料庫定義實驗 發布:2024-03-29 19:52:20 瀏覽:578
如何除去安卓手機的馬賽克 發布:2024-03-29 19:52:16 瀏覽:584
網站緩存設置 發布:2024-03-29 19:47:20 瀏覽:798
在jsp中使用資料庫 發布:2024-03-29 19:29:01 瀏覽:786
dns伺服器江川區ip地址 發布:2024-03-29 18:47:53 瀏覽:328
sql統計百分比 發布:2024-03-29 18:47:14 瀏覽:692
javatoolsfor 發布:2024-03-29 18:17:55 瀏覽:900
linuxi2c驅動 發布:2024-03-29 18:09:56 瀏覽:672
junit源碼下載 發布:2024-03-29 18:00:10 瀏覽:526