Solving problems by searching

CHAPTER 3

GENETIC ALGORITHM
TE/VI/COMPUTER
CSC604: Artificial Intelligence Credit:3

⚫ Prerequisite: Discrete Mathematics, Data Structures

Course Objectives:
1. To conceptualize the basic ideas and techniques underlying
the design of intelligent systems.
2. To make students understand and Explore the mechanism of
mind that enables intelligent thought and action.
3. To make students understand advanced representation
formalism and search techniques.
4. To make students understand working of an AI Systems like
Expert System NLP etc.
CSC604: Artificial Intelligence Credit:3
⚫ Course Outcomes: At the end of the course, the students will
be able to
1. Determine the types of environment and analyze the PEAS
descriptor for given AI problem.
2. Compare different types of intelligent agents and formulate the
problem for given AI problem.
3. Choose and Apply an appropriate informed / uninformed /
heuristic searching technique for solving given problem.
4. Use First Order Predicate logic for knowledge representation
for given facts and apply logical reasoning techniques for given
problem.
5. Apply planning language to generate the plan for given
problem and illustrate learning techniques using example.
6. Analyze AI Applications in real world scenarios.
Artificial Intelligence 4

Evolutionary Computation:
Genetic algorithms

● Introduction, or can evolution be intelligent?

● Simulation of natural evolution
● Genetic algorithms
● Example
Artificial Intelligence 5

Evolutionary Computation: Genetic Algorithm

● Evolution:
● The process by which different kinds of living
organism are believed to have developed from
earlier forms during the history of the earth.
● In biology, evolution is the change in the
characteristics of a species over several
generations and relies on the process of
natural selection.
● Survival of the fittest: In nature, there is
competition to survive and reproduce.
Artificial Intelligence 6

Introduction to Evolutionary Computation

● The theory of evolution is based on the idea that
all species are related and gradually change over
time.

● Genetic algorithm is a method for solving both

constrained and unconstrained optimization
problems that is based on natural selection, the
process that drives biological evolution.
Artificial Intelligence 7

Can evolution be intelligent?

● Intelligence can be defined as the capability of a
system to adapt its behaviour to ever-changing
environment.
● According to Alan Turing, the form or appearance
of a system is irrelevant to its intelligence.
Artificial Intelligence 8

Can evolution be intelligent?

●The evolutionary approach is based on computational
models of natural selection and genetics.
●If, over successive generations, the organism survives,
we can say that this organism is capable of learning to
predict changes in its environment.
●We call them evolutionary computation, an umbrella
term that combines genetic algorithms, evolution
strategies and genetic programming.
Artificial Intelligence 9

Can evolution be intelligent?

●Evolutionary computation simulates evolution on a

computer.
●The result of such a simulation is a series of
optimisation algorithms, usually based on a simple
set of rules.
●Optimisation iteratively improves the quality of
solutions until an optimal, or at least feasible,
solution is found.
Artificial Intelligence 10

Simulation of natural evolution

● All methods of evolutionary computation simulate
natural evolution by creating a population of
individuals, evaluating their fitness, generating a
new population through genetic operations, and
repeating this process a number of times.
Artificial Intelligence 11

Introduction to Genetic Algorithm

● Definition and Concept:
● Genetic Algorithms (GAs): Optimization techniques
inspired by natural selection and genetics.

● Evolutionary Algorithms: Mimic biological

evolution to solve complex problems.

● Process: Create a population, evaluate fitness, and

evolve via selection, crossover, and mutation.
Artificial Intelligence 12

● Evolution can be seen as a process leading to the

maintenance of a population’s ability to survive
and reproduce in a specific environment. This
ability is called evolutionary fitness.
● Evolutionary fitness can also be viewed as a
measure of the organism’s ability to anticipate
changes in its environment.
● The fitness, or the quantitative measure of the
ability to predict environmental changes and
respond adequately, can be considered as the
quality that is optimised in natural life.
Artificial Intelligence 13

How is a population with increasing fitness generated?

● Let us consider a population of rabbits. Some
rabbits are faster than others, and we may say that
these rabbits possess superior fitness, because they
have a greater chance of avoiding foxes, surviving
and then breeding.
● Over time the entire population of rabbits becomes
faster to meet their environmental challenges in the
face of foxes.

