01.07.2019 | Regular Research Paper | Ausgabe 1/2020
A memetic algorithm with optimal recombination for the asymmetric travelling salesman problem
- Zeitschrift:
- Memetic Computing > Ausgabe 1/2020
Wichtige Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Abstract
We propose a new memetic algorithm with optimal recombination for the asymmetric travelling salesman problem (ATSP). The optimal recombination problem (ORP) is solved in a crossover operator based on a new exact algorithm that solves the ATSP on cubic digraphs. A new mutation operator makes random jumps in 3-opt or 4-opt neighborhoods. The initial population is constructed by means of greedy constructive heuristics. The 3-opt local search is used to improve the initial and the final populations. A computational experiment on the TSPLIB instances shows that the proposed algorithm yields results competitive to those of other well-known algorithms for ATSP and confirms that the ORP may be used successfully in memetic algorithms.
