Optimized Crossover for the Independent Set Problem

Charu C. Aggarwal, James B. Orlin and Ray P. Tai
Additional contact information
Charu C. Aggarwal: Massachusetts Institute of Technology, Cambridge, Massachusetts
James B. Orlin: Massachusetts Institute of Technology, Cambridge, Massachusetts
Ray P. Tai: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1997, vol. 45, issue 2, 226-234

Abstract: We propose a knowledge-based crossover mechanism for genetic algorithms that exploits the structure of the solution rather than its coding. More generally, we suggest broad guidelines for constructing the knowledge-based crossover mechanisms. This technique uses an optimized crossover mechanism, in which the one of the two children is constructed in such a way as to have the best objective function value from the feasible set of children, while the other is constructed so as to maintain the diversity of the search space. We implement our approach on a classical combinatorial problem, called the independent set problem. The resulting genetic algorithm dominates all other genetic algorithms for the problem and yields one of the best heuristics for the independent set problem in terms of robustness and time performance. The primary purpose of this paper is to demonstrate the power of knowledge based mechanisms in genetic algorithms.

Keywords: programming; integer; heuristic; optimized crossover for independent set problem; networks/graphs; heuristic; optimized crossover for independent set problem (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.2.226 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:45:y:1997:i:2:p:226-234

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().