# 2 Constraint Handling

Motivation and the trouble

What is a constrained problem?

Evolutionary constraint handling

A selection of related work

Conclusions, observations, and suggestions

# 3 Motivation

Practical relevance:

a great deal of practical problems are constrained.

Theoretical challenge:

a great deal of intractable problems (NP-hard etc.) are constrained.

Why try with evolutionary algorithms?

EAs show a good ratio of (implementation) effort/performance.

EAs are acknowledged as good solvers for tough problems.

# 4 What is a constrained problem?

Consider the Traveling Salesman Problem for n cities, C = {city 1 , … , city n }

If we define the search space as

S = C n , then we need a constraint requiring uniqueness of each city in an element of S

S = {permutations of C}, then we need no additional constraint.

The notion ‘constrained problem’ depends on what we take as search space

# 5 What is constrained search? or What is free search?

• Even in the space S = {permutations of C} we cannot perform free search
• Free search : standard mutation and crossover preserve membership of S, i.e., mut(x)  S and cross(x,y)  S
• The notion ‘free search’ depends on what we take as standard mutation and crossover.
• mut is `_` `_` standard mutation if for all x 1 , … , x n , if
• mut(x 1 , … , x n ) =  x’ 1 , … , x’ n , then x’ i  domain(i)
• cross is `_` `_` standard crossover if for all x 1 , … , x n , y 1 , … , y n , if
• cross(x 1 , … , x n , y 1 , … , y n ) = z 1 , … , z n , then
• z i  {x i , y i } discrete case
• z i  [x i , y i ] continuous case

# 6 Free search space

Free search space: S = D 1  …  D n

one assumption on D i : if it is continuous, it is convex

the restriction s i  D i is not a constraint, it is the definition of the domain of the i-th variable

membership of S is coordinate-wise, hence a free search space allows free search

A problem can be defined through

an objective function (to be optimized)

constraints (to be satisfied)

# 7 Types of problems

Objective Function
Constraints Yes No
Yes Constrained optimization problem Constraint satisfaction problem
No Free optimization problem No Problem

# 8 Free Optimization Problems

Free Optimization Problem: S, f, •

S is a free search space

f is a (real valued) objective function on S

Solution of an FOP: s  S such that f (s) is optimal in S

FOPs are ‘easy’, in the sense that:

it’s ‘only’ optimizing, no constraints and

EAs have a basic instinct for optimization

Ackley function

# 10 Constraint Satisfaction Problems (1/2)

Constraint Satisfaction Problem: S, •, Φ

S is a free search space

Φ is a formula (Boolean function on S)

Φ is the feasibility condition

S Φ = {s  S | Φ(s) = true} is the feasible search space

Solution of a CSP:

s  S such that Φ(s) = true (s is feasible)

Φ is typically given by a set (conjunction) of constraints

c i = c i (x j1 , … , x jni ), where n i is the arity of c i

c i  D j1  …  D jni `_` `_` is also a common notation `_` `_`

FACTS :

The general CSP is NP-complete

Every CSP is equivalent with a binary CSP, where all n i  2

Constraint density and constraint tightness are parameters that determine how hard an instance is

# 11 CSP: Example

Graph 3-coloring problem:

G = (N, E), E  N  N , |N| = n

S = D n , D = {1, 2, 3}

Φ(s) = Λ e E c e (s), where

c e (s) = true iff e = (k, l) and s k  s l

# 12 Constrained optimization problems

Constrained Optimization Problem: S, f, Φ

S is a free search space

f is a (real valued) objective function on S

Φ is a formula (Boolean function on S)

Solution of a COP:

s  S Φ such that f(s) is optimal in S Φ

# 13 COP: Example

Travelling salesman problem

S = C n , C = {city 1 , … , city n }

Φ(s) = true  i, j  {1, … , n} i  j  s i  s j

f(s) =

# 14 Solving CSPs by EAs (1)

EAs need an f to optimize  S, •, Φ must be transformed first to a

FOP: S, •, Φ  S, f, • or

COP: S, •, Φ  S, f, Ψ 

The transformation must be (semi-)equivalent, i.e. at least:

1. f (s) is optimal in S  Φ(s)

2. ψ (s) and f (s) is optimal in S  Φ(s)

# 15 Constraint handling

‘Constraint handling’ interpreted as ‘constraint transformation’

Case 1: CSP  FOP

All constraints are handled indirectly , i.e., Φ is transformed into f and later they are solved by `simply’ optimizing in S, f, •

Case 2: CSP  COP

Some constraints handled indirectly (those transformed into f)

Some constraints handled directly (those remaining constraints in ψ)

In the latter case we also have ‘constraint handling’ in the sense of ‘treated during the evolutionary search’

# 16 Indirect constraint handling: Introduction (1/3)

Constraint handling has two meanings:

1. how to transform the constraints in Φ into f, respectively f, ψ before applying an EA

2. how to enforce the constraints in S, f, Φ while running an EA

Case 1: constraint handling only in the 1st sense (pure penalty approach)

Case 2: constraint handling in both senses

In Case 2 the question

‘How to solve CSPs by EAs’

transforms to

‘How to solve COPs by EAs’

Note: always needed

for all constraints in Case 1

for some constraints in Case 2

Some general options

1. penalty for violated constraints

2. penalty for wrongly instantiated variables

3. estimating distance/cost to feasible solution

Notation:

c i constraints, i = {1, … , m}

v j variables, j = {1, … , n}

C j is the set of constraints involving variable v j

Sc = {z  D j1  …  D jk `_` `_` | c(z) = true} is the projection of c, if v j1 , … , v jk are the var’s of c

d(s, S c ) := min{d(s, z) | z  2 S c } is the distance of s  S from S c (s is projected too)

# 17 Indirect constraint handling (3)

Observe that for each option:

# 19 Indirect constraint handling: pro’s & con’s

PRO’s of indirect constraint handling:

conceptually simple, transparent

problem independent

reduces problem to ‘simple’ optimization

allows user to tune on his/her preferences by weights

allows EA to tune fitness function by modifying weights during the search

CON’s of indirect constraint handling:

loss of info by packing everything in a single number

said not to work well for sparse problems

# 20 Direct constraint handling (1/2)

Options:

eliminating infeasible candidates (very inefficient, hardly practicable)

repairing infeasible candidates

preserving feasibility by special operators

(requires feasible initial population

decoding, i.e. transforming the search space

(allows usual representation and operators)

PRO’s of direct constraint handling:

it works well (except eliminating)

CON’s of direct constraint handling:

problem specific

no guidelines