1. Introduction
1.介绍
The aim of this series is to explain the idea of genetic algorithms and show the most known implementations.
本系列的目的是解释遗传算法的理念并展示最知名的实现。
In this tutorial, we’ll describe the concept of the ant colony optimization (ACO), followed by the code example.
在本教程中，我们将描述蚁群优化的概念（ACO），然后是代码示例。
2. How ACO Works
2.ACO是如何工作的
ACO is a genetic algorithm inspired by an ant’s natural behavior. To fully understand the ACO algorithm, we need to get familiar with its basic concepts:
ACO是一种遗传算法，其灵感来源于蚂蚁的自然行为。为了充分理解ACO算法，我们需要熟悉其基本概念。
- ants use pheromones to find the shortest path between home and food source
- pheromones evaporate quickly
- ants prefer to use shorter paths with denser pheromone
Let’s show a simple example of ACO used in the Traveling Salesman Problem. In the following case, we need to find the shortest path between all nodes in the graph:
让我们展示一个ACO用于旅行推销员问题的简单例子。在下面这个例子中，我们需要找到图中所有节点之间的最短路径。
Following by natural behaviors, ants will start to explore new paths during the exploration. Stronger blue color indicates the paths that are used more often than the others, whereas green color indicates the current shortest path that is found:
按照自然行为，蚂蚁在探索过程中会开始探索新路径。较强的蓝色表示比其他路径更经常使用的路径，而绿色表示当前发现的最短路径。
As a result, we’ll achieve the shortest path between all nodes:
因此，我们将实现所有节点间的最短路径。
The nice GUI-based tool for ACO testing can be found here.
基于GUI的不错的ACO测试工具可以在这里找到。
3. Java Implementation
3.Java实现
3.1. ACO Parameters
3.1.ACO参数
Let’s discuss the main parameters for the ACO algorithm, declared in the AntColonyOptimization class:
让我们讨论一下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;Parameter c indicates the original number of trails, at the start of the simulation. Furthermore, alpha controls the pheromone importance, while beta controls the distance priority. In general, the beta parameter should be greater than alpha for the best results.
参数c表示模拟开始时的原始小路数量。此外，alpha控制信息素的重要性，而beta控制距离的优先级。一般来说，beta参数应大于alpha以获得最佳结果。
Next, the evaporation variable shows the percent how much the pheromone is evaporating in every iteration, whereas Q provides information about the total amount of pheromone left on the trail by each Ant, and antFactor tells us how many ants we’ll use per city.
接下来，evaporation变量显示了每次迭代中信息素蒸发的百分比，而Q则提供了关于每个Ant留下的信息素总量的信息，antFactor告诉我们每个城市将使用多少只蚂蚁。
Finally, we need to have a little bit of randomness in our simulations, and this is covered by randomFactor.
最后，我们的模拟需要有一点随机性，这由randomFactor涵盖。
3.2. Create Ants
3.2.创造蚂蚁
Each Ant will be able to visit a specific city, remember all visited cities, and keep track of the trail length:
每个蚂蚁将能够访问一个特定的城市，记住所有访问过的城市，并记录足迹长度。
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. Setup Ants
3.3.设置蚂蚁
At the very beginning, we need to initialize our ACO code implementation by providing trails and ants matrices:
在一开始，我们需要通过提供轨迹和蚂蚁矩阵来初始化我们的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)));Next, we need to setup the ants matrix to start with a random city:
接下来，我们需要设置ants矩阵，从一个随机城市开始。
public void setupAnts() {
IntStream.range(0, numberOfAnts)
.forEach(i -> {
ants.forEach(ant -> {
ant.clear();
ant.visitCity(-1, random.nextInt(numberOfCities));
});
});
currentIndex = 0;
}For each iteration of the loop, we’ll perform the following operations:
对于循环的每一次迭代，我们将执行以下操作。
IntStream.range(0, maxIterations).forEach(i -> {
moveAnts();
updateTrails();
updateBest();
});3.4. Move Ants
3.4.移动蚂蚁
Let’s start with the moveAnts() method. We need to choose the next city for all ants, remembering that each ant tries to follow other ants’ trails:
让我们从moveAnts()方法开始。我们需要为所有蚂蚁选择下一个城市，记住，每只蚂蚁都会试图跟随其他蚂蚁的足迹。
public void moveAnts() {
IntStream.range(currentIndex, numberOfCities - 1).forEach(i -> {
ants.forEach(ant -> {
ant.visitCity(currentIndex, selectNextCity(ant));
});
currentIndex++;
});
}The most important part is to properly select next city to visit. We should select the next town based on the probability logic. First, we can check if Ant should visit a random city:
最重要的部分是正确选择下一个要访问的城市。我们应该根据概率逻辑来选择下一个城市。首先，我们可以检查Ant是否应该访问一个随机的城市。
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();
}
}If we didn’t select any random city, we need to calculate probabilities to select the next city, remembering that ants prefer to follow stronger and shorter trails. We can do this by storing the probability of moving to each city in the array:
如果我们没有选择任何随机的城市，我们需要计算概率来选择下一个城市，记住蚂蚁更喜欢遵循更强更短的路径。我们可以通过在数组中存储移动到每个城市的概率来做到这一点。
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;
}
}
}
After we calculate probabilities, we can decide to which city to go to by using:
在我们计算出概率后，我们可以通过使用决定去哪个城市。
double r = random.nextDouble();
double total = 0;
for (int i = 0; i < numberOfCities; i++) {
total += probabilities[i];
if (total >= r) {
return i;
}
}3.5. Update Trails
3.5.更新路径
In this step, we should update trails and the left pheromone:
在这一步，我们应该更新小路和左边的信息素。
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. Update the Best Solution
3.6.更新最佳解决方案
This is the last step of each iteration. We need to update the best solution in order to keep the reference to it:
这是每一次迭代的最后一步。我们需要更新最佳解决方案，以保持对它的引用。
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();
}
}
}After all iterations, the final result will indicate the best path found by ACO. Please note that by increasing the number of cities, the probability of finding the shortest path decreases.
在所有迭代之后，最终的结果将表明ACO找到的最佳路径。请注意，随着城市数量的增加，找到最短路径的概率会下降。
4. Conclusion
4.结论
This tutorial introduces the Ant Colony Optimization algorithm. You can learn about genetic algorithms without any previous knowledge of this area, having only basic computer programming skills.
本教程介绍了蚁群优化算法。你可以学习遗传算法，而不需要任何该领域的知识，只需具备基本的计算机编程技能。
The complete source code for the code snippets in this tutorial is available in the GitHub project.
本教程中代码片段的完整源代码可在GitHub项目中获得，。
For all articles in the series, including other examples of genetic algorithms, check out the following links:
对于该系列的所有文章，包括遗传算法的其他例子，请查看以下链接。
- How to Design a Genetic Algorithm in Java
- The Traveling Salesman Problem in Java
- Ant Colony Optimization (this)