Dissertation > Excellent graduate degree dissertation topics show
MPIbased parallel genetic algorithm for 01 knapsack problem Applied Research
Author: WuYun
Tutor: JiangZuo
School: Kunming University of Science and Technology
Course: System Analysis and Integration
Keywords: Parallel Computing MPI Parallel Genetic Algorithm Knapsack problem
CLC: TP18
Type: Master's thesis
Year: 2011
Downloads: 104
Quote: 0
Read: Download Dissertation
Abstract
Genetic algorithms as a global optimization based on natural selection and the search algorithm, with its simple and universal, implicit parallelism, which is widely used in various fields of science in engineering. Genetic algorithm is intelligent optimization algorithms compute one of the most important, has been successfully used in many largescale combinatorial optimization problems. However, genetic algorithm in solving largescale problems, although in theory be able to get global optimal solution, but in practice there exists convergence speed, so that can not get better results. Knapsack problem is a common area in operations research typical combinatorial optimization problem, but also other complex combinatorial optimization problems with a subproblem, many of the problems in life can be transformed into a knapsack problem to solve, so the research has important applications knapsack problem value. To solve the above problems, read a lot of literature, based on the proposed MPIbased parallel genetic algorithm to solve 01 knapsack problem. The algorithm can be selected resource knapsack problem and genetic algorithm parallelism inherent parallelism combining, which greatly improves the efficiency of search and solution quality. This article will use traditional genetic algorithms and coarsegrained parallel genetic algorithm to solve knapsack problem, the final comparative analysis of the two algorithms, the main contents are as follows: First, the introduction of the genetic algorithm knapsack problem in the research status, genetic algorithm basic structure and mathematical theory; then expounded parallel computer architecture, parallel programming theory, parallel algorithms and performance analysis, and MPI parallel programming knowledge, and use MPICH build a Windowsbased operating system minicomputer group system; then described in detail parallel genetic algorithm and MPIbased parallel genetic algorithm programming, the use of coarsegrained parallel genetic algorithm for the 01 knapsack problem analysis program design and implementation. This paper respectively 20, 50 backpack items for testing. Mainly studied the parallel genetic algorithm and traditional genetic algorithm in the number of different machines, processes, and maximum number of hereditary algebra conditions, the total value of goods loaded, fitness, running time were analyzed and compared. Experimental results show that the coarsegrained parallel genetic algorithm has higher speed ratio, which improves the speed of operation, reduces the average overhead time, changed the traditional genetic algorithm operating mechanism to increase the diversity of population, to avoid the premature convergence phenomenon .

Related Dissertations
 Research on Combinatorial Optimization Problem Based on DNA SelfAssemble,TP399C8
 Research and Design of a HighPerformance Scalable Public Key Cryptographic Coprocessor,TN918.1
 Research on Video Compression Algorithm Based on Multicore Computing Platform,TN919.81
 Research of Finite Element Method on GPU,O241.82
 Numerical Simulation of Radiofrequency Waves in Magnetized Plasma,TL612
 The Algorithm Researches of Novel Wide Area Backup Protection for Power Grid,TM774
 The Research on Online Adaptive Settings,TM77
 Overload virtual machine performance improvement under MPI communication method,TP302
 Fault Tolerance for MapReduce in the Cloud Environment,TP302.8
 High dynamic SINS navigation solution algorithm and parallelization of,TN966
 Image retrieval method and system for parallel computing,TP391.3
 GPUaccelerated particle filter PET image reconstruction algorithm,TP391.41
 GPUbased parallel search algorithm for time series,TP391.41
 CPUbased inverse algorithm source strength,TP18
 Parallel computing for dataintensive reconfigurable linear array processor architecture design,TP332
 Largescale approximation paragraph fingerprint  based page detection algorithm research,TP393.092
 Parallel and Dualsystems Cooperative Coevolutionary Differential Evolution Algorithms and Their Application,TP18
 Research on FaultTolerant Parallel Skyline Query Technology in Cloud Computing Environment,TP311.13
 A Study on Diagonal Computing Model for GPGPU Platform,TP391.41
 Multiobjective artificial fireflies swarm optimization algorithm and its application,TP301.6
 Algorithm Study on Accelerate CV Image Segmentation and Exterior Industrial Image Reconstruction by CUDA,TP391.41
CLC: > Industrial Technology > Automation technology,computer technology > Automated basic theory > Artificial intelligence theory
© 2012 www.DissertationTopic.Net Mobile
