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.
5 Comments
charliemsays...Upvote purely because this is very close to how routers perform route fowarding decisions. Ie. This is how the internet would work if you could see routers calculating least cost paths to each destination in their route table.
Doc_MConnect the dots. la lala lala
Connect the dots. la lala lala
Smugglarnsays...NO, NO, NO! GOD DID IT!
HaricotVertThat's pretty slick for an NP-hard problem.
siftbotThe thumbnail image for this video has been updated - thumbnail added by vaporlock.

Discuss...
Enable JavaScript to submit a comment.