The Traveling Salesman Problem in Java – Java中的旅行推销员问题

最后修改: 2016年 12月 19日

中文/混合/英文(键盘快捷键：t)

1. Introduction

1.介绍

In this tutorial, we’ll learn about the Simulated Annealing algorithm and we’ll show the example implementation based on the Traveling Salesman Problem (TSP).

在本教程中，我们将学习模拟退火算法，并展示基于旅行推销员问题（TSP）的实例实现。

2. Simulated Annealing

2.模拟退火

The Simulated Annealing algorithm is a heuristic for solving the problems with a large search space.

模拟退火算法是一种启发式算法，用于解决具有较大搜索空间的问题。

The Inspiration and the name came from annealing in metallurgy; it is a technique that involves heating and controlled cooling of a material.

灵感和名称来自冶金学中的退火；它是一种涉及加热和控制材料冷却的技术。

In general, the Simulated Annealing decreases the probability of accepting worse solutions as it explores the solution space and lowers the temperature of the system. The following animation shows the mechanism of finding the best solution with the Simulated Annealing algorithm:

一般来说，模拟退火算法在探索解决方案空间和降低系统温度的过程中，会降低接受较差解决方案的概率。下面的动画显示了用模拟退火算法寻找最佳解决方案的机制。

Hill Climbing with Simulated Annealing

As we may observe, the algorithm uses a wider solution range with high temperature of the system, searching for global optimum. While lowering the temperature, the search range is becoming smaller, until it finds the global optimum.

我们可以看到，在系统温度较高的情况下，该算法使用了较宽的求解范围，寻找全局最优。在降低温度的同时，搜索范围越来越小，直到找到全局最优。

The algorithm has a few few parameters to work with:

该算法有少数几个参数可以使用。

  • number of iterations – stopping condition for simulations
  • initial temperature – the starting energy of the system
  • cooling rate parameter – the percentage by which we reduce the temperature of the system
  • minimum temperature – optional stopping condition
  • simulation time – optional stopping condition

The values of those parameters must be carefully selected – since they may have significant influence on the performance of the process.

这些参数的值必须仔细选择–因为它们可能对工艺的性能有重大影响。

3. Traveling Salesman Problem

3.旅行推销员问题

The Travelling Salesman Problem (TSP) is the most known computer science optimization problem in a modern world.

旅行推销员问题（TSP）是现代世界中最著名的计算机科学优化问题。

In simple words, it is a problem of finding optimal route between nodes in the graph. The total travel distance can be one of the optimization criterion. For more details on TSP please take a look here.

简单地说，它是一个寻找图中节点之间最佳路线的问题。总旅行距离可以作为优化标准之一。关于TSP的更多细节，请看这里。

4. Java Model

4.Java模型

In order to solve the TSP problem, we’ll need two model classes, namely City and Travel. In the first one, we’ll store the coordinates of the nodes in the graph:

为了解决TSP问题，我们需要两个模型类，即城市和旅行。在第一个模型中，我们将存储图中节点的坐标。

@Data
public class City {

    private int x;
    private int y;

    public City() {
        this.x = (int) (Math.random() * 500);
        this.y = (int) (Math.random() * 500);
    }

    public double distanceToCity(City city) {
        int x = Math.abs(getX() - city.getX());
        int y = Math.abs(getY() - city.getY());
        return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
    }

}

The constructor of City class allows us to create random locations of the cities. The distanceToCity(..) logic is responsible for calculations regarding the distance between the cities.

城市类的构造函数允许我们创建城市的随机位置。distanceToCity(..)逻辑负责计算城市之间的距离。

The following code is responsible for modeling a traveling salesman tour. Let’s start with generating initial order of cities in travel:

下面的代码负责建立一个旅行推销员旅游的模型。让我们从生成旅行中的城市的初始顺序开始。

public void generateInitialTravel() {
    if (travel.isEmpty()) {
        new Travel(10);
    }
    Collections.shuffle(travel);
}

In addition to generating the initial order, we need the methods for swapping the random two cities in the traveling order. We’ll use it to search for the better solutions inside the Simulated Annealing algorithm:

除了生成初始顺序外，我们还需要交换行驶顺序中的随机两个城市的方法。我们将用它来搜索模拟退火算法里面更好的解决方案。

public void swapCities() {
    int a = generateRandomIndex();
    int b = generateRandomIndex();
    previousTravel = new ArrayList<>(travel);
    City x = travel.get(a);
    City y = travel.get(b);
    travel.set(a, y);
    travel.set(b, x);
}

Furthermore, we need a method to revert the swap generating in the previous step, if the new solution will be not accepted by our algorithm:

此外，如果新的解决方案不被我们的算法所接受，我们需要一种方法来恢复在前一步生成的交换。

public void revertSwap() {
    travel = previousTravel;
}

The last method that we want to cover is the calculation of the total travel distance, which will be used as an optimization criterion:

我们要介绍的最后一种方法是计算总的旅行距离，这将作为一个优化标准来使用。

public int getDistance() {
    int distance = 0;
    for (int index = 0; index < travel.size(); index++) {
        City starting = getCity(index);
        City destination;
        if (index + 1 < travel.size()) {
            destination = getCity(index + 1);
        } else {
            destination = getCity(0);
        }
            distance += starting.distanceToCity(destination);
    }
    return distance;
}

Now, let’s focus on the main part, the Simulated Annealing algorithm implementation.

现在，让我们专注于主要部分，即模拟退火算法的实现。

5. Simulated Annealing Implementation

5.模拟退火的实施

In the following Simulated Annealing implementation, we are going to solve the TSP problem. Just a quick reminder, the objective is to find the shortest distance to travel all cities.

在下面的模拟退火实现中，我们将解决TSP问题。简单提醒一下，我们的目标是找到前往所有城市的最短距离。

In order to start process, we need to provide three main parameters, namely startingTemperature, numberOfIterations and coolingRate:

为了启动进程，我们需要提供三个主要参数，即启动温度、迭代次数和冷却速率。

public double simulateAnnealing(double startingTemperature,
  int numberOfIterations, double coolingRate) {
    double t = startingTemperature;
    travel.generateInitialTravel();
    double bestDistance = travel.getDistance();

    Travel currentSolution = travel;
    // ...
}

Before the start of the simulation, we generate initial (random) order of cities and calculate the total distance for travel. As this is the first calculated distance, we save it inside the bestDistance variable, alongside with the currentSolution.

在模拟开始之前，我们生成初始（随机）的城市顺序，并计算出总的旅行距离。由于这是第一次计算的距离，我们将其保存在bestDistance变量中，与currentSolution.一起。

In the next step we start a main simulations loop:

在下一步，我们开始一个主模拟循环。

for (int i = 0; i < numberOfIterations; i++) {
    if (t > 0.1) {
        //...
    } else {
        continue;
    }
}

The loop will last the number of iterations that we specified. Moreover, we added a condition to stop the simulation if the temperature will be lower or equal to 0.1. It will allow us to save the time of simulations, as with low temperatures the optimization differences are almost not visible.

循环将持续我们指定的迭代次数。此外，我们添加了一个条件，如果温度低于或等于0.1，就停止模拟。这将使我们节省模拟的时间，因为在低温度下，优化的差异几乎是不可见的。

Let’s look at the main logic of the Simulated Annealing algorithm:

让我们来看看模拟退火算法的主要逻辑。

currentSolution.swapCities();
double currentDistance = currentSolution.getDistance();
if (currentDistance < bestDistance) {
    bestDistance = currentDistance;
} else if (Math.exp((bestDistance - currentDistance) / t) < Math.random()) {
    currentSolution.revertSwap();
}

In each step of simulation we randomly swap two cities in the traveling order.

在模拟的每一步中，我们随机交换两个城市的行驶顺序。

Furthermore, we calculate the currentDistance. If the newly calculated currentDistance is lower than bestDistance, we save it as the best.

此外，我们计算currentDistance。如果新计算的currentDistance低于bestDistance，我们将其保存为最佳。

Otherwise, we check if Boltzmann function of probability distribution is lower than randomly picked value in a range from 0-1. If yes, we revert the swap of the cities. If not, we keep the new order of the cities, as it can help us to avoid the local minima.

否则，我们检查概率分布的Boltzmann函数是否低于0-1范围内的随机挑选的值。如果是，我们就恢复城市的互换。如果不是，我们就保持新的城市顺序，因为这可以帮助我们避免局部最小值。

Finally, in each step of the simulation we reduce the temperature by provided coolingRate:

最后，在模拟的每一步中，我们通过提供冷却速率（coolingRate）来降低温度：。

t *= coolingRate;

After the simulation we return the best solution that we found using Simulated Annealing.

仿真结束后，我们返回我们用模拟退火法找到的最佳解决方案。

Please note the few tips on how to choose the best simulation parameters:

请注意关于如何选择最佳模拟参数的几个提示：。

  • for small solution spaces it’s better to lower the starting temperature and increase the cooling rate, as it will reduce the simulation time, without lose of quality
  • for bigger solution spaces please choose the higher starting temperature and small cooling rate, as there will be more local minima
  • always provide enough time to simulate from the high to low temperature of the system

Don’t forget to spend some time on the algorithm tuning with the smaller problem instance, before you start the main simulations, as it will improve final results. The tuning of the Simulated Annealing algorithm was shown for example in this article.

不要忘记在开始主要模拟之前，花一些时间对较小的问题实例进行算法调整，因为这将改善最终结果。例如，模拟退火算法的调整在本文中得到展示。

6. Conclusion

6.结论

In this quick tutorial we were able to learn about the Simulated Annealing algorithm and we solved the Travelling Salesman Problem. This hopefully goes to show how handy is this simple algorithm, when applied to certain types of optimization problems.

在这个快速教程中，我们能够了解到模拟退火算法，并且我们解决了旅行推销员问题。希望这能说明这种简单的算法在应用于某些类型的优化问题时是多么的方便。

The full implementation of this article can be found over on GitHub.

本文的完整实现可以在GitHub上找到over on GitHub.