A Genetic Approach for Maximum Independent Set Problems (Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems)

概要

論文の詳細を見る
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 experimental results show that our algorithm outperformed two of the best approaches by GMCA and CBH in final solutions.
社団法人電子情報通信学会の論文
1997-03-25