Java 蚁群优化算法 | Baeldung中文网

1. 概述

这个系列旨在解释遗传算法的概念，并展示最常见的实现。本教程将介绍蚂蚁群优化（Ant Colony Optimization, ACO） 的概念，随后给出代码示例。

2. 蚂蚁群优化的工作原理

蚂蚁群优化是一种受到蚂蚁自然行为启发的遗传算法。要全面理解ACO算法，我们需要了解其基本概念：

蚂蚁使用信息素寻找家与食物源之间的最短路径。
信息素会快速挥发。
蚂蚁更倾向于选择信息素浓度更高、路径较短的路线。

让我们通过一个例子来说明ACO在旅行商问题（Traveling Salesman Problem, TSP） 中的应用。在这个案例中，我们需要找到图中所有节点之间的最短路径：

根据自然行为，蚂蚁会在探索过程中开始尝试新的路径。蓝色线条越深，表示被蚂蚁频繁使用的路径，而绿色表示当前发现的最短路径：

最终，我们将得到所有节点之间的最短路径：

用于ACO测试的美观GUI工具可以在这里找到：此处。

3. Java实现

3.1. ACO参数

让我们讨论ACO算法的主要参数，这些参数在AntColonyOptimization类中声明：

private double c = 1.0;
private double alpha = 1;
private double beta = 5;
private double evaporation = 0.5;
private double Q = 500;
private double antFactor = 0.8;
private double randomFactor = 0.01;

参数c表示初始的轨迹数量，在模拟开始时。alpha控制信息素的重要性，而beta控制距离优先级。通常，为了获得最佳结果，beta参数应大于alpha。

接下来，evaporation变量表示每次迭代中信息素蒸发的百分比，Q提供了每个Ant在轨迹上留下的总信息素量，antFactor告诉我们每座城市将使用多少只蚂蚁。

最后，我们需要在模拟中引入一些随机性，这由randomFactor处理。

3.2. 创建蚂蚁

每个Ant将能够访问特定的城市，记住所有访问过的城市，并跟踪轨迹长度：

public void visitCity(int currentIndex, int city) {
    trail[currentIndex + 1] = city;
    visited[city] = true;
}

public boolean visited(int i) {
    return visited[i];
}

public double trailLength(double graph[][]) {
    double length = graph[trail[trailSize - 1]][trail[0]];
    for (int i = 0; i < trailSize - 1; i++) {
        length += graph[trail[i]][trail[i + 1]];
    }
    return length;
}

3.3. 设置蚂蚁

开始时，我们需要初始化ACO代码实现，提供轨迹和蚂蚁矩阵：

graph = generateRandomMatrix(noOfCities);
numberOfCities = graph.length;
numberOfAnts = (int) (numberOfCities * antFactor);

trails = new double[numberOfCities][numberOfCities];
probabilities = new double[numberOfCities];
ants = new Ant[numberOfAnts];
IntStream.range(0, numberOfAnts).forEach(i -> ants.add(new Ant(numberOfCities)));

然后，我们需要设置ants矩阵，以随机的城市开始：

public void setupAnts() {
    IntStream.range(0, numberOfAnts)
      .forEach(i -> {
          ants.forEach(ant -> {
              ant.clear();
              ant.visitCity(-1, random.nextInt(numberOfCities));
          });
      });
    currentIndex = 0;
}

对于循环的每一次迭代，我们将执行以下操作：

IntStream.range(0, maxIterations).forEach(i -> {
    moveAnts();
    updateTrails();
    updateBest();
});

3.4. 移动蚂蚁

我们从moveAnts()方法开始。我们需要为所有蚂蚁选择下一个城市，记住蚂蚁会尝试跟随其他蚂蚁的轨迹：

public void moveAnts() {
    IntStream.range(currentIndex, numberOfCities - 1).forEach(i -> {
        ants.forEach(ant -> {
            ant.visitCity(currentIndex, selectNextCity(ant));
        });
        currentIndex++;
    });
}

最重要的部分是正确选择下一个要访问的城市。 我们应该基于概率逻辑选择下一个城市。首先，我们可以检查蚂蚁是否应随机选择城市：

int t = random.nextInt(numberOfCities - currentIndex);
if (random.nextDouble() < randomFactor) {
    OptionalInt cityIndex = IntStream.range(0, numberOfCities)
      .filter(i -> i == t && !ant.visited(i))
      .findFirst();
    if (cityIndex.isPresent()) {
        return cityIndex.getAsInt();
    }
}

如果没有选择任何随机城市，我们需要计算选择每个城市的可能性，记住蚂蚁更倾向于遵循强度更大且更短的轨迹。我们可以将移动到每个城市的概率存储在一个数组中：

public void calculateProbabilities(Ant ant) {
    int i = ant.trail[currentIndex];
    double pheromone = 0.0;
    for (int l = 0; l < numberOfCities; l++) {
        if (!ant.visited(l)){
            pheromone
              += Math.pow(trails[i][l], alpha) * Math.pow(1.0 / graph[i][l], beta);
        }
    }
    for (int j = 0; j < numberOfCities; j++) {
        if (ant.visited(j)) {
            probabilities[j] = 0.0;
        } else {
            double numerator
              = Math.pow(trails[i][j], alpha) * Math.pow(1.0 / graph[i][j], beta);
            probabilities[j] = numerator / pheromone;
        }
    }
}

计算完概率后，我们可以使用以下方式决定去哪个城市：

double r = random.nextDouble();
double total = 0;
for (int i = 0; i < numberOfCities; i++) {
    total += probabilities[i];
    if (total >= r) {
        return i;
    }
}

3.5. 更新轨迹

在这个步骤中，我们应该更新轨迹和剩余的信息素：

public void updateTrails() {
    for (int i = 0; i < numberOfCities; i++) {
        for (int j = 0; j < numberOfCities; j++) {
            trails[i][j] *= evaporation;
        }
    }
    for (Ant a : ants) {
        double contribution = Q / a.trailLength(graph);
        for (int i = 0; i < numberOfCities - 1; i++) {
            trails[a.trail[i]][a.trail[i + 1]] += contribution;
        }
        trails[a.trail[numberOfCities - 1]][a.trail[0]] += contribution;
    }
}

3.6. 更新最优解

这是每次迭代的最后一步。我们需要更新最优解，以便保留对它的引用：

private void updateBest() {
    if (bestTourOrder == null) {
        bestTourOrder = ants[0].trail;
        bestTourLength = ants[0].trailLength(graph);
    }
    for (Ant a : ants) {
        if (a.trailLength(graph) < bestTourLength) {
            bestTourLength = a.trailLength(graph);
            bestTourOrder = a.trail.clone();
        }
    }
}

所有迭代结束后，最终结果将显示ACO找到的最佳路径。请注意，随着城市数量的增加，找到最短路径的概率会降低。

4. 总结

本教程介绍了蚂蚁群优化算法。即使没有遗传算法的先前知识，仅凭基础计算机编程技能，你也能学习到这个领域。

本教程中代码片段的完整源代码可以在GitHub项目中找到：GitHub项目。

要查看系列中的所有文章，包括其他遗传算法的例子，请参阅以下链接：

Persistence

REST

Security