AN ENHANCED ANT COLONY OPTIMIZATION METAHEURISTIC FOR THE MINIMUM DOMINATING SET PROBLEM
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
TAYLOR & FRANCIS INC
2006
|
| Subjects: | |
| Online Access: | http://shdl.mmu.edu.my/3252/ |
| _version_ | 1848790276297981952 |
|---|---|
| author | Ho, Chin Kuan Singh, Yashwant Prasad Ewe, Hong Tat |
| author_facet | Ho, Chin Kuan Singh, Yashwant Prasad Ewe, Hong Tat |
| author_sort | Ho, Chin Kuan |
| building | MMU Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T18:10:02Z |
| format | Article |
| id | mmu-3252 |
| institution | Multimedia University |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:10:02Z |
| publishDate | 2006 |
| publisher | TAYLOR & FRANCIS INC |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | mmu-32522011-10-13T06:00:07Z http://shdl.mmu.edu.my/3252/ AN ENHANCED ANT COLONY OPTIMIZATION METAHEURISTIC FOR THE MINIMUM DOMINATING SET PROBLEM Ho, Chin Kuan Singh, Yashwant Prasad Ewe, Hong Tat T Technology (General) QA75.5-76.95 Electronic computers. Computer science 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. TAYLOR & FRANCIS INC 2006-11 Article NonPeerReviewed 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 http://dx.doi.org/10.1080/08839510600940132 doi:10.1080/08839510600940132 doi:10.1080/08839510600940132 |
| spellingShingle | T Technology (General) QA75.5-76.95 Electronic computers. Computer science Ho, Chin Kuan Singh, Yashwant Prasad Ewe, Hong Tat AN ENHANCED ANT COLONY OPTIMIZATION METAHEURISTIC FOR THE MINIMUM DOMINATING SET PROBLEM |
| title | AN ENHANCED ANT COLONY OPTIMIZATION METAHEURISTIC FOR THE MINIMUM DOMINATING SET PROBLEM |
| title_full | AN ENHANCED ANT COLONY OPTIMIZATION METAHEURISTIC FOR THE MINIMUM DOMINATING SET PROBLEM |
| title_fullStr | AN ENHANCED ANT COLONY OPTIMIZATION METAHEURISTIC FOR THE MINIMUM DOMINATING SET PROBLEM |
| title_full_unstemmed | AN ENHANCED ANT COLONY OPTIMIZATION METAHEURISTIC FOR THE MINIMUM DOMINATING SET PROBLEM |
| title_short | AN ENHANCED ANT COLONY OPTIMIZATION METAHEURISTIC FOR THE MINIMUM DOMINATING SET PROBLEM |
| title_sort | enhanced ant colony optimization metaheuristic for the minimum dominating set problem |
| topic | T Technology (General) QA75.5-76.95 Electronic computers. Computer science |
| url | http://shdl.mmu.edu.my/3252/ http://shdl.mmu.edu.my/3252/ http://shdl.mmu.edu.my/3252/ |