Journal international d'intelligence d'essaim et de calcul évolutif

Abstrait

A Comparative Study of Prominent Particle Swarm Optimization Based Methods to Solve Traveling Salesman Problem

Akhand MAH, Shaik Imran Hossain and Shahina Akter

Computational methods inspired by natural phenomenon have gain much interest in the recent years. Among the developed algorithms, particle swarm optimization (PSO), mimicking behavior of bird flocking or fish schooling, seems the most famous method due to its simplicity as well as performance. A variant number of PSO based methods was developed for traveling salesman problem (TSP), the most popular combinatorial problem. The aim of the study is to make a comparative study of several prominent PSO based methods in solving TSP. The study is important because different PSO based methods have been developed by different researchers and tested on different sets of problems. Therefore, the description of the prominent PSO based methods in a similar fashion reveals distinct features of individuals. Moreover, experimental results on a common benchmark TSP data set will reveal performance of each method. In this study, the methods have been tested on a large number of benchmark TSPs and outcomes compared among themselves as well as ant colony optimization (ACO), the prominent method to solve TSP. Experimental results revealed that enhanced self-tentative PSO (ESTPSO) and velocity tentative PSO (VTPSO) outperformed ACO; and self-tentative PSO (STPSO) is competitive to ACO. On the other hand, experimental analysis revealed that ESTPSO is computationally heavier than others and VTPSO took least time to solve a benchmark problem. The reasons behind performance and time requirement of each individual method are explained and VTPSO is found most effective PSO based method to solve TSP.