A Parallel Algorithm For Solving MCP On OpenCL

Maximum Clique Problem(MCP)is one of classical combinatorial optimization problems in graph theory.Many practical problems from life can be formulated to it.Therefore,studying the MCP is full of significance both in theory and in practice.However,the MCP is NP-complete problem and there is no effective algorithm to solve it in polynomial time.In recent years,many scholars have proposed various algorithms for solving MCP.Exact algorithm is effective for solving small instances,but when the scale of the graph becomes larger,it would cost much time to find MC,and moreover it cannot find MC in reasonable time.Apart from exact algorithms,some approximation algorithms are also proposed for MCP,such as genetic algorithm(GA).Standard genetic algorithms have problems of low searching efficiency and premature convergence.Based on studying genetic algorithms solving for MCP,we made some improvements of standard GA.However,because of the exponential size of the solution space,especially when the s cale of problems become larger,we cannot find the solution in satisfactory time.Recently,the high performance computing technology based on OpenCL has become hot.In this paper,we combine genetic algorithm with OpenCL and propose a parallel genetic algorithm based on OpenCL for solving MCP.By using parallel genetic operators including selection,crossover,mutation,etc,it improves the efficiency of our algorithm greatly.The experimental results indicate that the algorithm proposed in this paper is more competitive with computation time and graph instances size than traditional CPU implementation.