Week 7 - Flocking and Particle Swarm Optimisation Flashcards
Name 7 flocking characteristics.
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
What do aggregation and segregation refer to?
Attraction and repulsion.
What are Reynolds’ rules for flocking?
- 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
What is the ‘Cornfield Vector’/Rooster Effect?
When food is left out for birds, often within minutes/hours there are a number of birds at that food source (similar to our optimal solution).
Therefore we can define a ‘fitness function’ which represents the quality of a solution (e.g. the odour of food).
The knowledge of the swarm is incorporated into the local behaviour of each particle.
All collaborate to find the food quickly.
In PSO, what is pbestx
The particle’s previous best position.
In PSO, what is gbest?
The population’s best position.
How does neighbourhood-based PSO differ from ordinary PSO?
lbest instead of gbest where lbest is the best solution in the current neighbourhood.
Name a positive of gbest and lbest.
gbest - tends to converge earlier as every particle has access to the best induvidual.
lbest - has larger diversity and less likely to get trapped in local minima.
What is the PSO termination criteria?
Max iterations.
Acceptable solution found.
No improvement for N iterations.
Normalised swarm radius close to zero (converged).
What does BPSO stand for?
Binary Particle Swarm Optimisation
What is the difference between traditional and geometric BPSO?
Traditional - velocity remains continuous using the original update rule. Positions are updated using the velocity as a probability threshold.
Geometric - no explicit velocity. Positions are updated by moving the particle towards the personal best and global best proportionally.
What is Boids’ Sensory System?
A local omni-directional sensory system
Relative range and bearing system (can detect position and bearing of all teammates within a certain radius - no occlusion
Perfectly identify all teammates in the range of direction
Immediate response - one perception-to-action loop (no sensory, computation capacity considered)
Homogenous system (all Boids have exactly the same sensory system)
No noise in the range and bearing measurement
Second order variables (velocity) estimated with 2 first order measures (position)
What are characteristics of Reynolds’ flocks?
They spontaneously polarise
They synchronise their changes in direction
Flocks join when they meet
If started too close together, flash expansion occurs
If started too far apart, they might slowly aggregate, or may form ‘flockettes’ which later merge, given enough time and a small enough space
How does PSO work (pseudocode)?
Create & initialise N random particles (solutions) on the search space
For each timestep:
- For each individual:
- - Update position by adding a velocity to the current particle position
- - Update velocity
- Next individual
Next timestep
