Simulated Annealing & genetic Algorithm - The Travelling Salesman Problem
This Java applications shows how to solve the travelling salesman problem using either annealing simulated or genetic algorithms. Given some nodes, the starting position and the goal position, both techniques offer a solution which describes how to reach the goal position from the initial position crossing all the nodes in the grid-map. The Java application (Annealing simulated):
(*): A and B are two constants which determine the behaviour of the thread when searching the solution path. Simulated Annealinghas the following steps:
1) Calculates de current Energy [Eo] (in this case, the Enery is the length of the path).
2) Randomly generates a new path, and calculates its Energy [Ef].
3) P=exp(-(Ef-Eo)/A*T) is the probability to be succesfull in the change. If Ef<=Eo then P>=1 and the change will be made.If not, read 4). A is one constant (which must be positive), which determines the speed of the annealing. T the "Temperature of the System". It decreases with time following the law: kT=exp(-B*time) where B is the second constant of the system.
4) if P<1, then the program makes a random number (R, which must be contained in [0,1]), if P>R then the change is made, but if P<R then any change is made. Now the loop starts again in 1).
Of course this method cannot always provide the same solution for the same problem. As you can see in the image below, two different solutions are given for the same grid configuration. Both of them are appropiate for a travelling salesman:
The Java application which uses a genetic algorithm has almost the same textfields and buttons, and it uses the same grid-map style. Here, three random solutions are created, and then the application introduces some variations in these solutions. Some of these variants may be worse than the original solutions, but others may be better. The three best choices become the three main solutions and then some variations are introduced again. After several selections, the program reaches a solution, as you can see in the image:
You can download the application (Simulated Annealing) here or (Genetic Algorithm) here, or you may want to visit our downloads section and click on Physics.
