LabVIEW Craft
  • Blog
  • About
  • Contact
  • Tools
  • Resources

The Traveling Salesman

6/14/2016

4 Comments

 
Jon McBee
The Traveling Salesman Problem (TSP) is a problem in Graph Theory requiring the discovery of the most efficient route a salesman can travel through the multiple cities.  As an example if the salesman's route included 20 cities he would have to choose the most efficient of 20! = 2432902008176640000 possible routes (If he evaluated one solution every second it would take over 77 Billion years).  Having that many possible routes to chose from makes optimization of the solution difficult and the optimization problem gets harder as the number of cities increases.
Picture
Because finding the optimal solution to the problem can be physically impossible we have to do our best to find a good-enough solution.  One way to find a good-enough solution is by using a genetic algorithm (GA).  To quote Wikipedia:
"In the field of artificial intelligence, a genetic algorithm (GA) is a search heuristic that mimics the process of natural selection. This heuristic (also sometimes called a metaheuristic) is routinely used to generate useful solutions to optimization and search problems."
An example of a GA providing a real world solution is the X-band antenna designed by NASA for the ST5 mission in 2006.  NASA used a GA that generated an initial group of random antenna designs.  But it didn't stop there, the GA then evaluated the first generation of designs against the parameters needed for a successful antenna, took the subset of the antenna that best fit the criterion, mated their designs and created a new generation.  
Picture
After about 10 hours of iterating the GA had designed the above antenna, which satisfied all of NASA's criteria.  This is a truly novel solution that a human designer probably wouldn't have been able to come up with on their own.  It is in these types of optimization problems that GA's shine, which is why we can apply it to the TSP.
Picture
I came across this blog post where blogger Lee Jacobson talks through how to create a GA for finding a good-enough solution to the TSP using Java.  I then went through and implemented his solution in LabVIEW so that I could gain a better understanding of how it works and also lower the barrier to entry for GA's to LabVIEW developers who don't want to work through Java code.
Here is a video of the GA in action.  I have included the code, written in LabVIEW 2015, below along with the original Java code that I based it on.  I used the LabVIEW Unit Test Framework to test the classes in the solution so that you have a bit of a safety net should you want to go into the code and poke around.  The code itself is pretty simple, see below for a quick tour.
Picture
Above is the block diagram for the Main.vi.  The GA makes use of 5 classes, I will cover what each class does below.
Picture
The City class allows us to create City objects, where each City object holds X and Y coordinates that define its location in traveling salesman space.  The City class also has a public method named, "Calculate Distance to City" that takes in two cities and returns the distance between them.
Picture
The Tour Manager class holds an array of destination City objects.  It provides public methods for adding cities to the tour, retrieving City objects from the array of destination cities by index, and returning the number of cities in the tour.  On the block diagram of the Main.vi the Tour Manager object is setup with an array of City objects and is then passed into other objects for use.
Picture
The Tour class keeps track individual routes that the salesman can take between all cities in the tour.  Each Tour object calculates and maintains "Distance" and "Fitness" metrics that are used to evaluate the optimization level of the tour.  With each generation of the GA new Tour objects are constructed and their optimization metrics are recalculated before they are used to create the next generation.
Picture
For each generation of the GA the Population class holds all of that generations Tours.  The Population class has public methods for managing the Tour objects and also has a public method that returns the fittest Tour object of that generations Population.  Just like with Darwin's survival of the fittest, the GA ensures that the fittest tour of each generation is propagated.
Picture
The Genetic Algorithm class holds the logic used to evolve each generations population.  The bulk of the complexity lives in this class.  The private class data for this class holds parameters for "Mutation Rate", "Tournament Size", and "Elitism", which directly impact how the GA functions.  The "Mutation Rate" defines the probability that a random mutation gets injected into a Tour as it evolves.  The "Tournament Size" defines the number of random tours from the current population that are pitted against each other in a survival of the fittest battle each generation.  The "Elitism" flag, when set to true, ensures that the fittest tour of each generation is passed on to the next.
Picture
There is an XY Graph on the Main.vi UI that shows real time feedback of the current generations fittest tour.  Below the XY Graph is a Waveform Chart that plots the change in distance over time.  As each generation evolves the Waveform Chart should show decreasing distance.
The Main.vi UI also has indicators that show the Initial Distance for the fittest tour in the first generation, as well as the Final Distance for the fittest tour in the final generation.  If the GA did its job then the Final Distance value should be more optimized than the Initial Distance, the GA can never guarantee the optimal solution but that trade off is made gladly in the interest of finding a good-enough solution in fewer than 77 Billion years.
Picture
Lastly the project has unit tests that can be run through the LabVIEW Unit Test Framework.  I did my best to apply TDD to the creation of this project, in fact I believe that an interesting TDD code kata could be created from this project.  One thing I realized was that it is difficult to test public methods that are designed to return randomized results each time they are executed.  This is particularly true with regard to the Genetic Algorithm class, I think that in order to properly test this class test cases would need to be created for its private methods.  This raises the interesting issue that private methods can't be tested by User Defined Tests in the Unit Test Framework due to the fact that they are private.  To make these methods testable they would either need to be wrapped in public methods or made public themselves.
You can download the code from the example project below.  It is a simple implementation of a genetic algorithm that provides an interesting solution to a cool problem.  

