A hybrid heuristic for the traveling salesman problem

被引：135

作者：

Baraglia, R ^{[1
]}

Hidalgo, JI

Perego, R

机构：

[1] CNR, Ist CNUCE, I-56010 Pisa, Italy

[2] Univ Complutense, Dept Arquitectura Comp & Automat, E-28040 Madrid, Spain

来源：

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION | 2001年 / 5卷 / 06期

关键词：

compact genetic algorithms; hybrid GA; Lin-Kernighan algorithm; TSP;

D O I：

10.1109/4235.974843

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The combination of genetic and local search heuristics has been shown to be an effective approach to solving the traveling salesman problem (TSP). This paper describes a new hybrid algorithm that exploits a compact genetic algorithm in order to generate high-quality tours, which are then refined by means of the Lin-Kernighan (LK) local search. Local optima found by the LK local search are in turn exploited by the evolutionary part of the algorithm in order to improve the quality of its simulated population. The results of several experiments conducted on different TSP instances with up to 13509 cities show the efficacy of the symbiosis between the two heuristics.

引用

页码：613 / 622

页数：10

共 26 条

[1]

Applegate D., 1998, DOC MATH J DTSCH MAT, P645

[2]

Applegate D., 1999, 99885 U BONN RES I D

[3]

Baluja S, 1994, Technical Report

[4]

BRAUN H, 1991, LECT NOTES COMPUT SC, V496, P129

[5] A METHOD FOR SOLVING TRAVELING-SALESMAN PROBLEMS [J].

CROES, GA .

OPERATIONS RESEARCH, 1958, 6 (06) :791-812

[6]

Glover F., 1989, ORSA Journal on Computing, V1, P190, DOI [10.1287/ijoc.2.1.4, 10.1287/ijoc.1.3.190]

[7] Asparagos96 and the traveling salesman problem [J].

GorgesSchleuter, M .

PROCEEDINGS OF 1997 IEEE INTERNATIONAL CONFERENCE ON EVOLUTIONARY COMPUTATION (ICEC '97), 1997, :171-174

[8]

Grefenstette J.J., 1985, P 1 INT C GENETIC AL, P160

[9] The gambler's ruin problem, genetic algorithms, and the sizing of populations [J].

Harik, G ;

CantuPaz, E ;

Goldberg, DE ;

Miller, BL .

PROCEEDINGS OF 1997 IEEE INTERNATIONAL CONFERENCE ON EVOLUTIONARY COMPUTATION (ICEC '97), 1997, :7-12

[10] The compact genetic algorithm [J].

Harik, GR ;

Lobo, FG ;

Goldberg, DE .

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 1999, 3 (04) :287-297

← 1 2 3 →