For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Genetic Approach for Maximum Independent Set Problems
Akio SAKAMOTO Xingzhao LIU Takashi SHIMAMOTO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1997/03/25
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>>
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.