Jon McBee is a Principal Software Engineer at Cambridge NanoTech and is a Certified LabVIEW Architect, Certified LabVIEW Embedded Developer, Certified TestStand Developer, an NI Certified Professional Instructor, a LabVIEW Champion, and a Certified ScrumMaster
Genetic Algorithm LV2015.zip
File Size: 1148 kb
File Type: zip
Download File

4 Comments
Furkan
6/20/2016 04:48:26 am

Hey Jon,

I recently stumbled upon your blog and I really liked your content and presentation. You all are doing a great job! Keep it going please :)

It was interesting to see how a genetic algorithm would work on the classic Travelling Sales Man problem, and especially to see it implemented in LabVIEW.

After I saw your post I gave it a try to solve the same problem by using another heuristic approach called Simulated Annealing. I used the same map as you used to be able to compare the two methods. My implementation is also on LabVIEW 2015 and is based on GOOP. You can find the link below.

Any comment is much appreciated :)
Furkan

https://drive.google.com/file/d/0B9Ybon9aqWbLU0FpXzcxYWZ0dEE/view?usp=sharing

Reply
Jon McBee
6/21/2016 10:09:14 am

Hi Furkan,

I'm glad you found the blog and that you find it useful. Thank you for putting together the Simulated Annealing example, I think having another implementation using a probabilistic technique is a great contribution. The more context for understanding these ideas (or at least seeing what they look like in LabVIEW) the better.

Thanks
Jon

Reply
Partha
8/1/2016 12:59:34 am

Hi Furkan,

Would you mind posting the zip of your solution here? I'm not able to download it from Google drive.

Reply
Chimsom Isidore Chukwuemeka
2/1/2018 11:30:10 am

Hi Jon

I downloaded Stream and GA framework, installed both in LabVIEW 2017, but I can only find Stream in functions Pallet under Composed Systems, no VIs for the GA framework. How do I fix this. Its very urgent.

Thank you sir.

Reply



Leave a Reply.

    RSS Feed

    Tags

    All
    Abstract Messaging
    Actor Framework
    Agile
    AI
    Asynchronous Programming
    Best Practices
    C#
    Complexity
    Continuations
    Control Values By Index
    Craftsmanship
    Dependency Inversion
    Dependency Viewer
    Futures/Promises
    Genetic Algorithm
    Liskov Substitution
    Malleable VIs
    Mediator Pattern
    .NET
    Object Oriented
    Object-Oriented
    Packed Project Library
    Parallelism
    Polymorphism
    Pub/Sub
    RawCap
    Root Loop
    Scrum
    Task Parallel Library
    TCP/IP
    TDD
    Test Engineering
    UML
    Unit Test
    VI Scripting
    VI Server
    WireShark

    Archives

    April 2019
    July 2018
    October 2017
    March 2017
    February 2017
    January 2017
    December 2016
    July 2016
    June 2016
    May 2016
    April 2016
    March 2016
    February 2016
    January 2016
    December 2015
    November 2015
    October 2015
    August 2015
    February 2015
    January 2015

    LabVIEW Blogs

    Eyes on VIs
    LabVIEW Hacker
    VI Shots
    LabVIEW Artisan
    Software Engineering for LabVIEW
    ​Wiresmith Techology
Picture
Powered by the Panda Ant

  • Blog
  • About
  • Contact
  • Tools
  • Resources