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.

Version: 1.0 - last updated Thursday, June 09, 2005

Links: Download (Contents: Executable (Windows), Source Code (C#))

Screenshots: