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 coars...
详细信息
ISBN:
(纸本)9781479925483
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 coarsegrained 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.
暂无评论