The transformation of the k-Shortest Steiner trees search problem into binary dynamic problem for effective evolutionary methods application

摘要

Evolutionary methods are well-known tools used for solving hard computational problems. In this paper, we consider k-Shortest Steiner Trees (kSST) problem appearing in a diverse set of domains, e.g., multicast tree construction in communication networks in general, and optical networks in particular. The kSST is relatively new and has not been widely investigated in the literature. Thus, only a few algorithms have been proposed, each requiring significant resources amount and long execution times, partially following from the NP-hard nature of the problem. The kSST problem solution is a set of different trees, where each single tree can be easily represented using a genotype-encoding. However, encoding the tree set may be challenging, as each tree must be unique. Especially, in most applications the number of trees is large, resulting with the genotype containing high number of necessary genes. Thus, in this paper, we propose a transformation of the kSST problem into a dynamic problem, and when applied in the evolutionary method, a single individual encodes a single tree instead of a whole tree set. The results of extensive numerical experiments executed on two representative network topologies show that the proposed transformation improves the effectiveness of all considered state-of-the-art evolutionary methods. (C) 2018 Elsevier Inc. All rights reserved.