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

Md. Rakib HASSAN; Md. Monirul ISLAM; Kazuyuki MURASE

doi:10.1587/transinf.E93.D.1127

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

Md. Rakib HASSAN, Md. Monirul ISLAM, Kazuyuki MURASE

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E93-D No.5 pp.1127-1136

Publication Date: 2010/05/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E93.D.1127

Type of Manuscript: PAPER

Category: Fundamentals of Information Systems

Cite this

Copy

Md. Rakib HASSAN, Md. Monirul ISLAM, Kazuyuki MURASE, "A New Local Search Based Ant Colony Optimization Algorithm for Solving Combinatorial Optimization Problems" in IEICE TRANSACTIONS on Information, vol. E93-D, no. 5, pp. 1127-1136, May 2010, doi: 10.1587/transinf.E93.D.1127.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.1127/_p

Copy

@ARTICLE{e93-d_5_1127,
author={Md. Rakib HASSAN, Md. Monirul ISLAM, Kazuyuki MURASE, },
journal={IEICE TRANSACTIONS on Information},
title={A New Local Search Based Ant Colony Optimization Algorithm for Solving Combinatorial Optimization Problems},
year={2010},
volume={E93-D},
number={5},
pages={1127-1136},
abstract={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.},
keywords={},
doi={10.1587/transinf.E93.D.1127},
ISSN={1745-1361},
month={May},}

Copy

TY - JOUR
TI - A New Local Search Based Ant Colony Optimization Algorithm for Solving Combinatorial Optimization Problems
T2 - IEICE TRANSACTIONS on Information
SP - 1127
EP - 1136
AU - Md. Rakib HASSAN
AU - Md. Monirul ISLAM
AU - Kazuyuki MURASE
PY - 2010
DO - 10.1587/transinf.E93.D.1127
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2010
AB - 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.
ER -