A Parallel Genetic Algorithm for Solving the Probabilistic Minimum Spanning Tree Problem

The probabilistic minimum spanning tree (PMST) problem is NP-complete and is hard to solve. However, it has important theoretical significance and wide application prospect. A parallel genetic algorithm based on coarse-grained model is proposed to solve PMST problem in this paper. Firstly, we discuss several problems of determinant factorization encoding, and develop repairing method for illegal individuals. Secondly, a coarse-grained parallel genetic algorithm, which combines message passing interface (MPI) and genetic algorithm, is designed to solve probabilistic minimum spanning tree problems. Finally, the proposed algorithm is used to test several probabilistic minimum spanning tree problems which are generated by the method introduced in the literature. The statistical data of the test results show that the expectation best solution and average best solution obtained by the proposed algorithm are better than those provided in the literature.