International Journal of Computational Intelligence Research (IJCIR)

Volume 2, Number 4 (2006)


A hybrid evolutionary approach to maximum weight clique problem

Alok Singh, Ashok Kumar Gupta 
J. K. Institute of Applied Physics and Technology, Faculty of Science, University of Allahabad, Allahabad 211002, India


In this paper we propose a hybrid evolutionary approach combining steady-state genetic algorithm and a greedy heuristic for the maximum weight clique problem. The genetic algorithm generates cliques that are then extended into maximum weight clique by the heuristic. Tests on a variety of benchmark problem instances demonstrate the effectiveness of our approach.

Combinatorial optimization, greedy heuristic, maximum weight clique, steady-state genetic algorithm.