Simulated Annealing - Solving the Travelling Salesman Problem (TSP)

• Download source code - 8.95 KB

Introduction

Combinatorial optimization is the process of finding an optimal solution for problems with a large discrete set of possible solutions. Such optimizations can be used to solve problems in resources management, operations management, and quality control, such as routing, scheduling, packing, production management, and resources assignment. Meta-heuristic algorithms have proved to be good solvers for combinatorial optimization problems, in a way that they provide good optimal solutions in a bounded (usually short) time.

Examples of meta-heuristics are: simulated annealing, tabu search, harmony search, scatter search, genetic algorithms, ant colony optimization, and many others. In this article, we will be discussing Simulated Annealing and its implementation in solving the Travelling Salesman Problem (TSP).

Background

Simulated Annealing was given this name in analogy to the “Annealing Process” in thermodynamics, specifically with the way metal is heated and then is gradually cooled so that its particles will attain the minimum energy state (annealing). Then, the aim for a Simulated Annealing algorithm is to randomly search for an objective function (that mainly characterizes the combinatorial optimization problem).

Simulated Annealing's advantage over other methods is the ability to obviate being trapped in local minima. In here, we mean that the algorithm does not always reject changes that decrease the objective function but also changes that increase the objective function according to its probability function:

P = exp (-∆f/T)

Where T is the control parameter (analogy to temperature) and ∆f is the variation in the objective function.

The probability function is definitely a derivative of the Boltzmann probability distribution function.

Travelling Salesman Problem

A salesman wants to travel t o N cities (he should pass by each city). How can we order the cities so that the salesman’s journey will be the shortest? The objective function to minimize here is the length of the journey (the sum of the distances between all the cities in a specified order).

To start solving this problem; we need:

1. Configuration setting: This is the permutation of the cities from 1 to N, given in all orders. Selecting an optimal one between these permutations is our aim.
2. Rearrangement strategy: The strategy that we will follow here is replacing sections of the path, and replacing them with random ones to retest if this modified one is optimal or not.
3. The objective function (which is the aim of the minimization): This is the sum of the distances between all the cities for a specific order.

Using the code

The class TravellingSalesmanProblem.cs does the job. Just instantiate a new object, and assign to it your adjacency matrix (which is a text file), then call the Anneal() method. The Anneal() method will return the shortest path (order of the cities).

TravellingSalesmanProblem problem = new TravellingSalesmanProblem();
problem.FilePath = "Cities.txt";
problem.Anneal();

Below is the code for the Simulated Annealing algorithm:

/// <summary>
/// Annealing Process
/// </summary>
public void Anneal()
{
    int iteration = -1;

    double temperature = 10000.0;
    double deltaDistance = 0;
    double coolingRate = 0.9999;
    double absoluteTemperature = 0.00001;

    LoadCities();

    double distance = GetTotalDistance(currentOrder);

    while (temperature > absoluteTemperature)
    {
        nextOrder = GetNextArrangement(currentOrder);

        deltaDistance = GetTotalDistance(nextOrder) - distance;

        //if the new order has a smaller distance
        //or if the new order has a larger distance but 
        //satisfies Boltzman condition then accept the arrangement
        if ((deltaDistance < 0) || (distance > 0 && 
             Math.Exp(-deltaDistance / temperature) > random.NextDouble()))
        {
            for (int i = 0; i < nextOrder.Count; i++)
                currentOrder[i] = nextOrder[i];

            distance = deltaDistance + distance;
        }

        //cool down the temperature
        temperature *= coolingRate;

        iteration++;
    }

    shortestDistance = distance;
}

References

• Optimization by Simulated Annealing – S. Kirkpatrick
• Simulated Annealing Overview - Franco Busetti
• Metaheuristics Progress as Real Problem Solvers – Springer
• Numerical Recipes in C: The Art of Scientific Computing