Improvement of bounded-diameter MST instances with hybridization of multi-objective EA
Soma Saha, Rajeev Kumar · 2011
The Bounded Diameter (a.k.a Diameter Constraint) Minimum Spanning Tree (BDMST/DCMST) is a well-known combinatorial optimization problem. In this work, we recast a few well-known heuristics, which are evolved for BDMST problem, to a Bi-Objective Minimum Spanning Tree (BO-MST) problem and then obtain Pareto fronts. On visualizing the Pareto fronts, it is observed that none of the heuristics provides the best solution across the complete range of the diameter. We have used a Multi-Objective Evolutionary Algorithm (MOEA) approach to improve the Pareto front for BOMST, which in turn provides better solution for BDMST instances. We observe that the MOEA provides improved Pareto front solutions across the complete range of the diameter over Pareto front solutions generated from individual heuristics.