Parallel hybrid genetic algorithm for maximum clique problem on OpenCL

作者：Li Li; Zhang Kai; Yang Siman; He Juanjuan

来源：Journal of Computational and Theoretical Nanoscience, 2016, 13(6): 3595-3600.

DOI：10.1166/jctn.2016.5188

• Adjacent vertices
• Comparison result
• Fitness evaluations
• Local optimization strategies
• Maximum clique problems
• OpenCL
• Parallel hybrid-genetic algorithms

The maximum clique problem is to find the maximum sized clique of pairwise adjacent vertices in a given graph, which is a NP-Complete problem. In this paper, an effective parallel hybrid genetic algorithm is proposed, which consists of genetic algorithm and a local optimization strategy for solving maximum clique problem. In this algorithm, selection, crossover, mutation, fitness evaluation and replacement operators are implemented parallel on OpenCL. In addition, we have tested our algorithm by using a set of benchmark instances from the DIMACS graphs. The comparison results shows that the implementation on GPU provide better performance that CPU, even when the benchmark graphs become more large and complicate.

• 出版日期2016
• 单位武汉科技大学