Integrating the Best 2-Opt Method to Enhance the Genetic Algorithm Execution Time in Solving the Traveler Salesman Problem

被引：0
作者：
Sabba, Sara
Chikhi, Salim
机构：
来源：
COMPLEX SYSTEMS AND DEPENDABILITY | 2012年 / 170卷
关键词：
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
The traveling salesman problem (TSP) is one of the classic combinatorial optimization problem NP-complete that requires much time to find the good solution. Indeed, the genetic algorithm is a stochastic optimization algorithm; it is to find an approximate solution of a hard problem. However, genetic algorithm has a great tendency to converge to a local minimum and stay stuck in adverse solutions. To solve this problem, we study in this paper the impact of the integration of a new local optimization heuristic Best 2-opt with the genetic operators on the quality of solution and the runtime of the GA. The hybridization proposed was tested on instances from 29 to 246 cities. The obtained results are very satisfied regarding to the solution qualities and the execution time.
引用
收藏
页码：195 / 208
页数：14
相关论文
共 15 条
[1]  
Davis L., 1985, IJCAI, P162
[2]  
Dorigo M., 1997, IEEE Transactions on Evolutionary Computation, V1, P53, DOI 10.1109/4235.585892
[3]  
Freisleben B., 1996, Parallel Problem Solving from Nature - PPSN IV. International Conference on Evolutionary Computation - The 4th International Conference on Parallel Problem Solving from Nature. Proceedings, P890, DOI 10.1007/3-540-61723-X_1052
[4]  
Goldberg Jr D.E., 1985, P 1 INT C GEN ALG TH, V154, P154
[5]   First vs. best improvement: An empirical study [J].
Hansen, P ;
Mladenovic, N .
DISCRETE APPLIED MATHEMATICS, 2006, 154 (05) :802-817
[6]  
Holland J.H., 1992, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence
[7]  
Jaszkiewicz A., 2000, RES REPORT
[8]  
KOZA JR, 1994, STAT COMPUT, V4, P87, DOI 10.1007/BF00175355
[9]  
Li LJ, 2007, COMM COM INF SC, V2, P208
[10]   COMPUTER SOLUTIONS OF TRAVELING SALESMAN PROBLEM [J].
LIN, S .
BELL SYSTEM TECHNICAL JOURNAL, 1965, 44 (10) :2245-+
12