Week 7

Question 1

Characteristics of flocking?

Answer 1

• Rapid directed movement of the whole flock
• Reactivity to predators (flash expansion, fountain effect)
• Reactivity to obstacles
• No collisions between flock members
• Coalescing and splitting of flocks
• Tolerant of movement within the flock, loss or gain of flock members
• No dedicated leader
• Different species can have different flocking characteristics — easy to recognise but not always easy to describe

Question 2

Benefits of flocking

Answer 2

Energy saving
Geese flying in Vs can extend range by over 70%
Flash expansion, fountain effect in fish, confuse predators

Question 3

How can we work out error of a flock direction?

Answer 3

IF
* Each individual has only a vague and noisy idea of which direction to fly in, or is a really incompetent flyer…
* and if a flock averaged out all the individual directions…
* Individual error in measuring the global field is uncorrelated

THEN
* From a simple statistical computation, flock direction should have an error proportional to
1/sqrt(𝑛) = # of individuals in the flock

Question 4

Examples of migration in nature

Answer 4

Monarch butterflies reach the same trees every year
Wrenecks do the same from Africa to Valais
Fish reach the same tiny spawning grounds

Application:
fishery statistics: models based on averaged navigational errors

Question 5

Who is Boids?

Answer 5

Computer animator who wanted to find a way of animating flocks that would be
realistic looking
computationally efficient (no worse than linear)
3D

Question 6

What is Boids sensory system?

Answer 6

Idealized system
Local, omni-directional sensory system
Relative range and bearing system
Can identify all teammates within range of detection
Immediate response
Homogenous system
No noise
Second order variables (velocity) estimated with 2 first order measures (position)

Question 7

What are Reynold’s Rules for Flocking

Answer 7

Separation: steer to avoid crowding local flockmates
Alignment/Velocity Matching: steer towards the average heading of local flockmates & attempt to match velocity
Cohesion: steer to move toward the average position of local flockmates.

Question 8

Characteristics of Reynold’s flocks

Answer 8

spontaneously polarize
synchronise their changes in direction
flocks join when they meet
if started too close together, flash expansion occurs
if started too far apart, they may slowly aggregate or form flockettes which later merge.

Question 9

What is particle swarm optimisation

Answer 9

Each particle is a candidate solution
- no mass or volume BUT velocity and acceleration apply
Swam - velocity matching not included (no coordination unlike flocking, collaboration instead)
Optimisation - discovery of near optimal solution by means of a population of individuals.

Question 10

The Cornfield Vector/ Rooster effect

Answer 10

How does swarming/flocking get us to a near optimal solution?
When food is left for birds, within minutes many birds are there, so we can define a fitness representing the quality of the solution (odor of food)
Knowledge of the swarm is incorporated into the local behaviour of each particle. All collaborate to find the food quickly.

Question 11

Basic PSO

Answer 11

Create N random particles (solutions)
For each timestep
For each individual
- update the position of particle by adding a velocity to current particle pos
- update velocity
next individual
next timestep

Question 12

How do we update the velocity of a particle?

Answer 12

vij[t+1] = vij[t] +c1rand()(pbestxij-presentxij)
+c2rand()(gbestxij-presentxij)

Where c1 & c2 are constants and rand() is a function which returns a random number between 0 and 1.
As before i is the individual and j is the dimension.
pbestx is that particle’s previous best position
gbestx is the population’s best position

Question 13

Why do we use rand() in PSO velocity update

Answer 13

Stops swarm from converging too quickly

Question 14

Why c1 and c2 in velocity update?

Answer 14

Change weighting between personal and population experience/knowledge

Question 15

Neighbour based PSO

Answer 15

Similar to global based PSO
lbest computed instead of gbest where lbest is best solution in current neighbourhood.
Neghbourhoods are normally not defined by closeness in search space
-no velocity matching required
- good solutions are spread throughout the population

gbest vs lbest
- gbest will converge earlier as every particle has access to best
- lbest has larger diversity, wont get trapped in local minima.

Question 16

PSO parameters

Answer 16

Swarm size
Neighbourhood size
Number of iterations
Acceleration coefficients (c1 & c2)

Question 17

PSO termination criteria

Answer 17

Max iterations
Acceptable solution found
No improvement for N iterations
Normalized swarm radius close to zero

Question 18

PSO applications

Answer 18

Design of:
antennae, aircraft wings, amplifiers
Scheduling of
TSP, task assignment
Generally requires a real vector representation.

Question 19

What is Binary PSO?

Answer 19

Can be modified to work on discrete spaces e.g. binary strings
Approach 1: interpret velocities as probabilities (traditional BPSO)
Approach 2: generalise motion to discrete spaces (geometric BPSO)

Question 20

Traditional BPSO

Answer 20

Velocity remains continuous using the original update rule
Positions are updated using the velocity as a probability threshold to determine if the jth component of the ith particle is a zero or 1
xij[t+1] = 1 if rand() < sig(vij[t])
0 otherwise