You are here

Simulated Annealing Traveling Salesman Problem with Javascript

Simulated annealing is a programming method that attempts to simulate the physical process of annealing. Annealing is a where a material is heated and then cooled (as steel or glass) usually for softening and making the material less brittle. Simulated annealing, therefore, exposes a "solution" to "heat" and cools producing a more optimal solution.

The "Traveling Salesman Problem" (TSP) is a common problem applied to artificial intelligence. The TSP presents the computer with a number of cities, and the computer must compute the optimal path between the cities. This applet uses simulated annealing to produce a solution to the "Traveling Salesman Problem".

Cities: , Stop after stable iterations.
Start Temp: , End Temp: , Cycles:

Ready.

Simulated annealing works by moving from the starting temperature to the ending temperature for each iteration. The cycle count allows you to specify the granularity at which the temperature decreases. The higher the temperature, the more randomness is introduced into the system. You can configure all three of these parameters.

Random Cities

The most common use of this program is to simply place random cities on the map. These cities will be placed in random locations over the map. Some random city combinations are harder than others. You can see a 50 random city map shown here.

You may want to evaluate how effective simulated annealing is when you vary the parameters. To rerun, you should just randomize the path. This will allow you to start over using the same city configuration.

Cities in a Circle

You can also place the cities in a circle. This makes it easier to visualize how close Simulated Annealing came to an optimal solution. The optimal path around a circle is around the perimeter. Here you can that simulated annealing found a nearly optimal path.

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer