蚁群算法(实例帮助理解)
@TOC
1. 算法简介
1.1 算法起源
- 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
- 它能够求出从原点出发，经过若干个给定的需求点，最终返回原点的最短路径。这也就是著名的旅行商问题(Traveling Saleman Problem，TSP)。
- 蚁群算法是一种模拟进化算法
1.2 算法应用
- 应用进展以蚁群算法为代表的蚁群智能已成为当今分布式人工智能研究的一个热点，许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究。
- 多年来世界各地研究工作者对蚁群算法进行了精心研究和应用开发，该算法现已被大量应用于数据分析、机器人协作问题求解、电力、通信、水利、采矿、化工、建筑、交通等领域。
- 蚁群优化算法最初用于解决TSP问题，经过多年的发展，已经陆续渗透到其他领域中，比如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域己获得成功的应用，其中最成功的是在组合优化问题中的应用
2. 基本原理
蚂蚁在行走过程中会释放一种称为“信息素”的物质，用来标识自己的行走路径。
在寻找食物的过程中，根据信息素的浓度选择行走的方向，并最终到达食物所在的地方。
信息素会随着时间的推移而逐渐挥发。
例：下图为蚂蚁觅食过程图，现有两只蚂蚁均在A点，食物在B点。途中从A到B有两条路径（即A->B和A->C->B），假设两只蚂蚁速度相同，两只蚂蚁释放的信息素浓度相同，且图中三角形为等边三角形。那么在t0时刻，蚂蚁1沿ACB出发，蚂蚁2沿AB出发。当到t1时刻后，蚂蚁1到达C点，蚂蚁2到达B点(食物)。此时AC路径和AB路径的信息素浓度相同，且蚂蚁1将继续从C到B爬行，蚂蚁2则从B到A返回。当到t2时刻后，蚂蚁1到达B点(食物)，蚂蚁2到达A点。此时发现AB路径的信息素浓度是BC路段的2倍，因此当蚂蚁1想要返回A点后，它不会再选择沿BCA原路返回，而是选择信息素浓度高的BA路径返回。这样持续下去，AB路径上的信息素浓度会越来越高，后面的蚂蚁都会选择AB路径来获取食物，从而找到了获取食物的最短路径。
3. 算法设计
3.1 算法步骤
初始化(各个参数): 在计算之初需要对相关的参数进行初始化，如蚂蚁数量m、信息素因子α、启发函数因子β、信息素挥发因子ρ、信息素常数Q、最大迭代次数t等等。
构建解空间： 将各个蚂蚁随机地放置于不同的出发点，对每个蚂蚁k（k=1，2，……，m），计算其下一个待访问的城市，直到所有蚂蚁访问完所有的城市。
更新信息素： 计算各个蚂蚁经过的路径长度L，记录当前迭代次数中的最优解（最短路径）。同时，对各个城市连接路径上的信息素浓度进行更新。
判断是否终止： 若迭代次数小于最大迭代次数则迭代次数加一，清空蚂蚁经过路径的记录表，并返回步骤二；否则终止计算，输出最优解。
下图是蚁群算法的整体流程图：
3.2 参数意义及设置
| 参数名称 | 参数意义 | 参数设置过大 | 参数设置过小 |
|---|---|---|---|
| 蚂蚁数量m | 蚂蚁数量一般设置为目标数的1.5倍较为稳妥 | 每条路径上信息素趋于平均，正反馈作用减弱，从而导致收敛速度减 | 可能导致一些从未搜索过的路径信息素浓度减小为0，导致过早收敛，解的全局最优性降低 |
| 信息素常量Q | 信息素常量根据经验一般取值在[10,1000] | 会使蚁群的搜索范围减小容易过早的收敛，使种群陷入局部最优 | 每条路径上信息含量差别较小，容易陷入混沌状态 |
| 最大迭代次数t | 最大迭代次数一般取[100,500],建议取200 | 运算时间过长 | 可选路径较少，使种群陷入局部最优。 |
| 信息素因子ɑ | 反映了蚂蚁运动过程中路径上积累的信息素的量在指导蚁群搜索中的相对重要程度。取值范围通常在[1, 4]之间。 | 蚂蚁选择以前已经走过的路可能性较大，容易使随机搜索性减弱 | 蚁群易陷入纯粹的随机搜索，使种群陷入局部最优 |
| 启发函数因子𝛽 | 反映了启发式信息在指导蚁群搜索中的相对重要程度，蚁群寻优过程中先验性、确定性因素作用的强度取值范围在[0, 5]之间 | 虽然收敛速度加快，但是易陷入局部最优 | 蚁群易陷入纯粹的随机搜索，很难找到最优解 |
| 信息素挥发因子𝜌 | 反映了信息素的消失水平，相反的1-𝜌反映了信息素的保持水平。取值范围通常在[0.2, 0.5]之间 | 信息素挥发较快，容易导致较优路径被排除 | 各路径上信息素含量差别较小，收敛速度降低 |
3.3 构建路径
我们知道蚂蚁是根据信息素的浓度来判断所走的路线的，但是事实上，不是说哪条路的信息素浓度高蚂蚁就一定走哪条路，而是走信息素浓度高的路线的概率比较高。那么首先我们就需要知道蚂蚁选择走每个城市的概率，然后通过轮盘赌法（相当于转盘）确定蚂蚁所选择的城市。
蚂蚁选择城市的概率公式如下：
其中：
其实这个公式也很好理解，蚂蚁选择城市的概率主要由𝜏ij (t)和𝜂ij (𝑡)有关，分母为蚂蚁k可能访问的城市之和（为常数），这样才能使蚂蚁选择各个城市的概率之后为1，符合概率的定义。𝜏ij (t)和𝜂ij (𝑡)上的指数信息素因子ɑ和启发函数因子𝛽只决定了信息素浓度以及启发函数对蚂蚁k从i到j的可能性的贡献程度。
例：下图为计算蚂蚁从起点城市2到可达城市的概率（套公式，很好理解）
3.4 更新信息素浓度
更新信息素的公式如下：
根据不同的规则我们可以将蚁群算法分为三种模型——蚁周模型(Ant-Cycle)、蚁量模型(Ant-Quantity)和蚁密模型(Ant-Density)。蚁周模型是完成一次路径循环后，蚂蚁才释放信息素，其利用的是全局信息。蚁量模型和蚁密模型蚂蚁完成一步后就更新路径上的信息素，其利用的是局部信息。本文章使用的是最常见的蚁周模型。
蚁周模型公式如下：
其中Q为信息素常量，Lk表示第k只蚂蚁在本次循环中所走路径的长度。
例：下图为信息素的更新过程，假设初始时各路径信息素浓度为10。
3.5 判断是否中止
蚁群算法中的终止条件：是否达到迭代次数。
一次迭代就是指m只蚂蚁都走完所有的城市，即存在m个搜索路径。
将所有路径进行比较，选择长度最短的路径，做出这一次迭代的可视化结果，更新信息素。并将当前的最短路径与过往的最短路径长度进行对比，同时迭代次数加1。
然后判断当前迭代次数是否等于设置的迭代次数。如果等于则停止迭代，否则进行下一次迭代。
4. 实例演示（TSP问题）
实例题目：
实例代码：
matlab蚁群算法代码
matlab运行结果展示：
- 点赞
- 收藏
- 关注作者
评论（0）