A multiethnic genetic approach for the minimum conflict weighted spanning tree problem

This paper addresses a variant of the minimum spanning tree problem in which, given a list of conflicting edges, the primary goal is to find a spanning tree with the minimum number of conflicting edge pairs and the secondary goal is to minimize the weight of spanning trees without conflicts. The problem is NP-hard and it finds applications in the design of offshore wind farm networks. We propose a multiethnic genetic algorithm for the problem in which the fitness function is designed to simultaneously manage the two goals of the problem. Moreover, we introduce three local search procedures to improve the solutions inside the population during the computation. Computational results performed on benchmark instances reveal that our algorithm outperforms the other heuristic approach, proposed in the literature, for this problem.