Theory and Methodology
Genetic algorithm approach on
multi-criteria minimum spanning tree problem
Gengui Zhou
1
, Mitsuo Gen
*
Department of Industrial and Systems Engineering, Ashikaga Institute of Technology, 268 Ohmae-cho, Ashikaga 326, Japan
Received 8 July 1997; accepted 24 November 1997
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 dicult for the tra-
ditional 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
ufer 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 eciency and eectiveness of the GA approach on the mc-MST problem. Ó 1999
Elsevier Science B.V. All rights reserved.
Keywords: Genetic algorithms; Minimum spanning tree; Multiple criteria decision making
1. Introduction
The Minimum Spanning Tree (MST) problem is
to ®nd a least cost spanning tree in an edge
weighted graph. This problem has been well stud-
ied and many ecient polynomial-time algorithms
have been developed by Dijkstra [6], Kruskal [13],
Prim [16] and Sollin [20]. More recently, some ex-
tended formulations of the MST problem have
received great attention due to some practical de-
mands, such as the degree-constrained MST by
Narula and Ho [15], the stochastic MST by Ishii
et al. [12], the probabilistic MST by Bertsimas [3]
and the quadratic MST by Xu [23]. As to these
extended MST problems, varieties of heuristics
including genetic algorithms (GAs) methods have
been used. The GA approaches, in particular, have
shown to be highly eective in solving the proba-
bilistic MST [1], the degree-constrained MST
[24,25] and the quadratic MST [26]. However, the
MST problem with multi-criteria has seldom re-
ceived attention in network optimization.
In the real world, there are usually such cases
that one has to consider simultaneously multi-
European Journal of Operational Research 114 (1999) 141±152
*
Corresponding author. E-mail: gen@genlab.ashitech.ac.jp
1
E-mail: zhou@genlab.ashitech.ac.jp
0377-2217/99/$ ± see front matter Ó 1999 Elsevier Science B.V. All rights reserved.
PII: S 0 3 7 7 - 2 2 1 7 ( 9 8 ) 0 0 0 1 6 - 2
剩余11页未读，继续阅读
资源评论
