Travelling Salesman Problem:
A salesman wants to travel to 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:
• 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.
• 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.
• 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.
Simulated Annealing:
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.
Here starting temperature = 400
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";
}
}

///

/// current configuration /// next configuration void computeNext(int[] c, int[] n)
{
for(int i=0;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;
}
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.