giving something back to the Flash community

simulated annealing and TSP

Tags: , , , , ,

using the simulated annealing algorithm to find solutions to the traveling salesman problem

i read an article (le recuit simulé(fr))about simulated annealing and thought it might prove useful some day.
it is one of the ways to solve the traveling salesman problem(TSP). it is somehow related to the way ant’s optimize their tracks.

in the article there’s this picture:
which might be very useful to ‘simplify’ a self-intersecting polygon before triangulating it.
but actually the simulated annealing would just spoil the original shape.
in fact it reorganizes a set of points and returns a sorted simple shape.
for instance the top left picture is a set of 500 nodes and the yellow shapes are the various solutions:
the solutions lengths are aproximately equivalent.

It is a heuristic approach which means that it won’t find THE solution for there is no such solution but plenty.
and there’s no way to find the optimal path but comparing various solutions and keep the one with the lowest cost(length).

it works like the particles in piece of metal cooling down.
you pass it 3 parameters : the set of cities ( an array of Points), a starting temperature and a cooing rate(delta).

annealing = new SimulateAnnealing( cities, temperature, delta );

the delta should be comprised between 0 and 1 otherwise the shape melts endlessly(pretty funny to generate chaos btw)
the lower the starting temperature, the faster it will find a solution.
then you run it like this:

//listens to the changes & completion
annealing.addEventListener( Event.CHANGE, changeHandler );
annealing.addEventListener( Event.COMPLETE, completeHandler );
//starts the algorithm

the CHANGE event is dispatched during the process and COMPLETE when it’s over

it will stop when a low cost solution is found that passes through all the points yet the results can really be odd
for instance if you start with the top left set of points you can get those (valid) solutions:
you can clearly see that the optimal solution is the bootom right one yet the others are valid too.
finallly here’s a quick demo:

you specify the amount of cities, then click respawn to randopmize them, then process to run the algorithm.
the interseting thing is to process several times the same set and see the differnt solutions.

it could be used to generate maps for games like islands in RTS, because you know that any point within the shape will be able to reach another point in the shape. or to create semi random shapes in box2D ; the sorted shape is always simple therefore it can be triangulated. it could also be used to generate livng creatures by randomizing some portions of their bodies.

here is the classe:

enjoy :)

Tags: , , , , ,

© 2009 HIDIHO!. All Rights Reserved.

This blog is powered by Wordpress and Magatheme by Bryan Helmig.