A new transgenetic approach for the biobjective spanning tree problem

摘要

This paper addresses a new transgenetic approach to the biobjective spanning tree, an NP-hard combinatorial optimization problem which can model different real applications on network design. The metaheuristic is inspired on endosymbiosis and horizontal gene transfer, two main evolutionary forces. The proposed algorithm is applied to 78 instances with different structures. The results concerning the quality of the approximation sets obtained with the proposed approach are compared to others previously published in the literature with basis on a Pareto compliant quality indicator. Comparisons regarding processing times are also reported. Statistical tests show that the proposed approach is comparable with the algorithms presented in the literature, outperforming them in solution quality for most instances.