If two parents have superior fitness, there is a good chance

that a combination of their genes will produce an offspring
with even higher fitness.
Artificial Intelligence 14

Genetic Algorithm
● In the early 1970s, John Holland introduced the
concept of genetic algorithms.
● His aim was to make computers do what
nature does. Holland was concerned with
algorithms that manipulate strings of binary
digits.
● Each artificial “chromosomes” consists of a
number of “genes”, and each gene is represented
by 0 or 1:
Artificial Intelligence 15

Terms used in Genetic Algorithm

1. Chromosome: A representation of a potential solution to
the problem, typically encoded as a string of genes.
2. Gene: A component of a chromosome representing a
specific parameter or feature of a solution.
3. Population: A collection of individuals (chromosomes)
representing potential solutions to the problem..
4. Fitness Function: A function that quantifies the suitability
or quality of a solution based on how well it performs in
solving the problem. Ex. In 8-queens , fitness function has
28 value for number of non-attacking pairs.
5. Selection: The process of choosing individuals from the
population for reproduction based on their fitness,
typically favoring individuals with higher fitness.
Artificial Intelligence 16

Terms used in Genetic Algorithm

6. Crossover (Recombination): Process of combining
genetic information from two parent individuals to create
offspring individuals with new combinations of genes.
7. Mutation: A random alteration applied to the genetic
information of an individual, introducing diversity into the
population.
8. Generation: A single iteration or step in the genetic
algorithm process, involving the evaluation of fitness,
selection, crossover, and mutation to create a new
population.
9. Convergence: State where the genetic algorithm has
reached a point where further iterations do not significantly
improve the solutions.
Artificial Intelligence 17

Basic genetic algorithms

Step 1: Represent the problem variable domain as a
chromosome of a fixed length, choose the size of a
chromosome population N, the crossover
probability pc and the mutation probability pm.

Step 2: Define a fitness function to measure the

performance, or fitness, of an individual chromosome
in the problem domain.
Fitness function establishes the basis for selecting
chromosomes that will be mated during reproduction.
Artificial Intelligence 18

Step 3: Randomly generate an initial population of

chromosomes of size N:
x1, x2, . . . , xN
Step 4: Calculate the fitness of each individual
chromosome:
f (x1), f (x2), . . . , f (xN)
Step 5: Select a pair of chromosomes for mating from
the current population. Parent chromosomes are
selected with a probability related to their fitness.
Step 6: Create a pair of offspring chromosomes by
applying the genetic operators − crossover and
mutation.
Artificial Intelligence 19

Step 7: Place the created offspring chromosomes in

the new population.
Step 8: Repeat Step 5 until the size of the new
chromosome population becomes equal to the size
of the initial population, N.
Step 9: Replace the initial (parent) chromosome
population with the new (offspring) population.
Step 10: Go to Step 4, and repeat the process until the
termination criterion is satisfied.
Artificial Intelligence 20
START
GA: Flowchart
Initial
Population

Selection

Crossover

Mutation

Terminate No
?

Ye
s
Best Individuals

Output

STOP
Artificial Intelligence 21

CROSSOVER (Recombination)
Single-Point Crossover:
Ex:
Parent 1 1 0 1 1 0 0 1 0
Parent 2 1 0 1 0 1 1 1 1

Child1 1 0 1 1 0 1 1 1
Child 2 1 0 1 0 1 0 1 0

Two mating chromosomes are cut once at corresponding

point
Artificial Intelligence 22

CROSSOVER (Recombination)
Two-Point Crossover:
Ex:
Parent 1 1 1 0 1 1 0 1 0
Parent 2 0 1 1 0 1 1 0 0

child 1 1 1 1 0 1 0 1 0
Child 2 0 1 0 1 1 1 0 0

Two crossover points are chosen & contents between

these points are exchanged
Artificial Intelligence 23

CROSSOVER (Recombination)
Uniform Crossover:
Ex:
Parent 1 1 0 1 0 0 0 1 1

Parent 2 0 0 0 1 1 0 1 0

Crossover mask 1 1 0 1 0 1 1 0

Child 1 1 0 0 01 0 1 0

Child 2 0 0 1 1 0 0 1 1

Child1: Crossover mask are random generated. If 1 in mask then

gene is copied from first parent and if 0 then from second parent.

