Transcript NP-COMPLETE PROBLEMS

Chapter 7
Genetic Algorithms to Constraint
Satisfaction Problems
1
Outline







What is a Genetic Algorithm?
Components of GA
How does GA work?
Constraint Handling in Gas
GA for 8-Queens Problems
GA for Exam Timetabling Problem
Memetic Algorithms
2



Genetic algorithm is a population-based search
method. Genetic algorithms are acknowledged as
good solvers for tough problems.
However, no standard GA takes constraints into
account.
This chapter describes how genetic algorithms can
be used for solving constraint satisfaction problems.
3
What is a Genetic Algorithm?

The general scheme of a GA:
begin
INITIALIZE population with random candidate solutions;
EVALUATE each candidate;
repeat
SELECT parents;
RECOMBINE pairs of parents;
MUTATE the resulting children;
EVALUATE children;
SELECT individuals for the next generation
until TERMINATION-CONDITION is satisfied
end
4
The general scheme of Genetic Algorithm
Parent selection
Parents
Initialization
Recombination
Population
Mutation
Termination
Children
Survivor selection
5
The general scheme of Genetic Algorithm
(cont.)



It’s clear that this scheme falls in the category of
generate-and-test algorithms.
The evaluation function represents a heuristic
estimation of solution quality and the search
process is driven by the variation and the selection
operator.
GA has a number of features:



GA is population-based
GA uses recombination to mix information of
candidate solutions into a new one.
GA is stochastic.
6
COMPONENTS OF GENETIC ALGORITHMS

The most important components in a GA consist of:

representation (definition of individuals)

evaluation function (or fitness function)

population

parent selection mechanism

variation operators (crossover and mutation)

survivor selection mechanism (replacement)
7
Representation





Objects forming possible solutions within original problem
context are called phenotypes, their encoding, the individuals
within the GA, are called genotypes.
The representation step specifies the mapping from the
phenotypes onto a set of genotypes.
Candidate solution, phenotype and individual are used to
denote points of the space of possible solutions. This space is
called phenotype space.
Chromosome, and individual can be used for points in the
genotye space.
Elements of a chromosome are called genes. A value of a gene
is called an allele.
8
Variation Operators

The role of variation operators is to create new
individuals from old ones. Variation operators form
the implementation of the elementary steps with the
search space.
Mutation Operator
 A unary variation operator is called mutation. It is
applied to one genotype and delivers a modified
mutant, the child or offspring of it.
 In general, mutation is supposed to cause a random
unbiased change. Mutation has a theoretical role: it
can guarantee that the space is connected.
9
Crossover Operator

A binary variation operator is called recombination or
crossover. This operator merges information from two parent
genotypes into one or two offspring genotypes.

Similarly to mutation, crossover is a stochastic operator: the
choice of what parts of each parent are combined, and the way
these parts are combined, depend on random drawings.
The principle behind crossover is simple: by mating two
individuals with different but desirable features, we can
produce an offspring which combines both of those features.

10
Parent Selection Mechanism


The role of parent selection (mating selection) is to
distinguish among individuals based on their quality
to allow the better individuals to become parents of
the next generation.
Parent selection is probabilistic.


High quality individuals get a higher chance to become
parents than those with low quality.
Low quality individuals are often given a small, but positive
chance, otherwise the whole search could become too
greedy and get stuck in a local optimum.
11
Survivor Selection Mechanism





The role of survivor selection is to distinguish among
individuals based on their quality.
In GA, the population size is constant, thus a choice has to be
made on which individuals will be allowed in the next
generation.
This decision is based on their fitness values, favoring those
with higher quality.
As opposed to parent selection which is stochastic, survivor
selection is often deterministic.
For instance, ranking the unified multiset of parents and
offspring and selecting the top segment (fitness biased), or
selection only from the offspring (age-biased).
12
Initialization and Termination Condition
Initialization
 Initialization is kept simple in most GA applications. Whether
