Hybrid genetic algorithm for the maximum clique problem combining sharing and migration
Abstract
The Maximum Clique Problem (MCP) has been studied for decades and is well known in graph theory as a problem that is difficult as it as it is known to be NP-complete. The MCP has a vast domain of application such as finance, biochemistry, bioinformatics, and many more. Many niching methods have been successfully applied in Genetic Algorithms (GA) to diversify the population and avoid getting trapped within local optima. In this paper, we propose an approach using the Sharing method and a Hybrid Genetic Algorithm (HGA) for the maximum clique problem. We also propose a non-evolutionary approach using a migration mechanism to boost the current HGA. Copyright © 2007, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
