A Genetic Algorithm to Approximate the Traveling Salesman Problem
Over the course of the last semester I did a project work with the title Approximation of the Traveling Salesman Problem utilising a genetic algorithm in a parallel system. As this is a very complex title by itself, I will explain what this work was about in a few sentences. For further details please take a look at the documentation.
The main goal of this project was to develop an algorithm to approximate an optimal tour for a traveling salesman that wants to visit X cities under the following conditions:
- every city must be visited exactly once
- the tour has to be a round trip
This is a NP-complete problem, meaning there is no efficient algorithm known to solve it in a worthwhile timeframe. Since nobody wants to wait for several hundreds or possibly thousands of years to get the optimal tour, there are some approximation algorithms which are good enough. As multi-core processors are becoming more and more common, developing applications that utilize multiple cores has become an important criteria.
This is where genetic algorithms come into play: Offering intrinstic parallelism they’re well suited for running on many CPU cores. They are also very general in nature: All that’s necessary is to encode the problem in a way the genetic alorithm can handle it. The algorithm does not need any problem-specific information, although it could be used to enhance the results.
Running the Executable
The genetic algorithm gives a handy overview over its parameters and usage when you call the exe:
*** Encapsulated Genetic Algorithm Usage: C:\Workspace\tmp\ega.exe <OBJECTIVE> <MODE> [-ss <SELECTION_SCHEME>] OBJECTIVE: tsp = traveling salesman problem pmx = tsp using partially matched crossover p2 = PowerOfTwo p10 = PowerOfTen MODE: s = sequential p = parallel SELECTION_SCHEME: rw = roulette wheel (default)
To run the
berlin52.tsp copy the file into the folder of the exe and type the first line in the example that follows
in a command line window:
PS $ .\ega.exe tsp p *** Encapsulated Genetic Algorithm *** Written by Michael Barth <firstname.lastname@example.org> Version 1.0, 15-03-2009 Run Configuration Mode: Parallel Selection Scheme: Roulette Wheel Objective: TSP Encoding: Permutation Enter relative path to file> berlin52.tsp NAME: berlin52 TYPE: TSP COMMENT: 52 locations in Berlin (Groetschel) DIMENSION: 52 EDGE_WEIGHT_TYPE: EUC_2D # of Cities read: 52 Initializing parameters... Enter Population size> 10000 Enter max. generations> 100 Enter crossover probability> 0.01 Enter mutation probability> 0.01
It will the output reports per generation, giving information like various fitness values to evaluate how well the solutions in the generation solved the underyling problem, how many crossovers and mutations have occurred, the best tour and the distance of the best tour.
The program was developed in Linux using eclipse CDT 5.0.1 and CMake 2.6, so this is the recommended environment to build and run it. It also utilizes OpenMP and TR1 for shared pointers, so make sure your compiler supports it. For further details, see How to build.
Building under Windows
By default the build environment is set to Linux to compile. If you want to compile it under windows, you have to set the appropriate define in the config.h file:
//#define LINUX #define WIN_32
Also note that this is a console application, so make sure you’ve set your IDE to the correct system.