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

Abstract
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.

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

______________________________________________________________________________________