吉林大学学报(工学版) ›› 2013, Vol. 43 ›› Issue (01): 147-151.

Previous Articles     Next Articles

Fast ant colony algorithm for solving traveling salesman problem

SHEN Xuan-jing1,2, LIU Yang-yang1,2, HUANG Yong-ping1,2, XU Tie3, He Xi-wen1   

  1. 1. College of Computer Science and Technology, Jilin University, Changchun 130012, China;
    2. Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China;
    3. Taohe Farm, Jilin Oil Refco Group Ltd, Songyuan 138000, China
  • Received:2012-02-15 Online:2013-01-01 Published:2013-01-01

RICH HTML

0   

PDF (PC)

632

Abstract: Using ant colony algorithm to solve Traveling Salesman Problem (TSP) has certain disadvantages, such plunging into local minimum, slower convergence speed and so on. In order to find the optimal path accurately and rapidly, an improved ant colony algorithm is proposed. The improved algorithm uses adaptive adjusting mechanism of pheromone decay parameter to adjust the convergence speed and ensure the global search ability. With the help of common path, the computation time is reduced and the better solution can be obtained. Experiments show that, in a relatively few iterations, the percentage deviation of the average solution to the best known solution is 0.46%, and the percentage deviation of the best solution to the best known solution is 0.23%. The improved algorithm has high accuracy and convergence speed.

Key words: artificial intelligence, ant colony algorithm, common path, adaptive, traveling salesman problem

CLC Number: 

  • TP18
[1] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transaction on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996, 26(1): 29-41.

[2] Dorigo M, Gambardella L M, Middendorf M, et al. Guest editorial: special section special section on ant colony optimization[J]. IEEE Transaction on, Evolutionary Computation, 2002, 6(4): 317-319.

[3] Stutzle T, Hoos H H. Max-min ant system[J]. Future Generation Computer Systems, 2000(16):889-914.

[4] Malisia A R, Tizhoosh H R. Applying opposition-based ideas to the ant colony system//2007 IEEE Congress on Swarm Intelligence Symposium, Hono-lulu, HI, 2007: 182-189.

[5] Duan H B, Zhang X Y, Wu J, et al. Max-min adaptive ant colony optimization approach to multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments[J]. Journal of Bionic Engineering, 2009,6(2): 161-173.

[6] Yu B, Yang Z Z, Yao B Z. An improved ant colony optimization for vehicle routing problem[J]. Euro-pean Journal of Operational Research, 2009, 196(1): 171-176.

[7] Tseng S P, Tsai C W, Chiang M C, et al. A fast ant colony optimization for traveling salesman problem//2010 IEEE Congress on Evolutionary Computation, Barcelona, 2010:1-6.

[8] 罗雪晖, 杨烨, 李霞. 改进混合蛙跳算法求解旅行商问题[J]. 通信学报, 2009, 30(7): 130-134. Luo Xue-hui, Yang Ye, Li Xia. Modified shuffled frog-leaping algorithm to solve traveling salesman problem[J]. Journal on Communications, 2009, 30(7): 130-134.

[9] Masutti T A S, Castro L N D. A self-organizing neural network using ideas from the immune system to solve the travelling salesman problems[J]. Information Sciences, 2009, 179(10): 1454-1468.

[10] Chen S M, Chien C Y. Solving the traveling sales-man problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques[J]. Expert Systems with Applications, 2011(38):14439-14450.
[1] GU Wan-li,WANG Ping,HU Yun-feng,CAI Shuo,CHEN Hong. Nonlinear controller design of wheeled mobile robot with H∞ performance [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1811-1819.
[2] ZHAO Wei-qiang, GAO Ke, WANG Wen-bin. Prevention of instability control of commercial vehicle based on electric-hydraulic coupling steering system [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1305-1312.
[3] DONG Sa, LIU Da-you, OUYANG Ruo-chuan, ZHU Yun-gang, LI Li-na. Logistic regression classification in networked data with heterophily based on second-order Markov assumption [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1571-1577.
[4] GU Hai-jun, TIAN Ya-qian, CUI Ying. Intelligent interactive agent for home service [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1578-1585.
[5] LIU Yuan-ning, LIU Shuai, ZHU Xiao-dong, CHEN Yi-hao, ZHENG Shao-ge, SHEN Chun-zhuang. LOG operator and adaptive optimization Gabor filtering for iris recognition [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1606-1613.
[6] WANG Xu, OUYANG Ji-hong, CHEN Gui-fen. Measurement of graph similarity based on vertical dimension sequence dynamic time warping method [J]. 吉林大学学报(工学版), 2018, 48(4): 1199-1205.
[7] ZHANG Hao, ZHAN Meng-ping, GUO Liu-xiang, LI Zhi, LIU Yuan-ning, ZHANG Chun-he, CHANG Hao-wu, WANG Zhi-qiang. Human exogenous plant miRNA cross-kingdom regulatory modeling based on high-throughout data [J]. 吉林大学学报(工学版), 2018, 48(4): 1206-1213.
[8] ZHAO Hong-wei, LIU Yu-qi, DONG Li-yan, WANG Yu, LIU Pei. Dynamic route optimization algorithm based on hybrid in ITS [J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[9] CAO Jing-hua, KONG Fan-sen, RAN Yan-zhong, SONG Rui-chen. Back pressure controller design of air compressor based on fuzzy self-adaptive PID control [J]. 吉林大学学报(工学版), 2018, 48(3): 781-786.
[10] HUANG Lan, JI Lin-ying, YAO Gang, ZHAI Rui-feng, BAI Tian. Construction of disease-symptom semantic net for misdiagnosis prompt [J]. 吉林大学学报(工学版), 2018, 48(3): 859-865.
[11] LI Xiong-fei, FENG Ting-ting, LUO Shi, ZHANG Xiao-li. Automatic music composition algorithm based on recurrent neural network [J]. 吉林大学学报(工学版), 2018, 48(3): 866-873.
[12] LIU Jie, ZHANG Ping, GAO Wan-fu. Feature selection method based on conditional relevance [J]. 吉林大学学报(工学版), 2018, 48(3): 874-881.
[13] CHEN Song, LI Xian-sheng, REN Yuan-yuan. Adaptive signal control method for intersection with hook-turn buses [J]. 吉林大学学报(工学版), 2018, 48(2): 423-429.
[14] WANG Xu, OUYANG Ji-hong, CHEN Gui-fen. Heuristic algorithm of all common subsequences of multiple sequences for measuring multiple graphs similarity [J]. 吉林大学学报(工学版), 2018, 48(2): 526-532.
[15] YANG Xin, XIA Si-jun, LIU Dong-xue, FEI Shu-min, HU Yin-ji. Target tracking based on improved accelerated gradient under tracking-learning-detection framework [J]. 吉林大学学报(工学版), 2018, 48(2): 533-538.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd