Ant Colony Optimization Algorithm with Pheromone Correction Strategy for the Minimum Connected Dominating Set Problem

Raka Jovanovic1 and Milan Tuba2

  1. Texas AM University at Qatar
    PO Box 23874, Doha, Qatar
    rakabog@yahoo.com
  2. Megatrend University Belgrade, Faculty of Computer Science
    Bulevar umetnosti 29, N. Belgrade, Serbia
    tuba@ieee.org

Abstract

In this paper an ant colony optimization (ACO) algorithm for the minimum connected dominating set problem (MCDSP) is presented. The MCDSP become increasingly important in recent years due to its applicability to the mobile ad hoc networks (MANETs) and sensor grids. We have implemented a one-step ACO algorithm based on a known simple greedy algorithm that has a significant drawback of being easily trapped in local optima. We have shown that by adding a pheromone correction strategy and dedicating special attention to the initial condition of the ACO algorithm this negative effect can be avoided. Using this approach it is possible to achieve good results without using the complex two-step ACO algorithm previously developed. We have tested our method on standard benchmark data and shown that it is competitive to the existing algorithms.

Key words

Ant colony optimization (ACO), Minimum connected dominating set problem, Swarm intelligence, Optimization metaheuristics

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS110927038J

Publication information

Volume 10, Issue 1 (Januar 2013)
Year of Publication: 2013
ISSN: 1820-0214 (Print) 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Jovanovic, R., Tuba, M.: Ant Colony Optimization Algorithm with Pheromone Correction Strategy for the Minimum Connected Dominating Set Problem. Computer Science and Information Systems, Vol. 10, No. 1, 133-149. (2013)