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

Edit (login required)