Artificial Intelligence

CS-216
Institute of Southern Punjab
Multan

Syed Zohair Quain Haider

Lecturer ISP Multan
Lecture#10
In the Last Lecture:
• Genetic algorithm

Last Discussion
Last Discussion
In Today’s Lecture
• Genetic algorithm

Today’s Discussion
Today’s Discussion
• Searching algorithm based on the mechanics of biological evolution
• Developed by John Holland, University of Michigan (1970’s)
• To understand the adaptive processes of natural systems
• To design artificial systems software that retains the robustness of
natural systems

Genetic Algorithm
Genetic Algorithm
• IF there are organisms that reproduce, and
• IF offspring's inherit traits from their progenitors, and
• IF there is variability of traits, and
• IF the environment cannot support all members of a growing population,
• THEN those members of the population with less-adaptive traits
(determined by the environment) will die out, and
• THEN those members with more-adaptive traits (determined by the
environment) will thrive
The result is the evolution of species

Darwin’s theory of natural selection

 “Select The Best, Discard The Rest”

• Creating a new complex object by adding two simple objects.

• Random mixing of gens.
This kind of Optimization is what we call genetic algorithm

Basic idea
Basic idea
• Provide efficient, effective techniques for optimization and machine
learning applications
• Widely-used today in business, scientific and engineering circles

Genetic Algorithm (cont.)

Genetic Algorithm (cont.)
 • Each cell of a living thing contains chromosomes - strings of
DNA
• Each chromosome contains a set of genes - blocks of DNA
• Each gene determines some aspect of the organism (like eye
colour)
• A collection of genes is sometimes called a genotype
• A collection of aspects (like eye colour) is sometimes called a
phenotype
• Reproduction involves recombination of genes from parents
and then small amounts of mutation (errors) in copying
• The fitness of an organism is how much it can reproduce
before it dies
• Evolution based on “survival of the fittest”

Evolution in the real world

Evolution in the real world
 • Suppose you have a problem & you don’t know how
to solve it
• What can you do?
• Can you use a computer to somehow find a solution
for you?
• This would be nice! Can it be done?

Start with a Dream…

Start with a Dream…
 A “blind generate and test” algorithm:

Repeat
Generate a random possible solution
Test the solution and see how good it is until solution is good
enough

A dumb solution
A dumb solution
 • Sometimes - yes:
• if there are only a few possible solutions
• and you have enough time
• then such a method could be used
• For most problems - no:
• many possible solutions
• with no time to try them all
• so this method can not be used

Can we use this dumb idea?

Can we use this dumb idea?
 Generate a set of random solutions
Repeat
Test each solution in the set (rank them)
Remove some bad solutions from set
Duplicate some good solutions
make small changes to some of them
Until best solution is good enough

A “less-dumb” idea (GA)

A “less-dumb” idea (GA)
• Encoding technique (gene, chromosome)
• Initialization procedure (creation)
• Evaluation function (environment)
• Selection of parents (reproduction)
• Genetic operators (mutation, recombination)
• Parameter settings (practice and art)

Components of a GA
Components of a GA
The GA Cycle of Reproduction
children
reproduction modification
modified
parents children
population evaluation
evaluated children
deleted
members

discard
 population

Chromosomes could be:

• Bit strings (0101 ... 1100)
• Real numbers (43.2 -33.1 ... 0.0 89.2)
• Permutations of element (E11 E3 E7 ... E1 E15)
• Lists of rules (R1 R2 R3 ... R22 R23)
• Program elements (genetic programming)
• ... any data structure ...

Population
Population
 children
reproduction

parents

population

Parents are selected at random with selection chances biased in

relation to chromosome evaluations.

Reproduction
Reproduction
 children
modification
modified children

• Modifications are stochastically triggered

• Operator types are:
• Mutation
• Crossover (recombination)

Chromosome Modification
Chromosome Modification
 modified
evaluated children
children
evaluation
• The evaluator decodes a chromosome and assigns it a
fitness measure
• The evaluator is the only link between a classical GA and
the problem it is solving

Evaluation
Evaluation
 population
discarded members

discard

• Generational GA:
entire populations replaced with each iteration

Deletion
Deletion
 • Binary Encoding
• Permutation Encoding
• Value Encoding
• Tree Encoding

Encoding
Encoding
 • Roulette Wheel Selection
