Use ParadisEO-EO to solve the Traveling Salesman Problem

This package contains many convenient classes to solve the traveling salesman problem within ParadisEO-EO. An example using a genetic algorithm is provided.

Problem description

The travelling salesman problem (TSP) is a problem in discrete or combinatorial optimization. It is a prominent illustration of a class of problems in computational complexity theory which are classified as NP-hard. Given a number of cities and the costs of travelling from any city to any other city, what is the cheapest round-trip route that visits each city exactly once and then returns to the starting city ? (taken from wikipedia)

Solver description

This problem is tackled by a genetic algorithm implemented using ParadisEO-EO (see the tsp.cpp in the archive).

The following components are representation-dependent:

  • Route: Solution encoding
  • RouteInit: The route intializer
  • RouteEval: Evaluator containing the objective function
  • PartialMappedXover: Partial mapped crossover
  • CitySwap: swap-based mutation

The others are generic in ParadisEO-EO:

  • eoPop: the population
  • eoGenContinue: Stopping criteria (fixed number of generations)
  • eoStochTournamentSelect: Stochastic tournament selector
  • eoElitism: Elitist merge strategy
  • eoStochTournamentTruncate: Stochastic replacement
  • eoEasyEA: the genetic algorithm itself

Download

Instructions

To install the package, follow these steps:

  • Download one of the previous archives and decompress it.
  • Edit the "install.cmake" file and replace the path by the absolute path of ParadisEO
    replaced by:
SET(PARADISEO_DIR "/home/.../paradiseoDirectory" CACHE PATH "ParadisEO directory" FORCE)
  • Go in the "build" directory
  • Run (in a terminal/console): cmake .. -G"<generator type>"
    (Several generators exist: see)
  • Compile using the appropriate tool (run "make" if you choose the "Unix Makefiles" generator)