A NEW HYBRID GENETIC ALGORITHM FOR MAXIMUM INDEPENDENT SET PROBLEM

Saeed Mehrabi, Abbas Mehrabi, Ali D. Mehrabi

2009

Abstract

In recent years, Genetic Algorithms (GAs) have been frequently used for many search and optimization problems. In this paper, we use genetic algorithms for solving the NP-complete maximum independent set problem (MISP). We have developed a new heuristic independent crossover (HIX) especially for MISP, introducing a new hybrid genetic algorithm (MIS-HGA). We use a repair operator to ensure that our offsprings are valid after mutation. We compare our algorithm, MIS-GA, with an efficient existing algorithm called GENEsYs. Also, a variety of benchmarks are used to test our algorithm. As the experimental results show: 1) our algorithm outperforms GENEsYs, and, 2) applying HIX to genetic algorithms with an appropriate mutation rate, gives far better performance than the classical crossover operators.

Paper Citation

in Harvard Style

Mehrabi S., Mehrabi A. and D. Mehrabi A. (2009). A NEW HYBRID GENETIC ALGORITHM FOR MAXIMUM INDEPENDENT SET PROBLEM . In Proceedings of the 4th International Conference on Software and Data Technologies - Volume 2: ICSOFT, ISBN 978-989-674-010-8, pages 314-317. DOI: 10.5220/0002253403140317

in Bibtex Style

@conference{icsoft09,
author={Saeed Mehrabi and Abbas Mehrabi and Ali D. Mehrabi},
title={A NEW HYBRID GENETIC ALGORITHM FOR MAXIMUM INDEPENDENT SET PROBLEM},
booktitle={Proceedings of the 4th International Conference on Software and Data Technologies - Volume 2: ICSOFT,},
year={2009},
pages={314-317},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002253403140317},
isbn={978-989-674-010-8},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 4th International Conference on Software and Data Technologies - Volume 2: ICSOFT,
TI - A NEW HYBRID GENETIC ALGORITHM FOR MAXIMUM INDEPENDENT SET PROBLEM
SN - 978-989-674-010-8
AU - Mehrabi S.
AU - Mehrabi A.
AU - D. Mehrabi A.
PY - 2009
SP - 314
EP - 317
DO - 10.5220/0002253403140317