Population-Based Optimization Algorithms for Solving the Travelling Salesman Problem
Mohammad Reza, Mostafa Rahimi, Hamed Shah Hosseini · InTech eBooks · 2008
Maybe this chapter is the first versatile study on the population based optimization algorithms focused on solving the TSP. In this study, the state of the art of population based optimization algorithms such as Evolutionary Algorithms (EA), Ant Colony Optimization Algorithms (ACO), Particle Swarm Optimization Algorithms (PSO), Intelligent Water-Drops Algorithm (IWD), Artificial Immune Systems (AIS), Bee Colony Optimization Algorithms (BCO) and finally Electromagnetism-like Mechanisms (EM) has been introduced and investigated. The chapter includes nine parts before this; first one is introduction on the TSP and optimization algorithm, seven sections are about mentioned population based optimization algorithms and some related works which use these methods for solving the TSP, and finally the last part encompasses experimental results on the perused studies. All the sections try to introduce the related population based algorithm truly. Then the authors attempt to explore some useful studies that have been done by other researchers for solving the TSP. In addition some important points, where contribution or innovation in different parts of the related algorithm or in solving the TSP can be applied, have been pointed. The experimental results demonstrate a brief comparison among the various population based optimization methods. In this section you can find some tables, graphs and figures which compare the presented methods with their counterparts in terms of efficiency using some well known benchmarks on the TSP. The performed study shows that all of the stated methods have some weakness and some strength points which are noticed at the related section. As a consequence, the further research can focus on these points for amplification of strengths and eliminating or improving the weaknesses. In addition, an innovative population based method inspired by natural water drops behaviour is reviewed in this chapter.