Java 蚁群算法入门

花园里的蚂蚁

蚂蚁总能找到办法：我曾经在花园里发现它们排着整齐的队伍，一边把食物运到它们的巢穴。而且它们确实是有序的：所有的蚂蚁似乎都在沿着我的眼睛看不到的路径前进。后来，我发现这些路径不仅是不可见的：它们也是最优的。这有点令人惊讶，因为蚂蚁的视力非常有限，大脑也非常小。

殖民地机制既简单又令人惊讶。当蚂蚁穿越地形寻找食物时，它们会释放一种叫做信息素的化学物质。这意味着偶然发现较短路径的蚂蚁也会在它们身上沉积更多的信息素。因为路径更短，他们可以在相同的时间内穿越更多次。

信息素对蚂蚁来说很特别，原因有二：它们有感知它的感觉，并且会被它吸引。这意味着蚂蚁将倾向于穿越具有更强信息素踪迹的路径。这个的技术术语是耻辱，是允许这种惊人行为的机制：

蚁群中的所有蚂蚁都追求食物。他们随机遍历寻找到达它的方法。
一只非常幸运的蚂蚁先到达那里，比其他任何蚂蚁都早。他抓住食物，把它放回巢里。
新蚂蚁被分配了将食物运到巢穴的任务。这些新蚂蚁找到了 2 中存放的信息素，因此它们会跟随这条线索。
当 2 中的蚂蚁不断从食物到巢穴时，其他倒霉的蚂蚁仍在努力寻找自己的路。
现在在 2 中发现的路径信息素非常密集，因为它被几只蚂蚁穿越了好几次。即使在 1 中采用低效路径的蚂蚁现在也采用 2 中发现的路径，因为它非常有吸引力（即信息素密集）。
现在所有的殖民地都遵循最佳路径。

这意味着殖民地不会挨饿，而且系统已经收敛到最优状态。

代码中的蚂蚁

但这是一篇编程文章，而不是生物学文章。 1992 年，Marco Dorigo 将蚂蚁策略应用于优化问题的求解。计算机科学中存在搜索空间如此之大以至于不可能完全遍历它并找到最佳解决方案的问题。因此，Dorigo 提出的是构建“软件蚂蚁”，它将遍历搜索空间并寻找最佳解决方案，就像真正的蚂蚁一样。这些人造蚂蚁不能保证我们会找到最佳解决方案，但它们会找到足以满足我们需求的解决方案。这种算法称为启发式算法。

可以用这种方式解决的优化问题很多：我现在可以提到旅行商问题、背包问题，甚至是图像分割和聚类等图像处理任务。自从 Dorigo 在 1992 年提出建议以来，出现了几种遵循使用人工蚂蚁原则的算法，如蚂蚁系统、蚁群系统、最大最小蚂蚁系统等。这些算法被归类为元启发式算法，现在称为蚁群优化 (ACO)。

Java 中的蚂蚁

因此，借助蚁群优化，您可以使用多种算法解决多种问题。为了节省一些代码行，我开发了一个小框架，允许在 Java 中轻松实现 ACO 算法，称为 Isula（可在此处免费获得）。我将使用 Isula 的一些片段来演示如何在 Java 中实现 Ant 算法。


 while (iteration < numberOfIterations) {
      antColony.clearAntSolutions();
      antColony.buildSolutions(environment, configurationProvider);


      applyDaemonActions(DaemonActionType.AFTER_ITERATION_CONSTRUCTION);


      updateBestSolution(environment);
      iteration++;
    }

这是任何蚁群算法的主循环。我们需要为我们的程序建立一个停止条件，所以我们定义了一个参数来设置我们的蚂蚁将遍历问题空间的最大迭代次数，在 ACO 域中，问题空间通常是一个图。在每次迭代中，这些事情都会发生：

我们的蚂蚁准备自己构建一个解决方案：这可以是一条路线、一个集群或我们的问题需要我们找到的任何其他实体。
蚁群将遍历问题图，每只蚂蚁都会构建一个解决方案。其中有些会很好，有些会很糟糕。
我们的算法可能需要一些全局操作。例如，我们可以对我们的蚂蚁进行排序，只允许其中一些蚂蚁沉积信息素。这些过程在 ACO 术语中称为守护进程操作。
我们存储迄今为止构建的最佳解决方案。当我们达到最大迭代次数时，这将是我们程序的输出。

