? 蚁群算法由Marco Dorigo于1992年提出，该算法模拟了自然界中蚂蚁的觅食行为。蚂蚁在寻找食物源时，会在其经过的路径上释放一种信息素，并能够感知其他蚂蚁释放的信息素。信息素浓度的大小表征路径的远近，信息素浓度越高，表示对应的路径距离越短。通常蚂蚁会以较大的概率优先选择信息素浓度较高的路径，并释放一定量的信息素，以增强该条路径上的信息素浓度，这样，会形成一个正反馈。最终，蚂蚁能够找到一条从巢穴到食物源的最佳路径，即距离最短。生物学家发现，路径上的信息素浓度会随着时间的推进而逐渐衰减。
? 蚁群算法的基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。
? 蚁群搜索食物的过程与TSP问题的求解过程非常相似，这里以TSP问题作为背景来介绍基本蚁群算法。所谓TSP问题就是求一条遍历所有n个城市且每个城市仅经过一次的最短路径。在ACO算法中，首先将m个蚂蚁随机分配到n个不同的城市中，通常m不大于n；然后m只蚂蚁同时由一个城市运动到另一个城市，逐步完成他们的搜索过程。蚂蚁k根据各个城市间的连接路径上的信息素浓度决定其访问的下一个城市，设$p_ij^k (t)$表示t时刻蚂蚁k从城市i转移到城市j的概率：
%% 清空环境变量
clear all
clc
%% 导入数据
load citys_data.mat % 从名为 'citys_data.mat' 的文件中加载数据
%% 计算城市间的相互距离
n = size(citys,1); % 获取城市数量
D = zeros(n,n); % 创建一个用于存储城市间距离的零矩阵
for i = 1:n
? for j = 1:n
? if i ~= j
? D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)) .^ 2)); %勾股定理
? else
? D(i,j) = 1 * 10^-4; % 对角线上的距离设置一个很小的值，避免出现零值
? end
? end
end
%% 初始化参数
m = 50; %蚂蚁数量
alpha = 1; %信息素重要程度因子
beta = 5; %启发函数重要程度因子
rho = 0.1; %信息素挥发因子
Q = 1; %蚁周模型中的常系数
Eta = 1 ./ D; %启发函数
Tau = ones(n,n); %信息素矩阵,初始化为n行n列的全1方阵
Table = zeros(m,n); %路径记录表,m只蚂蚁所以有m行记录,每只蚂蚁经过n个城市的次序所以是n列
iter = 1; %迭代次数初值
iter_max = 200; %最大迭代次数
Route_best = zeros(iter_max,n); %各代最佳路径
Length_best = zeros(iter_max,1);%各代最佳路径的长度
Length_ave = zeros(iter_max,1); %各代路径的平均长度
%% 迭代寻找最佳路径
while iter <= iter_max
? %随机产生各个蚂蚁的起点城市
? start = zeros(m,1); % 创建一个初始城市编号的数组
? for i = 1:m
? temp = randperm(n); %把1到n这些数随机打乱得到的一个数字序列
? start(i) = temp(1); %每只蚂蚁的起始位置是随机的
? end
? Table(:,1) = start; %路径记录表的第一列记为开始出发的城市
?
? %构建解空间
? citys_index = 1:n; %生成了一个1至31的一维数组
?
? %逐个蚂蚁路径选择
? for i = 1 : m
? %逐个城市路径选择
? for j = 2 : n
? tabu = Table(i,1:(j - 1)); %已访问的城市集合(禁忌表)
? allow_index = ~ismember(citys_index,tabu);
? %找到尚未访问的城市,判断前一矩阵是否在后一矩阵中的逻辑值,并取反
? allow = citys_index(allow_index); %待访问的城市集合
? P = allow; % 创建概率数组，用于存储城市间转移概率
? %计算城市间转移概率
? for k = 1:length(allow)
? 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; % 将下一个城市编号放入路径记录表
? end
? end
? %计算各个蚂蚁的路径距离
? Length = zeros(m,1); % 创建数组，用于存储各个蚂蚁的路径距离
? for i = 1:m
? Route = Table(i,:);
? for j = 1:(n-1)
? Length(i) = Length(i) + D(Route(j),Route(j+1));% 计算路径长度
? end
? Length(i) = Length(i) + D(Route(n),Route(1)); % 考虑最后一个城市回到起点的距离
? end
? %计算最短路径距离及平均距离
? if iter == 1
? [min_Length,min_index] = min(Length); % 获取最短路径长度及其索引(走出了最短路径的那只蚂蚁编号)
? Length_best(iter) = min_Length; % 存储本次迭代中的最短路径长度
? Length_ave(iter) = mean(Length); % 计算本次迭代产生所有值的平均路径长度
? Route_best(iter,:) = Table(min_index); % 存储最佳路径
? else
? [min_Length,min_index] = min(Length); % 获取最短路径长度及其索引
? Length_best(iter) = min(Length_best(iter - 1),min_Length);
? % 更新最短路径长度,第一个参数是矩阵,第二个参数是标量,凡矩阵中的元素大于标量的,都用标量值替代
? Length_ave(iter) = mean(Length); % 计算平均路径长度
? if Length_best(iter) == min_Length
? Route_best(iter,:) = Table(min_index,:); % 存储最佳路径
? else
? Route_best(iter,:) = Route_best((iter-1)??;% 若未找到更优路径，保持上一代的最佳路径
? end
? end
?
? %更新信息素
? Delta_Tau = zeros(n,n); % 创建用于存储信息素增量的矩阵,n个城市所以是n阶
?
? %逐个蚂蚁计算
? for i = 1:m
? %逐个城市计算
? for j = 1:(n-1)
? Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q / Length(i);
? % 计算信息素增量
? end
? Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i);
? % 考虑回到起点的信息素增量
? end
?
? Tau = (1-rho) * Tau + Delta_Tau; % 更新信息素
?
? %迭代次数+1,清空路径记录表
? iter = iter + 1;
? Table = zeros(m,n);
?
end
%% 结果显示
[Shortest_Length,index] = min(Length_best); % 获取最短路径长度及其索引
Shortest_Route = Route_best(index,:); % 获取最短路径
disp(['最短距离:' num2str(Shortest_Length)]);% 显示最短路径长度
disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]);% 显示最短路径
%% 绘图
figure(1)
plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
? [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');
grid on
for i = 1:size(citys,1)
? text(citys(i,1),citys(i,2),[' ' num2str(i)]);
end
text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),' 起点');
text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),' 终点');
xlabel('城市位置横坐标')
ylabel('城市位置纵坐标')
title(['蚁群算法优化路径(最短距离:' num2str(Shortest_Length) ')'])
figure(2)
plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:')
legend('最短距离','平均距离')
xlabel('迭代次数')
ylabel('距离')
title('各代最短距离与平均距离对比')
经验首页