A genetic algorithm approach on tree-like telecommunication network design problem

Abstract

In the context of telecommunication networks, the network terminals involve certain constraints that are either related with the performance of the corresponding network or with the availability of some classes of devices. In this paper, we discuss a tree-like telecommunication network design problem with the constraint limiting the number of terminals. First, this problem is formulated as a leaf-constrained minimum spanning tree (lc-MST). Then we develop a tree-based genetic representation to encode the candidate solutions of the lc-MST problem. Compared with the existing heuristic algorithm, the numerical results show the high effectiveness of the proposed GA approach on this problem.

Keywords:

• genetic algorithms
• network design
• minimum spanning tree
• telecommunication

Acknowledgements

This research work was partially supported by the National Nature Science Foundation of China (No. 60074035) and Zhejiang Provincial Nature Science Foundation (No. 600042). Thanks are given to two referees for their valuable comments on an earlier version of this paper.