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.
