We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On Evolutionary Algorithms for Maximum Independent Set Problem.
- Authors
Javidi, Mohammad M.; Mehrabi, Saeed
- Abstract
Given an undirected graph G = (V, E), the Maximum Independent Set Problem (MISP) consists of finding the largest subset of V, say V, such that none of the vertices in V share an edge. MISP is known to be M-complete. In this paper, we first review some previous and research and then introduce our algorithm which is based on Genetic Algorithms (GAs) with a heuristic independent crossover especially for MISP. Finally, we compare our algorithm with GA software package results and also test on a variety of benchmarks. As the experimental results show, our algorithm not only outperforms one of the best existing algorithms but it also demonstrates that with an appropriate mutation rate settings, it gives far better performance than the other classical meta heuristic algorithms.
- Subjects
COMBINATORIAL optimization; COMPUTATIONAL complexity; BENCHMARKING (Management); GRAPH theory; APPROXIMATION theory; HEURISTIC programming; HEURISTIC algorithms; COMPUTER software; STOCHASTIC analysis
- Publication
Journal of Artificial Intelligence: Theory & Application, 2010, Vol 1, Issue 2, p54
- ISSN
1737-9334
- Publication type
Article