Ant Colony Optimization approaches to the degree-constrained minimum spanning tree problem

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

[img] 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

View ItemEdit (login required)