

Artificial
Intelligence (CS607)
Lecture No.
1113
3 Genetic
Algorithms
3.1
Discussion on Problem Solving
In the
previous chapter we studied
problem solving in general and
elaborated on
various
search strategies that help
us solve problems through
searching in
problem
trees. We kept the
information about the tree
traversal in memory (in
the
queues),
thus we know the links
that have to be followed to
reach the goal. At
times we
don't really need to
remember the links that
were followed. In
many
problems
where the size of search
space grows extremely large
we often use
techniques in
which we don't need to keep
all the history in memory.
Similarly, in
problems
where requirements are not
clearly defined and the
problem is ill
structured,
that is, we don't exactly
know the initial state,
goal state and
operators
etc, we
might employ such techniques
where our objective is to
find the solution
not
how we got there.
Another
thing we have noticed in the
previous chapter is that we
perform a
sequential
search through the search
space. In order to speed up
the techniques
we can
follow a parallel approach
where we start from multiple
locations (states)
in the
solution space and try to
search the space in
parallel.
3.2
Hill Climbing in Parallel
Suppose we
were to climb up a hill. Our
goal is to reach the top
irrespective of
how we
get there. We apply
different operators at a given
position, and move in
the
direction that gives us
improvement (more height).
What if instead of
starting
from
one position we start to
climb the hill from
different positions as indicated
by
the
diagram below.
In other
words, we start with
different independent search
instances that start
from
different locations to climb up
the hill.
Further
think that we can improve
this using a collaborative
approach where
these
instances interact and
evolve by sharing information in
order to solve the
problem. You
will soon find out
that what we mean by
interact and evolve.
However, it is
possible to implement parallelism in
the sense that the
instances
can
interact and evolve to solve
the solution. Such
implementations and
76
Artificial
Intelligence (CS607)
algorithms
are motivated from the
biological concept of evolution of
our genes,
hence
the name Genetic
Algorithms,
commonly terms as GA.
3.3 Comment on
Evolution
Before we
discuss Genetic Algorithms in
detail with examples lets go
though
some
basic terminology that we
will use to explain the
technique. The
genetic
algorithm
technology comes from the
concept of human evolution. The
following
paragraph
gives a brief overview of
evolution and introduces
some terminologies
to the
extent that we will require
for further discussion on GA.
Individuals (animals
or plants)
produce a number of offspring
(children) which are almost,
but not
entirely,
like themselves. Variation
may be due to mutation (random
changes), or
due to inheritance
(offspring/children inherit some
characteristics from
each
parent).
Some of these offspring may
survive to produce offspring of
their own
some
will not. The "better
adapted" individuals are
more likely to survive.
Over
time,
generations become better and
better adapted to
survive.
3.4
Genetic Algorithm
Genetic
Algorithms is a search method in
which multiple search paths
are
followed in
parallel. At each step,
current states of different
pairs of these paths
are
combined to form new paths.
This way the search
paths don't remain
independent,
instead they share
information with each other
and thus try to
improve
the overall performance of
the complete search
space.
3.5 Basic
Genetic Algorithm
A very
basic genetic algorithm can
be stated as below.
Start with a
population of randomly generated, (attempted)
solutions to a
problem
Repeatedly do the
following:
Evaluate each of
the attempted solutions
Keep the "best"
solutions
Produce next
generation from
these
solutions
(using
"inheritance" and
"mutation")
Quit when you have a
satisfactory solution (or you run out of
time)
The two
terms introduced here are
inheritance and mutation. Inheritance
has the
same
notion of having something or
some attribute from a parent
while mutation
refers to a
small random change. We will
explain these two terms as
we discuss
the
solution to a few problems
through GA.
3.6
Solution to a Few Problems using GA
3.6.1 Problem
1:
77
Artificial
Intelligence (CS607)
Suppose your "individuals" are
32bit computer words
·
You want a string in which all
the bits in these words are ones
·
Here's how you can
do it:
·
· Create
100 randomly generated computer
words
· Repeatedly
do the following:
· Count the 1 bits in each
word
· Exit if any of the words
have all 32 bits set to 1
· Keep the ten words that
have the most 1s (discard the
rest)
· From each word,
generate 9 new words as follows:
· Pick a random bit in the
word and toggle (change)
it
Note that this
procedure does not guarantee that the
next
·
"generation" will have more 1
bits, but it's likely
As you can
observe, the above solution
is totally in accordance with
the basic
algorithm you
saw in the previous section.
The table on the next
page shows
which
steps correspond to
what.
Terms
Basic
GA
Problem
1
Solution
Initial
Start
with
a
Create
100
Population
population
of
randomly
randomly
generated
generated
computer
words
attempted
solutions
to a
problem
Evaluation
Evaluate
each of
Count
the 1 bits
Function
the
attempted
in each
word.
solutions.
Exit if
any of the
Keep
the "best"
words
have all
solutions
32 bits
set to 1
Keep
the ten
words
that have
the
most 1s
(discard
the
rest)
Mutation
Produce
next
From
each
generation
from
word,
generate
these
solutions
9 new words
as
(using
"inheritance"
follows:
and
"mutation")
Pick a
random
bit in
the word
and
toggle
(change)
it
78
Artificial
Intelligence (CS607)
For
the sake of simplicity we
only use mutation for
now to generate the
new
individuals. We
will incorporate inheritance
later in the example. Let's
introduce
the
concept of an evaluation function. An
evaluation function is the
criteria that
check
various individuals/ solutions
for being better than
others in the
population.
Notice
that mutation can be as
simple as just flipping a
bit at random or any
number of
bits.
We go on repeating
the algorithm until we
either get our required
word that is a
32bit
number with all ones, or we
run out of time. If we run
out of time, we
either
present
the best possible solution
(the one with most number of
1bits) as the
answer or we
can say that the
solution can't be found.
Hence GA is at times
used
to get
optimal solution given some
parameters.
3.6.2 Problem
2:
Suppose you have a
large number of data points (x, y),
e.g., (1, 4),
(3,
·
9),
(5, 8), ...
You would like to fit a
polynomial (of up to degree 1) through these
·
data points
· That is, you
want a formula y = mx + c that gives you a
reasonably good
fit to the actual data
· Here's the
usual way to compute goodness of fit of the
polynomial on the data
points:
· Compute the sum of
(actual y predicted y)2 for all the
data points
· The lowest sum
represents the best fit
You can use a
genetic algorithm to find a "pretty good"
solution
·
By a pretty
good solution we simply mean
that you can get reasonably
good
polynomial
that best fits the
given data.
Your formula is y = mx +
c
·
Your unknowns are m and c;
where m and c are integers
·
Your
representation is the array [m, c]
·
Your evaluation
function for one array is:
·
· For every
actual data point (x, y)
· Compute ý = mx +
c
· Find the sum of (y
ý)2 over all x
· The sum is your
measure of "badness" (larger
numbers
are
worse)
· Example: For
[5, 7] and the data points (1, 10) and
(2, 13):
· ý = 5x + 7 = 12 when x is
1
· ý = 5x + 7 = 17 when x is
2
· (10 
12)2 + (13
17)2 = 22 + 42 = 20
· If these are
the only two data points, the "badness" of
[5,
7] is 20
79
Artificial
Intelligence (CS607)
Your algorithm might be as
follows:
·
· Create
twoelement arrays of random
numbers
· Repeat 50
times (or any other number):
· For each of the
arrays, compute its badness (using all
data
points)
· Keep the best
arrays (with low badness)
· From the
arrays you keep, generate new
arrays as
follows:
· Convert the numbers in
the array to binary, toggle
one of the bits at
random
· Quit if the badness of
any of the solution is zero
· After all 50
trials, pick the best array as your final
answer
Let us
solve this problem in
detail. Consider that the
given points are as
follows.
(x, y) :
{(1,5) (3, 9)}
·
We start
will the following initial
population which are the
arrays representing
the
solutions (m and
c).
[2 7][1
3]
·
Compute
badness for [2 7]
ý = 2x + 7 = 9 when x is
1
·
ý = 2x + 7 = 13 when x is
3
·
(5 9)2 + (9 13)2 = 42 + 42 = 32
·
ý = 1x + 3 = 4 when x is
1
·
ý = 1x + 3 = 6 when x is
3
·
(5 4)2 + (9 6)2
= 12 + 32 = 10
·
Lets keep the one with low
"badness" [1 3]
·
Representation
[001 011]
·
Apply mutation to
generate new arrays [011
011]
·
Now we have [1 3] [3 3] as the
new population considering that we
·
keep the two best
individuals
Second
iteration
(x, y) :
{(1,5) (3, 9)}
·
[1 3][3
3]
·
· ý = 1x + 3 = 4 when x is
1
· ý = 1x + 3 = 6 when x is
3
· (5 4)2 + (9 6)2
= 12 + 32 = 10
ý = 3x + 3 = 6 when x is
1
·
ý = 3x + 3 = 12 when x is
3
·
80
Artificial
Intelligence (CS607)
(5 6)2 + (9 12)2 = 1 + 9 =
10
·
Lets keep the [3
3]
·
Representation
[011 011]
·
Apply mutation to
generate new arrays [010
011]
·
Now we have [3 3] [2 3] as the
new population
·
Third
Iteration
(x, y) :
{(1,5) (3, 9)}
·
[3 3][2
3]
·
· ý = 3x + 3 = 6 when x is
1
· ý = 3x + 3 = 12 when x is
3
· (5 6)2 + (9 12)2 = 1 + 9 =
10
ý = 2x + 3 = 5 when x is
1
·
ý = 2x + 3 = 9 when x is
3
·
(5 5)2 + (9 9)2
= 02 + 02 = 0
·
Solution found [2
3]
·
y =
2x+3
·
So you see
that how by going though
the iteration of a GA one can
find a solution
to the
given problem. It is not
necessary in the above
example that you get
a
solution
that gives 0 badness. In
case we go on doing iterations
and we run out of
time, we
might just present the
solution that has the
least badness as the
most
optimal
solution given these number
of iterations on this
data.
In the
examples so far, each
"Individual" (or "solution")
had only one parent.
The
only way to
introduce variation was
through mutation (random
changes). In
Inheritance or
Crossover, each "Individual"
(or "solution") has two
parents.
Assuming
that each organism has
just one chromosome, new
offspring are
produced by
forming a new chromosome
from parts of the
chromosomes of each
parent.
Let us
repeat the 32bit word
example again but this
time using crossover
instead
of
mutation.
Suppose your "organisms" are
32bit computer words, and you want
·
a string in which all the bits
are ones
Here's how you can
do it:
·
· Create
100 randomly generated computer
words
· Repeatedly
do the following:
· Count the 1 bits in each
word
· Exit if any of the words
have all 32 bits set to 1
· Keep the ten words that
have the most 1s (discard the
rest)
· From each word,
generate 9 new words as follows:
· Choose one of the other
words
81
Artificial
Intelligence (CS607)
Take the first
half of this word and combine it with
·
the second half of the other
word
Notice
that we are generating new
individuals from the best
ones by using
crossover. The
simplest way to perform this
crossover is to combine the
head of
one individual to
the tail of the other, as
shown in the diagram
below.
In the
32bit word problem, the
(twoparent, no mutation) approach, if it
succeeds,
is likely to
succeed much faster because
up to half of the bits
change each time,
not
just one bit. However, with
no mutation, it may not succeed at
all. By pure bad
luck,
maybe none of the first
(randomly generated) words
have (say) bit 17 set
to
1. Then
there is no way a 1 could ever
occur in this position.
Another problem is
lack of
genetic diversity. Maybe some of
the first generation did
have bit 17 set to
1, but
none of them were selected
for the second generation.
The best technique
in general
turns out to be a combination of
both, i.e., crossover with
mutation.
3.7 Eight
Queens Problem
Let us
now solve a famous problem
which will be discussed
under GA in many
famous
books in AI. Its called the
Eight Queens Problem.
The problem is to
place 8 queens on a chess
board so that none of them
can
attack
the other. A chess board
can be considered a plain
board with eight
columns
and eight rows as shown
below.
The possible
cells that the Queen
can move to when placed in a
particular square
are
shown (in black
shading)
82
Artificial
Intelligence (CS607)
We now
have to come up with a
representation of an individual/
candidate
solution
representing the board
configuration which can be
used as individuals in
the
GA.
We will
use the representation as
shown in the figure
below.
Where
the 8 digits for eight
columns specify the index of
the row where the
queen
is placed.
For example, the sequence 2
6 8 3 4 5 3 1 tells us that in first
column
the
queen is placed in the
second row, in the second
column the queen is in
the
6th row so on till in the
8th column the
queen is in the 1st row.
Now we need a
fitness function, a function by
which we can tell which
board
position is
nearer to our goal. Since we
are going to select best
individuals at
every
step, we need to define a
method to rate these board
positions or
individuals.
One fitness function can be
to count the number of pairs
of Queens
that
are not attacking each
other. An example of how to
compute the fitness of
a
board
configuration is given in the
diagram on the next
page.
83
Artificial
Intelligence (CS607)
So once
representation and fitness
function is decided, the
solution to the
problem is
simple.
Choose initial
population
·
Evaluate the
fitness of each individual
·
Choose the best individuals
from the population for crossover
·
Let us
quickly go though an example of
how to solve this problem
using GA.
Suppose
individuals (board positions)
chosen for crossover
are:
Where
the numbers 2 and 3 in the
boxes to the left and
right show the fitness
of
each
board configuration and
green arrows denote the
queens that can
attack
none.
The following
diagram shows how we apply
crossover:
84
Artificial
Intelligence (CS607)
The individuals in
the initial population are
shown on the left and
the children
generated by
swapping their tails are
shown on the right. Hence we
now have a
total of 4
candidate solutions. Depending on
their fitness we will select
the best
two.
The diagram
below shows where we select
the best two on the
bases of their
fitness. The
vertical over shows the
children and the horizontal
oval shows the
selected
individuals which are the
fittest ones according to
the fitness function.
Similarly,
the mutation step can be
done as under.
85
Artificial
Intelligence (CS607)
That
is, we represent the
individual in binary and we
flip at random a
certain
number of
bits. You might as well
decide to flip 1, 2, 3 or k number of
bits, at
random
position. Hence GA is totally a
random technique.
This
process is repeated until an
individual with required
fitness level is found.
If
no such
individual is found, then
the process is repeated till
the overall fitness
of
the
population or any of its
individuals gets very close
to the required
fitness
level. An
upper limit on the number of
iterations is usually used to end
the
process in
finite time.
One of
the solutions to the problem
is shown as under whose
fitness value is 8.
The following
flow chart summarizes the
Genetic Algorithm.
86
Artificial
Intelligence (CS607)
Start
Initialize
Population
Evaluate
Fitness
Apply
mutation
of
Population
No
Yes
Mate
Solution
End
individuals
in
Found?
population
You are
encouraged to explore the
internet and other books to
find more
applications of GA
in various fields
like:
· Genetic
Programming
· Evolvable
Systems
· Composing
Music
· Gaming
· Market
Strategies
· Robotics
· Industrial
Optimization
and many
more.
87
Artificial
Intelligence (CS607)
3.8
Problems
Q1 what
type of problems can be
solved using GA. Give
examples of at least 3
problems
from different fields of
life. Clearly identify the
initial population,
representation,
evaluation function, mutation and
cross over procedure and
exit
criteria.
Q2 Given
pairs of (x, y) coordinates,
find the best possible m, c
parameters of the
line y = mx + c
that generates them. Use
mutation only. Present the
best possible
solution
given the data after at
least three iterations of GA or
exit if you find the
solution
earlier.
(x, y) :
{(1,2.5) (2, 3.75)}
·
Initial population
[2 0][3 1]
·
Q3 Solve
the 8 Queens Problem on
paper. Use the representations
and strategy
as discussed in
the chapter.
88

