Transcript Genetic Algorithms

Genetic Algorithms
By: Jacob Noyes
4/16/2013
Traveling Salesman Problem
Given:
A list of cities
Distances between each city
Find:
Shortest path to reach every city once
Traveling Salesman Problem
Brute force
Exact Algorithms
Pro:
Will find the right answer
Con:
Does not scale well
Evolution
Change in inherited characteristics over time
Natural Selection:
A mechanism through which evolution happens
Survival of the fittest
Genes of the more suitable organisms get passed on more
often
Deoxyribonucleic acid(DNA):
Genes encoded in amino acids
Used to pass genes from parent to offspring
Genetic Algorithms: The Basics
Genetic algorithms are specialized search
heuristics which use the fundamental
principles of evolution through natural
selection to find the best solution to a
problem.
Genetic Algorithms: The Basics
Encoding
Initialization
Selection
Crossover
Mutation
Encoding
Changeable representation of individual's traits
is created
Completed only at the start
Its “string” is designed a series of bits
Concatenate multiple parameters
Examples: Max y-values?
Example 1:
y = -x^2 + 255x
0
≤ x ≤ 255
String: 00000000
Example 2:
y = 2w + x + 3z
≤ ≤
≤ x ≤ 11111111
≤ ≤
≤ ≤
0
w
7, 0
x
7, 0
z
7
String: 000/000/000 – 111/111/111
Initialization
Beginning population is created
Each bit(gene) is randomly generated to create variety
Performed only for the first generation and not repeated
Example: Initialization
Given
y = -x^2 + 255x
0 ≤ x ≤ 255
X
188
48
75
104
249
10
134
125
Binary x
10111100
00110000
01001011
01101000
11111001
00001010
10000110
01111101
Selection
Assign a fitness
measure of how close a solution is to fulfilling the problem
Assigned to each individual
Select individuals
Individuals with higher fitness will reproduce more often
Non-selected individuals will “die off”
Example: Fitness
Given
y = -x^2 + 255x
0 ≤ x ≤ 255
X
188
48
75
104
249
10
134
125
Binary x
10111100
00110000
01001011
01101000
11111001
00001010
10000110
01111101
Fitness
12596
9936
13500
15704
1494
2450
16214
16250
Optimums
Local optimum: A point where small
changes will lead to worse
results
Overall optimum: The best solution
Selection: Categories
Proportionate Selection: Fitness relative to other
individuals
Ranking Selection: Chance to reproduce based
on order
Tournament Selection: Pits individuals against
each other in smaller brackets
Gender Specific Selection: Splits Individuals
into groups based on “sex”
Genetic Relatedness Based Selection:
Individuals are selected based on their
genetic distance from others in the population
Selection: Proportionate Selection
Roulette wheel selection
Deterministic Sampling
Stochastic Remainder Sampling with Replacement
Stochastic Remainder Sampling without Replacement
Stochastic Universal Selection
Roulette Wheel Selection
1. Find Pf: Population fitness = sum of all fitness factors
2. Find Psel: Each individual's probability of selection
Psel = (fitness factor) / Pf
3. Load each Psel into an array
4. Generate random number between 0-100
5. Start at beginning of array, subtract each Psel from number until number <= 0
Deterministic Sampling
1. Average fitness is found
2. Individual fitnesses are divided by the average
3. Whole number results = number of spots in the mating pool
4. Extra slots filled starting by highest decimal
5. Random numbers generated to select individuals from the mating pool
Stochastic Remainder with Replacement
Uses Deterministic Sampling to fill slots with whole number results
Left over slots are then filled using the remainders with the Roulette Wheel
Selection Method
Stochastic Remainder without Replacement
Uses Deterministic Sampling to fill slots with whole number results
Uses a “weighted-coin toss” to determine the rest
1. Each remainder multiplied by 100
2. Random number between 0-100 generated
3. If random number <= remainder, accept
4. Loop until all spots are filled
Ranking Selection
Chance to breed based on order of fitness, not proportion
Pro: Easy to implement and understand
Con: Generally less accurate, less efficient, and
phase out diversity too quickly
Due to cons, not used often
Types:
Linear ranking selection
Truncate Selection
Linear Ranking Selection
1. Probabilities are set up for each rank
before fitnesses are even assessed
2. Individuals are ordered based on fitness
level
3. The predefined probabilities are
assigned to their rank
4. Individuals are selected based on the
probabilities
Truncate Selection
1. Candidates are put in order based on fitness
2. The top predefined percentage are chosen to reproduce
Tournament Selection
Individuals are pitted against each other in smaller brackets
The winner(s) of each bracket reproduces
Bracket participants only need to know fitness levels of others in bracket
No need for total or average population fitness factors
Good for situations when it is impossible or implausible to
calculate totals
Tournament Selection: Categories
Binary Tournament Selection
Larger Tournament Selection
Boltzmann Tournament Selection
Correlative Tournament Selection
Binary Tournament Selection
1. Two candidates are randomly selected out of
possible solutions
2. Candidate with best fitness factor is chosen
to reproduce
Larger Tournament Selection
1. More than two candidates are randomly selected out
of possible solutions
2. Candidate with best fitness factor is chosen to
reproduce
Only difference from Binary Tournament Selection is
number of candidates in each bracket
More candidates = higher selection pressure
Boltzmann Tournament Selection
N = temperature = variable describing number of differences in bit string
between two individuals
1. First candidate is chosen randomly
2. Second candidate is chosen as having exactly n differences in gene
string from first candidate
3. Third candidate is chosen
Half of the time has exactly n differences in gene string from first AND
second candidate (strict choice)
Other half of the time has exactly n difference in gene string from ONLY
first candidate (relaxed choice)
4. Choose the winner of the three to reproduce
Correlative Tournament Selection
Not so much a separate selection method as much as an extension of other
tournament selections
Once mating pool is selected, pairs are created based on how closely they
are related
Pairing similar individuals allows a better chance of passing on their
(probably) good similar trait
Gender Specific Selection
Genetic Algorithm with Chromosome Differentiation(GACD)
Restricted Mating
Correlative Family-based Selection
Genetic Algorithms with Chromosome Differentiation
Every individual has an extra 00 or 01 attached to their bit string
00 = female, 01 = male
When a male and female mate each parent randomly selects a bit to pass
onto the child
Females(00) can pass on 0 or 0
Males(01) can pass on 0 or 1
Hamming distance: the sum of the differences between each bit of two individuals
Ex: 00011111 and 11111111 have a hamming distance of 3.
Genetic Algorithm With Chromosome Differentiation
1. Males generated first randomly
2. Females created for each male with maximum hamming distance
3. Select individuals to put into mating pool by either:
Using a separate selection method for each sex
Or, lumping them together and using one selection method over all of them
4. Mate each individual in the mating pool twice
5. If there are fewer of one sex in the mating pool, mate leftovers with the
highest fitness individual of the opposite sex
Restricted Mating
In nature, different species cannot or will not mate
Restricted mating is based on species differentiations
Certain traits (predefined sections of the bit string) must be the same to
mate two candidates
Keeps several variations from converging to a local optimum
Correlative Family-based Selection
1. Two candidates are mated together twice
2. Between the two candidates and the two children, the most fit
solution is chosen
3. The hamming distance is calculated for each individual compared
to the other three
4. The individual with the highest hamming distance is also chosen
to reproduce
Genetic Relatedness Based Selection
Purpose is to search unexplored areas of the search space
Groups candidates based on similar fitness factors
Does not try to find most fit candidates
Includes:
Fitness Uniform Selection Scheme(FUSS)
Reserve Selection
Fitness Uniform Selection Scheme
Candidates with similar fitness factors are grouped together
Random numbers are generated from the range of minimum fitness to
maximum fitness
Candidates with fitnesses closest to the random number are selected
This gives a higher probability of selecting unexplored areas
Helps avoid local optimums
Reserve Selection
Candidates split into two categories
Non-reserved: Normal candidates with normal selection process applied
Reserved: Specific less fit candidates that are carried over from generation
to generation to keep variety in the population
Keeps pool out of local maximums
Elitism
Automatically carry over most fit individual to next generation
Extension of other selection methods
Makes sure best fit does not just get unlucky
Example: Selection
X
188
48
75
104
249
10
134
125
Binary x
10111100
00110000
01001011
01101000
11111001
00001010
10000110
01111101
Fitness
12596
9936
13500
15704
1494
2450
16214
16250
Gene pool
01111101
10000110
01101000
01001011
Given
y = -x^2 + 255x
0 ≤ x ≤ 255
Top half truncate selection
Crossover
Genes(bit strings) are combined from both parents to create offspring
Locus: the randomly generated point(s) at which each parent's bit string
is separated
Example: Crossover
Candidate
1
2
3
4
Gene pool
01111101
10000110
01101000
01001011
Locus
3
1
1
6
Parents
1, 2
2, 1
2, 3
3, 2
3, 4
4, 3
4, 1
1, 4
P1 String
011
100
1
0
0
0
010010
011111
P2 String
00110
11101
1101000
0000110
1001011
1101000
01
11
Offspring
01100110
10011101
11101000
00000110
01001011
01101000
01001001
01111111
Mutation in The Natural World
Brings diversity to a population
Without mutation, just different combinations of the same traits
Mutations happen when DNA is not copied properly
If the mutation has a benefit, or is just not a hindrance, it may be passed
on to new generations
Mutation in Genetic Algorithms
Purposely inject after crossover
Rate of mutation is decided beforehand
Ex: 1/2000th chance of mutation per bit
For every bit in a population, a random number is generated
If the probability hits, the bit is XOR'ed with 1
Example: Mutation
Given
mutation rate: 1/64
Pre-mutated
01100110
10011101
11101000
00000110
01001011
01101000
01001001
01111111
XOR
00000000
00000000
00000010
00000000
00000000
00000000
00000000
00000000
Offspring
01100110
10011101
11101010
00000110
01001011
01101000
01001001
01111111
Genetic Algorithms: End
Fitness threshold based
Each solution's fitness level is checked after each generation
If a given minimum fitness level is achieved, the algorithm finishes
running and outputs the maximum fitness candidate
Generation threshold based
Genetic algorithm runs for a predefined number of generations
Most fit solution over all generations is outputted
Uses of Genetic Algorithms
Optimal water network layouts
Facial recognition
Robotics
Trajectories for spacecraft
Fun with walking
Much More
Questions?