Basic Idea Of Principle Of Natural Selection
“Select The Best, Discard The Rest”
An Example of Natural Selection:
Rabbits are fast and smart
Some of them are faster and smarter than other rabbits. Thus, they are less
likely to be eaten by foxes.
They have a better chance of survival and start breeding.
The resulting baby rabbits (on average) will be faster and smarter
Now, evolved species are more faster and smarter
Genetic Algorithms Implement Optimization Strategies By Simulating Evolution Of
Species Through Natural Selection

70 trang |

Chia sẻ: thanhle95 | Lượt xem: 381 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu **Bài giảng Máy học nâng cao - Chương 14: Genetic Algorithm - Trịnh Tấn Đạt**, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên

Trịnh Tấn Đạt
Khoa CNTT – Đại Học Sài Gòn
Email: trinhtandat@sgu.edu.vn
Website: https://sites.google.com/site/ttdat88/
Contents
Introduction: Genetic Algorithm (GA)
GA Operators and Parameters
Example
Homework
Introduction
History Of Genetic Algorithms
“Evolutionary Computing” was introduced in the 1960s by I.
Rechenberg.
John Holland wrote the first book on Genetic Algorithms
‘Adaptation in Natural and Artificial Systems’ in 1975.
In 1992 John Koza used genetic algorithm to evolve programs to
perform certain tasks. He called his method “Genetic Programming”.
What Are Genetic Algorithms (GAs)?
GAs are search and optimization techniques based on Darwin’s Principle
of Natural Selection and Genetic Inheritance.
A class of probabilistic optimization algorithms.
Widely-used in business, science and engineering.
Basic Idea Of Principle Of Natural Selection
“Select The Best, Discard The Rest”
An Example of Natural Selection:
Rabbits are fast and smart
Some of them are faster and smarter than other rabbits. Thus, they are less
likely to be eaten by foxes.
They have a better chance of survival and start breeding.
The resulting baby rabbits (on average) will be faster and smarter
Now, evolved species are more faster and smarter
Genetic Algorithms Implement Optimization Strategies By Simulating Evolution Of
Species Through Natural Selection
Classes of Search Techniques
Fibonacci
Search Techniques
Calculus Base
Techniques
Guided random search
techniques
Enumerative
Techniques
BFSDFS Dynamic
Programming
Tabu Search Hill Climbing Simulated
Anealing
Evolutionary
Algorithms
Genetic
Programming
Genetic
Algorithms
Sort
Nature to Computer Mapping
GAs use a vocabulary borrowed from nature genetics
Nature Computer (GAs)
Population Set of solutions
Individuals in environment Solutions to a problem
Individual’s degree of adaptation to its
surrounding environment
Solutions quality (fitness function)
Chromosome Encoding for a Solution
Gene Part of the encoding of a solution
Selection, crossover and mutation in
nature’s evolutionary process
Stochastic operators
Working Mechanism Of GAs
Simple Genetic Algorithm
Simple_Genetic_Algorithm()
{
Initialize the Population;
Calculate Fitness Function;
While(Fitness Value != Optimal Value)
{
Selection;//Natural Selection, Survival Of
Fittest
Crossover;//Reproduction, Propagate favorable
characteristics
Mutation;//Mutation
Calculate Fitness Function;
}
}
Designing GAs
⚫ How to represent chromosomes?
⚫ How to create an initial population?
⚫ How to define fitness function?
⚫ How to define genetic operators?
⚫ How to generate next generation?
⚫ How to define stopping criteria?
GA Operators and Parameters
Search Space and Population
The search space S is the finite set of possible solutions.
Each solution x S is called an individual
Population of size N is a subset of search space S.
Start with a population of randomly generated individuals, or use
A previously saved population
A set of solutions provided by a human expert
A set of solutions provided by another heuristic algorithm
Representation (Encoding)
The process of representing the solution in the form of a string (chromosome)
that conveys the necessary information.
Just as in a chromosome, each gene controls a particular characteristic of the
individual
Similarly, each bit in the string represents a characteristic of the solution.
Binary Encoding
Binary Encoding
Binary Encoding – Most common method of encoding. Chromosomes are
strings of 1s and 0s
In classic genetic algorithms, binary strings of fixed length m are used.
In order to be able to encode each solution of the search space S in a one-to-one
way, the inequality
For example, we have S={1,2,,15}. Choose m = 4 to represent 15
chromosomes
||2 Sm
1621528 43 ==
Value Encoding
Every chromosome is a string of some values.
Values can be anything connected to problem, form numbers, real
numbers or chars to some complicated objects.
Permutation Encoding
Permutation encoding can be used in ordering problems, such as
travelling salesman problem or task ordering problem.
In permutation encoding, every chromosome is a string of numbers,
which represents number in a sequence.
Tree Encoding
Tree encoding is used mainly for evolving programs or expressions,
for genetic programming.
In tree encoding every chromosome is a tree of some objects, such as
functions or commands in programming language.
Fitness function
A fitness value is assigned to each solution depending on how close it actually is
to solving the problem.
A fitness function is a nonnegative function f
A fitness function quantifies the optimality of a solution (chromosome) so that particular solution
may be ranked against all the other solutions.
f : S → R
Genetic Operators
Reproduction (Selection)
Copy existing chromosomes, chosen at random, to the new population.
Recombination (Crossover)
Create new chromosomes by recombining randomly chosen substrings
from existing chromosomes.
Mutation
Create a new chromosome from an existing one by performing small
random changes.
Selection
The primary objective of the selection operator is to emphasize the good
solutions and eliminate the bad solutions in a population, while keeping the
population size constant.
“Selects The Best, Discards The Rest”.
Identify the good solutions in a population.
Make multiple copies of the good solutions.
Eliminate bad solutions from the population so that multiple copies of good
solutions can be placed in the population
The process that determines which solutions are to be preserved and allowed to reproduce and
which ones deserve to die out
Random Selection
Chromosomes are randomly selected from the population to be parents
to crossover.
Roulette Wheel Selection
Roulette Wheel Selection (fitness-proportional selection; stochastic sampling with replacement)
is an instance of a reproduction operator:
Strings that are fitter are assigned a larger slot and hence have a better chance of appearing in
the new population.
For example, after spinning 4 times, we have new population {2,4,2,1}
Rank Selection
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).
Elitism
When creating new population by crossover and mutation, we have a big
chance, that we will loose the best chromosome.
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
Tournament Selection
In K-Way tournament selection, we select K individuals from the
population at random and select the best out of these to become a parent.
Survivor Selection
The Survivor Selection Policy determines which individuals are to be
kicked out and which are to be kept in the next generation
Some GAs employ Elitism.
Age Based Selection
We don’t have a notion of a fitness
Each individual is allowed in the population for a finite generation where
it is allowed to reproduce, after that, it is kicked out of the population no
matter how good its fitness is.
Fitness Based Selection
The children tend to replace the least fit individuals in the population
Crossover
After selection, a specified percentage pc of chromosomes
in the mating pool P'(t) is chosen at random.
The selected chromosomes are mated at random, and each
pair of parents undergoes a crossover operation.
It is the process in which two chromosomes (strings) combine their genetic material (bits) to
produce a new offspring which possesses both their characteristics.
The cross-over probability pc is
another parameter of the genetic
algorithm.
Typical values are
between 60% and 90%.
One-point Crossover
A random point is chosen on the individual chromosomes (strings) and the
genetic material is exchanged at this point.
Two-Point Crossover
Two random points are chosen on the individual chromosomes (strings) and the
genetic material is exchanged at these points.
Chromosome1 11011 | 00100 | 110110
Chromosome 2 10101 | 11000 | 011110
Offspring 1 10101 | 00100 | 011110
Offspring 2 11011 | 11000 | 110110
Uniform crossover
Bits are randomly copied from the first or from the second parent
Arithmetic crossover
Some arithmetic operation is performed to make a new offspring
Tree crossover
Partially Matched Crossover (PMX)
Used in Permutation Encoding
Crossover
Crossover between 2 good solutions MAY NOT ALWAYS yield a better or as
good a solution.
However, parents are good probability of the child being good is high.
If offspring is not good (poor solution), it will be removed in the next iteration
during “Selection”.
Mutation
After crossover, a specified percentage pm of genes in the
pool P’’(t) is chosen at random.
A selected parent chromosome undergoes a mutation.
It is the process by which a string is deliberately changed so as to maintain diversity in the
population set.
The mutation probability pm is another parameter
of the genetic algorithm.
Typical values are below 1%.
Mutation
The classical mutation operator is the Bit-flip Mutation
Advantages Of GAs
Global Search Methods:
GAs search for the function optimum starting from a population of
points of the function domain, not a single one.
This characteristic suggests that GAs are global search methods.
Hill climbing (gradient descent - ascent) method
A new point is selected from the neighborhood of the current point based on
its fitness value.
local
global
GAs
I am not at the top.
My high is better!
I am at the top
Height is ...
I will continue
few microseconds after
Advantages Of GAs
Exploitation and Exploration:
Exploiting the best solutions
Takes the current search information from the experience of the last search to guide the
search toward the direction that might be close to the best solutions.
From Selection operator and Crossover operator.
Exploring the search space
Widens the search to reach all possible solutions around the search space.
From Mutation operator and Crossover operator.
Important task: GAs can balance exploitation and exploration.
Too high exploitation leads to premature convergence
Too high exploration leads to non-convergence and to no fitter solution.
Hill climbing only exploits the best solution. It neglects exploration of search
space.
Advantages Of GAs
Blind Search Methods
GAs only use the information about the fitness function to solve the
optimal problem
GAs use probabilistic transition rules
This makes them more robust and applicable to a large range of
problems.
GAs can be easily used in parallel machines
Reduce computation cost significantly.
Applications Of GAs
Optimal problems
Wire routing
Scheduling
Adaptive control
Game playing
Database query optimal
Feature selection
GA Examples
Maximum of Function
Let’s consider a function f
Problem: find x0 such that
First derivative
1)10sin()( += xxxf
]2,1[),()( 0 − xxfxf
0)10cos(10)10sin()(' =+= xxxxf
−−=
+
=
=
=
−
=
...2,1,
20
12
0
...2,1,
20
12
0
i
i
x
x
i
i
x
i
i
For x19=1.85, f(x19)=2.85
GA Examples
How GAs can solve this problem ?!?
Representation (convert real numbers to chromosomes)
Using binary vectors as a chromosome
Length of chromosome m=22
The mapping from a binary string into a real number x from [-1, 2]
is given by
2-1
3*106 real numbers
For example, a chromosome
GA Examples
Initial population
Create randomly population, each chromosomes v is a binary string of 22 bits
Fitness function: eval(v)=f(x),
1)10sin()( += xxxf
v3 is the best of three chromosomes
GA Examples
Mutation
Crossover
x3’=1.721 and f(x3’)=-0.0822
x3’’=1.630 and f(x3’’)=2.343
On the other hand
These offspring evaluate to
The second offspring has a better evaluation than both of its parents
f(v2)= 0.0788
f(v3)= 2.2506
GA Examples
Assume that pop_size=50, pc=25% and pm=1%
After 150 generations, we have
GA Examples
Traveling Salesman Problem (TPS)
The travelling salesman must visit every city in his territory
exactly once and then return back to the starting point.
Given the cost of travel between all cities, how should he plan
his itinerary for minimum total cost?
Cost = {money, distance, time,.}
GA Examples
Binary Representation
GA Examples
Why we cannot use binary string
Fail!
Alternative:
• Look for the most natural expression of the problem.
• Create genetic operators that avoid building illegal chromosomes
Nonbinary Representation
GA Examples
Swap Mutation
The following mutation operator is adapted to the path representation:
GA Examples
Why we cannot use single-point crossover
Fail!
GA Examples
PMX-Crossover
Also Partially Matched Crossover (PMX) avoids building illegal chromosomes:
How Do GAs Work?
Maximize a function of k variable, f(x1,,xk), where xi [ai,bi], and
f(x1,,xk)>0 for all xi.
Representation (binary string)
We divide [ai,bi] into (bi-ai)*10
4 equal size ranges
For each xi → binary string of length mi satisfies
To represent real value of a binary string
Thus, each chromosome is represent by a binary string of length
(bi-ai)*10
4 2mi - 1
v=(string1 string2stringk)
GA Examples
Selection (Roulette wheel selection)
GA Examples
Crossover(pc is probability of crossover)
Mutation (pm is probability of mutation)
For example, maximize the function
[-3, 12.1] → 15.1*104 equal size ranges
x1 → binary string of length 18
[4.1, 5.8] → 1.7 *104 equal size ranges
x2 → binary string of length 15
GA Examples
The total length of a chromosome is m=18+15=33 bits
GA Examples
Assume population of size (pop_size) equals 20. All 33 bits in all
chromosome are initialized randomly
Choose q11 and q4 ,etc.
New population
Crossover with pc=2.5%. If r < 0.25, we select a given chromosome of crossover
The chromosome v2’, v11’, v13’ and v18’ were selected for crossover
Mutation with pm=1%. We have 33*20=660 bits, we expect (on average) 6.6 mutation per generation.
Generate 660 random numbers r , if r < 0.01, we mutate the bit
After applying crossover and mutation, we have a new population
New population Old population
Conclusion
Genetic Algorithms (GAs) implement optimization strategies based on simulation of
the natural law of evolution of a species by natural selection
The basic GA Operators are:
Encoding
Selection
Crossover
Mutation
GAs have been applied to a variety of function optimization problems.
GA s have been shown to be highly effective in searching a large, poorly defined search
space even in the presence of difficulties such as high-dimensionality, discontinuity and
noise.
Homework
1) We're going to optimize a very simple problem: trying to create a list of N
numbers that equal X when summed together.
EX1: N = 5 ; X = 8 ; one solution is [2, 0, 0 ,4, 2]
EX2: N = 5 and X = 200, then these would all be appropriate solutions.
lst = [40,40,40,40,40]
lst = [50,50,50,25,25]
lst = [200,0,0,0,0]
Ref : https://lethain.com/genetic-algorithms-cool-name-damn-simple/
Homework
2) Uses a genetic algorithm to maximize a function of many variables
Ex 1 : Consider the function: z = f(x,y) -x^2+2x-y^2+4y
Find (x*,y*) to z is maximum
Ref:
https://github.com/philipkiely/floydhub_genetic_algorithm_tutorial/blob/mast
er/geneticmax.py
Ex 2: The equation is shown below:
Y = w1x1 + w2x2 + w3x3 + w4x4 + w5x5 + w6x6
Given inputs values are (x1,x2,x3,x4,x5,x6)=(4,-2,7,5,11,1). Find the parameters
(weights) that maximize such equation
Ref: https://towardsdatascience.com/genetic-algorithm-implementation-in-
python-5ab67bb124a6
Homework
3) Evolution of a salesman
Ref : https://towardsdatascience.com/evolution-of-a-salesman-a-complete-
genetic-algorithm-tutorial-for-python-6fe5d2b3ca35