Advertisement
Published in:
14-05-2019 | Methodologies and Application
A hybrid genetic algorithm for the degree-constrained minimum spanning tree problem
Published in: Soft Computing | Issue 3/2020
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Given an undirected, connected, edge-weighted graph G and a positive integer d, the degree-constrained minimum spanning tree (dc-MST) problem aims to find a minimum spanning tree T on G subject to the constraint that each vertex is either a leaf vertex or else has degree at most d in T, where d is a given positive integer. The dc-MST is \(\mathcal {NP}\)-hard problem for d\(\ge \) 2 and finds several real-world applications. This paper proposes a hybrid approach (\(\mathcal {H}\)SSGA) combining a steady-state genetic algorithm and local search strategies for the this problem. An additional step (based on perturbation strategy at a regular interval of time) in the replacement strategy is applied in order to maintain diversity in the population throughout the search process. On a set of available 107 benchmark instances, computational results show the superiority of our proposed \(\mathcal {H}\)SSGA in comparison with the state-of-the-art metaheuristic techniques.