## Citation

Bau, Yoon Teck and Ho, Chin Kuan and Ewe, Hong Tat (2008)*Ant Colony Optimization approaches to the degree-constrained minimum spanning tree problem.*Journal of Information Science and Engineering, 24 (4). pp. 1081-1094. ISSN 1016-2364

Text
Ant Colony Optimization Approaches.pdf Restricted to Repository staff only Download (1MB) |

## Abstract

This paper presents the design of two Ant Colony Optimization (ACO) approaches and their improved variants on the degree-constrained minimum spanning tree (d-MST) problem. The first approach, which we call p-ACO, uses the vertices of the construction graph as solution components, and is motivated by the well-known Prim's algorithm for constructing MST. The second approach, known as k-ACO, uses the graph edges as solution components, and is motivated by Kruskal's algorithm for the MST problem. The proposed approaches are evaluated on two different data sets containing difficult d-MST instances. Empirical results show that k-ACO performs better than p-ACO. We then enhance the k-ACO approach by incorporating the tournament selection, global update and candidate lists strategies. Empirical evaluations of the enhanced k-ACO indicate that on average, it performs better than Prufer-coded evolutionary algorithm (F-EA), problem search space (PSS), simulated annealing (SA), branch and bound (B&B), Knowles and Come's evolutionary algorithm (K-EA) and ant-based algorithm (AB) on most problem instances from a well-known class of data set called structured hard graphs. Results also show that it is very competitive with two other evolutionary algorithm based methods, namely weight-coded evolutionary algorithm (W-EA), and edge-set representation evolutionary algorithm (S-EA) on the same class of data set.

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 Computing and Informatics (FCI) |

Depositing User: | Ms Suzilawati Abu Samah |

Date Deposited: | 24 Aug 2011 06:32 |

Last Modified: | 21 Sep 2021 07:36 |

URII: | http://shdl.mmu.edu.my/id/eprint/2295 |

### Downloads

Downloads per month over past year

Edit (login required) |