New local search based ACO algorithm for solving combinatorial optimization problems

Abstract

ACO algorithms are a new branch of swarm intelligence. ACO algorithms have been introduced in the last decade. They have been applied to solve different combinatorial optimization problems successfully. Their performance is very promising when they solve small problem instances. When they try to solve large problems, their time complexity increases and their solution quality decreases. They get stuck in local optima due to improper balancing of exploration and exploitation of the search space. When their solution quality is tried to improve using local search, their time complexity is increased. When time complexity is tried to reduc'e, they produce poor . quality solutions. So, it is crucial to reduce the time requirement and at the same time to increase the solution quality produced by the algorithms for solving large combinatorial optimization algorithms. This thesis introduces Local Search based Ant Colony Optimization algorithm • (LSACO), a new ACO algorithm to solve large combinatorial optimization problems. The basis of LSACO is to apply an adaptive local search method to improve the solution quality. Adaptive local search automatically determines the number of edges to exchange during the run time of the algorithm. LSACO also applies pheromone updating rule and constructs solutions in a new way so as to decrease the convergence . time. LSACO makes it possible to produce very good quality solutions for large problem instances in a short time. 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 performs better optimization with a higher rate of convergence for most of the problems in a reasonable amount oftime.