L12 - Flocking: Particle Swarm Optimisation

Question 1

1. What is Particle Swarm Optimisation and what movement is it based on?

Answer 1

An iterative optimisation algorithm to find an optimal solution. It’s based on flocking.

Question 2

2. Who invented PSO and when?

Answer 2

Kennedy and Eberhardt - 1995

Question 3

What 2 properties does each particle have and not have?

Answer 3

Have: Velocity, Acceleration
Doesn’t Have: Mass, Volume

Question 4

What does each particle represent

Answer 4

Candidate Solution

Question 5

What is the rooster effect and how does it demonstrate optimisation in PSO?

Answer 5

Chickens scooping around on the floor for food is similar to PSO. Roosters within the group will lead other roosters to the optimal solution until all roosters have swarmed to the food.

Question 6

What type of representation was PSO developed for? Give some applications of PSO…

Answer 6

1. Continuous E.g X = ( 3.554, 7.56345, 12.334, -9.948)
2. Applications: Aeroplane wing design, design of antennae, amplifiers etc.

Question 7

Does PSO give us both global and local information?

Answer 7

Yes

Question 8

Why is it beneficial that PSO gives us both global and local information?

Answer 8

Because it means the algorithm can navigate local optimums.

Question 9

Explain how PSO works…

Answer 9

1. Create and initialise N particles within the solution space. Each particle is a candidate solution.
2. At each time step, each particle must:
   
   1. Update its position (by adding velocity to its current position).
   2. Update its velocity.
   3. Evaluate fitness of each particles position
3. Terminate once termination criteria is met.

Question 10

During PSO, how do we determine the new position of a particle?

Answer 10

1. By using its current position and current velocity.
2. Next position(t+1) = Current Position(t) + Current Velocity(t)
3. Particle position at next time step = position at current time step + velocity at current time step.

Question 11

How do we determine the new velocity of the particle? What is the formula?

Answer 11

1. New = Current velocity + ( random weight * (particles best encountered position - current position) ) + ( random weight * ( populations best encountered position - particles current position ) )
2. Vij(t+1) = Vij + C1Z1(Pij - Xij) + C2Z2(Gj - Xij)

Question 12

In the velocity update formula, explain what each of the variables represent?

Answer 12

T -> Time step
T+1 -> Next time step
i -> Indicates the particle
j -> Indicates the dimension
C -> Constants controlling weight of local and global information
Z -> Values between 0 and 1 to repent premature convergence
Gj -> The global best position found
Pij -> The particles best position in dimension j

Question 13

What are the the parameters of PSO?

Answer 13

1. Swarm Size
2. Neighbourhood size -> For calculating local best
3. Iteration count
4. Acceleration coefficients C1, C2

Question 14

If we increase C2, what affect does this have on global information?

Answer 14

Increases the weight of global information.

Question 15

What do the acceleration coefficients control in PSO? What effect does it have if they’re too low or high?

Answer 15

Manage the relationship between personal and global best solutions.

Too low -> Cause progress to slow.

Too high -> Can cause premature convergence.

Question 16

What are the 4 termination criteria for PSO?

Answer 16

1. Iterations exceeded
2. Acceptable solution found
3. No improvement for M iterations
4. Normalised swarm radius is close to 0 -> But need to be careful we aren’t in local optima.

Question 17

Describe the key idea of PSO…

Answer 17

The key idea behind PSO is that particles adjust their positions and velocities in the solution space based on their own experience (personal best) and the knowledge shared by the entire swarm (global best). This collective movement helps the swarm explore the solution space efficiently and converge towards an optimal solution.

Question 18

When updating the velocity and position of particles, what 2 factors is this based on?

Answer 18

• Its own past velocity and the difference between its current position and its personal best-known position.
• The global best-known position and the difference between its current position and the global best-known position.

Question 19

PSO generally works with real vectors, but can be modified if working in discrete spaces. What are 2 ways PSO could be modified?

Answer 19

1. Binary PSO where velocities are interpreted as probabilities and remains continuous, and positions are updated using the velocity probability to determine if the particle j or i is a 0 or 1 -> Resulting in binary representation of solutions.
2. Generalised Motion approach: No velocity -> Particle positions are updated by moving them proportionally to global best (C2) and local best (C1).