A New Local Search Based Ant Colony Optimization Algorithm for Solving Combinatorial Optimization Problems

Md. Rakib HASSAN  Md. Monirul ISLAM  Kazuyuki MURASE  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.5   pp.1127-1136
Publication Date: 2010/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.1127
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
ant colony optimization,  combinatorial optimization problem,  local search,  

Full Text: PDF>>
Buy this Article




Summary: 
Ant Colony Optimization (ACO) algorithms are a new branch of swarm intelligence. They have been applied to solve different combinatorial optimization problems successfully. Their performance is very promising when they solve small problem instances. However, the algorithms' time complexity increase and solution quality decrease for large problem instances. So, it is crucial to reduce the time requirement and at the same time to increase the solution quality for solving large combinatorial optimization problems by the ACO algorithms. This paper introduces a Local Search based ACO algorithm (LSACO), a new algorithm to solve large combinatorial optimization problems. The basis of LSACO is to apply an adaptive local search method to improve the solution quality. This local search automatically determines the number of edges to exchange during the execution of the algorithm. LSACO also applies pheromone updating rule and constructs solutions in a new way so as to decrease the convergence time. The performance of LSACO has been evaluated on a number of benchmark combinatorial optimization problems and results are compared with several existing ACO algorithms. Experimental results show that LSACO is able to produce good quality solutions with a higher rate of convergence for most of the problems.