【数之道 04】解决最优路径问题的妙招-蚁群ACO算法

以TSP问题为例

有如下假设：

1. 蚁群不会重复访问相同城市
2. 蚂蚁知道不同城市之间的距离，在其他条件相同的情况下，蚂蚁会优先走距离段的路
3. 蚂蚁会在其走过的路上释放弗洛蒙，在其他条件相同的情况下，蚂蚁会优先走弗洛蒙浓度高的道理

公式计算：

以上是蚂蚁从i地选择到j地的概率，其中

以及

以上是弗洛蒙浓度的更新公式

流程

1. 初始化蚁群
2. 随机放置蚂蚁
3. 蚂蚁移动：蚂蚁根据信息素（弗洛蒙浓度）或是根据路径的长短来选择下一步要前往的位置
4. 更新信息素（弗洛蒙浓度）
5. 判断是否达到迭代停止条件