Title: Traveling Salesman Problem via Genetic Algorithm
Author: David J. Stein, Esq.
Version: 1.0
Written: Fall, 2004
Abstract: The traveling salesman problem is a simple problem: given a 2D graph of cities, what is the shortest circuit - the shortest route that visits each city exactly once? The triviality of this task is deceptive: it is, in fact, NP-complete: while many algorithms can produce a very good route, no known method exists of finding the shortest route without some measure of brute-force trial-and-error computation.
This application is an attempt to solve the Traveling Salesman Problem with a genetic algorithm. This algorithm creates a number of full solutions, measures their comparative fitnesses, and selects the best ones for a new generation of solutions, while also featuring asexual budding, genetic mutation, and immigration features. In this way, the algorithm borrows from the process of biological evolution in order to "evolve" a very good solution for the Traveling Salesman Problem in a short timeframe.
Installation Instructions: Nothing unusual - simply run the enclosed executable. The application relies on an XML schema definition (.XSD) file stored in the Schema Files folder collocated with the executable, so don't alter or move this file.
Operation Instructions:
Genetic Algorithm: The typical genetic algorithm, which this application adapts for this problem, consists of the following steps:
- Generate an initial sample population of entities (each a full solution to the Traveling Salesman Problem) from scratch.
- Evaluate the fitness of each entity (with higher fitness assigned for shorter total distance.)
- Create a new generation of entities by randomly selecting two solutions from the current population, with random selection weighted based on the relative fitnesses of each entity, and crossing over their genetic contents at a random point to create a new solution.
- Simulate budding by randomly selecting an entity, again with randomness weighted by fitness, and splicing a random segment of its genetic data with random genetic data created from scratch.
- Simulate genetic mutation by scattering some random variations throughout the population.
- Simulate immigration by including some brand-new entities from scratch.
- Repeate steps 2-6 for successive generations until the user aborts the algorithm.
This algorithm may be applied by following these steps:
Create a map: Simply click in the Map window to produce cities. Left-clicking on a city deletes it, and right-clicking on the city enables the user to move it around the map.
Configure the genetic algorithm parameters: The genetic algorithm may be customized by selecting the population size, mutation rate (percentage), the rate of completely new entities to add to each generation (percentage), the rate of budding (percentage), and the rate of sexually reproduced replacements (percentage). Note that if these percentages add up to less than 1.0, the most successful parents of the previous generation are re-introduced to fill out the remaining population.
Apply the algorithm to produce a solution: First, you must initialize the SetBuilder list by clicking the "Initialize" button. Then, you may use the "Solve (Step)" and "Solve (Full)" buttons to use the SetBuilder algorithm to produce a solution. The former causes the algorithm to produce one new generation and displays the best solution (the longest one with the shortest distance) on the map. The latter runs the genetic algorithm continuously, displaying the best solutions in periodic intervals. This runs indefinitely until aborted by the user, since the algorithm may be capable of producing a better full solution with continued optimization.
Comments: The results produced by this genetic algorithm are quite good, and it rapidly evolves a closely optimized solution. However, two common problems arise:
- The solutions often involve one large cross. This may happen if two entities evolve two halves of an optimal solution - but they evolve in opposite directions (e.g., one is clockwise and the other is counterclockwise.) The algorithm will repeatedly glue together the two halves, featuring a serious kink that moderately damages fitness but cannot be easily resolved.
- The algorithm rapidly produces near-optimal solutions, but working out the last few non-optimal kinks is very difficult. The poblem is that the algorithm can evaluate the fitness of an entire solution, but cannot consider which parts of the solution are fit and which are not. An attempt to improve the algorithm in light of this observation was developed as the SetBuilder algorithm, separately available as a competing Traveling Salesman Problem solution.
Application History: This application was written as an experiment with a novel algorithm for solving the classic Traveling Salesman Problem. Although the problems mentioned above may be incapable of efficient resolution, the resulting algorithm is nevertheless competitive with alternative solutions for this problem.
Questions/Comments:
Please contact David J. Stein, Esq. via email at djs10@po.cwru.edu.
Terms and Conditions of Use:
Please see the enclosed "License.html" file for terms and conditions of use of this software package.