Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
COMP5400M Bio-Inspired Computing
Dr. Marc de Kamps
Lecture 5.2
Copyright By PowCoder代写 加微信 powcoder
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Reminder of the last lecture
Last time we introduced Genetic Algorithms or GA:
How biological evolution informed the desirable properties of
The need for variation, selection and heredity in the evolving population.
Variation arises when the offspring is ‘created’ from its parents (‘central dogma of molecular biology’).
Crossover and mutation inspired by DNA recombination.
How different problems may be represented (bit strings, etc.).
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Overview of today’s lecture
At the end of today’s lecture, you should be able to:
Appreciate some of the applications of GAs.
Understand fitness landscapes, and in particular their property known as ruggedness.
See how ruggedness relates to epistasis.
Understand in broad terms some of the factors affecting the
convergence of a GA.
I will also hand out the next item of coursework.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Genetic algorithms (GA) in practice
Coursework 2 Fitness landscapes and convergence Summary
Some applications Parallel GAs
History of GAs
Although attempts to design evolutionary algorithms go back as far as the 1950s (including von Neumann), two influential approaches were initiated in parallel in the 70s:
In 1975, pioneered the first GA as we now understand them1.
Hans- and developed evolutionary strategies in the 70s2.
Although strongly related, they differ in technical aspects (e.g. evolutionary strategies use real-valued candidate solutions).
1J.H. Holland, Adaptation in natural and artificial systems (MIT Press, 1975). 2e.g. H.-P Schwefel, von Computer-Modellen mittels der Evolutionsstrategie (Birkh ̈auser-Verlag, 1994).
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Genetic algorithms (GA) in practice
Coursework 2 Fitness landscapes and convergence Summary
Some applications Parallel GAs
Other related concepts are:
Evolutionary programming ( , 1960), where candidate solutions were encoded as finite state machines (i.e. simple computer programs).
Genetic programming ( , 1980s), where candidate solutions are Lisp trees.
GAs have ended up as the most popular technique but they do not exhaust the possibilities of the general idea of evolutionary computation.
GAs have also been used in the reverse direction to help understand natural evolution1.
1A. Livnat et al., Communications of the ACM 59, issue 11, p.84 (2016).
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Genetic algorithms (GA) in practice
Coursework 2 Fitness landscapes and convergence Summary
Some applications
Parallel GAs
GAs have been used to design a LEGO bridge using modified CAD
¥ ’s evolved Lego structures software, which was then built in reality:
Evolutionary Design I – p.25/29
This is just one of many GA projects from the :
http://www.demo.cs.brandeis.edu/pr/projects.html
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
An application
An application
Genetic algorit0h.5ms (GA) in practice Coursework 2 Fitness landscapes and convergence 1 Summary
Some applications
Parallel GAs
opulation Dispersion.
0 0.2 0.4 X 0.6 0.8 1
In Leeds there was a project to optimise the shape of airfoils,
Parameter Fig. 7. Pressure distribution of the optimum airfoils for inviscid and viscous cases using acceleration techniques.
which combined parallel computational fluid dynamics with GA:
0.5 0.4 0.3 0.2 0.1
0 -0.1 -0.2 -0.3 -0.4
pulation Concentration. Fig. 8. Unstructured grid around optimum airfoil.
A. Jahangirian and A. Shahrokhi, Computers and Fluids 46, 270 (2011).
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Excluded Region
Genetic algorithms (GA) in practice
Coursework 2 Fitness landscapes and convergence Summary
Some applications
Parallel GAs
Other applications include:
Drug Design: Unilever have used GA to develop new,
patented antimicrobials1.
Acoustics: Concert hall design matching ‘one of the best in
the world’2.
Scheduling: Aircraft landing software Ascent ‘raises
productivity by 30%’3. … and many others; see e.g.
www.talkorigins.org/faqs/genalg/genalg.html.
1B. Lemley, Machines that think, in Discover, Jan. 2001, p75. 2S. Sato et al., J. Sound Vibration 258, 517 (2002).
3J.E. Beasley et al., J. Operational Res. Soc. 52, 483 (2001).
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Genetic algorithms (GA) in practice
Coursework 2 Fitness landscapes and convergence Summary
Some applications Parallel GAs
GAs in parallel
It is usually easy to parallelise a GA:
Coarse-grained: Fine-grained:
The evaluation of each individual’s fitness is per- formed concurrently. Useful when this evaluation is computationally intensive.
‘Islands’ of sub-populations are evolved in parallel, with occasional migration between them.
Large number of small domains in a spatial popu- lation. Useful for massively parallel hardware such as GPUs (graphics cards).
Given the ongoing and seemingly never-ending trend towards parallel hardware, GAs should become increasingly competitive compared to less parallelisable optimisation schemes.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Notes for the second item of coursework
Coursework 1
The second item of coursework will give you some hands-on experience with a GA, applied to an agent-based model.
Uses the BEAST package, which you will need to download and build (instructions on the VLE).
Written in C++, but you only need to make small modifications (the coursework guidance highlights where).
Definitely works on the School machines; you may be able to install on your own machine (requires wxWidgets).
The GA is already encoded, and uses the Roulette-wheel selection criterion (i.e. stochastic selection, with a probability that is proportional to the fitness; see last lecture).
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Notes for the second item of coursework
[Also has implementations of some of the ‘ant’ algorithms we discussed in week 2]
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Notes for the second item of coursework
You are asked to modify various aspects of the model, and analyse/interpret your findings.
In particular, to try out different definitions of fitness, and observe and interpret what happens.
It may help to look over the swarm intelligence lectures from week 2.
Tasks 5 and 6 focus on co-evolution, which we will cover next week.
15% of the final module grade.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Landscapes in nature and GAs
Types of fitness landscape Epistasis and ruggedness Convergence
Fitness landscapes
Fitness landscapes were introduced by in 1932 to help visualise and model evolution.
Each individual has a fitness, however defined (e.g. number of grandchildren).
Over time, the population evolves so as to increase its fitness.
If we plotted fitness vs. genotype, we expect the population to
be a ‘cloud’ of points that moves ‘uphill.’
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Landscapes in nature and GAs
Types of fitness landscape Epistasis and ruggedness Convergence
Fitness landscapes for GAs
GAs are normally seeded at random.
Individuals will be scattered all over the landscape.
Low fitness individuals ‘die,’ those with high fitness reproduce.
With only mutation, offspring will always be similar to its parent. Individuals ‘diffuse’ over the surface until they merge.
They will be similar in genotype, i.e. low diversity.
In danger of becoming ‘stuck’ around a non-optimal genotype.
With crossover between two parents, offspring can inherit very different attributes.
They can ‘jump’ (non-randomly) around search space. Their fitness should still be high.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Landscapes in nature and GAs
Types of fitness landscape
Epistasis and ruggedness Convergence
Types of landscape
There are many different types of landscape, which effect how a GA or a real species evolves.
Types of landscapes for search
A simple one is the so-called ‘Mt. Fuji’ landscape, which is smooth
¥ What kinds of landscapes are there? with a single global optimum.
¥ Which ones are easy for a GA to search?
Easy to improve at each generation, even with just mutation.
“Mt. Fuji” landscape
This landscapeDri. sMasrcmdeoKoamthps.
ItCwOMilPl54b00eMeBaio-sInyspirfeod rCoampuGtinAg to
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Landscapes in nature and GAs
Types of fitness landscape
Epistasis and ruggedness Convergence
This landscape is smooth. It will be easy for a GA to
suboptimal solution.
Evolutionary Design II – p.7/38
“Mt. Fuji” landscape
Rugged landscapes are less smooth, and have multiple local
maxima that are not the global maximum.
If only small changes in the candidate solutions are allowed
improve in each generation.
(e.g. mutation), the population can get ‘stuck’ around a
If large ‘jumps’ are also allowed (e.g. cross-over), they will explore more candidate solutions and may find the global
Types of landscapes for search
Moderately rugged landscape
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
This landscape is somewhat rugged, but mutation and
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Landscapes in nature and GAs
Types of fitness landscape
Epistasis and ruggedness Convergence
For a highly rugged landscape, it may be impossible to find the
Types of landscapes for search
global optimum …
Highly rugged landscape
… aTlthoisuglahntdhsicsaspcheeimsaetxictrmemayelbyermugisglead,inagn:dFtihtneeGssAdempeanyds on manbyepuanrambeletetros,fisnodthtehelagnldosbcapleopistihmiguhmd.imensional, with many saddles that can facilitate slow improvements.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Landscapes in nature and GAs
Types of fitness landscape
Epistasis and ruggedness Convergence
Search spaces
The search space is the space over which candidate solutions may vary.
For the pizza example from last lecture, the search space has one dimension for each ingredient.
For a GA to work, the fitness function should ideally be locally correlated on the search space, i.e. nearby values in search space should have similar fitnesses.
This means similar candidate solutions should be ‘almost as good’ (or bad) as each other.
For the pizza example, if base+ham+onions scores well, so should base+ham+onions+olives, as well as base+ham.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Landscapes in nature and GAs Types of fitness landscape Epistasis and ruggedness Convergence
Epistasis in biology refers to interactions between genes, so that a property of the phenotype depends upon multiple genes.
In GAs, this means changing one component of a candidate solution might drastically change its fitness (because this changes multiple aspects of the solution’s performance at once).
It is therefore less locally correlated, i.e. more rugged.
For pizza example, this could happen if e.g. anchovies=good,
chillies=good, but anchovies+chillies=bad.
has theoretically explored the effect of ruggedness on evolution with his NK landscapes, and concluded that GAs deal with epistasis quite well1.
1S. Kauffman, The Origins of Order (OUP, 1993).
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Landscapes in nature and GAs Types of fitness landscape Epistasis and ruggedness Convergence
From Wikipedia. You do not need to understand additive or epistatic for this course.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Landscapes in nature and GAs Types of fitness landscape Epistasis and ruggedness Convergence
Convergence of GAs
GAs may be appealing, but how to they compare to other, simpler optimisation methods?
Consider the random restart hill climber:
1. Choose a single random solution.
2. Generate one mutated offspring (no crossover).
3. If the mutant is ‘better’ (i.e. has higher fitness) than the parent, it replaces the parent. Goto step 2.
4. If there are no improvements after N attempts, go back to step 1.
5. The final solution is the best one found throughout the whole process.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Landscapes in nature and GAs Types of fitness landscape Epistasis and ruggedness Convergence
Ironically, the simple random restart hill climber actually outcompetes GAs on many test problems.
However, GAs perform well in real-world problems, such as the applications mentioned earlier.
The reason is that ‘real’ fitness landscapes often have a hierarchy that model systems do not always have.
Broad peaks containing many smaller peaks, each of which contain many even smaller peaks, each of which …
The combination of crossover and mutation allows GAs to both explore and move uphill on such landscapes, at least for moderately rugged landscapes.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Landscapes in nature and GAs Types of fitness landscape Epistasis and ruggedness Convergence
Earlier we stated that GAs can become ‘stuck’ around sub-optimal solutions. This is known as premature convergence, and is inevitable even with crossover (eventually).
Analysis of real-world problems has revealed extensive neutral networks
Set of solutions with the same fitness related by mutations.
The population ‘cloud’ of solutions eventually comes to move
on a particular neutral network.
Fitness improvements occur when a mutation reveals a way up to another network of higher fitness.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Overview Genetic algorithms (GA) in practice Coursework 2 Fitness landscapes and convergence Summary
Today we have
Overviewed the history of GAs, and some their applications.
Tried to provide intuitive understanding in terms of fitness landscapes.
Seen how ruggedness may affect the convergence to the optimal solution.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com