65.9K
CodeProject 正在变化。 阅读更多。
Home

Java 蚁群算法入门

Carlos G. Gavidia
starIconstarIconstarIconstarIconstarIcon

5.00/5 (3投票s)

2015 年 7 月 20 日

CPOL

8分钟阅读

viewsIcon

31594

downloadIcon

1215

使用 Java 编程语言实现蚁群优化算法

引言

蚂蚁总能找到出路：我曾经在我家花园里看见它们排着整齐的队伍搬运食物回巢。它们确实很有秩序：所有的蚂蚁似乎都遵循着一条我肉眼看不见的路径。后来我发现，这些路径不仅是看不见的，而且是最佳的。这有点令人惊讶，因为蚂蚁的视力非常有限，大脑也很小。

群落机制既简单又令人惊讶。蚂蚁在搜寻食物的过程中，会留下一种叫做信息素的化学物质。这意味着，蚂蚁偶然发现了更短的路径，并在上面留下了更多的信息素。由于路径更短——即最优——它们在相同的时间内可以遍历更多次。

信息素对蚂蚁来说之所以特别，有两个原因：它们有感知它的能力，而且会被它吸引。这意味着蚂蚁倾向于遍历有更强信息素标记的路径。这个技术术语叫做“示信机制”，正是这个机制促成了这种惊人的行为。

  1. 群落里的所有蚂蚁都在寻找食物。它们随机地穿过花园，寻找到达食物的途径。
  2. 一只非常幸运的蚂蚁第一个到达了食物所在地，在其他蚂蚁之前。它抓起食物，并将其带回巢穴。
  3. 新的蚂蚁被分配了将食物运回巢穴的任务。这些新蚂蚁发现了（在2中）留下的信息素，于是沿着这条路前进。
  4. 当2号蚂蚁继续从食物返回巢穴时，其他不幸的蚂蚁仍在努力寻找自己的路。
  5. 现在，2号蚂蚁发现的路径信息素浓度很高，因为它被多只蚂蚁反复遍历。即使是那些走了低效路径（在1中）的蚂蚁，现在也选择了2号蚂蚁发现的路径，因为它现在非常有吸引力（即信息素浓度很高）。
  6. 现在，整个群落都遵循着这条最优路径。

这意味着群落不会挨饿，系统已经收敛到了最优解。

背景

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

可以用这种方式解决的优化问题非常多：我可以举出旅行商问题、背包问题，甚至是图像处理任务，如图像分割和聚类。自1992年Dorigo提出该方法以来，已经出现了许多遵循“人工蚂蚁”原理的算法，如蚁群系统（Ant System）、蚁群优化系统（Ant Colony System）、最大最小蚂蚁系统（Max-Min Ant System）等等。这些算法被归类到一个元启发式算法中，现在称为“蚁群优化”（Ant Colony Optimization, ACO）。

Using the Code

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

这是 AcoProblemSolver 类中 solveProblem() 方法的一部分。

        while (iteration < numberOfIterations) {

          antColony.clearAntSolutions();
          antColony.buildSolutions(environment, configurationProvider);

          applyDaemonActions(DaemonActionType.AFTER_ITERATION_CONSTRUCTION);

          updateBestSolution(environment);
          iteration++;
        }

这是任何蚁群算法的主要循环。我们需要为程序设定一个停止条件，因此我们定义一个参数来设置蚂蚁遍历问题空间的最多迭代次数，在 ACO 领域，这通常是一个图。每次迭代会发生三件事：

  1. 我们的蚂蚁准备构建一个解决方案：这可能是一条路径、一个聚类，或者我们的问题需要找到的任何其他实体。
  2. 蚁群将遍历问题图，每只蚂蚁都将构建一个解决方案。其中一些会很好，一些会很差。
  3. 有些全局操作可能需要包含在我们的算法中。例如，我们可以对蚂蚁进行排名，并只允许其中一些蚂蚁释放信息素。在 ACO 术语中，这些过程称为“守护者动作”（Daemon Actions）。
  4. 我们存储到目前为止构建的最佳解决方案。当我们达到最大迭代次数时，这将是我们程序的输出。

现在，让我们更深入地了解蚁群是如何构建解决方案的。这是 Isula AntColony 类中 buildSolution() 方法的一个代码片段。

        for (Ant<C, E> ant : hive) {

          while (!ant.isSolutionReady(environment)) {
            ant.selectNextNode(environment, configurationProvider);
          }

          ant.doAfterSolutionIsReady(environment, configurationProvider);
        }

