假设存在商人需要在N个城市进行商业活动, 如何通过最短的行进路线访问所有的城市.
相关数学原理解析已经非常多, 这里不做详细的介绍, 算法的解析可以参考B站连大数学建模的视频介绍
近似于蚂蚁通过特定的方式找到食物和巢穴的最短路径
正反馈机制, 最小路径 -> 最小路径 -> .....(蚂蚁走过的越多, 路径被选择的几率越高; 路径越长, 被选择几率越低)
| 参数 | 含义 | 过大 | 过小 |
|---|---|---|---|
| 蚂蚁数量m | 随机每个路径都有蚂蚁，导致路径上信息素趋于平均，正反馈作用减弱，收敛速度减慢 | 存在一些路径信息素减少为0，导致过早收敛，解的全局最优性降低 | |
| 信息素常量Q | 每只蚂蚁能携带的信息素 | 容易陷入局部最优，导致无法到达全局最优 | 信息含量差别较小，容易陷入混沌状态 |
| 最大迭代次数iter | 运算时间过长 | 陷入局部最优 | |
| 信息素因子α(ALPHA) | 蚂蚁运动过程中路径积累的信息素的量在蚁群搜索中的相对重要程度 | 蚂蚁选择以前已经走过的路可能性较大，容易使随机搜索性减弱 | 使蚁群的搜索范围减小容易过早收敛，陷入局部最优 |
| 启发函数因子β(BETA) | 启发式信息在蚂蚁搜索中的相对重要程度，蚁群寻优过程中先验性、确定性因素作用的强度 | 收敛速度加快，容易陷入局部最优 | 蚁群易陷入纯粹的随机搜索，很难找到最优解 |
| 信息素挥发因子ρ(RHO) | 信息素挥发的速度 | 信息素挥发较快，容易导致较优路径被排除 | 各路径上信息素含量差别较小，收敛速度降低 |
通过轮盘赌选择来选择下一个移动的城市
1.0版本, 常规的蚁群算法, 未做任何的优化(如: 精英蚁群, 排序等)
- 绘图使用tkinter的canvas和matplotlib.pyplot(seaborn)
- 模拟城市坐标使用numpy随机生成
- 50组坐标, 75个蚂蚁, 迭代300次基本可以得到"最"优解(高度稳定的收敛值, 实际上大部分迭代的稳定次数很少超过30次)
注: 这里的迭代, 是指在得到"最"小(收敛)路径继续迭代的次数
注意, 图的绘制是使用tkinter的canvas, 坐标的原点是在左上角, 所以Y轴的是向下的, 但是不影响数值的计算.