A hybrid method for solving traveling salesman problem

被引：4
作者：
Zarei, Bager [1 ]
Meybodi, M. R. [2 ]
Abbaszadeh, Mortaza [1 ]
机构：
[1] Islamic Azad Univ, Dept Comp Engn, Shabestar Branch, Tehran, Iran
[2] Amirkabir Univ, Dept Comp Engn & IT, Tehran, Iran
来源：
6TH IEEE/ACIS INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION SCIENCE, PROCEEDINGS | 2007年
关键词：
D O I：
10.1109/ICIS.2007.24
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
One of the important problems in graphs theory is TSP. Both learning automata and genetic algorithms acre search tools which are used for solving many NP-Complete problems. In this paper a hybrid algorithm is proposed to solve TSP. This algorithm uses both GA and LA simultaneously to search in state space. It has been shown that the speed of reaching to answer increases remarkably using LA and GA simultaneously in search process, and it also prevents algorithm from being trapped in local minimums. Experimental results show the superiority of hybrid algorithm over LA and GA.
引用
收藏
页码：394 / +
页数：2
相关论文
共 18 条
[1]  
[Anonymous], 2002, COMB OPT (SER)
[2]  
ARORA S, 1997, NEARLY LINEAR APPROX
[3]  
BASUTTI F, GENETIC ALGROTITHM O
[4]  
Beigy H., 1999, P 3 ANN INT COMP SOC, P417
[5]  
BRYANT K, 2000, THESIS DEP MATH
[6]  
CANTUPAZ E, 1997, 97003 ILL
[7]  
Cirasella J., 2001, LECT NOTES COMPUTER, P32, DOI DOI 10.1007/3-540-44808-X_3
[8]  
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
[9]   A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems [J].
Freisleben, B ;
Merz, P .
1996 IEEE INTERNATIONAL CONFERENCE ON EVOLUTIONARY COMPUTATION (ICEC '96), PROCEEDINGS OF, 1996, :616-621
[10]   SOLUTION OF LARGE-SCALE SYMMETRICAL TRAVELING SALESMAN PROBLEMS [J].
GROTSCHEL, M ;
HOLLAND, O .
MATHEMATICAL PROGRAMMING, 1991, 51 (02) :141-202
12