this step is worth the extra computational effort or not is very
much depending on the application.
Termination Condition
 GA is stochastic and mostly there are no guarantees to reach
an optimum.
 Commonly-used conditions for terminations are the following:




the maximally allowed CPU times elapses
The total number of fitness evaluations reaches a given
limit
for a given period of time, the fitness improvement remains
under a threshold value
the population diversity drops under a given threshold.
13
Population

Note: Premature convergence is the well-known
effect of loosing population diversity too quickly and
getting trapped in a local optimum.

Population



The role of the population is to hold possible
solutions.
A population is a multiset of genotypes.
In almost all GA applications, the population size
is constant.
14
HOW DO GENETIC ALGORITHMS WORK ?
Initialization
 In GA, an initial population that is generated
randomly.
 Some GAs use special techniques to produce a
higher quality initial population. Such an approach is
designed to give the GA a good start and speed up
the evolutionary process.
 Example: A GA for exam timetabling problem in
which the GA works only with feasible solutions. 
The initial population must also be made up of
feasible solutions. Then GA is run to improve the
fitness of the initial population.
15
Example 3.1




In a simple exam timetabling problem, we can use a non-binary
bit string representation to represent the chromosome because
it is easy to understand and represent.
Six positions represent six exams with each position’s value as
the time slot assigned to the exam.
We can generate the population randomly to assign each exam
a timeslot.
Day
AM
PM
time1
time2
time3 time4
Day1
e1
e3
Day2
e5
e6
e2,e4
If we randomly generate six numbers 3, 8, 4, 8, 6, 7 as six
timeslots for e1-e6, then the chromosome is 3 8 4 8 6 7.
16
If the population size is 5, an initial population can be
generated randomly as follows:
Index
Chromosome
Fitness
1
384867
0.005
2
737613
0.062
3
535558
0.006
4
767722
0.020
5
174522
0.040
17
Reproduction
There are two kinds of reproduction: generational reproduction
and steady-state reproduction.
Generational Reproduction
 The whole of a population is potentially replaced at each
generation.
 The procedure is to loop N/2 times, where N is the population
size, select two chromosomes each time according to the
current selection procedure, producing two children from those
two parents, finally producing N new chromosomes.
Steady-state Reproduction
 This method selects two chromosomes, performs crossover on
them to obtain one or two children, (perhaps applies mutation
as well), and installs the result back into that population; the
least fit is destroyed.
18
Parent Selection mechanism

The selection is to return a selected parent. The chance of each
parent being selected is in some way related to its fitness.
Fitness-based selection
 The standard, original method for parent selection is Roulette
Wheel selection: each chromosome has a chance of selection
that is directly proportional to its fitness.
 The effect of this method depends on the range of fitness
values in the current population.
Example: if fitness range from 5 to 10, then the fittest
chromosome is twice as likely to be selected as a parent than
the least fit.
 If we apply fitness-based selection on the population given in
example 3.1, we select the second chromosome 7 3 7 6 1 3 as
our first parent and 1 7 4 5 2 2 as our second parent.
19
Roulette Wheel Selection
1. Calculate fitness value f(vi) for each chromosome vi
2. Find the total fitness of the population
popsize
F=
 f (v )
i
i 1
3. Calculate the probability of selection pi cho each vi
pi = f(vi)/F
4. Calculate a cumulative probability qi for each vi
i
qi =
p
j
j 1
20
5. The selection process is based on spinning the
roulette wheel pop-size times, each time we select a
single chromosome for being a parent in the
following way:


Generate a random number r from [0..1].
If r < q1 the select v1; otherwise select the i-th chromosome vi
( 2 ≤ i ≤ pop-size) such that qi-1 < r ≤ qi
21
Parent Selection mechanism
Rank-based selection
 Selection probabilities are based on a
chromosome’s relative rank or position in the
population, rather than absolute fitness.
Tournament-based selection
 The tournament selection is to choose K parents at
