Abstract—The optimal communication spanning tree (OCST) problem finds a spanning tree that connects all node satisfies their communication requirements for a minimum total cost. In this paper, we present a new method of finding optimal solution for OCST problem based on Ant Colony Optimization (ACO) to reduce search space mentioned above but still converge to a global good solution. Our algorithm take account into node biased encoding (NBE) scheme to find nearly optimal solution. The new algorithm can achieve a result that is better than known heuristic algorithms do, as verified by a set of public benchmark problem instances.
Index Terms—Optimal communication spanning tree, node biased encoding, ant colony optimization.
Nhu Gia Nguyen is with the Duy Tan University, Danang, Vietnam (e-mail: Nguyengianhu@duytan.edu.vn).
Dac-Nhuong Le is with the Faculty of Information Technology, Haiphong University, Vietnam (e-mail: Nhuongld@ hus.edu.vn).
Nguyen Dang Le is with the Haiphong University, Vietnam (e-mail: Nguyenld@ hus.edu.vn).
[PDF]
Cite:Nhu Gia Nguyen, Dac-Nhuong Le, and Nguyen Dang Le, "A Novel Ant Colony Optimization-Based Algorithm for the Optimal Communication Spanning Tree Problem," International Journal of Computer Theory and Engineering vol. 5, no. 3, pp. 509-513, 2013.
