Particle swarm optimization with partial search to solve traveling salesman problem

• Main Authors: Akhand, M.A.H., Akter, Shahina, Rahman, S. Sazzadur, Rahman, M.M. Hafizur
• Format: Conference or Workshop Item
• Language: English
• Published: 2012
• Subjects: TK7800 Electronics. Computer engineering. Computer hardware. Photoelectronic devices
• Online Access: http://irep.iium.edu.my/24983/1/1058C.pdf; http://irep.iium.edu.my/24983/
• Institution: Universiti Islam Antarabangsa Malaysia

Particle Swarm Optimization (PSO) is population based optimization technique on metaphor of social behavior of flocks of birds and/or schools of fishes. For better solution, at every step each particle changes its velocity based on its current velocity with respect to its previous best position and position of the current best particle in the population. PSO has found as an efficient method for solving function optimization problems, and recently it also studied to solve combinatorial problems such as Traveling Salesman Problem (TSP). Existing method introduced the idea of Swap Operator (SO) and Swap Sequence (SS) in PSO to handle TSP. For TSP, each particle represents a complete tour and velocity is measured as a SS consisting with several SOs. A SO indicates two positions in the tour that might be swap. In the existing method, a new tour is considered after applying a complete SS with all its SOs. Whereas, every SO implantation on a particle (i.e., a solution or a tour) gives a new solution and there might be a chance to get a better tour with some of SOs instead of all the SOs. The objective of the study is to achieve better result introducing using such partial search option for solving TSP. The proposed PSO with Partial Search (PSOPS) algorithm is shown to produce optimal solution within a less number of generation than standard PSO, Genetic Algorithm in solving benchmark TSP.