蚂蚁的路径选择问题（蚁群优化算法）

luyuanhong

蚂蚁的路径选择问题（蚁群优化算法）

原创 围城里的猫 MathSpark 2024-05-13 08:01 陕西



之前有一期蚂蚁行走轨迹背后的数学原理，很多读者对此感兴趣，希望我们能够写得更详细和通俗一点，借着这个机会我们来聊聊著名的蚁群优化算法。这个算法是 20 世纪 90 年代 Marco Dorigo 在他的博士论文中首次提出的，最初被用来解决著名的旅行商问题，发展至今被广泛用于科学工业，想什么列车调度，容量规划，车辆路径还有组合优化都能见到它的身影。



蚂蚁是社会性昆虫，它们生活在群体中。蚂蚁的行为是由寻找食物的目标所控制的。在寻找食物的过程中，蚂蚁会在其巢穴周围游荡。一只蚂蚁会不断地从一个地方跳跃到另一个地方以寻找食物。在移动时，它会在地面上留下一种叫做信息素的有机化合物。蚂蚁通过信息素路径相互交流。当一只蚂蚁找到一些食物时，它会携带它能承载的最大量。返回时，它会根据食物的数量和质量在路径上留下信息素。蚂蚁能够闻到信息素，因此其他蚂蚁也能闻到并跟随那条路径。信息素水平越高，选择那条路径的可能性就越大，而且越多的蚂蚁跟随一条路径，该路径上的信息素量也会增加。



我们来看一个例子。假设从巢穴到食物的地点有两条路径。最初，这两条路径上都没有信息素，所以选择这两条路径的概率是相等的，也就是说各有 50% 的可能性。因此可以假设有两只蚂蚁选择了两条不同的路径到达食物，因为选择这些路径的概率是五五开。



这两条路径的距离不同。走较短路径的蚂蚁会比另一只蚂蚁更早到达食物点（假设它们同时出发）



找到食物后，它会携带一些食物返回蚁群。当它追踪返回路径时，它会将信息素沉积在地面上。走较短路径的蚂蚁会更早到达蚁群。



当第三只蚂蚁想要出去寻找食物时，它会根据地面信息素水平选择距离较短的路径。由于较短的路径比较长的路径具有更多的信息素，因此第三只蚂蚁将遵循具有更多信息素的路径。



当沿着较长路径的蚂蚁返回蚁群时，更多的蚂蚁已经沿着信息素水平更高的路径走了。然后，当另一只蚂蚁试图从蚁群到达目的地（食物）时，它会发现每条路径都具有相同的信息素水平。因此，它随机选择一个。



一次又一次地重复这个过程（不断迭代）一段时间后，较短的路径比其他路径具有更多的信息素水平，并且有更高的概率遵循该路径，所有蚂蚁下一次都会遵循较短的路径。



从图中看这条路径最终趋向于一条直线，这也与我们提到的最小作用原理相关联。下面我们可以简单地模拟一下这个算法：

1. 初始化：算法开始时，模拟的蚂蚁被随机放置在不同的节点上。

2. 构建解决方案：每只蚂蚁根据概率选择下一个节点访问，这个概率依赖于两个因素：

    ● 信息素的浓度：某一路径上的信息素越多，表示该路径被越多蚂蚁认为是优秀的路径，因此被选中的概率越大。

    ● 启发式信息：如节点之间的距离。通常，距离越短，选择的概率越高。

3. 信息素更新：所有蚂蚁完成一次路径选择后，信息素会更新。更新原则包括：

    ● 信息素挥发：信息素会随时间逐渐减少，避免算法过早收敛于局部最优解。

    ● 信息素增强：蚂蚁走过的路径根据路径的质量增加信息素，路径越短，增加的信息素越多。

4. 迭代循环：重复上述过程，直到达到停止条件，如迭代次数、时间限制或解的质量。

好了，今天这期就到这里吧，我们下期见。



围城里的猫 MathSpark