– Calculate sum of all chromosome finesses in population and generate
random number from interval. Go through the population and sum finesses
from 0 - sum s. When the sum s is greater then r, stop and return the
chromosome where you are.
• Rank Selection
– First ranks the population and then every chromosome receives fitness from
this ranking. The worst will have fitness 1, second worst 2 etc. and the best
will have fitness N (number of chromosomes in population).
• Steady State Selection
– In every generation are selected a few (good - with high fitness)
chromosomes for creating a new offspring. Then some (bad - with low
fitness) chromosomes are removed and the new offspring is placed in their
place. The rest of population survives to new generation.
• Elitism
– Elitism is name of method, which first copies the best chromosome (or a few
best chromosomes) to new population. The rest is done in classical way.
Elitism can very rapidly increase performance of GA, because it prevents
losing the best found solution.

Selection
Selection
• Single Point Crossover
• Two Point Crossover
• Multi Point Crossover
• Uniform Crossover
• Ring Crossover
• Arithmetic Crossover
Different Kind of Mutation

Crossover Operator
Crossover Operator
• Rate of Mutation
• Bit Inversion Mutation
• Order Changing Mutation

Mutation operator
Mutation operator
• Decade long debate: which one is better?
• Mainly depends on the problem
• Generally it is good to have both
• Certainly both have different role

• Exploration: Discovering promising areas in the search space, i.e. gaining

information on the problem
• Exploitation: Optimising within a promising area, i.e. using information
• There is co-operation AND competition between them
• Crossover is explorative, it makes a big jump to an area somewhere “in between”
two (parent) areas
• Mutation is exploitative, it creates random small diversions, thereby staying near
(in the area of ) the parent

Crossover or mutation
Crossover or mutation
• Only crossover can combine information from two parents
• Only mutation can introduce new information
• Crossover does not change the frequencies of the population
• To hit the optimum you often need a ‘lucky’ mutation

Crossover or mutation
Crossover or mutation
• Simple problem: max x2 over {0,1,…,31}
• GA approach:
• Representation: binary code, e.g. 01101  13
• Population size: 4
• 1-point crossover, bitwise mutation
• Roulette wheel selection
• Random initialization
• We show one generational cycle done by hand

An example
 x2 example: selection
x example: selection
2
 X 2 example: crossover
X example: crossover
2
• Choosing basic implementation issues:
 representation
 population size, mutation rate, ...
 selection, deletion policies
 crossover, mutation operators
• Termination Criteria
• Solution is only as good as the evaluation function (often
hardest part)

Issues for GA Practitioners

Issues for GA Practitioners
• Concept is easy to understand
• Supports multi-objective optimization
• Good for “noisy” environments
• Always an answer; answer gets better with time
• Many ways to speed up and improve a GA-based
application as knowledge about problem domain is
gained
• Easy to exploit previous or alternate solutions
• Flexible building blocks for hybrid applications

Benefits of Genetic Algorithms

 Domain Application Types
Control gas pipeline, pole balancing, missile evasion, pursuit

Design semiconductor layout, aircraft design, keyboard

configuration, communication networks
Scheduling manufacturing, facility scheduling, resource allocation

Robotics trajectory planning

Machine Learning designing neural networks, improving classification

algorithms, classifier systems
Signal Processing filter design

Game Playing poker, checkers, prisoner’s dilemma

Combinatorial set covering, travelling salesman, routing, bin packing,

graph colouring and partitioning
Optimization

Some GA Application Types

• When the chromosome encodes an entire program or function itself
this is called genetic programming (GP)
• In order to make this work encoding is often done in the form of a
tree representation
• Crossover entials swaping subtrees between parents

Genetic Programming
Genetic Programming
Eight Queens Problems

Eight Queens Problems

Eight Queens Problems
 Eight Queens Problems
Eight Queens Problems
 Eight Queens Problems
Eight Queens Problems
 Eight Queens Problems
Eight Queens Problems
 Eight Queens Problems
Eight Queens Problems
 Eight Queens Problems
Eight Queens Problems
 Eight Queens Problems
Eight Queens Problems
 Eight Queens Problems
Eight Queens Problems
 Eight Queens Problems
Eight Queens Problems
 Eight Queens Problems
Eight Queens Problems
 Eight Queens Problems
Eight Queens Problems
 Eight Queens Problems
Eight Queens Problems
 Eight Queens Problems
Eight Queens Problems
Reference
https://www.obitko.com/tutorials/genetic-algorithms/ga-basic-description.php
 Questions

Questions Session
Questions Session