这里有一些需要注意的地方：

  1. AntColony 类管理着许多蚂蚁，它们存储在 hive 属性中。你想使用多少只蚂蚁取决于你的算法特性或一个参数。
  2. 蚁群中的每只蚂蚁都会向其解决方案添加组件，直到解决方案被认为完成。例如，如果我们正在尝试对图像进行聚类，我们将继续向聚类中添加像素，直到覆盖图像中的所有像素。
  3. 下一个组件的选择是随机的：蚂蚁将根据某些概率进行选择。它们决策的一个关键因素是与解决方案组件相关的信息素量，但根据你使用的算法，还会考虑其他几个因素。
  4. 一旦蚂蚁完成了它的解决方案，可能会发生一些事情。例如，你可以使用局部搜索过程来改进生成的解决方案，或者你可以开始释放信息素。同样，这取决于你的算法的性质。

而且，如果你正在研究“蚂蚁”算法，最重要的一点是“蚂蚁”本身。这是 Isula 中 Ant 类的代码片段。

public abstract class Ant<C, E extends Environment> {

  private int currentIndex = 0;
  private List<AntPolicy<C, E>> policies = new ArrayList<AntPolicy<C, E>>();
  private C[] solution;
  private List<C> visitedComponents = new ArrayList<C>();

注意这一点：

  1. 这是一个参数化类。类参数 C 代表我们解决方案中的一个组件：在图像聚类示例中，这个类将代表一个像素及其分配的簇。
  2. 解决方案是这些组件的一个数组。这个 Java Ant 通过在数组中维护当前组件索引来控制解决方案的构建方式。
  3. 蚂蚁的行为也由你正在使用或提出的算法决定。例如，选择组件的特定规则在算法之间差异很大。这种特定的蚂蚁行为在 Isula 框架中被建模为 AntPolicy。

让我们让我们的蚁群工作起来，解决一个特定的优化问题。流水车间调度（Flow Shop Scheduling）优化问题试图找到一组作业的最佳排序，给定每个作业需要在某些机器上处理，并且在每台机器上需要的时间取决于作业的性质。

我们将尝试找到一个作业的排序——组合学上的排列——以便我们在最短的时间内完成所有作业的处理。根据作业和机器的数量，精确地解决这个问题可能需要相当长的时间，所以我们依赖 Isula 上的蚂蚁来找到一个“足够好”的解决方案。

          FlowShopProblemSolver problemSolver;

          ProblemConfiguration configurationProvider = new ProblemConfiguration();
          problemSolver = new FlowShopProblemSolver(graph, configurationProvider);
          configurationProvider.setEnvironment(problemSolver.getEnvironment());

          problemSolver.addDaemonActions(
              new StartPheromoneMatrixForMaxMin<Integer, FlowShopEnvironment>(),
              new FlowShopUpdatePheromoneMatrix());
          problemSolver.getAntColony().addAntPolicies(
              new PseudoRandomNodeSelection<Integer, FlowShopEnvironment>(),
              new ApplyLocalSearch());

          problemSolver.solveProblem();
          showSolution(graph, problemSolver);

这是 Isula 上一个基于 Java 的程序中的代码片段，该程序可在 此处 找到，它是 Thomas Stutzle 在论文“An ant approach to the flow shop problem”中提出的算法的一个改编。请看下面的内容：

  1. FlowShopProblemSolver 是我们之前回顾过的 AcoProblemSolver 类的扩展，并做了一些小的修改以适应流水车间问题。我们调用 solveProblem() 方法来触发解决方案的生成。
  2. 该论文提出了一种对众所周知的最大最小蚂蚁系统算法的改编，因此我们重用了该算法已有的代码，例如用于初始化信息素矩阵的守护者动作。信息素矩阵更新策略也被重用，但需要进行一些调整。
  3. Dorigo 在其蚁群系统算法中提出了一种非常流行的节点选择规则。Stutzle 在其论文中也使用了相同的规则，因此我们可以直接从 Isula 代码中可用的实现中重用它。
  4. 作者提出了一种在蚂蚁完成其解决方案构建后进行局部搜索的程序。我们为该任务开发了一个自定义的蚂蚁策略。

我们将使用一个包含 20 个作业和 5 台机器的问题实例来测试我们的算法（数据集可在 此处 找到）。这是找到的解决方案的视觉表示。

Flow Shop Scheduling Solution

关注点

我希望这篇文章能帮助你对通过蚁群算法可以实现的目标以及如何在 Java 编程语言中实现它们有所了解。我还邀请你查看 Isula 框架 并尝试使用已有的代码。我想用一些使用 ACO 算法解决优化问题的 Java 项目来结束本文。

© . All rights reserved.