蚁群算法（ACO）解决TSP问题

本文主要是介绍蚁群算法（ACO）解决TSP问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、蚁群算法

1.基本原理

蚁群算法（Ant Colony Optimization，ACO）是一种基于种群寻优的启发式搜索算法，有意大利学者M.Dorigo等人于1991年首先提出。该算法受到自然界真实蚁群集体在觅食过程中行为的启发，利用真实蚁群通过个体间的信息传递、搜索从蚁穴到食物间的最短路径等集体寻优特征，来解决一些离散系统优化中的困难问题。

经过观察发现，蚂蚁在寻找食物的过程中，会在它所经过的路径上留下一种被称为信息素的化学物质，信息素能够沉积在路径上，并且随着时间逐步挥发。在蚂蚁的觅食过程中，同一蚁群中的其他蚂蚁能够感知到这种物质的存在及其强度，后续的蚂蚁会根据信息素浓度的高低来选择自己的行动方向，蚂蚁总会倾向于向信息素浓度高的方向行进，而蚂蚁在行进过程中留下的信息素又会对原有的信息素浓度予以加强，因此，经过蚂蚁越多的路径上的信息素浓度会越强，而后续的蚂蚁选择该路径的可能性就越大。通常在单位时间内，越短的路径会被越多的蚂蚁所访问，该路径上的信息素强度也越来越强，因此，后续的蚂蚁选择该短路径的概率也就越大。经过一段时间的搜索后，所有的蚂蚁都将选择这条最短的路径，也就是说，当蚁巢与食物之间存在多条路径时，整个蚁群能够通过搜索蚂蚁个体留下的信息素痕迹，寻找到蚁巢和食物之间的最短路径。

蚁群算法中，蚂蚁个体作为每一个优化问题的可行解。首先随机生成初始种群，包括确定解的个数、信息素挥发系数、构造解的结构等。然后构造蚁群算法所特有的信息素矩阵每只妈蚁执行蚂蚊移动算子后，对整个群体的蚂蚁做一评价，记录最优的蚂蚁。之后算法根据信息素更新算子更新信息素矩阵，至此种群的一次选代过程完成。整个蚂蚁群体执行一定次数的选代后退出循环、输出最优解。

2.术语介绍

（1）蚂蚁个体。每只蚂蚁称为一个单独的个体，在算法中作为一个问题的解。

（2）蚂蚁群体。一定数量的蚂蚁个体组合在一起构成一个群体，蚂蚁是群体的基本单位。

（3）群体规模。群体中个体数目的总和称为群体规模，又叫种群大小。

（4）信息素。信息素是蚂蚁在所经过的路径上所释放的一种化学物质，后来的蚂蚁根据路径上的信息素的强度选择路径。

（5）蚂蚁移动算子。蚂蚁在寻优过程中通过蚂蚁移动算子来改善基因位，向最优解靠近。

（6）信息素更新算子。蚂蚁算法中，种群在每次迭代过程中，通过信息素更新算子来改变信息素矩阵，为蚂蚁移动算子提供基础。

3.基本流程

（1）算法流程图

 （2）算法描述

①初始化蚁群。初始化蚁群参数，包括设置蚂蚁数量、蚂蚁解的结构、信息素挥发系数等。

②构造信息素矩阵。

③每只蚂蚁执行蚂蚁移动算子。蚂蚁依据前面蚂蚁所留下的信息素，修改自己的解结构，完成一次循环。

④依据适应度值对蚂蚁进行排序，对前n个解执行局部搜索算子。

⑤评价蚁群。根据目标函数对每只蚂蚁的适应度值做一评价，并记录最优解。

⑥根据信息素更新算子更新信息素矩阵。

⑦若满足终止条件，即最短路径，输出最优解；否则，信息素挥发，算法继续进行步骤③。

4.算法特点

（1）自组织。组织力或组织指令是来自于系统的内部。 在抽象意义上讲，自组织就是在没有外界作用下使得系统熵减小的过程(即是系统从无序到有序的变化过程)。

（2）并行搜索。每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。 在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。

（3）正反馈。蚂蚁能够最终找到最短路径，直接依赖于最短路径上信息激素的堆积，而信息激素的堆积却是一个正反馈的过程。

二、ACO解决TSP问题

1.算法步骤

（1）算法流程图

 （2）算法描述

①初始化(各个参数): 在计算之初需要对相关的参数进行初始化，如蚂蚁数量m、信息素因子α、启发函数因子β、信息素挥发因子ρ、信息素常数Q、最大迭代次数iter_max等等。

②构建解空间： 将各个蚂蚁随机地放置于不同的出发点，对每个蚂蚁k（k=1，2，……，m），计算其下一个待访问的城市，直到所有蚂蚁访问完所有的城市。

③更新信息素： 计算各个蚂蚁经过的路径长度L，记录当前迭代次数中的最优解（最短路径）。同时，对各个城市连接路径上的信息素浓度进行更新。

④判断是否终止： 若迭代次数小于最大迭代次数则迭代次数加一，清空蚂蚁经过路径的记录表，并返回步骤二；否则终止计算，输出最优解。

2.参数设置

3.构建解空间

将各个蚂蚁随机地置于不同的出发地，对每个蚂蚁k ( k = 1 , 2 , ⋯   , m ) ，按照轮盘赌法得到下面的转移概率公式计算其下一个待访问的城市，直到所有蚂蚁访问完所有的城市。

上式中，i ,j 分别为起点和终点； 

η_ij(t)=1/d_ij 是启发函数，值两点i,j路径距离的倒数；

τ_ij(t)为时间 t 时由 i 到 j 的信息素浓度；

allowed_k为尚未访问过的节点的集合。

4.更新信息素

根据信息素更新策略的不同，Dorigo M 提出了三种不同的基本蚁群算法模型，分别称之为蚁量系统（ant-quantity system）模型、蚁密系统（ant-density system）模型、蚁周系统（ant-cycle system）模型。三种模型的差别仅在于 ∆τ_ij 的表达式不同，这里采用蚁周模型。

 5.判断是否终止

蚁群算法中的终止条件：是否达到迭代次数。 一次迭代就是指m只蚂蚁都走完所有的城市，即存在m个搜索路径。 将所有路径进行比较，选择长度最短的路径，做出这一次迭代的可视化结果，更新信息素。并将当前的最短路径与过往的最短路径长度进行对比，同时迭代次数加1. 然后判断当前迭代次数是否等于设置的迭代次数。如果等于则停止迭代，否则进行下一次迭代。

6.编码实现

% I.清空环境变量
clear all
clc

% II. 符号说明
%{

iter_max                          -- 最大迭代次数
m                                 -- 蚂蚁数量,一般设置为目标数的1.5倍
D(i,j)                            -- 城市i和j之间的距离
Eta(i, j) = 1./ D(i, j)           -- 启发函数
alpha                             -- 表征信息素重要程度的参数,通常[1, 4]之间
beta                              -- 表征启发函数重要程度的参数,通常[0, 5]之间
rho                               -- 信息素挥发因子,通常[0.1,0.2, 0.5]之间
Q                                 -- 常系数
route_best                        -- 各代最佳的路线
length_best                       -- 各代最佳路线的长度
length_average                    -- 各代的平均长度

%}

% III.导入数据
load cities.mat

%  IV. 计算城市建的距离（欧式距离）
n = size(cities,1); %城市个数
D = zeros(n,n);
for i = 1:n
    for j = i+1:n
        %D(i,j) = sqrt(sum((cities(1,:)-cities(j,:)).^2));  
        D(i, j) = sqrt((cities(i, 1) - cities(j, 1))^2 + (cities(i, 2) - cities(j, 2))^2);
        D(j,i) = D(i,j);
    end
    D(i,i) = 1e-4;
