Dissertation > Excellent graduate degree dissertation topics show

MPI-based parallel genetic algorithm for 0-1 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 large-scale combinatorial optimization problems. However, genetic algorithm in solving large-scale 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 sub-problem, 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 MPI-based parallel genetic algorithm to solve 0-1 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 coarse-grained 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 Windows-based operating system minicomputer group system; then described in detail parallel genetic algorithm and MPI-based parallel genetic algorithm programming, the use of coarse-grained parallel genetic algorithm for the 0-1 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 coarse-grained 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

  1. Research on Combinatorial Optimization Problem Based on DNA Self-Assemble,TP399-C8
  2. Research and Design of a High-Performance Scalable Public Key Cryptographic Coprocessor,TN918.1
  3. Research on Video Compression Algorithm Based on Multi-core Computing Platform,TN919.81
  4. Research of Finite Element Method on GPU,O241.82
  5. Numerical Simulation of Radiofrequency Waves in Magnetized Plasma,TL612
  6. The Algorithm Researches of Novel Wide Area Backup Protection for Power Grid,TM774
  7. The Research on Online Adaptive Settings,TM77
  8. Overload virtual machine performance improvement under MPI communication method,TP302
  9. Fault Tolerance for MapReduce in the Cloud Environment,TP302.8
  10. High dynamic SINS navigation solution algorithm and parallelization of,TN966
  11. Image retrieval method and system for parallel computing,TP391.3
  12. GPU-accelerated particle filter PET image reconstruction algorithm,TP391.41
  13. GPU-based parallel search algorithm for time series,TP391.41
  14. CPU-based inverse algorithm source strength,TP18
  15. Parallel computing for data-intensive reconfigurable linear array processor architecture design,TP332
  16. Large-scale approximation paragraph fingerprint - based page detection algorithm research,TP393.092
  17. Parallel and Dual-systems Cooperative Co-evolutionary Differential Evolution Algorithms and Their Application,TP18
  18. Research on Fault-Tolerant Parallel Skyline Query Technology in Cloud Computing Environment,TP311.13
  19. A Study on Diagonal Computing Model for GPGPU Platform,TP391.41
  20. Multi-objective artificial fireflies swarm optimization algorithm and its application,TP301.6
  21. 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