✅作者简介：热爱科研的Matlab仿真开发者，修心和技术同步精进，matlab项目合作可私信。
🍎个人主页：Matlab科研工作室
🍊个人信条：格物致知。
更多Matlab仿真内容点击👇
⛄ 内容介绍
旅行商问题,即TSP问题(Trav01ingSalegmanProblem)是数学领域中著名问题之一,这是一个NP难题也是一个著名的组合优化问题.它广泛地应用于电力系统故障诊断,国防武器一目标分配(weapon—targetassignment)问题等领域.蚁群算法是模仿蚂蚁在寻找食物过程中的行为而形成的一种寻找优化路径的机率型模拟进化算法,经研究表明该算法具有许多优良的性质,具有一定的有效性和应用价值.根据蚂蚁寻找食物的行为和旅行商活动的相似性,利用蚁群算法可以求解旅行商问题,从而找到最短路径,实现最优解.
⛄ 部分代码
%蚁群算法求解TSP问题的matlab程序
clear all
close all
clc
% 程序运行计时开始
t0 = clock;
%初始化蚁群
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
]; %%31个省会坐标
Nc_max=100;%最大循环次数，即算法迭代的次数，亦即蚂蚁出动的拨数（每拨蚂蚁的数量当然都是m）
alpha=1;%蚂蚁在运动过程中所积累信息（即信息素）在蚂蚁选择路径时的相对重要程度，alpha过大时，算法迭代到一定代数后将出现停
beta=5;%启发式因子在蚂蚁选择路径时的相对重要程度
rho=0.2;%0<rho<1,表示路径上信息素的衰减系数（亦称挥发系数、蒸发系数），1-rho表示信息素的持久性系数
Q=100;%蚂蚁释放的信息素量，对本算法的性能影响不大
m=192;%蚁群中蚂蚁的数量，当m接近或等于城市个数n时，本算法可以在最少的迭代次数内找到最优解
%变量初始化
n=size(C,1);%表示TSP问题的规模，亦即城市的数量
D=ones(n,n);%表示城市完全地图的赋权邻接矩阵，记录城市之间的距离
for i=1:n
for j=1:n
if i<j
D(i,j)=sqrt((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2);
end
D(j,i)=D(i,j);
end
end
eta=1./D;%启发式因子，这里设为城市之间距离的倒数
max_ph=1000;
min_ph=0;
pheromone=max_ph.*ones(n,n);%信息素矩阵
tabu_list=zeros(m,n);%禁忌表，记录蚂蚁已经走过的城市，蚂蚁在本次循环中不能再经过这些城市。当本次循环结束后，禁忌表被用来
repeat=0;
scale=1;
Nc=0;%循环次数计数器
routh_best=zeros(Nc_max,n);%各次循环的最短路径
length_best=ones(Nc_max,1);%各次循环最短路径的长度
length_average=ones(Nc_max,1);%各次循环所有路径的平均长度
while Nc<Nc_max
%将m只蚂蚁放在n个城市上
rand_position=[];
for i=1:ceil(m/n)
rand_position=[rand_position,randperm(n)];
end
tabu_list(:,1)=(rand_position(1:m))';%将蚂蚁放在城市上之后的禁忌表，第i行表示第i只蚂蚁，第i行第一列元素表示第i只蚂蚁
%m只蚂蚁按概率函数选择下一座城市，在本次循环中完成各自的周游
for j=2:n
for i=1:m
city_visited=tabu_list(i,1:(j-1));%已访问的城市
city_remained=zeros(1,(n-j+1));%待访问的城市
probability=city_remained;%待访问城市的访问概率
cr=1;
for k=1:n%for循环用于求待访问的城市。比如如果城市个数是5，而已访问的城市city_visited=[2 4],则经过此for循环后
if length(find(city_visited==k))==0
city_remained(cr)=k;
cr=cr+1;
end
end
%状态转移规则****************************************
q0=0.5;
if rand>q0
for 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(probability));
to_visit=city_remained(position(1));
end
else
for k=1:length(city_remained)
probability(k)=(pheromone(city_visited(end),city_remained(k)))^alpha*(eta(city_visited(end),city_remained(k)))^beta;
end
probability=probability/sum(probability);
pcum=cumsum(probability);
select=find(pcum>=rand);
to_visit=city_remained(select(1));
end
tabu_list(i,j)=to_visit;
%**************************************************************
end
end
if Nc>0
tabu_list(1,:)=routh_best(Nc,:);%将上一代的最优路径（最优解）保留下来，保证上一代中的最适应个体的信息不会丢失
end
%记录本次循环的最佳路线
total_length=zeros(m,1);%m只蚂蚁在本次循环中分别所走过的路径长度
for i=1:m
r=tabu_list(i,:);%取出第i只蚂蚁在本次循环中所走的路径
for j=1:(n-1)
total_length(i)=total_length(i)+D(r(j),r(j+1));%第i只蚂蚁本次循环中从起点城市到终点城市所走过的路径长度
end
total_length(i)=total_length(i)+D(r(1),r(n));%最终得到第i只蚂蚁在本次循环中所走过的路径长度
end
length_best(Nc+1)=min(total_length); %把m只蚂蚁在本次循环中所走路径长度的最小值作为本次循环中最短路径的长度
position1=find(total_length==length_best(Nc+1));%找到最短路径的位置，即最短路径是第几只蚂蚁或哪几只蚂蚁走出来的
routh_best(Nc+1,:)=tabu_list(position1(1),:);%把第一个走出最短路径的蚂蚁在本次循环中所走的路径作为本次循环中的最优路径
length_average(Nc+1)=mean(total_length);%计算本次循环中m只蚂蚁所走路径的平均长度
f_best=length_best(1)
if f_best>length_best(Nc+1)
f_best=length_best(Nc+1)
end
%更新信息素
delta_pheromone=zeros(n,n);
for j=1:n-1
delta_pheromone(tabu_list(position(1),j),tabu_list(position(1),j+1))=delta_pheromone(tabu_list(position(1),j),tabu_list(position(1),j+1))+1/log(length_best(Nc+1));
delta_pheromone(tabu_list(position(1),n),tabu_list(position(1),1))=delta_pheromone(tabu_list(position(1),n),tabu_list(position(1),1))+1/log(length_best(Nc+1));
if mod(Nc,5)==0
delta_pheromone(tabu_list(position(1),j),tabu_list(position(1),j+1))=delta_pheromone(tabu_list(position(1),j),tabu_list(position(1),j+1))+1/log(f_best);
delta_pheromone(tabu_list(position(1),n),tabu_list(position(1),1))=delta_pheromone(tabu_list(position(1),n),tabu_list(position(1),1))+1/log(f_best);
end
end%至此把m只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去
%t=sigmf(Nc,[-0.01 Nc_max/2])
pheromone=0.6.*pheromone+delta_pheromone;
max_ph=max(pheromone(1,:));
min_ph=max_ph/(2*n);
for i=1:n
for j=1:n
if(pheromone(i,j)>max_ph)
pheromone(i,j)=max_ph;
end
if(pheromone(i,j)<min_ph)
pheromone(i,j)=min_ph;
end
end
end
tabu_list=zeros(m,n);
Nc=Nc+1
end
%输出结果，绘制图形
position=find(length_best==min(length_best));
shortest_path=routh_best(position(1),:)
shortest_length=length_best(position(1))
%绘制最短路径
figure(1)
set(gcf,'Name','Ant Colony Optimization——Figure of shortest_path','Color','r')
N=length(shortest_path);
scatter(C(:,1),C(:,2),10,'filled');
hold on
plot([C(shortest_path(1),1),C(shortest_path(N),1)],[C(shortest_path(1),2),C(shortest_path(N),2)])
set(gca,'Color','g')
hold on
for i=2:N
plot([C(shortest_path(i-1),1),C(shortest_path(i),1)],[C(shortest_path(i-1),2),C(shortest_path(i),2)])
hold on
end
%绘制每次循环最短路径长度和平均路径长度
figure(2)
set(gcf,'Name','Ant Colony Optimization——Figure of length_best and length_average','Color','r')
plot(length_best,'r')
set(gca,'Color','g')
hold on
plot(length_average,'k')
⛄ 运行结果
⛄ 参考文献
[1]徐义豪. 基于蚁群算法求解旅行商问题[J]. 电子技术与软件工程, 2013(17):2.
