[3] Evolutionary Computation

Question 1

What are GAs?

Answer 1

Genetic algorithms closely mini biology:

• each individual only has one parent
• chromosomes are the data structure; they are fixed length strings

Question 2

What are the basic processes in GAs?

Answer 2

Selection

Mutation

Crossover

Question 3

How does selection work?

Answer 3

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

Question 4

How does crossover work?

Answer 4

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

Question 5

What options exist for termination criteria for GAs?

Answer 5

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)

Question 6

What are steady-state GAs?

Answer 6

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

Question 7

What is elitism?

Answer 7

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

Question 8

How can illegal solutions to GAs be avoid?

Answer 8

• Restrict crossover and mutation so that it only gives valid children
• Heavily penalise invalid solutions
• Repair broken individuals

Question 9

What is the basic procedure for a GA?

Answer 9

[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

Question 10

What is differential evolution?

Answer 10

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

Question 11

What is deterministic evolution?

Answer 11

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

Question 12

What is Michaelwicz’s interpretation?

Answer 12

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

Question 13

What are memetic algorithms?

Answer 13

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

Question 14

What representation do GPs use?

Answer 14

Tree

Question 15

What are the basic structures of GP tree?

Answer 15

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

Question 16

How should the function and terminal sets be selected?

Answer 16

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

Question 17

What is the initial population of a GP constructed?

Answer 17

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]

Question 18

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

Answer 18

Fully, entirely balanced trees are constructed

Question 19

What are the genetic operators for GPs?

Answer 19

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

Question 20

What is the main use case of GPs?

Answer 20

Symbolic regression

Question 21

What are the they key differences between GAs and GPs?

Answer 21

• 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

Question 22

What are repeating patterns in a GP tree called?

Answer 22

Building blocks

Question 23

What are building blocks?

Answer 23

Repeating patterns in a GP

Question 24

What special operator do many GPs use?

Answer 24

Protected division, which is zero if the denominator is 0

Question 25

How do Strongly Typed GPs work?

Answer 25

They restrict cross-over and mutation to ensure they only produce valid offspring Genetic types ensure functions can handle a range of datatypes

Question 26

What are the key challenges of strongly typed GPs?

Answer 26

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

Question 27

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

Answer 27

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

Question 28

How does semantics work?

Answer 28

*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

Question 29

What are the principles of PSO?

Answer 29

- 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

Question 30

What are the components of velocity in PSO?

Answer 30

- Previous velocity (weighed with w) - Cognitive component (weighted with c1) - Social component (weighted with c2)

Question 31

How does the previous velocity component work?

Answer 31

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

Question 32

How does the cognitive component work?

Answer 32

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

Question 33

How does the social component work?

Answer 33

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

Question 34

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

Answer 34

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

Question 35

How does changing the inertia weight affect PSO?

Answer 35

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

Question 36

What is the major tradeoff with PSO?

Answer 36

Exploration vs exploitation

Question 37

What the coefficients for PSO called?

Answer 37

w is the inertia weight c1 and c2 are collectively the acceleration coefficients

Question 38

How do the acceleration coefficients affect swarm behaviour?

Answer 38

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

Question 39

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

Answer 39

It is very domain specific, but in general: - use c1 > c2 for multimodal problems - use c1 < c2 for unimodal problems

Question 40

What options exist for the global best?

Answer 40

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

Question 41

How does binary PSO work?

Answer 41

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