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