A Genetic Algorithm to Approximate the Traveling Salesman Problem cover
Downloads

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.

Requirements

The TSPLIB of the Uni Heidelberg was used for sample data, which is pretty nice as there are best known solutions for it. At the time of this project there were only the plain text *.tsp data files.

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 <mbarth@little-things.de>
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.

Documentation
Beginning of a run
End of a run

Build Environment

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.