Premium
A multiethnic genetic approach for the minimum conflict weighted spanning tree problem
Author(s) -
Carrabs Francesco,
Cerrone Carmine,
Pentangelo Rosa
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21883
Subject(s) - minimum spanning tree , spanning tree , distributed minimum spanning tree , mathematical optimization , benchmark (surveying) , kruskal's algorithm , computer science , tree (set theory) , heuristic , computation , genetic algorithm , enhanced data rates for gsm evolution , population , mathematics , algorithm , artificial intelligence , combinatorics , geography , demography , geodesy , sociology
Abstract 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.