⑴ TSP中用蟻群演算法和遺傳演算法有區別么
TSP,只是一個普通但很經典的NP-C問題。具有大的難以想像的解空間。一般的branch-and-bound演算法是很難搞定的。於是,人們嘗試智能演算法,包括遺傳演算法,蟻群演算法,粒子群演算法等。遺傳演算法和蟻群演算法都是基於種群的。但是這兩個演算法有著本質區別。遺傳演算法的進化機制是基於個體競爭,而蟻群演算法的搜索機制則是螞蟻之間的信息素傳導機制下的群體合作。因此,蟻群演算法,粒子群演算法,人工魚群演算法等,被歸納為群智能演算法,成為了一個有別於遺傳演算法的另一個進化計算領域的分支。由於搜索機制的不同,這兩種演算法對於不同的問題,具有不同的效率。就拿標准遺傳演算法和標准蟻群演算法來說,應該是蟻群演算法更適合求解TSP。然而,無論是遺傳演算法還是蟻群演算法,都有大量的變種演算法或者稱為改進演算法,所以很難簡單的說誰更適合TSP。
記得採納啊
⑵ 急求 蟻群混合遺傳演算法在matlab上的實現以解決TSP旅行商的問題 小弟感激不盡
建立m文件
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%-------------------------------------------------------------------------
%% 主要符號說明
%% 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; %i=j時不計算，應該為0，但後面的啟發因子要取倒數，用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 %開始時置0
J(Jc)=k;
Jc=Jc+1; %訪問的城市個數自加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); %cumsum，元素累加即求和
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); %開始距離為0，m*1的列向量
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(j+1)); %原距離加上第j個城市到第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); %開始時信息素為n*n的0矩陣
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);
%此次循環在路徑（i，j）上的信息素增量
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)); %找到最佳路徑（非0為真）
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,'r')
title('平均距離和最短距離') %標題
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)],'g')
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)],'g')
hold on
end
title('旅行商問題優化結果 ')
建m文件
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)],'g')
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)],'g')
hold on
end
title('TSP問題優化結果 ')
命令窗口運行
C=[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
];
m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;
[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
⑶ 我在研究粒子群演算法，請問什麼叫粒子的適應度值啊
粒子的適應度就是指目標函數的值。一般來說，目標函數的選擇由具體問題來決定，假如是求最大值問題，適應度就是函數的大小，適應度當然越大越好。如果是TSP問題，路徑的距離就是粒子的適應度。