A Clustering-Enhanced Memetic Algorithm for the Quadratic Minimum Spanning Tree Problem

The quadratic minimum spanning tree problem (QMSTP) is a spanning tree optimization problem that considers the interaction cost between pairs of edges arising from a number of practical scenarios. This problem is NP-hard, and therefore there is not a known polynomial time approach to solve it. To fi...

Full description

Saved in:
Bibliographic Details
Published in:Entropy (Basel, Switzerland) Switzerland), 2022-12, Vol.25 (1), p.87
Main Authors: Zhang, Shufan, Mao, Jianlin, Wang, Niya, Li, Dayan, Ju, Chengan
Format: Article
Language:English
Subjects:
agglomerative clustering
Algorithms
Clustering
combinatorial optimization
Costs
Diversification
Exploitation
Genetic algorithms
Graph theory
Levy distribution
memetic algorithm
Mutation
Neighborhoods
Optimization
Polynomials
quadratic minimum spanning tree problem
Upper bounds
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The quadratic minimum spanning tree problem (QMSTP) is a spanning tree optimization problem that considers the interaction cost between pairs of edges arising from a number of practical scenarios. This problem is NP-hard, and therefore there is not a known polynomial time approach to solve it. To find a close-to-optimal solution to the problem in a reasonable time, we present for the first time a clustering-enhanced memetic algorithm (CMA) that combines four components, i.e., (i) population initialization with clustering mechanism, (ii) a tabu-based nearby exploration phase to search nearby local optima in a restricted area, (iii) a three-parent combination operator to generate promising offspring solutions, and (iv) a mutation operator using Lévy distribution to prevent the population from premature. Computational experiments are carried on 36 benchmark instances from 3 standard sets, and the results show that the proposed algorithm is competitive with the state-of-the-art approaches. In particular, it reports improved upper bounds for the 25 most challenging instances with unproven optimal solutions, while matching the best-known results for all but 2 of the remaining instances. Additional analysis highlights the contribution of the clustering mechanism and combination operator to the performance of the algorithm.
ISSN:1099-4300
1099-4300
DOI:10.3390/e25010087