Metaphor
Geneticalgorithmisasearchmethodthatisinspiredbythe process of natural evolution.
Itislikeotherlocalsearchmethods,butthemaindifferenceis population‐based search, where solutions with higher fitness in the population have better chance to survive and produce offspring.
NATURAL EVOLUTION
PROBLEM SOLVING
Individual Fitness Environment Generation
Candidate Solution Quality Problem Iteration
Algorithm Procedure
But first we need to know how to represent a solution!
Designing a Representation
Usuallyanindividual(phenotype)ingeneticalgorithmis represented as a genotype.
Therearemanywaystodothisandthewaywechoosemust be relevant to the problem that we are solving.
Whenchoosingarepresentation,weneedtobearinmindhow the genotypes will be evaluated and what the genetic operators (i.e. crossover and mutation) might be.
Binary Representation
Binaryencodingisacommonlyusedrepresentation. Whatcanthefollowing8‐bitgenotyperepresent?
CHROMOSOME
Phenotype: • Integer
GENE
• Real Number • Subset
• …
Binary Representation for integer numbers
Genotype: Phenotype: = 163
1*27 + 0*26 + 1*25 + 0*24 + 0*23 + 0*22 + 1*21 + 1*20 = 128 + 32 + 2 + 1 = 163
Binary Representation for real numbers
Example:minimise variable is
,wherethedomainofthe
Genotype:
Phenotype: = 14.0059
.
Other Representations
Realnumberrepresentation:directlyuserealnumbersto represent solutions; in this case there is no difference between genotype and phenotype.
For the above example of minimising 4 , ∈ 2.5, 20.5, we can directly consider the real number of in genetic algorithm (as long as we can come up with variation operators for it).
Ordinalrepresentation:usepermutationstorepresentsolutions; suitable for ordering/sequencing problems
Example: Travelling Salesman Problems (TSPs), every city gets a unique number from 1 to n. A solution can be (5, 1, 2, 3, 4).
Need special variation operators to make sure solutions stay valid permutations.
Component – Population Initialisation
Population Initialisation
Inmostcases,sampleuniformly from the search space, e.g.:
Example: minimise 1 ,wherethedomainof
Binary representations: 0 or 1 with probability 0.5;
the variable is [0, 3]. 1011
Real‐valued representations: uniformly on a given interval.
Seedthepopulationwithexisting results (e.g. from some approximation methods in TSP); but we may avoid premature convergence.
0110 0001 1010
Population Evaluation
Evaluate individuals (based on the objective function) and assign fitness to them.
Example: minimise
1 , where the domain of
Individuals’ fitness can be their objective values for single‐objective problems.
the variable is [0, 3]. 1011
For multi‐objective problems, one needs to design very different fitness assignment methods.
0110 0001 1 0 1 0
Can be expensive in some real‐world scenarios like in black‐box simulator e.g., complex software systems and car engine calibration.
Solution1: 2.2, Solution2: 1.2, Solution3: 0.2, Solution4: 2.0
1.44 0.04 0.64
1.0
Selection
Selection(ormatingselection)istoselectsolutionsfromthe population to produce offspring based on their fitness.
Thebasicprincipleisthatwewanttogivebettersolutionshigher chance to produce offspring, but also to give less good solutions at lest some chance (they may include some useful genes).
Roulettewheelselection:probability of solution being selected is
,
where _ is the sum of the fitness of all solutions. For maximisation problem, the fitness of a solution can be its objective value; for minimisation problem the fitness can be 1 for example.
Selection
Selection(ormatingselection)istoselectsolutionsfromthe population to produce offspring based on their fitness.
Thebasicprincipleisthatwewanttogivebettersolutionshigher chance to produce offspring, but also to give less good solutions at lest some chance (they may include some useful genes).
Tournamentselection:Pick
solutions (e.g., ) from
the population, select the best
one for mating; repeat this
times, so solutions are in M mating pool.
ELFD
G
Population
B H ACMN
C
F
Contestants (k=3)
F
Winner
Crossover
Crossover(alsocalledrecombination)isageneticoperatorusedto combine the genetic information of two parents to generate new offspring. It is usually applied with a high probability, e.g. .
Therearemanycrossoveroperators:
Parents
0110 0001
Single-point crossover
0 1 1 1 0000
Offspring
Binary representation: single‐point crossover, k‐point crossover, uniform crossover
Real‐valued representation: single‐point crossover, simplex crossover, simulated binary crossover
Mutation
Mutationisageneticoperatorusedtomaintaingeneticdiversity by altering one or more gene values in a chromosome. It is usually applied with a very low probability, e.g. .
Itshouldbedesignedinsuchawaythateverypartofthesearch space can be reached.
Therearedifferentmutationoperators:
Parent
Bit flip
0 1 1 1 mutation 0 1 0 1 Offspring
Binary representation: bit flip mutation
Real‐valued representation: Gaussian mutation, polynomial mutation
Population Updating
Populationupdating(orenvironmentalselection)istoupdatethe old population by newly‐produced solutions.
Elitism:bestsolutionshouldalwaysbekept.
Therearedifferentmethods(esp.formulti‐objectiveoptimisation),
one of which is purely based on fitness.
Old population 1.44 1 0 1 1
Newly produced individuals
New population
0.04 0 1 1 0 0.64 0 0 0 1 1.0 1 0 1 0
1.0 0 0 0 0 3.24 1 1 1 0 0.36
0.0 0 1 0 1
0 1 0 1
0 1 1 0 0 0 1 0 0010 0001
Stopping Criterion
Optimumisreached.
Givenamountoftime,ormaximumgenerations.
Aftersomegenerations,thereisnoimprovementonthe population’s quality.
Donotdrawanyconclusionfromasinglerundueto randomness nature of genetic algorithm (initialisation, selection, crossover and mutation):
Runthealgorithmasufficientnumberofindependent times, e.g. 30 runs.
Usestatisticalresultstoevaluatethealgorithm,e.g. mean and standard deviation.
Applications
Itcanbeappliedtovariousproblems,wheretheoptimal solution cannot be derived analytically (e.g. by math programming methods) or be obtained in reasonable time (e.g. by exhaustive search like DFS and A*).
Domains:
Numerical, Combinatorial Optimisation
System Modeling and Identification
Planning and Control
Engineering Design
Data Mining
Machine Learning
Artificial Life
Applications
Softwareengineering
Schedulingincouldcomputing
Automatedproductdisassembly
Emergencyreliefsupplydistribution
Creatingunexpectedpatternsinart
Neuralarchitecturesearch
Reinforcementlearningforvideogames