The Traveling Salesman

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.

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.  

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.

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.

Above is the block diagram for the Main.vi.  The GA makes use of 5 classes, I will cover what each class does below.

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.

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.

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.

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.

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.

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.

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

---