Research On Parallel Of Modern Optimization Algorithms Using CUDA Platform

Modern optimization algorithm is a new global optimization algorithm in the rise of the1980s, the main purpose is to solve NP-hard problem. With the practical issues of diversityand discrete, the solving time of combinatorial optimization problem, especially NP-hardproblem, will exponentially growing with problem size increases. Modern optimizationalgorithms are built on the basis of objective existence of natural phenomena, throughbiological evolution or biological communities to emulate a smart way to solve complexpractical problems.The arrival of NVIDIA CUDA technology, the GPU general computing applications hasbeen fully expanded, which attracted the interest of many researchers. CUDAtakes advantageof computational ability of GPU to increase the performance of calculating. The CUDAplatform provides more favorable conditions for developers to make full use of the powerfulcomputation ability of GPU, and greatly simplifies the programming of GPU.Gravitation Field Algorithm (GFA) is a simple and very effective heuristic searchalgorithm. This algorithm has obvious advantages in multimodal function optimizationproblems compared with SA and GA. However, when higher accuracy requirements of theglobal optimal value, we need a lot of initial dusts involved in computing, which causes a lowefficiency of the algorithm. In this paper, through the study of GFA and CUDA platform,taking advantage of the powerful computing ability of GPU and CUDA parallel computingarchitecture, we propose Parallel Gravitation Field Algorithm (PGFA) based on the islandmodel. In PGFA dust points uniformly distributed in a plurality of islands, and we achieved aparallel movement and evolution of dusts on each island. The proposed method has beencompared with GFA in the unimodal functions and multimodal functions. The experimentalresults show that the proposed PGFA can not only get an effective speedup, but also higheraccuracy than the GFA.Gravitational Search Algorithm (GSA) is an effective heuristic search algorithm whichbased on the law of gravity and mass interactions. Compared with GA and PSO on thefunction optimization problem GSA has obvious advantages. GSA is a random searchalgorithm based on small sample, so it can lead to the optimal solution easily to fall into local optimal solution and premature convergence in the search process. In this paper, we proposeParallel GSA(PGSA) based on three-layer islands model, and the algorithm is parallelized onthe CUDA platform. At first, in PGSA a large number of random samples uniformlydistributed on the island in the first layer, after a certain number of iterations, the local optimalsolution vector as a sample in the next layer of islands. After training a certain number ofiterations in the second layer islands, similarly, we get the optimal solution vector as the lasttraining samples to train again and get the final global optimal solution. We compare theperformance of GSA and PGSA on unimodal functions and multimodal functions.Experimental results show that, PGSA can not only get a good speedup, but also not easilyfall into local optimal solution.Future work: in the gravitation field algorithm, the decomposition operator will directlyaffect the efficiency and results of the implementation the algorithm, so we need to study thedesign of new decomposition operator, which can be combined with parallel gravitation fieldalgorithm to improve search efficiency. PGFA and PGSAget a better accelerate effect and theconvergence rate in benchmark function, so in the future we consider two algorithms areapplied to practical problems.