A Genetic Approach for Maximum Independent Set Problems

Akio SAKAMOTO  Xingzhao LIU  Takashi SHIMAMOTO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.3   pp.551-556
Publication Date: 1997/03/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems)
genetic Algorithm,  maximum independent set problem,  maximum clique problem,  heuristic algorithms,  

Full Text: PDF>>
Buy this Article

Genetic algorithms have been shown to be very useful in a variety of search and optimization problems. In this paper we present a genetic algorithm for maximum independent set problem. We adopt a permutation encoding with a greedy decoding to solve the problem. The DIMACS benchmark graphs are used to test our algorithm. For most graphs solutions found by our algorithm are optimal, and there are also a few exceptions that solutions found by the algorithm are almost as large as maximum clique sizes. We also compare our algorithm with a hybrid genetic algorithm, called GMCA, and one of the best existing maximum clique algorithms, called CBH. The exiperimental results show that our algorithm outperformed two of the best approaches by GMCA and CBH in final solutions.