
3D Travelling Salesman using Genetic Algorithms
2 years ago
Edit: I've responded to a few critiques below.
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?"
I used the open source classes listed at the link below to create a Processing program that would solve the 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.
I also made the problem 3D, simply because... well, everything looks nicer in 3D and, to be honest, it was incredibly easy to program, given the class I used from the link below. I would've made this a lot prettier but I'm running out of free/unemployed time as I start a new job soon, so I got it working and left it.
Updated: Hello Reddit and Wired. The simulation posted does not claim to be the 'perfect' solution for the layout shown. Running the program a number of times produces not only different 'solutions' but also a wide variation in the number of generations required to create a 'solution' - anything from 800 to 5000, depending entirely on the randomised initial population and their genetic makeup.
Genetic Algorithm classes: heatonresearch.com
Travelling Salesman: en.wikipedia.org/wiki/Traveling_salesman_problem
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?"
I used the open source classes listed at the link below to create a Processing program that would solve the 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.
I also made the problem 3D, simply because... well, everything looks nicer in 3D and, to be honest, it was incredibly easy to program, given the class I used from the link below. I would've made this a lot prettier but I'm running out of free/unemployed time as I start a new job soon, so I got it working and left it.
Updated: Hello Reddit and Wired. The simulation posted does not claim to be the 'perfect' solution for the layout shown. Running the program a number of times produces not only different 'solutions' but also a wide variation in the number of generations required to create a 'solution' - anything from 800 to 5000, depending entirely on the randomised initial population and their genetic makeup.
Genetic Algorithm classes: heatonresearch.com
Travelling Salesman: en.wikipedia.org/wiki/Traveling_salesman_problem
-
Vimeo: About / Blog / Developers / Jobs / Community Guidelines / Community Forums / Help Center / Site Map / Merchandise
/ Get Vimeo

Previous Week
Great, clear video. I'm trying to implement a TSP solution for Rhinoscript. You write that you got your code from "heatonresearch.com". Was it this book?:
"Introduction to Neural Networks for Java, 2nd Edition"
heatonresearch.com/book/programming-neural-networks-java-2.html
or was everything available on their site somewhere? I've only found a brief intro to the problem there and this link to buy the book.
Thanks in advance.
I pulled the example source from here, if memory serves: heatonresearch.com/articles/65/page1.html
I do, actually, have the book you mentioned though.
As you'll see when you look at the source, all I really did was make it more visually appealing. The majority of the work was done by Heaton's example code.
r
Would you give me permission to use it (properly credited) direct form my laptop? I don't ant to risk a dodgy internet connection.
You can check my credentials at
janeprophet.com
The talk is at
creativityandcognition09.org/
best wishes
Jane Prophet
jane AT janeprophet DOT com