Feasible encodings for GA solutions of constrained minimal spanning tree problems
William Edelson, Michael L. Gargano · 2000
We solve by a genetic algorithm (GA), three NP-hard, constrained, minimal spanning tree (MST) problems on a complete graph using a novel encoding for the genotype which ensures feasibility of the search space when performing crossover and mutation and when initializing the population. By employing a feasible encoding the standard, mainstream, GA paradigm is preserved allowing us to capture the full benefits of the genetic operators. We do not need to resort to the elaborate and time consuming detection and repair operations proposed by other researchers to handle non feasible population members. The feasible genotype for the degree constrained or leaf constrained MST problem is a permutation code which is suitably mapped into a Prufer code (phenotype) whose spanning tree obeys the desired tree constraints. This methodology can provide a framework for the development of feasible GA encodings for a wide class of other constrained minimal spanning tree problems on a complete graph. The effectiveness and competitive performance of this methodology is demonstrated by convergence to a global optimum for various degree constrained MST problems including a benchmark problem often cited in the literature.