2001 | OriginalPaper | Buchkapitel
Evolutionary Algorithms and Constraint Satisfaction: Definitions, Survey, Methodology, and Research Directions
verfasst von : A. E. Eiben
Erschienen in: Theoretical Aspects of Evolutionary Computing
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this tutorial we consider the issue of constraint handling by evolutionary algorithms (EA). We start this study with a categorization of constrained problems and observe that constraint handling is not straightforward in an EA. Namely, the search operators mutation and recombination are ‘blind’ to constraints. Hence, there is no guarantee that if the parents satisfy some constraints the offspring will satisfy them as well. This suggests that the presence of constraints in a problem makes EAs intrinsically unsuited to solve this problem. This should especially hold if there are no objectives but only constraints in the original problem specification — the category of constraint satisfaction problems. A survey of related literature, however, discloses that there are quite a few successful attempts at evolutionary constraint satisfaction. Based on this survey we identify a number of common features in these approaches and arrive at the conclusion that the presence of constraints is not harmful, but rather helpful in that it provides extra information that EAs can utilize. The tutorial is concluded by considering a number of key questions on research methodology and some promising future research directions.