## 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

Edit (login required) |