COMP5400M Bio-Inspired Computing
Dr. Marc de Kamps
Lecture 5.1
Dr. Marc de Kamps
Copyright By PowCoder代写 加微信 powcoder
COMP5400M Bio-Inspired Computing
Reminder of the lectures up until now
So far in this course we have looked at multiple examples of bio-inspired computing:
Swarm intelligence, i.e. ‘ant’ algorithms to reduce traffic congestion.
Artificial neural networks inspired by real neurons; so far: How a single perceptron can be used as a linear classifier. How multi-layer perceptrons can tackle more general
Throughout we have repeatedly emphasised the advantages of bio-inspired solutions over engineered ones, i.e. their robustness, adaptability etc.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Overview of the next few lectures
Although we will return to consider more advanced artificial neural networks later in the course, for the next few lectures we will look at another computational application of a biological concept: Genetic Algorithms or GAs.
We can evolve algorithms to solve complex problems, without necessarily understanding how they work.
Somewhat similar to how we train artificial neural networks, without needing to understand what the weights represent.
How they are constructed, mimicking known biological processes.
Their strengths and limitations, and some successful applications.
Co-evolution of two or more ‘species.’
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Natural Evolution
Although some of the ideas that we now associate with evolution were around prior to its publication, the enduring, most compelling case was made by in this book ‘On the origin of species by the means of natural selection’ (1859)1.
This argued that the complex organisms we now observe have arisen from a series of incremental adaptations to changing environments, where the environment includes other organisms that are also evolving (which is known as co-evolution).
This process was named natural selection: Nature ‘selects’ which organisms prosper and reproduce, and which die without offspring.
1Full text available free: www.talkorigins.org/faqs/origin.html
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
However, evolution occurs even without natural selection:
Domestication of animals arose from humans selecting which individuals to breed, based on their characteristics.
The first chapter of Darwin’s book, Variation under Domestication, discussed exactly this process.
Anti-microbial resistance results from (uncontrolled) use of antibiotics/antimicrobials, which favours the spread of mutants of microbes that are resistant to these treatments.
They are doing this far faster than we can design new antiomicrobials, potentially resulting in the ‘end of the antibiotic era.’
Cancer drugs also drive the growth of mutant tumour cells that are resistant.
Combination therapy aims to kill all tumour cells before they evolve resistance to each drug.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
As envisaged by Darwin, evolution requires a population of replicating individuals with the following three features:
Variation: Selection: Heredity:
Not all individuals are the same; there is some ran- dom variation present.
Not all individuals survive to reproduce, and some reproduce more than others.
Individuals tend to be like their parents.
Darwin assumed that the variation happened at birth; however, in his time it was not known how heredity information was passed from parent to child, nor where variation came from.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Variation Selection Heredity
Image from , University of Leeds.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
e bare essentials
In 1866 an Augustinian friar called published experiments on vegetables that demonstrated information was passed down the generations in atoms of hereditary information, what we now call genes.
These are known as the laws of Mendelian inheritance.
Not widely known at the time, and was rediscovered multiple
times some three decades later.
Mendelian inheritance was combined with Darwinian evolution
in the 1940’s to produce the Modern Synthesis.
In 1953, , , and others discovered that DNA was a double helix of nucleotides A, T, C and G which paired (A ↔ T, C ↔ G).
Three nucleotides code for a single amino acid, the building blocks of the proteins from which organisms are made.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Central dogma of molecular biology
The central dogma of molecular biology was first stated by (1958), and essentially says that the information in DNA is mapped onto proteins (and, eventually, bodies), but that the reverse process is not possible.
An alternative proposed by Jean- (18091), is that characteristics acquired by an organism during its life are passed to its offspring.
This has since been discredited (although Lamarck did get a lot of other things right).
This means variation must come from the point of conception, i.e. when the DNA of the organism is first formed.
1The year Darwin was born!
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Diploid organisms like us inherit two sets of chromosomes from our parents; e.g. humans have 23 pairs1.
The process by which each parent’s chromosome is merged to form the child’s chromosome pairs is known as recombination. This involves a random crossover of the genetic material, i.e.
https://rokus01.wordpress.com/category/chromosomes/
1For comparison, bacteria are haploid and only have a single chromosome.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Crossover and mutation
The points at which chromosomes cross over are random, so crossover is a source of variation. However, it is not a source of novelty as it can only ‘shuffle’ the initial information around.
There are also random mutations which are capable of generating entirely new information.
These can be caused by copying errors.
Radiation and some chemicals can also cause mutations. Also biological mechanisms.
The simplest mutation, known as the point mutation, changes one of the DNA nucleotides (A,T,C,G) from one type to another type.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Biological to virtual evolution … ?
Since evolution has generated many very complex and highly adapted organisms on Earth, can we harness it to apply to problems of interest to us? Conversely, can modelling it help us better understand how our biosphere came to be?
Biological evolution suggests we will need the following ingredients:
Heredity: Information, whatever it represents and however it is stored, is passed from ‘parent(s)’ to their ‘offspring.’
Variation: Crossover and mutation when the offspring’s chromo- some(s) are first formed.
Selection: How to select between individuals so that those that are ‘good’ (in some sense) produce the most offspring.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
fit solutions are used to produce new solutions,
Examplew:iEthvosolvminegdpeigzzreae of random variation.
Evolutionary Design I – p.7/29
Suppose a pizza chef wants to find an ‘optimal’ pizza recipe, and decides to cook many variations and ask customers to rate them.
Evolving pizza
The pizzas have up to ten ingredients, each of which can be
included or not, so a single recipe can be represented by a string of 10 binary digits or bits:
An example to illustrate how GAs work.
Cheese Ham Pepperoni Chillies Mushrooms
Base Tomato Onion Anchovies Olives sauce
A pizza chef wants to find his “optimal” pizza recipe.
How should the chef go about finding the customers’ favourite?
Custome10rs will give numerical ratings for the pizzas Cook all 2 = 1024 possibilities? Cook some random selection?
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
The pizzas have up to 10 ingredients: we can specify a specific pizza recipe with a string of 10 binary digits.
The GA (Genetic Algorithm) strategy
1. Make a random batch of (say) 20 pizzas, perhaps by tossing a coin for each ingredient.
2. Send the 20 pizzas out and record the customer ratings.
3. To make the next batch of 20:
3.1 Take the the two that did the best in the last batch.
3.2 Cross them over at a random point to make two new recipes.
3.3 Repeat the random crossover until you have 20 new recipes.
3.4 Occasionally make an arbitrary change, such as leaving out
mushrooms or adding onions.
4. Go back to step 2 until ‘happy.’
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
and asexual reproduction in nature.
}Two good solutions
Randomly determined crossover point
}Two offspring solutions
Evolutionary Design I – p.1
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Components of a genetic algorithm
A population of individuals, solutions, recipes etc.
A mapping from the coded information (the bit string) to the ‘organism’ (pizza etc).
In biology, the information in the DNA is known as the genotype, and the resulting organism’s form is known as its phenotype.
Some way to evaluate the success of each individual. This is usually referred to as its fitness.
The selection procedure itself (who has offspring?).
The introduction of variation in the offspring (crossover and mutation).
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Population of individuals
What does an ‘individual’ actually look like?
Requires some sort of data structure.
The pizza example used a bit string, which is popular.
However, real-valued data can also be used, as can almost any other data type.
How big does the population need to be?
Too large and it will take a long time to evaluate the fitnesses of each individual, slowing down the computation.
Too small and there will be little diversity for selection to act on.
Numbers in the range 30 to 1000 are common in practice.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Genotype to phenotype
Choice of mapping or encoding scheme is important.
The pizza example afforded an obvious mapping (i.e. bit
string to recipe ingredients).
What about more complex problems?
www.chess-space.com
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Encoding chess positions
Scheme 1: Encode each square by the piece on it (or none).
64 squares, each of which can be one of 13 states (6 piece
types per side, or empty).
Requires at least 64 × log2 13 = 237 bits.
Scheme 2: Specify the location of each of the 32 pieces. Each can be in 64 different squares, or ‘off the board.’ Requires at least 32 × log2 65 = 193 bits.
The second scheme has a smaller ‘space’ to act in, so we might expect evolution to be faster (although this is not guaranteed).
Note that both schemes ‘over-count’ because they also include many impossible configurations.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Fitness functions
Evolutionary Design I – p.15/29
A key ingredient of any GA is the choice of fitness function, fitness function example
which can be challenging to get right.
• We want to evolve robot controllers that produce Take the example of robot controllers to smoothly navigate a track:
smooth movement around the track.
• Start with a fitness function that rewards collision
avoidance, e.g.D,r. aMavrcgde.Kdamips t
anCOcMeP5f40r0oM mBio-InwspiraedlClo,mpoutvinger the
First attempt: Define a fitness that rewards collision avoidance. Robots move far from walls and then stop.
Second attempt: Increase fitness if the robot travels a long way. Robots may sit and spin in a circle.
Final attempt: Penalise (i.e. lower fitness for) tight turning angles.
May get the behaviour you were hoping for1.
If much trial-and-error is required to get suitable behaviour, then the potential benefits of GAs start to seem like too much work to be worth it.
1Floreano et al., in From animals to animats 3: Proc. of the 3rd international conference on simulation of adaptive behaviour (MIT, 1994).
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
How to select the ‘fit’ individuals?
Various choices for a selection operator:
Rank based: Roulette-wheel:
Select the n individuals with the highest fitnesses Probability pi of selecting individual i is propor- tional to its fitness fi:
pi = Nj=1 fj
Run several ‘tournaments’ between a few individ- uals chosen at random, and select the winner of each.
Tournament:
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Crossover and mutation
Mutation in a bit-string can be implemented as a probability that a bit is ‘flipped’ during reproduction.
Can be generalised to real-value genotypes, but is fraught with difficulties1.
Will need to systematically vary the mutation rate to get good results.
Crossover allows advantageous mutations to be shared around the whole population (rather than just direct descendants of the first individual to have that mutation).
One-point crossover is the simplest form.
Multi-point crossover is also possible, but may not provide any
significant benefits.
1S. Bullock, in Advances in Artificial Life (ed. Floreano et al., 1999).
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
Today we have
Summarised natural evolution from a biological perspective.
Started to look at how we could exploit these ideas to evolve ‘good’ algorithms.
Next time we will probe the key issues in GA design in more detail.
Chapter 1 of M. Affenzeller et al., Genetic Algorithms and Genetic Programming (CRC Press,2009) gives a nice introduction to GAs.
Dr. Marc de Kamps
COMP5400M Bio-Inspired Computing
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com