Mpi-based Parallel Genetic Algorithm 0-1 Knapsack Problem

Genetic algorithm is a search method, which is based on natural selection and global optimization. It is widely used in various fields of engineering science as its special properties, including simplicity, universality, implicit parallelism, etc. As one of the most important algorithms in intelligent optimization algorithm, genetic algorithm has been successfully used in many massive combinatorial optimization problems. The global optimal solution in theory can be gotten, but there exists a convergence rate problem in practical applications. Consequently, the genetic algorithm in solving massive problems can not get better results.Knapsack Problem is a typical combinatorial optimization problem in operational research field and a sub-problem of other complex combinatorial optimization problems. Lots of problems can be converted to Knapsack Problem to solve in daily life. Therefore, researching Knapsack Problem has important value in application.For the above problems, the paper presents the parallel genetic algorithm based on Message Passing Interface to solve the 0-1 knapsack problem after reading the extensive documents. It combines the parallelism of resource selection in Knapsack Problem and the inherent parallelism in genetic algorithm, which improves greatly the searching efficiency and the quality of solution. This article will use the traditional genetic algorithms and coarse-grained parallel genetic algorithms to solve 0-1 knapsack problem. Finally, comparison and analysis of two algorithms is achieved, main contents are as follows:Firstly, the development of domestic and foreign in the genetic algorithm and knapsack problem and the basic composition and mathematical theory of genetic algorithm are introduced. Then, this paper elaborates the architecture of the parallel computer, the theory of parallel programming, parallel algorithms, performance analysis, and the knowledge of MPI parallel programming. While, a cluster system based on windows operating by using MPICH is built. Finally, this paper describes in detail the genetic algorithm and programming designed of genetic algorithm based on MPI. The analysis and realization of programming of 0-1 knapsack problem by the coarse-grained parallel genetic algorithm is executed.In this paper,20 and 50 backpack goods are tested respectively. The analysis and comparison of the parallel genetic algorithm and the traditional genetic algorithm on the total value, fitness, running time in the condition of different machines, processes and the maximum genetic algebra is carried out. Experiment results show that the coarse-grained parallel genetic algorithm has a higher speedup. It improves the operation speed, reduces the average cost of time, changes operating mechanism of the traditional genetic algorithm, increases the diversity of the species, and avoids the phenomenon of premature convergence.