Module 4 - Lecture 10 - Evolutionary Computation Flashcards by Rikard Donnelly

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.

How well did you know this?

Not at all

Perfectly

Evolutionary computation

What is a trait?

A trait, as related to genetics, is a specific characteristic of an individual. (Phenotype?)

How well did you know this?

Not at all

Perfectly

Evolutionary computation

What do traits affect? (2)

Survival and reproduction

How well did you know this?

Not at all

Perfectly

Evolutionary computation

What does natural selection favor?

Good traits

How well did you know this?

Not at all

Perfectly

Evolutionary computation

What is John Henry Holland known for?

Published a groundbreaking book on GA, “Adaptation in Natural and Artificial Systems”

How well did you know this?

Not at all

Perfectly

Evolutionary computation

When was “Adaptation in Natural and Artificial Systems” published?

1975

How well did you know this?

Not at all

Perfectly

Evolutionary computation

How are genes expressed (Data format)

Collection of bits, integers, real numbers etc.

How well did you know this?

Not at all

Perfectly

Evolutionary computation

How is natural selection guided?

Through a fitness function

How well did you know this?

Not at all

Perfectly

Evolutionary computation

What are some examples of mutation in a GA?

Bit flips, integer swaps, random pertubations etc.

How well did you know this?

Not at all

Perfectly

Evolutionary computation

How is crossover typically performed?

Parents swap substrings

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

Evolutionary computation

How is the initial population generated

Typically at random

How well did you know this?

Not at all

Perfectly

Evolutionary computation

What does probabilistic selection mean?

The best are not always picked
The worst are not always excluded

How well did you know this?

Not at all

Perfectly

Evolutionary computation

How do you choose whether to apply crossover or mutation?

Selected at random

How well did you know this?

Not at all

Perfectly

Evolutionary computation

What is greedy exploitation?

Following the best solution only

How well did you know this?

Not at all

Perfectly

Evolutionary computation

What is adventurous exploration?

Going through and exploring as many options as possible

How well did you know this?

Not at all

Perfectly

Evolutionary computation

Does GA do greedy exploitation or adventurous exploration?

Yes, both.

How well did you know this?

Not at all

Perfectly

Evolutionary computation

What is a chromosome?

A collection of genes, e.g. a position vector.

How well did you know this?

Not at all

Perfectly

Evolutionary computation

What is a gene?

Part of a chromosome, e.g. one of the numbers in a position vector.

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

Evolutionary computation

Who introduced particle swarm optimization (PSO)?

Kennedy and Eberhart

How well did you know this?

Not at all

Perfectly

Evolutionary computation

When was PSO introduced?

1995

How well did you know this?

Not at all

Perfectly

Evolutionary computation

What was the goal of PSO?

To develop a visual simulation of bird flocking behaviour.

How well did you know this?

Not at all

Perfectly

Evolutionary computation

What is a particle (PSO)?

The position of one individual in a flock

How well did you know this?

Not at all

Perfectly

# 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.