Genetic algorithm approach on multi-criteria minimum spanning tree problem

Genetic algorithm approach on multi-criteria minimum spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor20001822
Country: Netherlands
Volume: 114
Issue: 1
Start Page Number: 141
End Page Number: 152
Publication Date: Apr 1999
Journal: European Journal of Operational Research
Authors: ,
Keywords: genetic algorithms
Abstract:

Minimum Spanning Tree (MST) problem is of high importance in network optimization. The multi-criteria MST (mc-MST) is a more realistic representation of the practical problem in the real world, but it is difficult for the traditional network optimization technique to deal with. In this paper, a genetic algorithm (GA) approach is developed to deal with this problem. Without neglecting its network topology, the proposed method adopts the Prüfer number as the tree encoding and applies the Multiple Criteria Decision Making technique and nondominated sorting technique to make the GA search give out all Pareto optimal solutions either focused on the region near the ideal point or distributed all along the Pareto frontier. Compared with the enumeration method of Pareto optimal solution, the numerical analysis shows the efficiency and effectiveness of the GA approach on the mc-MST problem.

Reviews

Required fields are marked *. Your email address will not be published.