寻找最佳路径的概率技术

优化问题在科学和工业领域都非常重要。这些优化问题的一些实际例子是时间表调度，护理时间分配调度，火车调度，容量规划，旅行商问题，车辆路线问题，网上商店调度问题，投资组合优化等。为此，开发了许多优化算法这个原因。蚁群优化就是其中之一。蚁群优化是一种寻找最佳路径的概率技术。在计算机科学和研究中，蚁群优化算法用于解决不同的计算问题。

蚁群优化（ACO）最初是由Marco Dorigo在90年代提出的。论文。该算法是根据蚂蚁的觅食行为引入的，以寻找它们的殖民地和原始食物之间的路径。最初，它用于解决众所周知的旅行推销员问题。后来，它用于解决不同的硬优化问题。

蚂蚁是社交昆虫。他们生活在殖民地。蚂蚁的行为受寻找食物的目标控制。搜索时，蚂蚁在其殖民地附近漫游。一只蚂蚁反复从一个地方跳到另一个地方寻找食物。移动时，它会在地面上沉积成为费洛蒙的有机化合物。蚂蚁通过信息素路径相互通信。当蚂蚁发现一定数量的食物时，它会携带尽可能多的食物。返回时，它会根据食物的数量和质量在路径上沉积信息素。蚂蚁会闻到信息素。因此，其他蚂蚁可以闻到并沿着那条路走。信息素水平越高，选择该路径的可能性就越高，并且跟随该路径的蚂蚁越多，该路径上信息素的数量也会增加。

让我们来看一个例子。让我们考虑有两种途径可以从殖民地获取食物。首先，地面上没有信息素。因此，选择这两个路径的概率相等，即50％。让我们考虑两只蚂蚁选择两条不同的途径到达食物，因为选择这些途径的概率为五十。

这两条路径的距离不同。遵循较短路径的蚂蚁将比其他蚂蚁更早地到达食物。

找到食物后，它会随身携带一些食物，然后返回殖民地。当它跟踪返回路径时，它将信息素沉积在地面上。沿着较短路径的蚂蚁将更早到达殖民地。

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

到了沿着较长路径的蚂蚁返回殖民地时，更多的蚂蚁已经沿着具有更多信息素水平的路径行进了。然后，当另一只蚂蚁试图从殖民地到达目的地（食物）时，它将发现每条路径具有相同的信息素水平。因此，它随机选择一个。让我们考虑选择上面的一个（在下面的图片中）

在一段时间后，一次又一次地重复此过程，较短的路径具有比其他路径更高的信息素水平，并且遵循该路径的可能性更高，并且下次所有蚂蚁都将遵循较短的路径。

为了解决ACO的不同问题，建议使用三种不同的Ant-System版本：

蚂蚁密度和蚂蚁数量：每次蚂蚁从一个位置移动到另一个位置时，信息素都会更新。

蚂蚁周期：所有蚂蚁完成巡回演出后，信息素会更新。

让我们看看应用蚁群优化算法的伪代码。人工蚂蚁被用来寻找最佳解决方案。解决问题的第一步，每个蚂蚁都会生成一个解决方案。第二步，比较不同蚂蚁找到的路径。第三步，更新路径值或信息素。

procedure ACO_MetaHeuristic is while not_termination do generateSolutions() daemonActions() pheromoneUpdate() repeatend procedure

在许多优化问题中，您可以使用ACO查找最佳解决方案。他们之中有一些是：

1. 车辆通行能力不足的问题

2. 随机车辆路径问题（SVRP）

3. 带取送的车辆路径问题（VRPPD）

4. 网上商店调度问题（GSP）

5. 护理时间分配安排问题

6. 置换流水车间问题（PFSP）

7. 频率分配问题

8. 冗余分配问题

9. 旅行商问题（TSP）

让我们看一下ACO的数学术语（通常用于TSP问题）。

信息素更新

等式的左侧指示给定边x，y上的信息数量

ρ—信息素蒸发的速率

右边的最后一项表示信息素的沉积量。

其中L是蚂蚁游走长度的成本，而Q是常数。