Transcript Genetic Algorithms

Genetic Algorithms


Introduction
Advanced
Simple Genetic Algorithms:
Introduction







What is it?
In a Nutshell
References
The Pseudo Code
Illustrations
Applications
Chinese Version of Introduction
Simple Genetic Algorithms:
Illustrations


An Illustration Based on Portfolio
Optimization
An Illustration Based on Facial Mask
Design
Simple Genetic Algorithms:
Applications

Portfolio Optimization
Genetic Algorithms: Advanced



Theory
Variants of Genetic Algorithms
Genetic Algorithms and Other Machine
Learning Tools
Variants of Genetic Algorithms




Adaptive Genetic Algorithms (AGA)
Niching Genetic Algorithms (NGA)
Interactive Genetic Algorithms (IGA)
Adaptive Genetic Algorithms
Father of GAs


Genetic algorithms were originally
developed by Holland (1975).
They are a class of adaptive search and
optimization techniques based on an
evolutionary process.
Chromosomes


By representing potential or candidate
solutions to a problem using vectors
consisting of binary digits or bits,
mathematical operations known as
crossover and mutation, can be performed.
These operations are analogous to the
genetic recombinations of the
chromosomes in living organisms.
Genetic Operation


By performing these operations,
generations of new candidates can be
created and evolved over time through an
iterative procedure.
However, there do exist restrictions on the
process of crossover so as to ensure that
better performing candidates are evolved
over time.
What is it?

Similar to the theory of natural selection or
survival of the fittest, the better performing
candidates have a better than average
probability of surviving and reproducing
relative to the lower performing candidates
which eventually get eliminated from the
population.
Fitness Function and Selection


The performance of each candidate can be
assessed using a suitable objective function.
A selection process based on performance
is applied to determine which of the
candidates should participate in crossover,
and thereby pass on their favorable traits to
future generations.
Process of Improvement


It is through this process of ``survival of
the fittest'' that better solutions are
developed over time.
This evolutionary process continues until
the best (or better) performing individual(s),
consisting of hopefully the optimal or near
optimal solutions, dominate the population.
Binary Strings


Binary representation is convenient but not
necessary for the application of the
recombination operations.
These vectors also known as strings, are
linear combinations of zeros and ones,
for example [0 1 0 0 1].
An Example

A binary representation
is based on the binary number system
which has a corresponding equivalent
decimal value given by
An Example

For example, the decimal equivalent of the
vector [0 1 0 0 1] is
=8+1=9
Selection Method



Rank-Based Selection
Roulette-Wheel Selection
Tournament Selection
Rank-Based Selection


The Reference
The Procedure
Reference

Whitley D. (1989), ``The GENITOR
Algorithm and Selection Pressure: Why
Rank-Based Allocation of Reproductive
Trials is Best, ’’ in: D. J. Schaffer (ed.)
Proceedings of the Third International
Conference on Genetic Algorithms,
Morgan Kaufmann, San Mateo, pp.116-121.
The Procedure

This approach involves ranking all
candidates according to performance and
then replacing the worst performing
candidates by copies of the better
performing candidates.
Crossover


The method by which promising (better
performing) candidates are combined, is
through a process of binary recombination
known as crossover.
One-Point Crossover
One-Point Crossover

To illustrate the process of crossover,
assume that two vectors
A = [1 0 1 0 0]
B = [0 1 0 1 0 ]
are chosen at random and that the position
of partitioning is randomly chosen to be
between the second and third elements of
each vector.
A = [1 0 | 1 0 0]
B = [0 1 | 0 1 0 ]
C = [1 0 | 0 1 0 ]
D = [0 1 | 1 0 0 ]
C = [1 0 0 1 0 ]
D = [0 1 1 0 0 ]
Mutation


Mutation involves the introduction of
random shocks into the population, by
slightly altering the binary representation of
candidates.
This increases the diversity in the population
and unlike crossover, randomly re-directs the
search procedure into new areas of the
solution space which may or may not be
beneficial.
Mutation


This action underpins the genetic
algorithms ability to find novel
inconspicuous solutions and avoid being
anchored at local optimum solutions.
Mathematically, this operation is
represented by switching a binary digit
from a one to a zero or vice versa.
Mutation


However, the probability of this occurrence
is normally very low, so as to not
unnecessarily disrupt the search process.
This operation can be illustrated by an
example.
An Example

Assume that the third element in vector C
undergoes mutation.
C = [1 0 0 1 0 ]
E = [1 0 1 1 0 ]

The genetic algorithm procedure can be
summarized by the following steps:






Create an initial population of candidates
randomly.
Evaluate the performance of each candidate.
Select the candidates for recombination.
Perform crossover and mutation.
Evaluate the performance of the new candidates.
Return to step 3, unless a termination criterion
is satisfied.
Termination Criteria


The last step in the genetic algorithm
involves checking a well-defined
termination criterion.
The termination criterion adopted, is
satisfied when either one of the following
conditions is met:
Termination Criteria



The population converges to a unique
individual.
A predetermined maximum number of
generations is reached.
There has been no improvement in the
population for a certain number.
In a Nutshell


The genetic algorithms, first proposed by
Holland (1975), seek to mimic some of the
natural evolution and selection.
The first step of Holland’s genetic
algorithm is to represent a legal solution of
a problem by a string of genes known as a
chromosome.
In a Nutshell


Then an initial population of chromosome
is generated randomly at the first
generation.
At each generation, the fitness of each
chromosome in the population is evaluated
by a fitness function.
In a Nutshell


The chromosomes with higher fitness have
a higher possibility to be selected to
produce offspring for the next generation.
After many generations of evolution, the
optimal solution of the problem is
hopefully be found in the population.
Goldberg (1989)

Goldberg D. E. (1989),
Genetic Algorithms in
Search, Optimisation,
and Machine Learning.
Addison-Wesley,
Reading.
Michalewicz (1996)

Michalewicz, Z.
(1996), Genetic
Algorithms + Data
Structures =
Evolution Programs,
Springer.
Vose (1999)

Vose M. D. (1999),
The Simple Genetic
Algorithm :
Foundations and
Theory (Complex
Adaptive Systems).
Bradford Books;
Genetic Algorithms and Other
Machine Learning Tools

Simulated Annealing