random and returns the fittest one of these.
22
Crossover Operator


The crossover operator is the most important in GA.
Crossover is a process yielding recombination of bit
strings via an exchange of segments between pairs
of chromosomes.
There are many kinds of crossover.



One-point crossover
Two-point crossover
Uniform crossover
23
One-point Crossover


This crossover is to randomly generate a number ( ≤ l, the
chromosome length) as the crossover position. Then, keep the
bits before the number unchanged and swap the bits after the
crossover position between the two parents.
Example: With the two parents selected above, we randomly
generate a number 2 as the crossover position:
Parent1: 7 3| 7 6 1 3
Parent2: 1 7| 4 5 2 2
Then we get two children:
Child 1 : 7 3| 4 5 2 2
Child 2 : 1 7| 7 6 1 3
24
Two-point Crossover



This crossover is similar to that of one-point crossover except
that we must select two positions and only the bits between the
two positions are swapped.
This crossover method can preserve the first and the last parts
of a chromosome and just swap the middle part.
Example: With the two parents selected above, we randomly
generate two numbers 2 and 4 as the crossover positions:
Parent1: 7 3 |7 6 |1 3
Parent2: 1 7 |4 5| 2 2
Then we get two children:
Child 1 : 7 3| 4 5| 1 3
Child 2 : 1 7| 7 6| 2 2
25
Uniform Crossover


The uniform crossover : each gene of the first parent has a 0.5
probability of swapping with the corresponding gene of the
second parent.
Example: For each position, we randomly generate a number
between 0 and 1, for example, 0.2, 0.7, 0.9, 0.4, 0.6, 0.1. If the
number generated for a given position is less than 0.5, then
child1 gets the gene from parent1, and child2 gets the gene
from parent2. Otherwise, vice versa.
Parent1: 7 *3 *7 6 *1 3
Parent2: 1 *7 *4 5 *2 2
Then we get two children:
Child 1 : 7 7* 4* 6 2* 3
Child 2 : 1 3* 7* 5 1* 2
26
Inversion



It operates on a single chromosome and inverts the
order of the elements between two randomly chosen
points on the chromosome.
While this operator was inspired by a biological
process, it requires additional overhead.
Example: Given a chromosome 3 8 4 8 6 7. If we
randomly choose two positions 2, 5 and apply the
inversion operator, then we get the new string:
3 6 8 4 8 7.
27
Mutation




Mutation has the effect of ensuring that all possible
chromosomes are reachable.
With crossover and even inversion, the search is constrained
to alleles which exist in the initial population.
The mutation operator can overcome this by simply randomly
selecting any bit position in a string and changing it.
Example: Assume that we have already used crossover to get a
new string: 7 3 4 5 1 3.
Assume the mutation rate is 0.001. For the first bit 7, we
generate randomly a number between 0 and 1. If the number is
less than the mutation rate (0.001), then the first bit 7 needs to
mutate. We generate another number between 1 and the
maximum value 8, and get a number (e.g. 2). Now the first bit
mutates to 2. We repeat the same procedure for the other bits.
In our example, if only the first bit mutates, and the rest of the
bits don’t mutate, then we’ll get a new chromosome:
234513
28
CONSTRAINT HANDLING IN GENETIC
ALGORITHMS

There are many ways to handle constraints in a GA. At the high
conceptual level we can distinguish two cases:





indirect constraint handling
direct constraint handling.
Indirect constraint handling: we deal with the problem of
satisfying constraints by incorporating them in the fitness
function f such that f optimal implies that the constraints are
satisfied, and use the power of GA to find a solution.
Direct constraint handling means that we leave the constraints
as they are and ‘adapt’ the GA to enforce them.
Direct and indirect constraint handling can be applied in
combination, i.e., in one application we can handle some
constraints directly and others indirectly.
29
Direct constraint handling



