蚁群算法

（加入了自己的详解，原文链接）

什么是蚁群算法

基本原理的过程就是蚂蚁觅食的过程。首先，蚂蚁在觅食的过程中会在路径上留下信息素，并在寻找食物的过程中感知信息素的强度，并指导自己的行动方向，它们总会朝着浓度高的方向前进。因此可以看得出来，蚂蚁觅食的过程是一个正反馈的过程，该路段经过的蚂蚁越多，信息素留下的就越多，浓度越高，更多的蚂蚁都会选择这个路段。

蚁群算法的实现原理

1. 避障规则 如果蚂蚁要移动的方向有障碍物挡住，他会随机的选择另外一个方向，如果有信息素指引的话，会按照信息素的指引前进。 2. 散播信息素规则 每只蚂蚁在刚找到食物的时候散发出来的信息素最多，并随着行进的距离，散播的信息越少。 3. 范围 蚂蚁观察的范围有限，只能在局部的范围内进行选择。例如蚂蚁观察的范围为3*3，那么它能够移动的范围也就是在这个3*3区域内。 4. 移动规则 前面也说过，蚂蚁的前进方向的选择依赖于信息素的浓度，回朝向信息素高的方向移动。当周围没有信息素或者信息素相同的时候，那么蚂蚁就会按照原来的方向继续前进，并且在前进方向上受到一个随机的扰动，为了避免再原地转圈，他会记住之前经过的点，下一次遇到的时候就会避开这个已经经过的点。 5. 觅食规则 如果蚂蚁在感知范围内找到食物则直接过去，加速模型的收敛，否则朝着信息素高的方向前进，并且每只蚂蚁都有小概率的犯错误，从而不是信息素最多的点移动，打破局部最优解的情况。 6. 环境 每只蚂蚁之间相互独立，他们依赖环境中的信息素进行交流。每只蚂蚁都仅仅能感知到环境内的信息。并且随机信息素会随着时间逐渐减少。如果这条路上经过的蚂蚁越来越少，那么信息素也会越来越少。

蚁群算法解决TSP问题的过程

TSP问题就是一个旅行者要遍历区域内的所有城市，最后路线成环，求解最短的路径。

基本过程如下：

初始化参数，设置迭代次数；
将 ants 只蚂蚁放置到 cities 个城市上；
ants只蚂蚁按照概率函数选择下一个城市，并完成所有城市的周游；
记录本次迭代的最优路线；
全局更新信息素。
终止。本例终止条件是迭代次数，也可以设置运行时间或最短路径的下限。
输出结果

程序中矩阵大小以及含义

程序中矩阵说明(首字母大写)：

矩阵	大小	含义
Distance	(城市数量，城市数量)	表征各个城市之间的距离信息
Eta	(城市数量，城市数量)	表征各个城市之间的启发因子
Tau	(城市数量，城市数量)	表征各个城市之间信息素的值
Route	(蚂蚁个数，城市数量)	每只蚂蚁周游城市的记录矩阵
R_best	(迭代次数，城市数量)	每次迭代的最优路线
L_best	(迭代次数，1)	每次迭代的最短距离
L_ave	(迭代次数，1)	每次迭代的平均距离

整体架构

'初始化变量参数'
'初始化矩阵参数'

while '迭代次数'
    '安排蚂蚁初始位置'
    '蚂蚁周游'
    '记录最优路线以及最短距离'
    '更新信息素'
end
'结果输出'

初始化变量参数

初始化主要对程序当中重要参数进行声明（四项参数在后面蚂蚁周游和更新信息素时要用到）。 程序实现：

% 随机产生40个城市的坐标
position = 50 * randn(40, 2);
epochs = 50;  % 迭代次数
% 蚂蚁个数最好大于等于城市个数，保证每个城市都有一个蚂蚁，这里蚂蚁数和城市数相等
ants = 40;  
alpha = 1.4;  % 表征信息素重要程度参数
beta = 2.2;  % 表征启发因子重要程度参数
rho = 0.15;  % 信息素挥发参数
Q = 10^6;  % 信息素增强系数
cities = size(position, 1);  % 城市个数

初始化矩阵参数

主要实现了重要矩阵声明以及初始化。 程序实现：

% 城市之间的距离矩阵
Distance = ones(cities, cities);
for i = 1: cities
    for j = 1: cities
        if i ~= j
            % 坐标点欧氏距离
            Distance(i, j) = ((position(i, 1) - position(j, 1))^2 + (position(i, 2) - position(j, 2))^2)^0.5;
        else
            % 因为后面要取倒数，所以取一个浮点数精度大小
            Distance(i, j) = eps;
        end
        Distance(j, i) = Distance(i, j);
    end
end
% 启发因子矩阵，启发因子越大蚂蚁移动的可能性就大，可以看出距离越小启发因子越大
Eta = 1./Distance;
% 信息素初始值每个路线均相同为 1
Tau = ones(cities, cities);
% 每只蚂蚁的路线图
Route = zeros(ants, cities);
% 第一次迭代
epoch = 1;
% 记录每次迭代最优路线
R_best = zeros(epochs, cities);
% 记录每次迭代最短距离
L_best = inf .* ones(epochs, 1);
% 记录每次迭代平均距离
L_ave = zeros(epochs, 1);

安排蚂蚁初始位置

主要是将所有的蚂蚁安置在所有的城市当中，蚂蚁个数 >= 城市个数。并且保证均匀分布。

% 初始随机位置
RandPos = [];
% ceil四舍五入
% randperm随机置换，返回一个值范围为1到n的矩阵，顺序不定
for i = 1: ceil(ants / cities)
    RandPos = [RandPos, randperm(cities)];
