An Improved Genetic Algorithm for Solving the Clustered Steiner Tree Problem

Abstract

In a complex network comprising many devices, a set of nodes may be partitioned into multiple local clusters with distinct functions, properties, or communication protocols. Thus, there has been an increase in network design problems with additional constraints regarding the clustering of vertices, one of which is the Clustered Steiner Tree Problem – a variant of the Steiner Tree Problem. There have been a few studies working on this problem in the literature, but they either solve it only in the metric case, or their exploration capability remains limited. Therefore, their results are not good in many cases. To overcome the drawbacks, we propose a Priority-Based Genetic Algorithm to solve the Clustered Steiner Tree Problem. The proposed algorithm maintains a balance between exploration and exploitation to prevent the search from getting stuck in local optima. Experiments and comparisons to existing works in non-metric and metric cases are carefully conducted to prove the remarkable performance of the proposed algorithm.