Simulated Annealing Example in C#

• Download source files - 16.11 KB

Introduction

Simulated annealing (SA) is an AI algorithm that starts with some solution that is totally random, and changes it to another solution that is “similar” to the previous one. It makes slight changes to the result until it reaches a result close to the optimal.

Simulated annealing is a stochastic algorithm, meaning that it uses random numbers in its execution. So every time you run the program, you might come up with a different result. It produces a sequence of solutions, each one derived by slightly altering the previous one, or by rejecting a new solution and falling back to the previous one without any change.

When SA starts, it alters the previous solution even if it is worse than the previous one. However, the probability with which it will accept a worse solution decreases with time,(cooling process) and with the “distance” the new (worse) solution is from the old one. It always accepts a new solution if it is better than the previous one.

The probability used is derived from The Maxwell-Boltzmann distribution which is the classical distribution function for distribution of an amount of energy between identical but distinguishable particles. It's value is:

Exp(-delta/temperature)

Besides the presumption of distinguishability, classical statistical physics postulates further that:

• There is no restriction on the number of particles which can occupy a given state.
• At thermal equilibrium, the distribution of particles among the available energy states will take the most probable distribution consistent with the total available energy and total number of particles.
• Every specific state of the system has equal probability.

The name “simulated annealing” is derived from the physical heating of a material like steel. This material is subjected to high temperature and then gradually cooled. The gradual cooling allows the material to cool to a state in which there are few weak points. It achieves a kind of “global optimum” wherein the entire object achieves a minimum energy crystalline structure.

If the material is rapidly cooled, some parts of the object, the object is easily broken (areas of high energy structure). The object has achieved some local areas of optimal strength, but is not strong throughout, with rapid cooling.

In my program, I took the example of the travelling salesman problem: file tsp.txt.The matrix designates the total distance from one city to another (nb: diagonal is 0 since the distance of a city to itself is 0).

As for the program, I tried developing it as simple as possible to be understandable.

You could change the starting temperature, decrease or increase epsilon (the amount of temperature that is cooling off) and alter alpha to observe the algorithm's performance.

The program calculates the minimum distance to reach all cities(TSP). The best minimal distance I got so far using that algorithm was 17. Can you calculate a better distance?

The Code

public string StartAnnealing()
{
    TspDataReader.computeData();
    ArrayList list = new ArrayList();
    //primary configuration of cities
    int [] current={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};
    //the next configuration of cities to be tested
    int []next=new int[15];
    int iteration =-1;
    //the probability
    double proba;
    double alpha =0.999;
    double temperature = 400.0;
    double epsilon = 0.001;
    double delta;
    double distance = TspDataReader.computeDistance(current);

    //while the temperature did not reach epsilon
    while(temperature > epsilon)
    {
        iteration++;
    
        //get the next random permutation of distances 
        computeNext(current,next);
        //compute the distance of the new permuted configuration
        delta = TspDataReader.computeDistance(next)-distance;
        //if the new distance is better accept it and assign it
        if(delta<0)
        {
            assign(current,next);
            distance = delta+distance;
        }
        else
        {
            proba = rnd.Next();
            //if the new distance is worse accept 
            //it but with a probability level
            //if the probability is less than 
            //E to the power -delta/temperature.
            //otherwise the old value is kept
            if(proba< Math.Exp(-delta/temperature))
            {
                assign(current,next);
                distance = delta+distance;
            }
        }
        //cooling process on every iteration
        temperature *=alpha;
        //print every 400 iterations
        if (iteration%400==0)
        Console.WriteLine(distance);
    }
    try
    {
        return "best distance is"+distance;
    }
    catch
    {
        return "error";
    }
}

/// <summary>
/// compute a new next configuration
/// and save the old next as current
/// </summary>
/// <param name="c">current configuration</param>
/// <param name="n">next configuration</param>
void computeNext(int[] c, int[] n)
{
    for(int i=0;i<c.Length;i++)
    n[i]=c[i];
    int i1 = (int)(rnd.Next(14))+1;
    int i2 = (int)(rnd.Next(14))+1;
    int aux = n[i1];
    n[i1]=n[i2];
    n[i2]=aux;
}

Make sure the debug window is opened to observe the algorithm's behavior through iterations.

Happy programming!