New Discrete Particle Swarm Algorithm for Traveling Salesman Problem

Abstract:

In this paper, a novel algorithm called CIPSO for short based on particle optimization algorithm(PSO) and Chaos optimization Algorithm(COA) is presented to solve traveling salesman problem(TSP). We propose some new operators to solve the difficulties of implementing PSO into solving this discrete problem based on the special fitness landscape of TSP. Meanwhile embedded with chaos theory it can enhance particles’ global searching ability so as not to converge to the local optimal solution too quickly, and the introduction of information intercourse can enhance thire local searching ability. Comparing to SA, GA, ACS and so on, this new algorithm shows its validity and satisfactory effect on several benchmark test problems.

• Periodical: Advanced Materials Research (Volumes 148-149)
• Pages: 210-214
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.148-149.210
• Online since: October 2010
• Authors: Jiu Yong Li, Jing Wang
• Keywords: Chaos Theory, Information Intercourse, Particle Swarm Optimization Algorithm (PSO), Traveling Salesman Problem (TSP)

References

[1] Eberhart R C and Kennedy J, Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks. IEEE Service Center, Piscataway, NJ, pp: 1942-1948, IV, (1995).

[2] Shi Y H and Eberhart R C, A modified particle swarm optimizer, IEEE Int Conf on Evolutionary Computation, Anchorage, pp: 69-73, (1998).

[3] (2000)Discrete particle swarm optimization illustrated by the traveling salesman problem. [Online]. Available: http: /www. mauriceclerc. net.

[4] Li A G, Qin Z, and Bao F M, Particle swarm optimization algorithms, Computer Engineering and Applications, 38(21): 1-3, (2002).

[5] Clerc M, Discrete Particle Swarm Optimization, Illustrated by Traveling Salesman Problem, Onwubolu G C, Babu B V. New Optimization Techniques in Engineering. Berlin: SpringerVerlag, (2004).

DOI: 10.1007/978-3-540-39930-8_8

[6] Wang Kang-ping, Huang Lan, Zhou Chun-guang. Particle Swarm optimization for traveling salesman problem, IEEE Service Center, Proceedings of the Second International Conference on Machine Learning and Cybernetics, Xi'an: IEEE Press, November, pp: 1583-1585, 5, (2003).

DOI: 10.1109/icmlc.2003.1259748

[7] Zhanglei Yuan, Liliang Yang, Yaohua Wu, Chaotic Particle Swarm Optimization Algorithm for Traveling Salesman Problem, Proceedings of the IEEE International Conference on Automation and Logistics, August 18-21, Jinan, China: 1121-1124, (2009).

DOI: 10.1109/ical.2007.4338736

[8] Jing-jing Sun and Xiu-juan Lei. Geese-inspired Hybrid Particle Swarm Optimization Algorithm for Traveling Salesman Problem. IEEE Computer Society, April 4th, pp: 134-138, (2009).

DOI: 10.1109/aici.2009.425