蚁群算法

蚁群算法简介

蚁群算法（Ant Algorithm 简称AA）是近年来刚刚诞生的随机优化方法，它是一种源于大自然的新的仿生类算法。由意大利学者Dorigo最早提出，并首先使用于解决TSP（旅行商问题）。蚂蚁算法主要是通过蚁群之间的信息传递而达到寻优的目的，最初又称蚁群优化方法（Ant Colony optimization 简称ACO）。由于模拟仿真中使用了人工蚂蚁的概念，因此又称蚂蚁系统（Ant System 简称AS）。

蚁群算法原理

蚁群算法的基本原理来源于自然界蚂蚁觅食的最短路径原理，根据昆虫学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并且能够在环境发生变化（如原有的路径上有了障碍物）之后，自适应的搜索新的最佳路径。

蚁群算法基本流程

1.路径构造
2.信息素更新

蚁群算法优缺点

蚁群算法是一种分布式的本质并行算法，蚁群算法是一种正反馈算法，蚁群算法具有较强的鲁棒性，易于与其他方法结合。但是蚁群算法的收敛速度慢，计算时间长，易于过早陷入局部最优，不利于解决连续问题；蚁群算法目前还带有明显的经验性，很多结果只是建立在实验的基础之上，需要逐步奠定其理论基础。

实验过程

实验代码

%% 旅行商问题(TSP)优化
%% 清空环境变量
clear all
clc

%% 导入数据
load citys_data.mat

%% 计算城市间相互距离
fprintf('Computing Distance Matrix... \n');
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) = 1e-4;      
        end
    end    
end

%% 初始化参数
fprintf('Initializing Parameters... \n');
m = 50;                              % 蚂蚁数量
alpha = 1;                           % 信息素重要程度因子
beta = 7;                            % 启发函数重要程度因子
rho = 0.1;                           % 信息素挥发因子
Q = 1;                               % 常系数
Eta = 1./D;                          % 启发函数
Tau = ones(n,n);                     % 信息素矩阵
Table = zeros(m,n);                  % 路径记录表
iter = 1;                            % 迭代次数初值
iter_max = 150;                      % 最大迭代次数 
Route_best = zeros(iter_max,n);      % 各代最佳路径       
Length_best = zeros(iter_max,1);     % 各代最佳路径的长度  
Length_ave = zeros(iter_max,1);      % 各代路径的平均长度  

%% 迭代寻找最佳路径
figure;
while iter <= iter_max
    fprintf('迭代第%d次\n',iter);
    % 随机产生各个蚂蚁的起点城市
      start = zeros(m,1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43