今天给大家分享一下matlab实现蚁群优化算法，解决旅行商问题。
在上一篇博客中对蚁群优化算法做了较为详细的介绍，有需要的小伙伴可以看一下
https://blog.csdn.net/HuangChen666/article/details/115827732
1. 初始化城市信息
1.1 随机获取城市坐标
1.2 求出城市之间距离
2. 初始化参数
3. 迭代寻找最佳路径
3.1 随机产生蚂蚁起点城市
3.2 迭代计算选择城市概率
3.3 轮盘赌选出下一个城市
3.4 更新最短路径
3.5 更新信息素
4. 得出结果
5. 全部代码
对角线上是城市 i 到 i 的距离，用一个很小的数代替。
https://blog.csdn.net/xuxinrk/article/details/80158786
所以这里可以改进一下，基本思想是：如果本次周游中的最短路径大小比上一次的要大，则本次的最短路径大小改为和上一次一样，这样就不会出现后面迭代出比前面还要打的最短距离，这样处理会更符合人们的观念，更加合理，修改后如下所示
下面是最短距离收敛曲线和平均距离收敛曲线
命令行输出结果
https://www.bilibili.com/video/BV1c4411W7zc
https://www.bilibili.com/video/BV1Z7411H78S?from=search&seid=14512389210209190890
clc;clear;
t0=clock; %用于计时
%% 初始化城市信息
n=30; %定义城市个数
city=[(randperm(100,n))',(randperm(100,n))']; %获取城市坐标
figure('name','蚁群优化算法');
plot(city(:,1),city(:,2),'o'); %描点
for i=1:n
text(city(i,1)+0.5,city(i,2),num2str(i)); %标号
end
title('蚁群优化算法');
%设置横纵坐标范围
grid on %网格线
hold on
%% 求出各个城市之间的距离
D=zeros(n,n); %新建一个n*n的矩阵存放距离
for i=1:n
for j=1:n
if i~=j
D(i,j)=sqrt(sum((city(i,:)-city(j,:)).^2));
else
D(i,j)=eps; %设置成一个很小的数，但不能为0，因为后面分母中会用到
end
end
end
%% 初始化参数
m=75; %蚂蚁数量
alpha = 1; %信息素重要程度因子
beta = 5; %启发函数重要程度因子
rho = 0.2; %信息素挥发因子
Q=10; %常系数
Eta = 1./D; %启发函数(距离的倒数)
Tau = ones(n,n); %信息素矩阵(初始时每条路上的信息素都设为1)
Table = zeros(m,n); %路径记录表，记录m个蚂蚁走过的路径
iter = 1; %迭代次数初值
iter_max = 100; %最大迭代次数
Route_best = zeros(iter_max,n); %各代最佳路径
Length_best = zeros(iter_max,1); %各代最佳路径的长度
Length_ave = zeros(iter_max,1); %各代路径的平均长度
%% 迭代寻找最佳路径
for iter=1:iter_max
%随机产生蚂蚁的起点城市
for i=1:m
Table(i,1)=randperm(n,1);
end
citys_index=1:n; %定义全部城市索引
for i=1:m %遍历所有蚂蚁
for j=2:n %遍历其他所有城市
tabu=Table(i,1:(j-1)); %已访问城市(禁止访问表)
allow=citys_index(~ismember(citys_index,tabu)); %除去已访问城市(待访问城市)
P=allow; %存放概率，定义成什么都可以，只要和allow长度一样
%计算城市间的选择概率
for k=1:length(allow)
%tabu(end)代表该蚂蚁此刻所在城市，allow(k)代表该蚂蚁即将去向的城市
P(k)=Tau(tabu(end),allow(k))^alpha*Eta(tabu(end),allow(k))^beta;
end
P=P/sum(P); %得到最终去往其他城市的概率集合
Pc=cumsum(P); %累计概率
%轮盘赌选择下一个城市
target_index=find(Pc>=rand); %从累计概率中找出大于随机值的情况
target=allow(target_index(1)); %取出第一个即为轮盘赌的结果
Table(i,j)=target; %确定第i只蚂蚁去往的第j-1个城市
end
end
%每只蚂蚁周游一遍后计算每只蚂蚁的路径长度
Length=zeros(m,1);
for i=1:m
for j=1:(n-1)
Length(i)=Length(i)+D(Table(i,j),Table(i,j+1));
end
%最后加上最后一个点回到起点的距离
Length(i)=Length(i)+D(Table(i,n),Table(i,1));
end
%% 计算最短路径距离及平均距离
[min_length,min_index]=min(Length); %取出最短路径及其下标
if iter==1
Length_best(iter)=min_length; %保存此次最短路径距离
else
Length_best(iter)=min(Length_best(iter-1),min_length); %选择本次和上次中最短路径较小的
end
Route_best(iter,:)=Table(min_index,:); %保存此次最短路线路径
Length_ave(iter)=mean(Length); %保存此次路线距离平均值
%% 更新信息素
Tau_Ant=Q./Length; %每条蚂蚁在路径上留下的信息素浓度
Tau_Temp=zeros(n,n);
for i=1:m
for j=1:n-1
%更新信息素
Tau_Temp(Table(i,j),Table(i,j+1))=Tau_Temp(Table(i,j),Table(i,j+1))+Tau_Ant(i);
end
%最后更新最后一个节点到起点的信息素
Tau_Temp(Table(i,n),Table(i,1))=Tau_Temp(Table(i,n),Table(i,1))+Tau_Ant(i);
end
Tau=(1-rho)*Tau+Tau_Temp; %信息素挥发后再加上新增的信息素
Table = zeros(m,n); %清空路线，进行下一轮周游
end
%% 命令行窗口显示结果
[min_length,min_index]=min(Length_best); %取出最短路径及其下标
Finnly_Route=Route_best(min_index,:);
last_time=etime(clock,t0);
disp(['最短距离为：' num2str(min_length)]);
disp(['最短路径为：' num2str(Finnly_Route)]);
disp(['运行时间：' num2str(last_time) '秒']);
%% 绘图
plot([city(Finnly_Route,1);city(Finnly_Route,1)],...
[city(Finnly_Route,2);city(Finnly_Route,2)],'bo-'); %描点
text(city(Finnly_Route(1),1),city(Finnly_Route(1),2),' 起点');
text(city(Finnly_Route(end),1),city(Finnly_Route(end),2),' 终点');
figure(2);
subplot(1,2,1); %显示在一行两列图像中的第一列
plot(Length_best);
xlabel('迭代次数');
ylabel('最短距离');
title('最短距离收敛曲线');
subplot(1,2,2); %显示在一行两列图像中的第二列
plot(Length_ave);
xlabel('迭代次数');
ylabel('平均距离');
title('平均距离收敛曲线');