IEICE TRANSACTIONS on Fundamentals
A Genetic Approach for Maximum Independent Set Problems
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.3 pp.551-556
- Publication Date
- 1997/03/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Akio SAKAMOTO, Xingzhao LIU, Takashi SHIMAMOTO, "A Genetic Approach for Maximum Independent Set Problems" in IEICE TRANSACTIONS on Fundamentals,
vol. E80-A, no. 3, pp. 551-556, March 1997, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_3_551/_p
Copy
@ARTICLE{e80-a_3_551,
author={Akio SAKAMOTO, Xingzhao LIU, Takashi SHIMAMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Genetic Approach for Maximum Independent Set Problems},
year={1997},
volume={E80-A},
number={3},
pages={551-556},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={March},}
Copy
TY - JOUR
TI - A Genetic Approach for Maximum Independent Set Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 551
EP - 556
AU - Akio SAKAMOTO
AU - Xingzhao LIU
AU - Takashi SHIMAMOTO
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 1997
AB - 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.
ER -
English
