Genetic Algorithms

<< Problem Solving

Knowledge Representation and Reasoning >>

Artificial Intelligence (CS607)

Lecture No. 11-13

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

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:

Artificial Intelligence (CS607)

Suppose your "individuals" are 32-bit 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)

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

Solution

Initial

Start

with

a Create

100

Population

population

of randomly

randomly

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

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

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

32-bit 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 1-bits) 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

Artificial Intelligence (CS607)

Your algorithm might be as follows:

· Create two-element 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

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 32-bit word example again but this time using crossover instead

of mutation.

Suppose your "organisms" are 32-bit 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

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 32-bit word problem, the (two-parent, 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)

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.

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:

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.

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.

Artificial Intelligence (CS607)

Start

Initialize

Population

Evaluate Fitness

Apply mutation

of Population

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.

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.

Table of Contents: