Genetic algorithms for the travelling salesman problem:: A review of representations and operators

被引：524

作者：

Larrañaga, P ^{[1
]}

Kuijpers, CMH ^{[1
]}

Murga, RH ^{[1
]}

Inza, I ^{[1
]}

Dizdarevic, S ^{[1
]}

机构：

[1] Univ Basque Country, Dept Comp Sci & Artificial Intelligence, E-20080 San Sebastian, Spain

来源：

ARTIFICIAL INTELLIGENCE REVIEW | 1999年 / 13卷 / 02期

关键词：

Travelling Salesman Problem; Genetic Algorithms; binary representation; path representation; adjacency representation; ordinal representation; matrix representation; hybridation;

D O I：

10.1023/A:1006529012972

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper is the result of a literature study carried out by the authors. It is a review of the different attempts made to solve the Travelling Salesman Problem with Genetic Algorithms. We present crossover and mutation operators, developed to tackle the Travelling Salesman Problem with Genetic Algorithms with different representations such as: binary representation, path representation, adjacency representation, ordinal representation and matrix representation. Likewise, we show the experimental results obtained with different standard examples using combination of crossover and mutation operators in relation with path representation.

引用

页码：129 / 170

页数：42

共 61 条

[1]

Ackley D. H., 1987, CONNECTIONIST MACHIN

[2] HEURISTIC COMBINATORIAL OPTIMIZATION BY SIMULATED DARWINIAN EVOLUTION - A POLYNOMIAL-TIME ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM [J].