Dissertation > Excellent graduate degree dissertation topics show

A Cross Entropy Algorithm for Maximum Clique Problem and on It’s Parallelization Study

Author: BaiZhanHua
Tutor: LvQiang
School: Suzhou University
Course: Applied Computer Technology
Keywords: Maximum Clique Problem Cross entropy algorithm Heuristic algorithm Parallel computing OpenMP MPI
CLC: TP301.6
Type: Master's thesis
Year: 2007
Downloads: 190
Quote: 1
Read: Download Dissertation


The maximum clique problem is a classic combinatorial optimization problem , has important value in theoretical research and practical application , the latest research progress of the maximum clique problem Analysis Summary . Cross Entropy algorithm is the Rubinstein initiated a new problem-solving method , characteristics of the cross- entropy algorithm is used to generate a good mathematical framework for updating the learning strategies , the main idea is to use the Kullback-Leibler cross entropy , importance sampling well Boltzmann distribution , the optimal solution combinatorial optimization problem into a simple stochastic optimization problem solving auxiliary . In order to study a new problem-solving strategies , design and implementation of cross- entropy algorithm for solving the largest group to solve . Use of the fitness terrain analysis methods, the analysis of the actual operation of the algorithm , and pseudo-random mechanism with local disturbances improvement strategies based on the experimental results . Cross entropy algorithm simulation based on the large amount of data , in order to speed up the algorithm runs , the article also designed and implemented based on OpenMP and MPI parallel algorithms . Based on OpenMP parallel algorithm for shared memory platform . MPI-based parallel algorithms for distributed architecture design of a parallel strategy based on leadership behavior . Finally, of the 80 instances in DIMACS have done experiments, another 27 instances of the selected best algorithm to do the comparison , the experimental results show that the proposed algorithm for the problem instance applicable , applications and research value. The speedup of parallel algorithms and efficient experimental results show that this paper two parallel algorithms with good acceleration performance .

Related Dissertations

  1. Research of Finite Element Method on GPU,O241.82
  2. Overload virtual machine performance improvement under MPI communication method,TP302
  3. Paralleling Genetic Annealing Algorithm with OpenMP,TP301.6
  4. FCM combines multi-resolution image cone multicore parallel image segmentation algorithm,TP391.41
  5. Application of Parallel FDTD and MPSTD Algorithm in EM Scattering,O441.4
  6. Tension Control System and Application of a Copper Slitting Line,TG333.21
  7. Study on Clinical Applications of Gated Myocardial Perfusion Imaging (G-MPI) Before and After Coronary Artery Bypass Grafting,R654.2
  8. BSD protocol stack performance analysis and optimization of parallel,TP393.04
  9. Study on Automatic Registration Algorithm and Parallel Implementation for HJ-satellite Optical Imagery,TP391.41
  10. Software optimization techniques in software development projects,TP311.52
  11. The Research of Three-dimensional FDTD Parallel Algorithm Based on MPI and OpenMP,TN011
  12. Research and Improvement on Genetic Algorithm for Solving TSP,TP18
  13. Data Similarity Analysis and Optimization Technology for MPI Programs,TP311.11
  14. The Applied Research of Cluster Based on Linux,TP338
  15. The Model and Correctness Verification of Parallal Programs in Embedded Multi-Core Environment,TP368.1
  16. H.264/AVC Based Video Encoder Design and Optimization,TN762
  17. The Research and Realization of the Partitioning Strategy of Vector Spatial Data in Parallel Computing Environment,P208
  18. The Research of the High-Speed Parallel Wavelet and Its Applications in Power System,TP338
  19. Research and Implementation of a multi - texture image segmentation algorithm in parallel,TP391.41
  20. Study and Application of OpenMP Parallel Programming Model and Optimization Method of Performance,TP311.11
  21. Research of Multi-core Program Optimization Based on Task Parallel Strategies,TP332

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Algorithm Theory
© 2012 www.DissertationTopic.Net  Mobile