Title :
A Parallel Genetic Algorithm for Solving the Probabilistic Minimum Spanning Tree Problem
Author :
Zhurong Wang ; Changqing Yu ; Xinhong Hei ; Bin Zhang
Author_Institution :
Sch. of Comput. Sci. & Eng., Xi´an Univ. of Technol., Xi´an, China
Abstract :
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.
Keywords :
application program interfaces; computational complexity; genetic algorithms; mathematics computing; message passing; parallel processing; trees (mathematics); MPI; NP-complete problem; PMST problem; average best solution; coarse-grained model; coarse-grained parallel genetic algorithm; expectation best solution; factorization encoding; message passing interface; probabilistic minimum spanning tree problem; repairing method; Algorithm design and analysis; Encoding; Genetic algorithms; Probabilistic logic; Program processors; Sociology; Statistics; Determinant factorization encoding; Message passing interface (MPI); Parallel genetic algorithm; Probabilistic minimum spanning tree;
Conference_Titel :
Computational Intelligence and Security (CIS), 2013 9th International Conference on
Conference_Location :
Leshan
Print_ISBN :
978-1-4799-2548-3
DOI :
10.1109/CIS.2013.20