More
See all Show me
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

Credits

19 Likes

  • moka 2 years ago
    nice idea!
  • Ryan Bateman 2 years ago
    Thanks. :)
  •  
  • n4p41m 2 years ago
    great!
  •  
  • josh draper plus 2 months ago
    Hi Ryan,

    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.
  • Ryan Bateman 2 months ago
    Hi Josh,

    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
  •  
  • jane prophet 18 days ago
    Hi Ryan. I'd like to play this animation as part of a talk I'm doing next week.

    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 prophet 18 days ago
    PS email me if possible

    jane AT janeprophet DOT com
  •  
This conversation is missing your voice. Take five seconds to join Vimeo or log in.

Advertisement

Statistics

  •  
    plays
    likes
    comments
  • Total
    plays 5,330
    likes 19
    comments 7
  • Nov 9th
    plays 0
    likes 0
    comments 0
  • Nov 8th
    plays 5
    likes 0
    comments 0
  • Nov 7th
    plays 0
    likes 0
    comments 0
  • Nov 6th
    plays 1
    likes 0
    comments 0
  • Nov 5th
    plays 0
    likes 0
    comments 0
  • Nov 4th
    plays 2
    likes 0
    comments 0
  • Nov 3rd
    plays 3
    likes 0
    comments 0
  • Nov 2nd
    plays 1
    likes 0
    comments 0
Previous Week

Downloads

Please join Vimeo or log in to download the original file. It only takes a few seconds.