13. Constraint Handling

In this chapter we return to an issue first introduced in the first chapter, namely that some problems have constraints associated with them. This means that not all possible combinations of variable values represent valid solutions to the problem at hand, and we examine how this impacts on the design of an evolutionary algorithm.

This issue has great practical relevance because many real-world problems areconstrained. It is also theoretically challenging, since
many intractable problems (NP-hard, NP-complete, etc.) are
constrained. Unfortunately, constraint handling is not
straightforward in an EA, because the variation operators (mutation
and recombination) are typically `blind’ to constraints. This means that even if the parents satisfy some
constraints, there is no guarantee their offspring will. This chapter reviews the most commonly used techniques for constraint handling, identifies a number of
common features, and provides some guidance for the algorithm designer.

Contents:

13.1  Two Main Types of Constraint Handling ……………….203

13.2  Approaches to Handling Constraints …………………..204

13.2.1 Penalty Functions ……………………………206

13.2.2 Repair Functions …………………………….208

13.2.3 Restricting Search to the Feasible Region………….209

13.2.4 Decoder Functions……………………………210

13.3  Example Application: Graph Three-Colouring……………211

Suggested Reading

Exercises

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

The on-line accompaniment to the book Introduction to Evolutionary Computing