现在让我们更深入地了解一下殖民地如何构建解决方案。这是 AntColony 类的 buildSolution() 方法的一个片段：


 while (iteration < numberOfIterations) {
      antColony.clearAntSolutions();
      antColony.buildSolutions(environment, configurationProvider);


      applyDaemonActions(DaemonActionType.AFTER_ITERATION_CONSTRUCTION);


      updateBestSolution(environment);
      iteration++;
    }

那里需要注意一些事项：

AntColony 类管理存储在 hive 属性中的许多蚂蚁。这取决于您的算法特性或您要使用多少只蚂蚁的参数。
蚁群中的每只蚂蚁都会向它们的解决方案中添加组件，直到它被认为完成为止。例如，如果我们尝试对图像进行聚类，我们将继续向聚类中添加像素，直到我们覆盖了图像中的每个像素。
下一个组件的选择是随机的：蚂蚁会根据一些概率进行选择。他们做出决定的一个关键因素是与溶液成分相关的信息素数量，但根据您使用的算法，还会考虑其他几个因素。
Ant 完成其解决方案后，可能会发生一些事情。例如，您可以使用本地搜索程序改进生成的解决方案，或者您可以开始放置信息素。同样，这取决于您的算法的性质。

而且，如果您正在研究 Ant 算法，则更重要的类是 Ant 本身。这是取自 Isula 的 Ant 类的片段：


 while (iteration < numberOfIterations) {
      antColony.clearAntSolutions();
      antColony.buildSolutions(environment, configurationProvider);


      applyDaemonActions(DaemonActionType.AFTER_ITERATION_CONSTRUCTION);


      updateBestSolution(environment);
      iteration++;
    }

注意这一点：

这是参数化类。类参数 C 代表我们解决方案中的一个组件：在图像聚类示例中，此类将代表一个像素和分配的集群。
解决方案是这些组件的数组。此 Java Ant 通过将当前组件索引保留在数组中来控制解决方案的构建方式。
Ant 的行为还取决于您正在使用或建议的算法。例如，选择组件的具体规则因算法而异。这种特定的蚂蚁行为在 Isula 框架中被建模为 AntPolicy。

行动中的蚂蚁

让我们让我们的群体工作以解决特定的优化问题。流水车间调度优化问题试图找到多个作业的最佳排序，假设每个作业都需要在某些机器上处理，根据作业性质需要在每台机器上花费特定的时间。

我们将尝试找到作业的顺序——组合术语中的排列——以便我们在最短的时间内完成所有作业的处理。根据作业和机器的数量，精确解决这个问题可能需要相当长的时间，因此我们依靠基于 Isula 的蚂蚁来找到足够好的解决方案：


 while (iteration < numberOfIterations) {
      antColony.clearAntSolutions();
      antColony.buildSolutions(environment, configurationProvider);


      applyDaemonActions(DaemonActionType.AFTER_ITERATION_CONSTRUCTION);


      updateBestSolution(environment);
      iteration++;
    }

这是此处提供的基于 Isula 的 Java 程序的片段，它是 Thomas Stutzle 在论文“An ant approach to the flow shop problem”中提出的算法的改编版。看看以下内容：

FlowShopProblemSolver 是我们之前审查过的 AcoProblemSolver 类的扩展，经过一些小的修改以适应 Flow-Shop 问题。我们调用 solveProblem() 方法来触发解决方案的生成。
该论文提出了对著名算法 Max-Min Ant System 的改编，因此我们重用了该算法已有的一些代码，例如用于初始化信息素矩阵的守护程序操作。更新信息素矩阵策略也被重用，但需要进行一些调整。
Dorigo 在其蚁群系统算法中提出了一个非常流行的节点选择规则。 Stutzle 在其论文中使用了相同的方法，因此我们可以直接从 Isula 代码中可用的实现中重用它。
作者在 Ant 完成构建其解决方案后提出了本地搜索过程。我们为该任务开发了自定义 Ant Policy。

我们将使用包含 20 个作业和 5 台机器的问题实例来尝试我们的算法（此处提供数据集）。这是找到的解决方案的直观表示：