Citation

Ho, Chin Kuan and Singh, Yashwant Prasad and Ewe, Hong Tat (2006) AN ENHANCED ANT COLONY OPTIMIZATION METAHEURISTIC FOR THE MINIMUM DOMINATING SET PROBLEM. Applied Artificial Intelligence, 20 (10). 881-903 . ISSN 0883-9514

Full text not available from this repository.

Abstract

This paper proposes an enhanced Ant Colony Optimization (ACO) metaheuristic called ACO-TS to attack the minimum dominating set (MDS) problem. One of the recognized difficulties faced by ACO in its original form is premature convergence, which produces less satisfactory solutions. We propose a way to encourage a higher degree of exploration of the search space by incorporating a technique based oil. a concept borrowed from genetic algorithms called tournament selection. Instead of always following the standard mechanism for selecting the next solution component, an ant would make its decision based on. the outcome of a tournament between randomly selected allowable components. The frequency of the tournament selection. is controlled by a probability measure. The,use of tournament selection. is coupled with an iteration-best pheromone update. To evaluate the enhanced ACO, we consider the MDS problem formulated from ad hoc network clustering. A comparison with its original form shows that the enhanced ACO produces better solutions using fewer number of cycles. We also empirically demonstrate that the proposed ACO produces better solutions than. a genetic algorithm. Finally, we argue, based on empirical results, why the tournament selection approach is preferable to a pure random selection method.

Item Type:	Article
Subjects:	T Technology > T Technology (General) Q Science > QA Mathematics > QA71-90 Instruments and machines > QA75.5-76.95 Electronic computers. Computer science
Divisions:	Faculty of Engineering and Technology (FET)
Depositing User:	Ms Suzilawati Abu Samah
Date Deposited:	13 Oct 2011 06:00
Last Modified:	13 Oct 2011 06:00
URII:	http://shdl.mmu.edu.my/id/eprint/3252

Downloads

Edit (login required)