end
% 初始位置转置就对应了Route矩阵中每只蚂蚁的初始位置
Route(:, 1) = (RandPos(1, 1:ants))';

蚂蚁周游

蚂蚁的初始位置已经确定，主要任务就是周游剩余的所有城市，循环（cities-1）次。里面的循环就是将所有的蚂蚁进行周游一次。

对于每只蚂蚁的周游主要是对剩余的城市进行周游，不能重复拜访同一个城市。NoVisited矩阵存储着该蚂蚁未访问的城市。然后在所有没有访问过城市中选择一个。选择的方式也是类似于轮盘赌法。概率函数表征信息素和启发因子，两者有着不同的重要程度。

P = [\tau_{ij}(t)]^\alpha · [\eta_{ij}]^\beta

其中为路线上上的信息素浓度；为路线上上的启发式信息； 程序实现：

for j = 2: cities
		% 对每一只蚂蚁做的周游操作
        for i = 1: ants
        	% 第i个蚂蚁的已访问行向量
            Visited = Route(i, 1:j-1);
            % 未访问的行向量，每次j循环一次就少一个
            NoVisited = zeros(1, (cities - j + 1));
            P = NoVisited;
            % 设定NoVisited矩阵的动态长度
            num = 1;
            % find函数返回逻辑值矩阵，后面的n表示按列返回满足条件的前n个索引值，
            % 这里的意思就是遍历所有的城市看看是否已经在Visit矩阵中了，如果不是的就把城市标号赋给NoVisited
            for k = 1: cities
                if  isempty(find(Visited == k, 1))
                    NoVisited(num) = k;
                    num = num + 1;
                end
            end
            % 对于每一个未访问的城市，计算概率强度，就是Visited矩阵最后一个也就是现在的位置到遍历NoVisited矩阵的概率
            % 第一次迭代，这里的信息素矩阵和启发因子矩阵是初始化的
            for k = 1: length(NoVisited)
                P(k) = (Tau(Visited(end), NoVisited(k))^alpha) * (Eta(Visited(end), NoVisited(k))^beta);
            end
            % sum函数对P行向量求和，cumsum函数对行向量求累积和
            % 第一次P是向下一个点前进的计算公式概率，我把它理解为强度，除以总和后就是向每个点前进的概率
            % select运用了轮盘赌方法，这样做的好处是：如果单纯的把概率强度最大的路段作为下一个要走的路段，
            % 那么后面的蚂蚁就会都往这里走，陷入局部最优了。
            P = P / sum(P);
            Pcum = cumsum(P);
            select = find(Pcum >= rand);
            % 把选出来的第一个未访问点赋给下个要去的地方，再把路径更新
            to_visit = NoVisited(select(1));
            Route(i, j) = to_visit;
        end
end

轮盘赌法：

轮盘赌法2

如上图所示，把所有事件的概率画在圆盘上，从起点顺时针概率和逐渐增大。红线表示一个随机数选到这了，然后通过find函数找到大于等于这个数的区域是D和E，选择第一个满足的区域D。还可以通过下面这个一维图理解：

轮盘赌法1

记录最优路线以及最短距离

计算每个回合每只蚂蚁走过的距离。并记录该回合最短路径，最短距离和平均距离。

% 本次迭代初始化一个距离列向量
Distance_epoch = zeros(ants, 1);
for i = 1: ants
	% 取出第i只蚂蚁的路线
    R = Route(i, :);
    for j = 1: cities - 1
    	% 把这第i个蚂蚁的路线距离累加起来
        Distance_epoch(i) = Distance_epoch(i) + Distance(R(j), R(j + 1));
    end
    Distance_epoch(i) = Distance_epoch(i) + Distance(R(1), R(cities));
end
% 记录最短路线长度
L_best(epoch) = min(Distance_epoch);
% 找到这个最短路径是从哪个地点出发的
pos = find(Distance_epoch == L_best(epoch));
% 把该回合最优路线保存
R_best(epoch, :) = Route(pos(1), :);
% 记录该回合的平均路径长度
L_ave(epoch) = mean(Distance_epoch);
epoch = epoch + 1;

更新信息素

更新信息素主要保证获得最优距离的那条路线的信息素得到最大的增强。

Delta_Tau = zeros(cities, cities);
for i = 1: ants
    for j = 1: (cities - 1)
    	% 每一只蚂蚁对于每一段小路径留下信息素的值为Q / Distance_epoch(i)，对应前面说的散播信息素规则
        Delta_Tau(Route(i, j), Route(i, j + 1)) = Delta_Tau(Route(i, j), Route(i, j + 1)) + Q / Distance_epoch(i);
    end
    Delta_Tau(Route(i, 1), Route(i, cities)) = Delta_Tau(Route(i, 1), Route(i, cities)) + Q / Distance_epoch(i);
end
% 新信息素是在原信息素挥发后加上增量ΔTau得到
Tau = (1 - rho) .* Tau + Delta_Tau;
% 本次迭代完毕，路线重置
Route = zeros(ants, cities);

结果输出

迭代完成后,在R_best矩阵中得到最短路径的最小路线，最后输出最优的结果。 结果输出实现：

% 在所有迭代中找到路径最短的那个起始位置
Pos = find(L_best == min(L_best));
% 取出最短路线
Short_Route = R_best(Pos(1), :);
% 记录最短长度
Short_Length = L_best(Pos(1), :);
figure
subplot(121);
DrawRoute(position, Short_Route);
subplot(122);
plot(L_best);
hold on
plot(L_ave, 'r');
title('平均距离和最短距离');

画图函数实现：

% C传入的是城市坐标，R传入的最佳路径
function DrawRoute(C, R)
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('旅行商规划');

本文章使用limfx的vscode插件快速发布