Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators

Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators

1999 | P. LARRAÑAGA, C.M.H. KUIJPERS, R.H. MURGA, I. INZA and S. DIZDAREVIC
This paper reviews various attempts to solve the Travelling Salesman Problem (TSP) using Genetic Algorithms (GAs). The authors present different crossover and mutation operators designed for GAs with various representations, including binary, path, adjacency, ordinal, and matrix representations. The paper also discusses experimental results obtained using these operators with standard TSP examples, focusing on the path representation. The introduction provides an overview of evolutionary algorithms, their inspiration from natural processes, and their application to combinatorial optimization problems. The paper is structured to cover the basics of genetic algorithms, the TSP, different representations, operators, and experimental results, concluding with a discussion of local search integration and future directions.This paper reviews various attempts to solve the Travelling Salesman Problem (TSP) using Genetic Algorithms (GAs). The authors present different crossover and mutation operators designed for GAs with various representations, including binary, path, adjacency, ordinal, and matrix representations. The paper also discusses experimental results obtained using these operators with standard TSP examples, focusing on the path representation. The introduction provides an overview of evolutionary algorithms, their inspiration from natural processes, and their application to combinatorial optimization problems. The paper is structured to cover the basics of genetic algorithms, the TSP, different representations, operators, and experimental results, concluding with a discussion of local search integration and future directions.
Reach us at info@study.space