蚂蚁算法

1.概念及原理

概念：蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
原理：蚁群算法的基本思想来源于自然界蚂蚁觅食的最短路径原理，根据昆虫科学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它们可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并在周围环境发生变化后，自适应地搜索新的最佳路径。

蚂蚁在寻找食物源的时候，能在其走过的路径上释放一种叫信息素的激素，使一定范围内的其他蚂蚁能够察觉到。当一些路径上通过的蚂蚁越来越多时，信息素也就越来越多，蚂蚁们选择这条路径的概率也就越高，结果导致这条路径上的信息素又增多，蚂蚁走这条路的概率又增加，生生不息。这种选择过程被称为蚂蚁的自催化行为。对于单个蚂蚁来说，它并没有要寻找最短路径，只是根据概率选择；对于整个蚁群系统来说，它们却达到了寻找到最优路径的客观上的效果，这就是群体智能。

2.代码设计

关键参数：
蚂蚁数量：

设M表示城市数量，m表示蚂蚁数量。m的数量很重要，因为m过大时，会导致搜索过的路径上信息素变化趋于平均，这样就不好找出好的路径了；m过小时，易使未被搜索到的路径信息素减小到0，这样可能会出现早熟，没找到全局最优解。一般上，在时间等资源条件紧迫的情况下，蚂蚁数设定为城市数的1.5倍较稳妥。

信息素因子：

信息素因子反映了蚂蚁在移动过程中所积累的信息量在指导蚁群搜索中的相对重要程度，其值过大，蚂蚁选择以前走过的路径概率大，搜索随机性减弱；值过小，等同于贪婪算法，使搜索过早陷入局部最优。实验发现，信息素因子选择[1,4]区间，性能较好。

启发函数因子：

启发函数因子反映了启发式信息在指导蚁群搜索过程中的相对重要程度，其大小反映的是蚁群寻优过程中先验性和确定性因素的作用强度。过大时，虽然收敛速度会加快，但容易陷入局部最优；过小时，容易陷入随机搜索，找不到最优解。实验研究发现，当启发函数因子为[3,4.5]时，综合求解性能较好。

信息素挥发因子：

信息素挥发因子表示信息素的消失水平，它的大小直接关系到蚁群算法的全局搜索能力和收敛速度。实验发现，当属于[0.2，0.5]时,综合性能较好。

信息素常数：

这个参数为信息素强度，表示蚂蚁循环一周时释放在路径上的信息素总量，其作用是为了充分利用有向图上的全局信息反馈量，使算法在正反馈机制作用下以合理的演化速度搜索到全局最优解。值越大，蚂蚁在已遍历路径上的信息素积累越快，有助于快速收敛。实验发现，当值属于[10,1000]时，综合性能较好。

最大迭代次数：

最大迭代次数值过小，可能导致算法还没收敛就已结束；过大则会导致资源浪费。一般最大迭代次数可以取100到500次。一般来讲，建议先取200，然后根据执行程序查看算法收敛的轨迹来修改取值。

%% 旅行商问题(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) = 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17