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

Citation

Yoon-Teck, Bau and Chin-Kuan, Ho and Hong-Tat, Ewe (2008) Ant Colony Optimization approaches to the degree-constrained minimum spanning tree problem. INST INFORMATION SCIENCE, 24 (4). pp. 1081-1094.

Full text not available from this repository.

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 Engineering and Technology (FET)
Depositing User: Ms Suzilawati Abu Samah
Date Deposited: 24 Aug 2011 06:32
Last Modified: 24 Aug 2011 06:32
URII: http://shdl.mmu.edu.my/id/eprint/2295

Downloads

Downloads per month over past year

View ItemEdit (login required)