Treating constraints directly implies that violating them is not
reflected in the fitness function, thus there is no bias towards
chromosomes satisfying them. Therefore, we have to create
and maintains feasible chromosomes in the population.
The basic problem: the genetic operators are blind to
constraints, mutating one or crossing over two feasible
chromosomes can result in infeasible offspring.
Typical approaches to handle constraints directly are:




eliminating infeasible candidates
repairing infeasible candidates
preserving feasibility by special operators
decoding, i.e. transforming the search space.
30




Eliminating infeasible candidates is very inefficient, and
therefore hardly applicable.
Repairing infeasible candidates requires a repair procedure
that modifies a given chromosome such that it will not violate
constraints. This technique is thus problem dependent.
The preserving approach amounts to designing and applying
problem-specific operators that do preserve the feasibility of
parent chromosomes.  It requires the creation of a feasible
initial population, which can be NP-complete.
Decoding can simplify the problem search space and allow an
efficient genetic algorithm. Formally, decoding can be seen as
shifting to a search space that is different from the Cartesian
product of the domains of the variables in the original problem
formulation.
31
Indirect Constraint Handling
• The optimization objectives replacing the constraints are
viewed penalties for constraint violation hence to be
minimized.
• In general penalties are given for violated constraints although
some GAs allocate penalties for wrongly instantiated variables
or as the distance to a feasible solution.
• Advantages:
- generality
- reduction of the problem to ‘simple’ optimization
- possibility of embedding user preferences by means of
weights.
Disadvantages:
-
loss of information
-
does not work well with sparse problems.
32
GA FOR 8-QUEENS PROBLEM

Solution Representation
A chromosome is a permutation of the number 1,…,8 and a
given g = < i1,…, i8> denotes the board configuration where the
k-th column contains exactly one queen placed on the ik th row.
Example: The permutation g = < 1,2,3,4,5,6,7,8> represents a
board where the queens are placed along the main diagonal.
The solution space is now the set of all permutations of 1,…,8.
33
Solution Representation (cont.)

By using such chromosome, we restrict the search
to board configurations where horizontal constraint
violation (two queens on the same column) and
vertical constraint violation (two queens on the same
row) do not occur.

The representation guarantees “half” number of the
constraints and what remains to be minimized is the
number of diagonal constraint violations.
34
Crossover Operator (cut and crossfill)

Given two parents, which are two permutations, the
following mechanism will create two child
permutations.
1.
2.
3.
4.
5.
select a random position, crossover point, i  {1, …, 7}
cut both parents in two segments after this position
copy the first segment of parent1 into child1 and the
first segment of parent2 into child2
scan parent2 from left to right and fill the second
segment of child1 with values from parent2 skipping
those that already contained in it.
do the same for parent1 and child2.
35
Example of crossover
Parent1
Parent2
1 3 5| 7 6 2 4 8
2 1 8| 6 4 3 5 7
Child1:
Child2:
1 3 5| 2 8 6 4 7
2 1 8| 3 5 7 6 4
Mutation Operator
• We select two positions in a given chromosome and swaps the
values standing on those positions.
• Mutation will cause a small undirected change and crossover
creates children that inherit genetic material from both parents.
36
Parent selection and survivor selection

Parent selection (best 2 out of random 5) choosing 5
individuals randomly from the population and taking
the best two as parents that undergone crossover.
This ensures a bias towards using parents with relatively
high fitness.

Survivor selection: (replace worst) after merging the
population and offsprings, then ranks them
according to fitness and deletes the worst two.
37
Other issues
Some other parameters for the GA are as follows:





Recombination probability
100%
Mutation probability
80%
Population size
100
Initialization
random
Termination
Solution or 10000 evaluations
38
A GA for Exam Timetabling Problem



Burke et al., 1995 [1] proposed a genetic algorithm
for solving exam timetabling problem.
This algorithm combines direct representation and
heuristic crossover operators to ensure that the
most fundamental constraints are never violated.
Heuristic crossovers are used to propagate the most
desirable features of the timetable to produce good
quality solutions.
39
Solution Representation


