Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

COMP 422 > [3] Evolutionary Computation > Flashcards

[3] Evolutionary Computation Flashcards

1
Q

What are GAs?

A

Genetic algorithms closely mini biology:

  • each individual only has one parent
  • chromosomes are the data structure; they are fixed length strings
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the basic processes in GAs?

A

Selection

Mutation

Crossover

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

How does selection work?

A

Only the fittest individuals are used to form the next population

Roulette wheel selection selects individuals in proportion to their fitness

Tournament selection picks the best individual from random samples of the population

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

How does crossover work?

A

Single-point and two-point crossover breaks the chromosomes at one or two points respectively

Uniform crossover uses a bit mask to ensure each gene is equally likely to be swapped

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What options exist for termination criteria for GAs?

A

After a fixed number of iterations, if the best solution hasn’t changed for a while, if the average fitness hasn’t changed for a while, or when convergence has been reached (all individuals have the same genotype)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are steady-state GAs?

A

They don’t use generations; good individuals are selected to breed and produce offspring which replace bad ones

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is elitism?

A

Ensuring that the best individuals are always copied to the next generation, so the best solutions aren’t lost

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How can illegal solutions to GAs be avoid?

A
  • Restrict crossover and mutation so that it only gives valid children
  • Heavily penalise invalid solutions
  • Repair broken individuals
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the basic procedure for a GA?

A

[1] Initialise the population
[2] Evaluate the fitness of each individual in the current population
[3] Until the next population is created:
- select individuals from the current population
- perform genetic operations on the individuals
- insert the new operations into the next population
[4] Check if the termination criteria has been met. If not, repeat [2-4]
[5] Output the best individual

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is differential evolution?

A

Mutation is used to create a trail vector, which is used with crossover to create one offspring

The step size is influences by differences between individuals in the population

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is deterministic evolution?

A

The parent is only replaced by their offspring if they have higher fitness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is Michaelwicz’s interpretation?

A

As GAs are tailored to particular problems, they do worse for arbitrary problems

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are memetic algorithms?

A

They either:

  • include local search in the EC loop
  • Use domain-specific knowledge in the genetic operators, such as avoiding the creation of infeasible solutions
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What representation do GPs use?

A

Tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are the basic structures of GP tree?

A

Functions form the root and internal nodes of the the tree. They perform operations on their inputs

Terminals have no arguments and form the leaves of the tree. They may be inputs, constants or random numbers

Collectively, functions and terminals are called primitives

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How should the function and terminal sets be selected?

A

They should satisfy two criteria:

  • Sufficiency - some collection of primitives should be able to solve the problem
  • Closure - any function can accept input from any function or terminal
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the initial population of a GP constructed?

A

Full method - functions are selected as the does until a given depth is reached. Then terminals are selected to form leaf nodes

Grow method - nodes are selected from either the function or terminal sets. If a terminal is selected, the generation process moves on to the next non-terminal branch of the tree

Ramped half-and-half method - half of the population is generated from each of the above

[THESE ARE ALSE USED FOR MUTATION]

18
Q

What is the advantage of the full method for generating GPs?

A

Fully, entirely balanced trees are constructed

19
Q

What are the genetic operators for GPs?

A

Reproduction - the program is copied as-is to next generation

Mutation - a random subtree is replaced using the program generation method

Cross-over - sub-trees are randomly swapped between individuals

20
Q

What is the main use case of GPs?

A

Symbolic regression

21
Q

What are the they key differences between GAs and GPs?

A
  • GAs use strings to represent solutions while GPs use trees
  • GA strings are fixed-length, while GP trees can vary in length
  • GA uses a binary alphabet, while GPs use various alphabets
  • GA solutions have to be encoded and decoded while GPs can be interpreted directly as code
22
Q

What are repeating patterns in a GP tree called?

A

Building blocks

23
Q

What are building blocks?

A

Repeating patterns in a GP

24
Q

What special operator do many GPs use?

A

Protected division, which is zero if the denominator is 0

25
Q

How do Strongly Typed GPs work?

A

They restrict cross-over and mutation to ensure they only produce valid offspring

Genetic types ensure functions can handle a range of datatypes

26
Q

What are the key challenges of strongly typed GPs?

A

Ensuring the fitness function works for a multiple types, and ensuring there is a range of functions for each type

27
Q

What is a key problem with GPs? How is it addressed?

A

Small changes can have a big affect on the output, and so offspring have low relatedness to their parents

Conversely, many changes have no impact.

This is addressed by semantics

28
Q

How does semantics work?

A

Semantics are vectors of the outputs; the target output vector is the target semantics

Each semantic is a point in semantic space. Similar solutions will have a low distance in this space

Semantic awareness is incorporated using precise genetic operators i.e. only perform cross-over between semantically similar sub-programs

Geometric Semantic Search performs cross-over so that the offspring have an equal semantic difference from their parents; mutation ensure the offspring aren’t too semantically different. However, this is computationally expensive and causes the offspring to quickly grow in size

29
Q

What are the principles of PSO?

A
  • Each particle represents a candidate solution
  • Particles fly in the search space to find the best solutions
  • Each particle remembers its personal best, and knowns the global best
  • Each particle has a position and a velocity
30
Q

What are the components of velocity in PSO?

A
  • Previous velocity (weighed with w)
  • Cognitive component (weighted with c1)
  • Social component (weighted with c2)
31
Q

How does the previous velocity component work?

A

The particle remembers its previous velocity, preventing it from suddenly changing direction

32
Q

How does the cognitive component work?

A

It attracts particles to their personal best, especially if there current fitness isn’t very good

33
Q

How does the social component work?

A

It attracts particles to the swarm’s global best, especially if its current location isn’t very good

34
Q

What is a common issue with PSO? How is it addressed?

A

The velocities can become really high, so they are commonly clamped

35
Q

How does changing the inertia weight affect PSO?

A

For w >= 1, velocity increases overtime and the swarm diverges

For 0 < w < 1, the particles decelerate, and may converge based on the values of c1 and c2

36
Q

What is the major tradeoff with PSO?

A

Exploration vs exploitation

37
Q

What the coefficients for PSO called?

A

w is the inertia weight

c1 and c2 are collectively the acceleration coefficients

38
Q

How do the acceleration coefficients affect swarm behaviour?

A

c1 > 0; c2 = 0: each search independently does local search

c1 = 0; c2 > 0: the swarm is a stochastic hill climber

c1 = c2 > 0: particles are attracted the average of their personal best and global best

Low c1 and c2 lead to smooth particle trajectories; high values lead to abrupt changes in speed and direction

39
Q

How should the acceleration coefficient be chosen based on the problem being solved?

A

It is very domain specific, but in general:

  • use c1 > c2 for multimodal problems
  • use c1 < c2 for unimodal problems
40
Q

What options exist for the global best?

A

It can be the true global best of the swarm, or it can be a local best based on the particles neighbourhood

41
Q

How does binary PSO work?

A

The velocity is calculated, and x is set based on whether a random number is less than the sigmoid of the velocity

COMP 422 (4 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions