A Comparative Analysis of ACO and BCO forSolving the TSP
Date
2014
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Department of Computer Science and I.T.
Abstract
Combinatorial optimization problems are very difficult to solve, since these problems span alarge space of NP-hard problems. Various solution models are introduced and used to solve these problems. The Travelling Salesman Problem (TSP) is an intractable NP-hard combinatorial optimization problem studied in operations research and theoretical computer science. Exact methods, heuristics, evolutionary approaches, and meta-heuristic models are widely used to solve TSP like problems.Ant Colony Optimization (ACO) is a modern and very popular Swarm Intelligence optimization paradigm inspired by the ability of ant colonies to find shortest paths between their nest and a food source. ACO is one of the high performance computing methods for Travelling Salesman Problem (TSP). It still has some drawbacks such as stagnation behavior,long computational time, and premature convergence problem on TSP. Those problems will be more obvious when the considered problem size increases.Bee Colony Optimization (BCO) meta-heuristic belongs to the group of Swarm Intelligence techniques. BCO is the name given to the collective food foraging behavior of honey bee.The bee system is a standard example of organized team work, well coordinated interaction,coordination, labor division, simultaneous task performance, specialized individuals, and well-knit communication. The BCO uses a similarity among the way in which bees in nature look for a food, and the way in which optimization algorithms search for an optimum in combinatorial optimization problems.The Swarm-based Algorithm is a search algorithm capable of locating good solutions efficiently. The algorithm could be considered as belonging to the category of “Intelligent Optimization Tools”.General ACO and BCO are implemented and tested on benchmark problems from TSPLIB and evaluations are carried out. Evaluation results have shown that BCO has improved 13.35%optimal path solutions on average and computational time is improved by13.41%on average.
Description
Keywords
Combinatorial Optimization, BCO, ACO, Swarm Intelligence