蚁群算法

1.蚂蚁算法介绍

1.1蚁群算法起源

蚁群优化（ant colony optimization, ACO）是20世纪90年代初由意大利学者 M.Dorigo等通过模拟蚂蚁的 行为而提出的一种随机优化技术。
最初用于求解旅行商问题，现在已经成功用于许多组合优化问题。

1.2蚁群算法基本原理

在研究蚂蚁觅食行为过程中，人们发现，尽管单只蚂蚁的能力十分有限，但整个蚁群却在觅食过程中可以发现 从蚁巢到食物源的最短路径。在觅食过程中，蚂蚁通过“媒介质”来协调它们之间的行动。所谓“媒介质”指的是一种以环境的变化为媒介的间接通信方式。蚂蚁在寻找食物时，以其产生的被称为信息素的化学物质作为媒介而间接的传递信息。当蚂蚁从蚁穴走到食物源，从而形成了含有信息素的路径。
蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法：蚂蚁在运动过程中，能够在它所经过的路径上留下信息素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向。由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。

1.3蚁群算法基本流程

在ACO算法中，人工蚂蚁实际上代表的是一个解的随机构建过程，从最初的空解开始，通过不断地向部分解添加解 的成分而构建出一个完整的解
• AS算法对TSP的求解主要有两大步骤：
• 1、路径构建
• 2、信息素更新

2.旅行商问题

2.1问题简介

T S P 问 题 可 以 用 一 个 带 权 完 全 图 G=(N,A)来表示，其中N是带有n=|N|点（城 市）的集合，A是完全连接这些点的边的集合。每一条边（i,j）属于A都带有一个权值 ，它代表城市i与城市j之间的距离。TSP问题就是要找到图中的最短哈密尔顿回路。

2.2流程图

其中，结束条件为如下4条：
1、算法已经找到与最优解的距离在预定义范围内的一个解
2、算法已经探索的路径数目达到最大值，或者算法执行的迭代次数达到最大值
3、程序执行的CPU时间达到最大值
4、算法陷入停滞状态

2.3两大步骤

2.3.1路径构建

AS中的随机比例规则:对于每只蚂蚁k ,路径记忆向量Rk按照访问顺序记录了所有k已 经经过的城市序号。设蚂蚁k当前所在城市为i，则其选择城市j作为下一个访问对象的概率为：

2.3.2信息素更新

这里m是蚂蚁个数, ρ是信息素的蒸发率，规定0≤ ρ≤1， 在AS中通常设置为 ρ =0.5，Δτij是第k只蚂蚁在它经过的 边上释放的信息素量，它等于蚂蚁k本轮构建路径长度的 倒数。Ck表示路径长度，它是Rk中所有边的长度和。

3.代码实现与运行结果分析

说明：alpha为信息素重要程度因子，beta为启发函数重要程度因子，rho为 信息素挥发因子

3.1控制alpha = 1，beta=5，变化rho。

3.1.1当rho = 0.1时

3.1.2当rho = 0.3时

3.1.3当rho = 0.5时

3.1.4分析

实验结果

	最短路径长度	迭代次数（收敛时）
rho=0.1	12455.1241	125
rho=0.3	12529.5431	25
rho=0.5	12621.5333	17

分析：
从数据结果来看，信息素挥发因子rho越小，最短路径长度越小，更接近最优值。但是收敛效率低，与rho为0.3时的迭代次数相比相差了100次。
结论：
当信息素挥发因子rho越小时，在各路径上残留的信息素越多。当rho=0.1时，收敛速率低可能是由于rho过小，路径上残留的信息素过多，导致无效路径持续被搜索，也就导致了收敛速率低。同理，当rho=0.5时，最短路径长度偏离最优值的原因可能是由于信息素挥发因子rho过大时，无效的路径虽然可以被排除搜索，但是不能保证有效路径全部保留，影响到最优值的搜索。

3.2控制alpha = 1，rho=0.1，变化beta。

3.2.1当beta = 3时

3.2.2当beta = 5时

3.2.3当beta = 7时

3.2.4分析

实验结果

	最短路径长度	迭代次数（收敛时）
beta = 3	12455.1241	110
beta = 5	12455.1241	125
beta = 7	12527.0234	4

分析：
从数据结果来看，启发函数重要程度因子beta越大，最短路径长度越大，更家偏离近最优值。但是收敛效率高，当beta = 7时，只迭代了4次就收敛了，并且与beta=5时相比，相差了121次。
结论：
针对于beta=5于beta=7的收敛时所需的迭代次数来看，可能是由于启发函数重要程度因子beta过大，导致蚁群偏向选择局部最短路径，所以收敛速度极快，但是也导致了随机性降低，容易得到局部的最优解。

3.3控制beta = 5，rho=0.1，变化alpha。

3.3.1当alpha = 1时

3.3.2当alpha = 3时

3.3.3当alpha = 15时

*本来选择的是alpha=5的值，但是与alpha=3的时候数据几乎相同，所以选择了一个相对大于beta的值。

3.3.4分析

实验结果

	最短路径长度	迭代次数（收敛时）
alpha = 1	12455.1241	125
alpha = 3	12527.0234	45
alpha = 15	12611.7143	20

分析：
从数据结果来看，信息素重要程度因子alpha越大，最短路径长度越大，更家偏离近最优值。但是收敛效率高。alpha=1时迭代次数高达125次。
结论：
针对于alpha=1与alpha=3这两条数据来讲，alpha=1时迭代次数多出了80次。可能是因为alpha值过小，蚁群走之前的路径的可能性会变小，排除无效路径的效率也降低，导致迭代次数相对较高。

4.总结

1、关于信息挥发因子rho
当rho过小时，在各路径上残留的信息素过多，进而无效的路径继续被搜索，影响到算法的收敛速率。
当rho过大，无效的路径虽然可以被排除搜索，但是不能保证有效的路径不会被放弃搜索，影响到最优值的搜索。
2、关于启发函数重要程度因子beta
beta值越大，蚁群就越容易选择局部较短路径，算法的收敛速度因此加快，但是随机性也就降低了，容易产生相对最优解
3、关系信息素重要程度因子alpha
alpha值越大，蚂蚁选择之前走过的路径可能性就越大，搜索路径的随机性减弱，类似于beta偏大，也容易产生相对最优解。