Particle swarm optimization with partial search to solve traveling salesman problem

Akhand, M.A.H. and Akter, Shahina and Rahman, S. Sazzadur and Rahman, M.M. Hafizur (2012) Particle swarm optimization with partial search to solve traveling salesman problem. In: International Conference on Computer and Communication Engineering (ICCCE 2012), 3-5 July 2012, Seri Pacific Hotel Kuala Lumpur.

PDF (Particle swarm optimization with partial search to solve traveling salesman problem) Restricted to Registered users only Download (104kB) | Request a copy

Abstract

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.

Item Type:	Conference or Workshop Item (Full Paper)
Uncontrolled Keywords:	Particle Swarm Optimization (PSO), Traveling Salesman Problem (TSP) and Swap Sequence.
Subjects:	T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800 Electronics. Computer engineering. Computer hardware. Photoelectronic devices
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Information and Communication Technology > Department of Computer Science Kulliyyah of Information and Communication Technology > Department of Computer Science
Depositing User:	Dr. M.M. Hafizur Rahman
Date Deposited:	07 Sep 2012 13:56
Last Modified:	18 Sep 2012 10:17
URI:	http://irep.iium.edu.my/id/eprint/24983

Actions (login required)

View Item