Parallel Hybrid Genetic Algorithm for Maximum Clique Problem on OpenCL
Li Li, Kai Zhang, Siman Yang, Juanjuan He · Journal of Computational and Theoretical Nanoscience · 2016
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.