The most logical approach is to directly encode
solutions with events matched to periods.
Figure 5.1 shows such an encoding for n events
where each gene in the chromosome represents
which period in which a particular event is to be
scheduled.
Event 1
Period
1
Event 2
Period
3
Event n-1
Period
2
Event n
Period
7
40
The Creation of an Initial Population

The random sequential graph coloring algorithm is used to
generate the starting population. It can create conflict-free
graph colorings.
For each population member:
Generate a random ordering of exams
Take each exam in turn according to that ordering:
Find the first period in which the exam may be placed without
conflict and so that the number of students does not go
above a predefined maximum.
Place the exam in that period.

This algorithm can quickly produce large populations of
random feasible exam timetables.
41
The Creation of an Initial Population (cont.)

Note: The method allows the length of the timetable
to vary.

It uses on average about twice as many periods as
the optimal amount.
Then the GA evolves new timetables, possibly
reducing the length.
This approach guarantees a feasible timetable.


42
Crossover Operators

The crossover operator should satisfy the properties of respect
and assortment given by Radcliffe.

Respect is the property that if an exam is timetabled to the
same period in both parents then it will be scheduled to that
period in the child.

Assortment is the property that the operator can generate a
child such that if Exam1 is scheduled to Period 1 in the first
parent and Exam2 is scheduled to Period 2 in the second
parent then the child may have Exam 1 in Period 1 and Exam 2
in Period 2 providing that these are compatible.
43
Crossover Operators (cont.)
The crossover operator works for the period i as
follows:
 The operator starts by looking at the first period. It
takes exams scheduled in that period (in both
parents) and then uses an algorithm to select other
exams so that none clash with those already
scheduled and the limit on the number of spaces is
not violated. Once this is completed, the crossover
looks at period two and so on until all exams are
placed.
44
Heuristic Crossover Operator

Period i of child Timetable:
1.
2.

Take those exams schedules in period i in both
parents 1 and 2.
select extra exams from the exams scheduled in
period i in either parent1 or parent2 or left over
from period i-1.
(Any unscheduled exams are passed onto period
i+1).
45
Heuristic Crossover Operator
46

Once an exam is selected, all other exams that clash
with it are labeled as unscheduled for that period.

The authors construct a number of different
crossover operators based on the same framework
but using alternative selection algorithms. Some of
such operators are as follows.
 Random
Exams are selected at random. This is closest to
the standard uniform crossover.
 Largest Degree
Exams are selected according to the number of
other exams they conflict with.
47
Mutation Operator



Mutation, like crossover, must also ensure that a
timetable remains feasible after its action.
It cannot take any exam and shift it to another period
at random, since this may cause a conflict between
the moved exams and ones already scheduled.
Mutation is included into the crossover algorithm by
adding exams to the current search that would
otherwise not be considered until a later period.
48
Fitness Calculation


The evaluation function can be made up of any timetabling
related factors.
For example, we may focus on two particular common
requirements:
The length of the timetable
The num of conflicts between exams in adjacent
periods.

Given a space P of candidate solutions to a problem, fitness
function f(p) for p  P measures the quality of a solution p.

Note: The quality of a solution p may not vary smoothly as the
genes comprising p vary since the genetic operators such as
crossover and mutation do not vary the gene values smoothly.
49
Fitness calculation (cont.)



It seems reasonable to distinguish between timetables in terms
of fitness based on the numbers and kinds of different
constraints violated.
For instance, if V(p) is the number of violated soft constraints
in candidate p, one could choose:
f(p) = 1/(1 + V(p))
so that the range of f(p) is from 0 to 1.
If we have n kinds of soft constraints, the penalty associated
with constraint-type i is wi, p is a timetable, and ci(p) is the
number of violations of constraints of type i in p, then the
fitness function becomes:
n
f(p) = 1/(1 +  wici(p))
i =1
50
Other Issues

