The generalized approaches of genetic algorithms on constrained minimum spanning tree problems
Gengui Zhou, Yi-hua Zhu, Xiaobin Weng, Feng Ye · 2004
This paper explores the generalization of problem-solving by genetic algorithms (GAs) for a class of constrained minimum spanning tree (MST) problems. These constrained MST problems are quite different from each other in constraints and usually NP-hard but of high practical importance. The paper emphasizes that it is possible for GAs to generalize the problem-solving as long as the problems at hand can be generalized in data structure of solutions. The proposed method adopts only one solution encoding and one algorithm to deal with three constrained MST problems. Numerical experiments show that the proposed GAs approach can respectively compete with the existing heuristic algorithms on these constrained MST problems.