Child 2: Crossover mask are random generated. If 1 in mask then

gene is copied from second parent and if 0 then from first parent.
Artificial Intelligence 24

CROSSOVER (Recombination)
Three Parent Crossover:
Ex:
Parent 1 1 1 0 1 0 0 0 1
Parent 2 0 1 1 0 1 0 0 1
Parent 3 0 1 1 0 1 1 0 0
Child 0 1 1 0 1 0 0 1

each bit of parent 1 is compared with parent 2, if both

bits are same then bit from parent 1 is selected for
offspring else from parent 3.
Artificial Intelligence 25

Mutation
Mutation Flipping:
Ex:

Parent 1 0 1 1 0 1 0 1

Mutation chromosome 1 0 0 0 1 0 0 1

Child 0 0 1 1 1 1 0 0

if mutation chromosome bit is 1 then corresponding parent

bit changed.
Artificial Intelligence 26

Mutation
Interchanging :
Ex:

Parent 1 0 1 1 0 1 0 0
Child 0 0 1 1 1 1 0 0

two random positions are interchanged

Artificial Intelligence 27

Mutation

Reversing:
Ex:

Parent 1 0 1 1 0 1 0 1
Child 0 0 1 1 1 0 1 0

All bits from random position are interchanged.

Stopping condition for GA flow
• Termination
• This generational process is repeated until a termination
condition has been reached.
• Common terminating conditions are:
• A solution is found that satisfies minimum criteria
• Fixed number of generations reached
• Allocated budget (computation time/money) reached
• The highest ranking solution's fitness is reaching or has reached
a plateau such that successive iterations no longer produce
better results
• Manual inspection
• Any Combinations of the above
Artificial Intelligence 29

GA Example
• Problem Statement: Suppose we want to find the optimal
binary string of length 5 that maximizes the number of
ones.
• Genetic Algorithm Steps:
1. Initialization:
1. Generate an initial population of binary strings of length 5.
2. Example:
1. Population: [11010, 10100, 01101, 11100, 00011]
2. Evaluation:
• Evaluate the fitness of each individual based on the number of
ones in the binary string.
• Example:
• Fitness: [3, 2, 3, 3, 2]
Artificial Intelligence 30

GA Example
3. Selection:
•Select individuals from the population for reproduction based on
their fitness.
•Example : Probability of selection:
• Individual 1: 3/11
• Individual 2: 2/11
• Individual 3: 3/11
• Individual 4: 3/11
• Individual 5: 2/11
Artificial Intelligence 31

GA Example
4. Crossover (Recombination):
•Perform crossover to create offspring individuals from selected
parent individuals.
•Example (using single-point crossover):
• Selected parents:
• Parent 1: 11010

• Parent 2 : 01101

• Offspring 1: 11001
• Offspring 2: 01110

•Initial Population: [11010, 10100, 01101, 11100, 00011]

Artificial Intelligence 32

GA Example
5. Mutation:
•Apply mutation to introduce random alterations to the genetic
information of offspring individuals.
•Example:
• Offspring after mutation: 11001, 01010
6. Replacement:
1. Replace individuals in the current population with the newly
created offspring individuals.
2. Example:
1. Updated population: [11001, 10100, 01110, 11100, 01010]
7. Termination Criteria:
3. Repeat steps 2 to 6 for a certain number of generations or until
a satisfactory solution is found.
Artificial Intelligence 33

GA Example
8. Iterate:
1. Repeat the process of evaluation, selection, crossover,
mutation, and replacement for a predetermined number of
iterations (generations).
9. Solution Extraction:
2. Once the algorithm terminates, extract the individual with the
highest fitness from the final population as the solution.
3. Example:
1. Best solution: 11100
Example: Maximizing f(x) = x²
• Goal: Find the maximum value of f(x) = x² for x in
[-10, 10].
• Initial Population: Random numbers (e.g., -5, 3, 8,
-2, 7).
• Fitness Evaluation: Compute f(x) = x² for each
value.
• Selection: Choose the best candidates (e.g., 8
and 7).
• Crossover: Generate a new value (e.g., 7.5).
• Mutation: Introduce a small change (e.g., 7.8).
• Repeat until optimal solution is found.
Artificial Intelligence 35

THANK YOU