The new Certification Class of REST With Spring is out:

>> CHECK OUT THE COURSE

1. Introduction

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).

2. Simulated Annealing

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:

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

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

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.

4. Java Model

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:

@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.

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 = 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

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.

In order to start process, we need to provide three main parameters, namely startingTemperaturenumberOfIterations 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.

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.

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.

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.

Finally, in each step of the simulation we reduce the temperature by provided 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

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.

Go deeper into building a REST API with Spring:

>> CHECK OUT THE COURSE

  • sprcow

    I’m a little confused by your swapCities method. It appears to move a city from point b to point a in the list, but never does anything with the city in point a. Doesn’t this result in one city being represented twice in the list, and one city being overridden?

    • sprcow

      Follow up question: Is there any reason not to terminate the simulateAnnealing method as soon as the cooling rate has fallen below 0.1? It looks like the loop just spins and does nothing once that occurs.

      • Michał Aibin

        Hi @sprcow:disqus,
        Thanks for noticing. Indeed, there was a small bug with swap cities as well as the main loop can be terminated when temperature of the system is below 0.1 (it’s not a cooling rate, but I understood the context).
        We updated the code on GitHub, the article will be updated shortly.

        • sprcow

          Thanks for the response. Another observation: Math.exp((current-best) / t) appears as though it will always give a value > 1, because if you’re entering that block, you know current > best, so you’re putting a positive value into exp(). If the return is always >1, then it will never be less than Math.random(). Is this statement supposed to be best-current instead? or am I misinterpreting it somehow?

          Similarly, your earlier conditional checks for currentDistance == 0. Is this intended to be current-best? I am not clear on how current could be 0.

          • Michał Aibin

            @sprcow:disqus The code was reviewed after your first comments, and the article was updated, so it should be fine now. Thanks for your feedback.

  • Viet Nguyen

    Thank you for your great post. It somehow looks like The Gradient Descent Algorithm. To me, it is a little weird to hard code the `numberOfIterations`. Did you compare these 2 methods, e.g. by comparing `numberOfIterations` with `convergedCoefficient` of TGDA?

    • Michał Aibin

      Thanks!
      The number of iterations is somehow the maximum limit for simulations. That’s why we introduce minimum temperature level, in order to break the loop after the t < 0.1, as later there are almost no improvements.
      Anyways, I never tried The Gradient Descent Algorithm, it's on my list to check 🙂