tsp蟻群演算法
❶ 遺傳演算法和蟻群演算法在求解TSP問題上的對比分析
【原創】比遺傳演算法性能更好：蟻群演算法TSP(旅行商問題)通用matlab程序
聲明：本程序為本人原創，在研學論壇首次發表，本人保留一切權利，僅供學習交流用，如轉載請註明原作者！
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%=========================================================================
%% ACATSP.m
%% Ant Colony Algorithm for Traveling Salesman Problem
%% ChengAihua,PLA Information Engineering University,ZhengZhou,China
%% Email:[email protected]
%% All rights reserved
%%-------------------------------------------------------------------------
%% 主要符號說明
%% C n個城市的坐標，n×2的矩陣
%% NC_max 最大迭代次數
%% m 螞蟻個數
%% Alpha 表徵信息素重要程度的參數
%% Beta 表徵啟發式因子重要程度的參數
%% Rho 信息素蒸發系數
%% Q 信息素增加強度系數
%% R_best 各代最佳路線
%% L_best 各代最佳路線的長度
%%=========================================================================
%%第一步：變數初始化
n=size(C,1);%n表示問題的規模（城市個數）
D=zeros(n,n);%D表示完全圖的賦權鄰接矩陣
for i=1:n
for j=1:n
if i~=j
D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
else
D(i,j)=eps;
end
D(j,i)=D(i,j);
end
end
Eta=1./D;%Eta為啟發因子，這里設為距離的倒數
Tau=ones(n,n);%Tau為信息素矩陣
Tabu=zeros(m,n);%存儲並記錄路徑的生成
NC=1;%迭代計數器
R_best=zeros(NC_max,n);%各代最佳路線
L_best=inf.*ones(NC_max,1);%各代最佳路線的長度
L_ave=zeros(NC_max,1);%各代路線的平均長度
while NC<=NC_max%停止條件之一：達到最大迭代次數
%%第二步：將m只螞蟻放到n個城市上
Randpos=[];
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';
%%第三步：m只螞蟻按概率函數選擇下一座城市，完成各自的周遊
for j=2:n
for i=1:m
visited=Tabu(i,1:(j-1));%已訪問的城市
J=zeros(1,(n-j+1));%待訪問的城市
P=J;%待訪問城市的選擇概率分布
Jc=1;
for k=1:n
if length(find(visited==k))==0
J(Jc)=k;
Jc=Jc+1;
end
end
%下面計算待選城市的概率分布
for k=1:length(J)
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
end
P=P/(sum(P));
%按概率原則選取下一個城市
Pcum=cumsum(P);
Select=find(Pcum>=rand);
to_visit=J(Select(1));
Tabu(i,j)=to_visit;
end
end
if NC>=2
Tabu(1,:)=R_best(NC-1,:);
end
%%第四步：記錄本次迭代最佳路線
L=zeros(m,1);
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(j+1));
end
L(i)=L(i)+D(R(1),R(n));
end
L_best(NC)=min(L);
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:);
L_ave(NC)=mean(L);
NC=NC+1
%%第五步：更新信息素
Delta_Tau=zeros(n,n);
for i=1:m
for j=1:(n-1)
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
end
Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
end
Tau=(1-Rho).*Tau+Delta_Tau;
%%第六步：禁忌表清零
Tabu=zeros(m,n);
end
%%第七步：輸出結果
Pos=find(L_best==min(L_best));
Shortest_Route=R_best(Pos(1),:)
Shortest_Length=L_best(Pos(1))
subplot(1,2,1)
DrawRoute(C,Shortest_Route)
subplot(1,2,2)
plot(L_best)
hold on
plot(L_ave)
function DrawRoute(C,R)
%%=========================================================================
%% DrawRoute.m
%% 畫路線圖的子函數
%%-------------------------------------------------------------------------
%% C Coordinate 節點坐標，由一個N×2的矩陣存儲
%% R Route 路線
%%=========================================================================
N=length(R);
scatter(C(:,1),C(:,2));
hold on
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])
hold on
for ii=2:N
plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])
hold on
end
設置初始參數如下：
m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;
31城市坐標為：
1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
3238 1229
4196 1004
4312 790
4386 570
3007 1970
2562 1756
2788 1491
2381 1676
1332 695
3715 1678
3918 2179
4061 2370
3780 2212
3676 2578
4029 2838
4263 2931
3429 1908
3507 2367
3394 2643
3439 3201
2935 3240
3140 3550
2545 2357
2778 2826
2370 2975
運行後得到15602的巡遊路徑，
❷ 蟻群演算法求解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問題，獲得了成功，後來又廣泛應用於各類組合優化問題。但是該演算法理論基礎較薄弱，演算法收斂性都沒有得到證明，很多參數的設定也僅靠經驗，實際效果也一般，使用中也常常早熟。
遺傳演算法是比較成熟的演算法，它的全局尋優能力很強，能夠很快地趨近較優解。主要應用於解決組合優化的NP問題。
這三種演算法可以相互融合，例如GA可以優化神經網路初始權值，防止神經網路訓練陷入局部極小且加快收斂速度。蟻群演算法也可用於訓練神經網路，但一定要使用優化後的蟻群演算法，如最大-最小蟻群演算法和帶精英策略。
❹ 蟻群演算法求解tsp問題能設置不限城市數量嗎
如果不限制城市數量，需要找到自適應的演算法參數。
如果可以找到自適應演算法參數的情況下，或者說能得到與城市數量相關的參數設置函數，不限定城市數量應該也是可以的。
❺ 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矩陣的第二個和第三個數值就重復了。
❼ TSP中用蟻群演算法和遺傳演算法有區別么
TSP,只是一個普通但很經典的NP-C問題。具有大的難以想像的解空間。一般的branch-and-bound演算法是很難搞定的。於是,人們嘗試智能演算法,包括遺傳演算法,蟻群演算法,粒子群演算法等。遺傳演算法和蟻群演算法都是基於種群的。但是這兩個演算法有著本質區別。遺傳演算法的進化機制是基於個體競爭,而蟻群演算法的搜索機制則是螞蟻之間的信息素傳導機制下的群體合作。因此,蟻群演算法,粒子群演算法,人工魚群演算法等,被歸納為群智能演算法,成為了一個有別於遺傳演算法的另一個進化計算領域的分支。由於搜索機制的不同,這兩種演算法對於不同的問題,具有不同的效率。就拿標准遺傳演算法和標准蟻群演算法來說,應該是蟻群演算法更適合求解TSP。然而,無論是遺傳演算法還是蟻群演算法,都有大量的變種演算法或者稱為改進演算法,所以很難簡單的說誰更適合TSP。
記得採納啊
❽ 請教，採用蟻群演算法求解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問題怎麼編碼
n個城市，編號為1---n for循環的次數是螞蟻重復城市的次數