14,326,100 members

# Simulated Annealing Example in C#

Rate this:
30 Jun 2006CPOL
Artificial intelligence algorithm: simulated annealing

## 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()
{
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;

//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
//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!

## Share

 Architect Lebanon
No Biography provided

 First Prev Next
 poor explanation Omar Gameel Salem15-Sep-14 14:24 Omar Gameel Salem 15-Sep-14 14:24
 Thanks - and some information endian67522-Nov-09 10:33 endian675 22-Nov-09 10:33
 Re: Thanks - and some information peterkjgaard27-Apr-12 1:57 peterkjgaard 27-Apr-12 1:57
 Is this a Bug? Member 897296-Nov-09 11:18 Member 89729 6-Nov-09 11:18
 Re: Is this a Bug? MikeDC22-May-12 14:54 MikeDC 22-May-12 14:54
 delta problem alitozan16-Nov-06 0:14 alitozan 16-Nov-06 0:14
 Nice summary and concise explanations Hal Angseesing30-Jun-06 1:13 Hal Angseesing 30-Jun-06 1:13
 Re: Nice summary and concise explanations Assaad Chalhoub2-Jul-06 20:48 Assaad Chalhoub 2-Jul-06 20:48
 Last Visit: 14-Oct-19 15:27     Last Update: 14-Oct-19 15:27 Refresh 1

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Article
Posted 14 Apr 2006

107.1K views