Ant Colony Optimization approaches to the degree-constrained minimum spanning tree problem
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
JISE
2008
|
| Subjects: | |
| Online Access: | http://shdl.mmu.edu.my/2295/ http://shdl.mmu.edu.my/2295/1/Ant%20Colony%20Optimization%20Approaches.pdf |
| _version_ | 1848790017731723264 |
|---|---|
| author | Bau, Yoon Teck Ho, Chin Kuan Ewe, Hong Tat |
| author_facet | Bau, Yoon Teck Ho, Chin Kuan Ewe, Hong Tat |
| author_sort | Bau, Yoon Teck |
| building | MMU Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T18:05:56Z |
| format | Article |
| id | mmu-2295 |
| institution | Multimedia University |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T18:05:56Z |
| publishDate | 2008 |
| publisher | JISE |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | mmu-22952021-09-21T07:36:37Z http://shdl.mmu.edu.my/2295/ Ant Colony Optimization approaches to the degree-constrained minimum spanning tree problem Bau, Yoon Teck Ho, Chin Kuan Ewe, Hong Tat T Technology (General) QA75.5-76.95 Electronic computers. Computer science 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. JISE 2008-07 Article NonPeerReviewed text en http://shdl.mmu.edu.my/2295/1/Ant%20Colony%20Optimization%20Approaches.pdf 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 https://jise.iis.sinica.edu.tw/JISESearch/pages/View/PaperView.jsf?keyId=43_722 |
| spellingShingle | T Technology (General) QA75.5-76.95 Electronic computers. Computer science Bau, Yoon Teck Ho, Chin Kuan Ewe, Hong Tat Ant Colony Optimization approaches to the degree-constrained minimum spanning tree problem |
| title | Ant Colony Optimization approaches to the degree-constrained minimum spanning tree problem |
| title_full | Ant Colony Optimization approaches to the degree-constrained minimum spanning tree problem |
| title_fullStr | Ant Colony Optimization approaches to the degree-constrained minimum spanning tree problem |
| title_full_unstemmed | Ant Colony Optimization approaches to the degree-constrained minimum spanning tree problem |
| title_short | Ant Colony Optimization approaches to the degree-constrained minimum spanning tree problem |
| title_sort | ant colony optimization approaches to the degree-constrained minimum spanning tree problem |
| topic | T Technology (General) QA75.5-76.95 Electronic computers. Computer science |
| url | http://shdl.mmu.edu.my/2295/ http://shdl.mmu.edu.my/2295/ http://shdl.mmu.edu.my/2295/1/Ant%20Colony%20Optimization%20Approaches.pdf |