An evolutionary heuristic for the maximum independent set problem

The results obtained from the application of a genetic algorithm, GENEsYs, to the NP-complete maximum independent set problem are reported. In contrast to many other genetic algorithm-based approaches that use domain-specific knowledge, the approach presented in this paper relies on a graded penalty term component of the fitness function to penalize infeasible solutions. The method is applied to several large problem instances of the maximum independent set problem. The results clearly indicate that genetic algorithms can be successfully used as heuristics for finding good approximative solutions for this highly constrained optimization problem