The Travelling Salesman problem is stated as: "Given a number of cities and the costs of travelling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once?"
Ryan Bateman used the open source classes listed at heatonresearch.com to create a Processing program that would solve the 3D Travelling saleman problem using Genetic algorithms. Re-used paths (corresponding to Chromosomes) increase in visibility as they're re-used, fading otherwise,
meaning the paths 'emerge' as certain chromosomes become more dominant.
The problem is considered 'solved' when a hundred generations have passed without a more optimal solution having been found. This is really a philosophical position because this definiton of "solved" is not conventional, and if it really is "solved," this solution can be used to do all sorts of exciting things like break cryptographic algorithms, and such.
For more on genetic algorithms used to produce art (including a fair amount of math), see
http://www.videosift.com/video/Google-talks-Scott-Draves-on-technical-details-for-art.
Load Comments...
Discuss...
Enable JavaScript to submit a comment.