Motivation and the trouble

What is a constrained problem?

Evolutionary constraint handling

A selection of related work

Conclusions, observations, and suggestions

Why bother about constraints?

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.

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

- 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

- z

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)

Objective Function | ||
---|---|---|

Constraints | Yes | No |

Yes | Constrained optimization problem | Constraint satisfaction problem |

No | Free optimization problem | No Problem |

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

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

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**

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
**Φ**

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) =

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:

f (s) is optimal in S Φ(s)

ψ (s) and f (s) is optimal in S Φ(s)

‘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’

Constraint handling has two meanings:

how to

**transform**the constraints in Φ into f, respectively f, ψ**before**applying an EAhow 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

penalty for violated constraints

penalty for wrongly instantiated variables

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)

Observe that for each option:

**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

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