University of Karbala
MSc. Of
infrastructure
Dep.Of civil Eng
GENETIC ALGORITHMS
Prepared by Ridhaa Mahdi Kadhim
Supervised by Assist Prof. Dr. Riyadh Jasim Mohammed
What is GA 1
A genetic algorithm (or
GA)
is a search technique used in
computing to find true or
approximate solutions to
.optimization and search problems
Genetic algorithms are categorized
.as global search heuristics
Genetic algorithms are a particular
What is GA 2
Genetic algorithms are
implemented as a computer
simulation in which a population of
abstract representations (called
chromosomes or the genotype or the
genome) of candidate solutions (called
individuals, creatures, or phenotypes)
to an optimization problem evolves
toward better solutions.
Chromosome, Genes and Genomes
3
•Each chromosome consists of a number of “ genes “ , and
each gene represented by 0 or 1 :
Key terms 4
Individual - Any possible solution
Population - Group of all individuals
Search Space - All possible solutions to the
problem
Chromosome - Blueprint for an individual
Trait - Possible aspect (features) of an individual
Allele - Possible settings of trait (black, blond,
etc.)
Locus - The position of a gene on the
chromosome
Genome - Collection of all chromosomes for an
individual
Genotype and 5
Phenotype
Genotype:
– Particular set of genes in a genome
Phenotype:
– Physical characteristic of the genotype
(smart, beautiful, healthy, etc.)
Representation 6
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 ...
Basic of genetic algorithms 7
The most common type of genetic
algorithm works like this:
a population is created with a group of individuals
created randomly.
The individuals in the population are then
evaluated.
The evaluation function is provided by the
programmer and gives the individuals a score
based on how well they perform at the given task.
Two individuals are then selected based on their
fitness, the higher the fitness, the higher the
chance of being selected.
These individuals then "reproduce" to create one or
more offspring
Selection& Crossover& 8
Mutation
Selection Individual solutions are selected through a
fitness-based process, where fitter solutions (as measured
by a fitness function) are typically more likely to be selected.
Crossover the most common type is single point crossover. In
single point crossover, you choose a locus at which you swap the
remaining alleles from on parent to the other
Mutation After selection and crossover, you now have a new
population full of individuals. Some are directly copied, and
others are produced by crossover. In order to ensure that the
individuals are not all exactly the same, you allow for a small
chance of mutation. You loop through all the alleles of all the
individuals, and if that allele is selected for mutation, you can
either change it by a small amount or replace it with a new
value.
GA optimization process 9
1. Generation of initial population randomly
2. Fitness evaluation
3. Mating of individual
4. Selection
5. Crossover
6. Mutation
10
1. Choose initial population
2. Evaluate the fitness of each individual in the
population
3. Repeat
4. Select best-ranking individuals to reproduce
5. Breed new generation through crossover and
mutation (genetic operations) and give birth to
offspring
6. Evaluate the individual fitnesses of the offspring
7. Replace worst ranked part of population with
offspring
8. Until <terminating condition>
Example 11
Maximizing a Function of One Variable f(x)=x2 where x is
allowed to vary between 0 and 31
solution:
Step-1 make initial population
we must encode the possible values of x as chromosomes and for this example, we will encode x as
a binary integer of length 5. Thus, the chromosomes for our genetic algorithm will be sequences
of 0’s and 1’s with a length of 5 bits, and have a range from 0 (00000) to 31 (11111).
01001(13)&11000(24)&01000(8)&1001
1(19)
Step-2 calculate fitness f(x)=x2
f(13)=169
f(24)=576
f(8)=64
f(19)=361
Example 12
• Step-3: We select the chromosomes that will reproduce based on their
fitness values, using the following probability: Pi(chromosome i reproduces)
Example 13
Step-4 make crossover
To create their offspring, a crossover point is chosen at random, which is
shown in the table as a vertical line. Note that it is possible that crossover
does not occur, in which case the offspring are exact copies of their parents.
Example 14
Step-4 make mutation:
Symbolic AI VS. Genetic Algorithms
15
Most symbolic AI systems are very static.
Most of them can usually only solve one given
specific problem, since their architecture was
designed for whatever, that specific problem was
in the first place.
Thus, if the given problem were somehow to be
changed, these systems could have a hard time
adapting to them, since the algorithm that would
originally arrive to the solution may be either
incorrect or less efficient.
Genetic algorithms (or GA) were created to
combat these problems; they are basically
algorithms based on natural biological evolution.
Symbolic AI VS. Genetic Algorithms
16
The architecture of systems that implement genetic
algorithms (or GA) are more able to adapt to a wide range
of problems.
A GA functions by generating a large set of possible
solutions to a given problem.
It then evaluates each of those solutions, and decides on a
"fitness level" (you may recall the phrase: "survival of the
fittest") for each solution set.
These solutions then breed new solutions.
The parent solutions that were more "fit" are more likely to
reproduce, while those that were less "fit" are more unlikely
to do so.
In essence, solutions are evolved over time. This way you
evolve your search space scope to a point where you can
find the solution.
(Genetic algorithms can be incredibly efficient if
programmed correctly).
