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.
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)
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
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)