Transcript Cont`d- What is a Genetic algorithm?

Genetic Algorithms
Nehaya Tayseer
1.Introduction
What is a Genetic algorithm?
 A search technique used in computer
science to find approximate solutions for
optimization and search problems
 A class of evolutionary algorithms that use
techniques inspired by evolutionary biology
such as inheritance, mutation, natural
selection, and recombination (or crossover).
Cont’d- What is a Genetic algorithm?

Typically implemented as a computer
simulation in which a population of abstract
representations (called chromosomes) of
candidate solutions (called individuals) to an
optimization problem evolves toward better
solutions.
Introduction
Some History!
 Genetic algorithms originated from the studies of
cellular automata, conducted by John Holland
and his colleagues at the University of Michigan
in the mid 70’s.
 The first commercial genetic algorithm, called
the evolver, was produced in 1985.
 now used by a majority of 500 companies to
solve difficult scheduling, data fitting, trend
spotting and budgeting problems
2. Optimization Problems

In mathematics, the term optimization, or
mathematical programming, refers to the
study of problems in which one seeks to
minimize or maximize a real function by
systematically choosing the values of real or
integer variables from within an allowed set.
Cont’d- Optimization Problems
-
A Simple Case
City C
5
5
22
City A
8
2
City D
3
City B
1
6
City E
Figure 1: an example of a small sized optimization problem, here we have
exactly 5 paths between city A and B. the number above the path is the cost of
exploring the path. The optimal path is A,E,D,B with a total cost of 6.
Cont’d- Optimization Problems:
Why do we need non trivial Techniques?
City
A
City
B
Figure 2: an Example of a huge solution space, assume we have n cities
between A and B. the n cities are fully connected then the solution space
is n! size. Computationally, this problem is defined as NP-Hard.
Cont’d- Optimization Problems:
Why do we need non trivial Techniques?

Possible Solutions:
- Choose any path.
- Local Search algorithms
- Genetic Algorithms
- Neural Networks
The Canonical Genetic Algorithm

Typical Operations in any Genetic Algorithm include:

Initialization
Selection
Crossover
Mutation
Termination




Cont’d- Canonical GA
Initialization




Many individual solutions are randomly generated to
form an initial population
The population size depends on the nature of the
problem (typically several hundreds)
Each member of this population will be a binary
string of length L which corresponds to the problem
encoding
Strings (individuals) are usually called
Chromosomes.
Cont’d- Canonical GA
Selection

each string is then evaluated and assigned a fitness function.

A fitness function is a particular type of objective function that
quantifies the optimality of a solution (that is, a chromosome) in
a genetic algorithm so that that particular chromosome may be
ranked against all the other chromosomes
Cont’d- Canonical GA
Selection

In the canonical genetic algorithm, fitness is defined by:
f
i

f


Where fi is the evaluation associated with string i and fº is the
average evaluation of all the strings in the population.
Fitness can also be assigned based on a string's rank in the
population or by sampling methods
Cont’d- Canonical GA
Selection
(Duplication)
Recombination
(Crossover)
String 1
String 1
OffSpring A
String 2
String 1
OffSpringB
String 3
Sring 2
OffSpringC
String 4
String 3
OffSpringD
…
String 3
OffSpringE
…
String 3
OffSpringF
Current
Generation
Intermediate
Generation
Next
Generation
Figure 3: One generation is broken down into a selection phase and recombination
phase.
Cont’d- Canonical GA
Selection Methods
- Stochastic sampling with replacement: We
might view the population as mapping onto a
roulette wheel, where each individual is
represented by a space that proportionally
corresponds to its fitness. By repeatedly
spinning the roulette wheel, individuals are
chosen.
Cont’d- Canonical GA
Selection Methods
- Remainder stochastic sampling : if fitness is greater
than 1.0, the integer portion of this number indicates
how many copies of that string are directly placed in
the intermediate population. All strings (including
those with less than 1.0) then place additional copies
In the intermediate population with a probability
corresponding to the fractional portion of the fitness.
Cont’d- Canonical GA
Remainder stochastic sampling
 Example, a string with fitness 1.36 places 1
copy in the intermediate population, and then
receives a 0.36 chance of placing a second
copy. A string with a fitness of 0.54 has a
0.54 chance of placing one string in the
intermediate population
Cont’d- Canonical GA
Crossover
 Creating the next population from the
intermediate population
 One point crossover
Cont’d- Canonical GA

One point crossover Example
- Father: 1101001100101101
- Mother: yxyyxyxxyyyxyxxy
- Crossover: 11010 \ / 01100101101
yxyyx / \ yxxyyyxyxxy
- Children: 11010yxxyyyxyxxy and
yxyyx01100101101
Cont’d- Canonical GA
Mutation
 Maintains genetic diversity from one generation of
chromosomes to the next. It is analogous to
biological mutation.
 Usually performed by either flipping one bit in the
chosen chromosome or setting the bit to 0 or 1.
 Typically the mutation rate is applied with less than
1% probability.
Cont’d- Canonical GA
Termination
 The process of evaluation, selection, recombination
and mutation forms one generation in the execution
of a genetic algorithm.
Common terminating conditions are
 A solution is found that satisfies minimum criteria
 Fixed number of generations reached
 Allocated budget (computation time/money) reached
 Manual inspection
 Combinations of the above.
Some Applications






Artificial Creativity
Code Breaking
Design of water distribution systems
Traveling Salesman Problem
Scheduling applications
Electronic circuit design
Thank You