A New Crossover Mechanism for Genetic Algorithms for Steiner Tree Optimization
Qiongbing Zhang, Shengxiang Yang, Min Liu, Jianxun Liu, Lei Jiang
Abstract
Genetic algorithms (GAs) have been widely applied in Steiner tree optimization problems. However, as the core operation, existing crossover operators for tree-based GAs suffer from producing illegal offspring trees. Therefore, some global link information must be adopted to ensure the connectivity of the offspring, which incurs heavy computation. To address this problem, this article proposes a new crossover mechanism, called leaf crossover (LC), which generates legal offspring by just exchanging partial parent chromosomes, requiring neither the global network link information, encoding/decoding nor repair operations. Our simulation study indicates that GAs with LC outperform GAs with existing crossover mechanisms in terms of not only producing better solutions but also converging faster in networks of varying sizes.