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