Genetic algorithm approach on multi-criteria minimum spanning tree problem |
| |
Institution: | 1. Departamento de Física, Universidade Estadual da Paraíba, 58429-500, Campina Grande - PB, Brasil;2. Departamento de Física, Universidade Federal de Campina Grande, 58429-900, Campina Grande - PB, Brasil;3. Departamento de Física, Universidade Federal do Rio Grande do Norte, 59078-970, Natal - RN, Brasil |
| |
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 (MCDM) 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|