Genetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem

DOI10.1007/978-3-319-73441-5_36MaRDI QIDQ3297452zbMATH OpenOpenAlexFDO

Authors Anton Valentinovich Eremeev, Julia Viktorovna Kovalenko

Publication date 20 July 2020

Published in Large-Scale Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.06920

zbMATH Keywords

genetic algorithmlocal searchoptimal recombination

Mathematics Subject Classification ID

Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: We propose a new genetic algorithm with optimal recombination for the asymmetric instances of travelling salesman problem. The algorithm incorporates several new features that contribute to its effectiveness: (i) Optimal recombination problem is solved within crossover operator. (ii) A new mutation operator performs a random jump within 3-opt or 4-opt neighborhood. (iii) Greedy constructive heuristic of W.Zhang and 3-opt local search heuristic are used to generate the initial population. A computational experiment on TSPLIB instances shows that the proposed algorithm yields competitive results to other well-known memetic algorithms for asymmetric travelling salesman problem.

Recommendations

• A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem
• Genetic algorithms for the traveling salesman problem
• scientific article; zbMATH DE number 4104744
• An Efficient Genetic Algorithm for the Traveling Salesman Problem
• A genetic algorithm for traveling salesman problems
• A reinforced hybrid genetic algorithm for the traveling salesman problem
• A hybrid random-key genetic algorithm for a symmetric travelling salesman problem
• A new genetic algorithm applied to the traveling salesman problem
• An improved genetic algorithm for solving travel salesman problem

Cites work

• A new memetic algorithm for the asymmetric traveling salesman problem
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• Feature Article—Genetic Algorithms for the Operations Researcher
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1082106 (Why is no real title available?)
• Local Search for the Asymmetric Traveling Salesman Problem
• Optimal recombination in genetic algorithms for combinatorial optimization problems. II
• Statistics: A biomedical introduction.
• The algebra of genetic algorithms
• The Traveling Salesman Problem for Cubic Graphs
• The use of dynamic programming in genetic algorithms for permutation problems
• Tour merging via branch-decomposition
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(7)

• A new memetic algorithm for the asymmetric traveling salesman problem
• A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem
• scientific article; zbMATH DE number 1696560 (Why is no real title available?)
• A genetic distance metric to discriminate the selection of algorithms for the general ATSP problem
• An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem
• The “One-fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ,λ)) Genetic Algorithm
• Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: Genetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3297452)