end

% V. 初始化参数
m = 50;             % 蚂蚁数量
alpha = 1;          %信息素重要程度因子
beta = 5;           % 启发函数重要程度因子
rho = 0.1;          % 信息素挥发因子
Q = 20;            %常系数
Eta = 1./D;         % 启发函数
Tau = ones(n,n);    %信息素矩阵,Tau(i, j)表示边(i, j)的信息素量，一开始都为1
Table = zeros(m,n); %路径记录表
iter = 1;           %迭代次数初值
iter_max = 200;     %最大迭代次数
route_best = zeros(iter_max,n); %各代最佳路径
length_best = zeros(iter_max,1); %各代最佳路径长度
length_average = zeros(iter_max,1); %各代路径的平均长度

% VI.迭代寻找最佳路径
while iter <= iter_max
    
    %step 1,随机产生各个蚂蚁的起点城市
    start = zeros(m,1);
    for i = 1:m
        temp = randperm(n);     %1-n的随机数
        start(i) = temp(1);
    end
    Table(:,1) = start;     %Table第一列即是所有蚂蚁的起点城市
    cities_index = 1:n;     %所有城市索引的一个集合
    
    %step 2,逐个蚂蚁路径选择
    for i = 1:m
        %逐个城市路径选择
        for j = 2:n
            visited = Table(i,1:(j-1));     % 蚂蚁i已访问的城市集合(禁忌表)
            allow_index = ~ismember(cities_index, visited);
            allow = cities_index(allow_index);   % 存放待访问的城市集合
            P = allow;
            
            % 计算城市间转移概率
            for k = 1:length(allow)
                P(k) = Tau(visited(end), allow(k))^alpha * Eta(visited(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
    
    % step 3,计算各个蚂蚁的路径距离
    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

    % step 4,计算最短路径距离及平均距离
    if iter == 1
        [min_Length, min_index] = min(Length);
        length_best(iter) = min_Length;
        length_average(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_average(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
    
    % step 5,更新信息素
    Delta_Tau = zeros(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;
    
    %step 6,迭代次数加1, 清空路径记录表
    iter = iter + 1;
    Table = zeros(m, n);
end

% VII. 结果显示
[Shortest_Length, index] = min(length_best);
Shortest_Route = route_best(index, :);
disp(['最短距离', num2str(Shortest_Length)]);
disp(['最短路径', num2str([Shortest_Route Shortest_Route(1)])]);

% VIII. 绘图
figure(1);
plot([cities(Shortest_Route,1);cities(Shortest_Route(1),1)],...
     [cities(Shortest_Route,2);cities(Shortest_Route(1),2)],'o-');
grid on;
for i = 1:size(cities,1)
    text(cities(i,1),cities(i,2),['   ' num2str(i)]);
end
text(cities(Shortest_Route(1),1),cities(Shortest_Route(1),2),'       起点');
text(cities(Shortest_Route(end),1),cities(Shortest_Route(end),2),'       终点');
xlabel('城市位置横坐标')
ylabel('城市位置纵坐标')
title(['蚁群算法优化路径(最短距离:' num2str(Shortest_Length) ')'])
figure(2)
plot(1:iter_max,length_best,'b',1:iter_max,length_average,'r:')
legend('最短距离','平均距离')
xlabel('迭代次数')
ylabel('距离')
title('各代最短距离与平均距离对比')

7.实验结果

运行结果：

1 最短距离15601.9195
2 最短路径14  12  13  11  23  16   5   6   7   2   4   8   9  10   3  18  17  19  24  25  20  21  22  26  28  27  30  31  29   1  15  14

三、参考文献

1.cities.mat文件

2.基于蚁群算法的旅行商问题(TSP)的优化，CSDN博主「~心升明月~」

这篇关于蚁群算法（ACO）解决TSP问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！