Research Of Parallel Discrete Particle Swarm Optimization Algorithm For Solving Graph Vertex Coloring Based On CUDA

The graph vertex coloring problem is a hot topic of discrete mathematics and graph theory,and it is also a classic NP-complete problem.There is still no precise algorithm to solve the problem in polynomial time.However,the graph vertex coloring algorithm has important applications in many fields such as frequency allocation,shortest path,and medical image encryption and so on.Therefore,the algorithm of graph coloring problem has important theoretical and practical value.In recent years,cluster-based particle swarm optimization algorithm has attracted the attention of many scholars.Particle swarm optimization algorithm has been widely used in many research fields with strong global optimization ability.In this paper,a particle swarm optimization algorithm is applied to solve the graph vertex coloring problem,and a discrete particle swarm optimization algorithm is proposed.The algorithm improves the traditional particle swarm algorithm which can only solve the continuous problem.Apart from redefining the position,velocity,and updating method of particle,it also redefine the addition and subtraction in the particle swarm algorithm as well as multiplication and other operations in the solution space of the discrete problem.The algorithm is validated by 64 examples of American Institute of Discrete Mathematics and Theoretical Computing and Research(DIMACS).Compared with other heuristic algorithms such as HPGA,the validity of the algorithm has been proved,and the minimum number of chromatic numbers of DIMACS can be efficiently searched.In addition,since the vertex coloring problem of the graph has exponential solution space,if the graph G has N vertices,the vertex is colored with K colors,and the solution space of the color scheme is KN.Therefore,when solving the problem of large scale N,we must improve the speed of the particle swarm algorithm to efficiently search the exponential solution space.In this paper,CUDA is used to accelerate the algorithm based on GPU-based parallel computing platform.CUDA-based parallel discrete particle swarm optimization algorithm is proposed.The algorithm achieves the parallel particle population initialization,particle velocity,position update,fitness value calculation,and parallel reduction to solve the global optimal particles,which greatly improves the efficiency of the algorithm.In particular,compared with the serial comparison method,which has O(n)time complexity,the time complexity of logarithmic stepwise alternating method is only O(log n)when reducing to gain the global optimal particles.The experimental results show that compared with other algorithms,the time required to find the minimum coloring scheme of the known legend is less.Compared with the CPU algorithm,the CUDA parallel algorithm reduces the computation time to a large extent.Therefore,CUDA-based parallel discrete particle swarm optimization algorithm has a great potential in solving larger scale.