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.