A Modified Genetic Algorithm for Maximum Independent Set Problems

摘要

A modified genetic algorithm is proposed for maximum independent set problems. A specially designed mutation operator is adopted to search the solution space more efficiently, where adjacent relation of a graph is integrated. The DIMACS benchmark graphs are used to test our algorithm, and the results show that the algorithm outperforms our previous version. Moreover two new low bounds are found for graphs in DIMACS.