The Genetic algorithm for exam timetabling problem
uses:
- Generational Reproduction
- Population size = 200
- Rank-based selection mechanism
Remarks
• Burke et al. [1] combines traditional CSP solving heuristics with GAs.
• The underlying motivation is to get the best of two worlds. The
greediness of the heuristics (which can lead to dead-ends) and the
blindness of the stochastic genetic search.
• The heuristics can be incorporated into the genetic operators mutation
and crossover.
51
Conclusions



Constraint handling is not straightforward in a GA
because the search operators such as mutation and
recombination are ‘blind’ to constraints.
There is no guarantee that if the parents satisfy
some constraints, the offspring will satisfy them as
well.
However, genetic algorithms can be effective
constraint solvers when knowledge about the
constraints is incorporated either into



the genetic operators,
in the fitness function, or
in repair mechanisms.
52
References


[1] Burke, E. K., Elliman, D.G., Weave, R. F., A Hybrid
Genetic Algorithm for Highly Constrained Timetabling
Problems, Proc. of 6th International Conference on the
Practice and Theory of Automated Timetabling, Napier
University, Edinburgh, UK, 1995.
[2] Craenen, B. C. W., Eiben, A. E. and Marchiori, E.,
How to Handle Constraint with Evolutionary Algorithms.
In L. Chambers (Ed.), The Practical Handbook of
Genetic Algorithms: Applications, 2nd Edition, volume 1,
Chapman & Hall/CRC, 2001, pp. 341 – 361.
53
Appendix: Randomly Sequential Graph
Coloring Algorithm

A coloring of a graph is an assignment of a color to
each vertex of the graph so that no two vertices
connected by an edge have the same color.

One strategy for graph coloring is the following
“greedy” algorithm.

Initially we try to color as many as vertices as
possible with the first color, then as many as
possible of the un-colored vertices with the second
color, and so on.
54
To color vertices with a new color, we perform the
following steps.
1.
2.
Select some uncolored vertex and color it with the
new color.
Scan the list of uncolored vertices. For each
uncolored vertex, determine whether it has an edge
to any vertex already colored with the new color. If
there is no such edge, color the present vertex with
the new color.
55
Example
In figure having colored vertex 1 red, we can color
vertices 3 and 4 red also.
3
red
red
1
2
5
4
red
There are some heuristics on the order of selecting
one vertex from the list of uncolored vertices.
56
MEMETIC ALGORITHMS



Memetic algorithm introduced by Moscato and
Norman in 1992 is an improved variant of genetic
algorithm.
It takes the concept of evolution as in genetic
algorithm.
However, while genetic algorithm is based on
biological evolution, memetic algorithm is based on
cultural evolution or idea evolution. In the evolution
of ideas, an idea may be improved not only by
recombination from others, but also by adaptation
from itself.
57
A meme



A meme, a unit of information in memetic algorithm
can be improved by the individual holding it before it
is passed on.
A meme differs from a gene in that as it is passed
between individuals, each individual adapts the
meme as it see best whereas genes are passed
unchanged.
A basic memetic algorithm, is then, an evolution
algorithm incorporated with some local search
technique.
58
An Example Memetic Operation
Original solution
Solution after
mutation
Solution after
mutationand
andlocal
local
Mutation
search
search
59
Memetic Algorithm



Normally, the local search technique is hill-climbing
and the evolutionary operators are only mutation
operators.
In genetic algorithm, while the mutation creates new
genes for the population, the crossover operator
orients seeking the best solution from the genes in
the population.
In memetic algorithm, this orientation is achieved by
local search. Local search reduces the search space
and reaches to high quality solution faster.
60
Outline of a Memetic Algorithm


create initial population
repeat
1. take each individual in turn:
Choose a mutation method
Apply mutation operator to chosen individuals
Apply hill-climbing to individual just created.
Insert it into the population.
2. select a half of them to reduce the population to
its original size.
until termination condition is true
61