Module 4 - Lecture 10 - Evolutionary Computation Flashcards
Evolutionary computation
What is an allele?
An allele is one of two or more versions of DNA sequence (a single base or a segment of bases) at a given genomic location.
Evolutionary computation
What is a trait?
A trait, as related to genetics, is a specific characteristic of an individual. (Phenotype?)
Evolutionary computation
What do traits affect? (2)
Survival and reproduction
Evolutionary computation
What does natural selection favor?
Good traits
Evolutionary computation
What is John Henry Holland known for?
Published a groundbreaking book on GA, “Adaptation in Natural and Artificial Systems”
Evolutionary computation
When was “Adaptation in Natural and Artificial Systems” published?
1975
Evolutionary computation
How are genes expressed (Data format)
Collection of bits, integers, real numbers etc.
Evolutionary computation
How is natural selection guided?
Through a fitness function
Evolutionary computation
What are some examples of mutation in a GA?
Bit flips, integer swaps, random pertubations etc.
Evolutionary computation
How is crossover typically performed?
Parents swap substrings
Evolutionary computation
What is the definition of GA? (Mathematical)
A probabilistic search algorithm which transforms a set of mathematical objects, each with a fitness value, into a new population using: Darwinian evolution and operations like crossover/mutation
Evolutionary computation
How is the initial population generated
Typically at random
Evolutionary computation
What does probabilistic selection mean?
- The best are not always picked
- The worst are not always excluded
Evolutionary computation
How do you choose whether to apply crossover or mutation?
Selected at random
Evolutionary computation
What is greedy exploitation?
Following the best solution only
Evolutionary computation
What is adventurous exploration?
Going through and exploring as many options as possible
Evolutionary computation
Does GA do greedy exploitation or adventurous exploration?
Yes, both.
Evolutionary computation
What is a chromosome?
A collection of genes, e.g. a position vector.
Evolutionary computation
What is a gene?
Part of a chromosome, e.g. one of the numbers in a position vector.
Evolutionary computation
What are the steps in a GA? (6) (CFNDIR)
1) Create a base population
2) Calculate fitness
3) Create new individuals based on chromosomes (e.g. Crossover, mutation)
4) Delete undesirable individuals.
5) Insert the new individuals into the population.
6) Repeat 2-6 until convergence.
Evolutionary computation
Who introduced particle swarm optimization (PSO)?
Kennedy and Eberhart
Evolutionary computation
When was PSO introduced?
1995
Evolutionary computation
What was the goal of PSO?
To develop a visual simulation of bird flocking behaviour.
Evolutionary computation
What is a particle (PSO)?
The position of one individual in a flock
Evolutionary computation
What are the 5 basic principles of swarm intelligence (SI)? PQDSA
- Proximity
- Quality
- Diverse response
- Stability
- Adaptability
Evolutionary computation
In SI, what is proximity?
agents can perform basic space and time calculations
Evolutionary computation
In SI, what is Quality?
agents can respond to environmental conditions
Evolutionary computation
In SI, what is “Diverse response”?
population can exhibit a wide range of behaviour
Evolutionary computation
In SI, what is Stability?
Behaviour of population does not necessarily change every time the environment does
Evolutionary computation
In SI, what is Adaptability?
The behaviour of a population must be able to adapt to the environment, if necessary.
Evolutionary computation
What two vectors are associated with a PSO particle?
Position and velocity
Evolutionary computation
What are the guiding signals a PSO particle receives?
- Personal best
- Global best
Evolutionary computation
What is a PSO particle’s personal best?
the best value it has found so far (pbest – personal best) and its location
Evolutionary computation
What is a PSO article’s global best?
the best value any individual in the population has found so far (gbest – global best) and its location
Evolutionary computation
How does a PSO particle move?
- Each particle has a velocity.
- The velocity is updated based on its current velocity, the direction of its personal best position, and the global best known position.
Evolutionary computation
What components does a PSO particle consist of? (3+2)
3 vectors: position, speed, personal best position
2 fitness values: current position, personal best
Evolutionary computation
What is the cognition term of a PSO particle?
The velocity update contribution from its personal best.
Evolutionary computation
What is the social term of a PSO article?
The velocity update contribution from its global best.
Evolutionary computation
When updating a PSO particle’s position, what are c_1 and c_2?
Coefficients for the contribution of the cognition term/social best and social term/global best, respectively.
Evolutionary computation
When updating a PSO particle’s position, what are r_1 and r_2?
Random contributions from the cognition term/social best and social term/global best, respectively.
Evolutionary computation
What is the inertia weight?
A constant scalar (vector/matrix?) that decays the velocity of the particle to promote exploitation.
Evolutionary computation
For PSO, What is the “The refined algorithm”?
Setting c_1 and c_2 (Contrib from pbest and gbest) fo 2, increasing exploration.
Evolutionary computation
What are the termination conditions for PSO? (3)
- Max number of iterations
- Solution exceeds a quality threshold (good solution found)
- Average velocity falls below some threshold.
Evolutionary computation
What is ACO?
Ant colony optimization
Evolutionary computation
What is the basic idea behind ant colony optimization (ACO)?
Ants communicate by leaving pheromone trails, signalling which paths are the most preferable.
Evolutionary computation
What class of problems is ACO particularly suited for?
Discrete optimization problems
Evolutionary computation
What is stigmergic communication?
Stigmergy is a communication method used in decentralized systems in which individuals communicate with each other by changing the surrounding environment.
Evolutionary computation
Why does SI have better scalability?
Communication via the environment leads to less overhead; ants do not communicate with all other ants.
Evolutionary computation
What is autocatalytic behavior?
Jumpstarting behavior. The more ants follow a trail, the more attractive that trail becomes for being followed.
Evolutionary computation
Why is ACO a positive feedback loop?
The probability of a path choice increases with the # of times that path was previously chosen.
Evolutionary computation
Who coined stigmergy?
Pierre-Paul Grasse
Evolutionary computation
What is stigmergy?
Interaction through the environment
Evolutionary computation
Is stigmergy direct or indirect?
Typically indirect.
Evolutionary computation
What was ACO originally used for?
The travelling Salesman Problem (TSP).
Evolutionary computation
Who designed the “Ant System”?
Marco Dorigo
Evolutionary computation
When was the “Ant system” designed?
1992
Evolutionary computation
What are the steps of the “Ant system”? (CMUEDR)
1) Create ants
2) Move ants
3) Update pheromone
4) Evaporate pheromones
5) Daemon activities
6) Repeat 2-5 until convergence
Evolutionary computation
This is the transition probability function.
How does the parameter alpha impact the algorithm?
Alpha says how important pheromones are.
Evolutionary computation
This is the transition probability function.
How does the parameters beta impact the algorithm?
Beta is the “Degree visibility”, i.e. how far away the ant can “look”.
Evolutionary computation
In ACO, what is a daemon activity?
E.g. local search.
