Week 9: Particle Swarm Optimization #1 Flashcards

Question 1

Q

Particle Swarm Optimizations are computational methods that \_\_\_\_\_\_\_ a problem by \_\_\_\_\_\_\_ trying to improve a population of \_\_\_\_\_\_\_

Answer

A

optimizes 
iteratively 
solutions

Question 2

Q

Particle Swarm Optimization are \_\_\_\_\_\_\_ inspired algorithms

Answer

A

nature

Question 3

Q

What is a "Swarm" in PSO?

Answer

A

It is the population of solutions that the algorithms processes

Question 4

Q

Do the less fit individuals in PSO die?

Answer

A

no. The less fit particles don't die

Question 5

Q

What does PSO use to improve the fitness of the population?

Answer

A

PSO uses past experience and relationships to neighbours to improve the existing set of solution

Question 6

Q

Is PSO stochastic or deterministic?

Answer

A

Stochastic

Question 7

Q

PSO manipulates a \_\_\_\_\_\_\_ of solutions at once

Answer

A

number/population

Question 8

Q

In PSO, a single solution is referred to as a \_\_\_\_\_\_, whereas the whole population of solutions is referred to as a \_\_\_\_\_\_

Answer

A

particle
 swarm

Question 9

Q

In PSO, each particle holds 6 pieces of information, which are essential for its movement

Answer

A

1. Current postion: x_i
 2. Current velocity: v_i
 3. The best position it has achieved so far: pbest_i or p_i
 4. The best position achieved by particles in its neighbourhood: Nbest
 5. The best solution achieved by the whole swarm (only if the neighbourhood is the whole swarm): gbest_i or p_g
 6. The local best (only if the neighbourhood is restricted to a few particles): Lbest or p_i

Question 10

Q

If the neighbourhood is restricted to a few particles, what is the best solution called?

Answer

A

any of:
 - local best
 - Lbest
 - p_i

Question 11

Q

Each particle adjust its \_\_\_\_\_\_ to move towards its personal \_\_\_\_\_\_ and the \_\_\_\_\_\_ neighbourhood \_\_\_\_\_\_

Answer

A

velocity
 best
 swarm
 best

Question 12

Q

After the \_\_\_\_\_\_ is updated, the particle adjusts its \_\_\_\_\_

Answer

A

velocity
 position

Question 13

Q

in PSO, what are the equations of motion?

Answer

A

Question 14

Q

in PSO, random numbers are generated for each \_\_\_\_\_\_\_ and not for each \_\_\_\_\_\_\_

Answer

A

dimension/variable
 particle

Question 15

Q

What is linear PSO? what is the disadvantage of linear PSO?

Answer

A

Linear PSO is when the numbers are generated for each particle.
 
 Linear PSO produces sub-optimal solutions compared to regular PSO

Question 16

Q

The PSO motion equation is composed of 3 components, what are they?

Answer

A

- Inertia component
 - Cognitive component
 - Social component

Question 17

Q

What is the purpose of the inertia component in the PSO motion equation?

Answer

A

it accommodates the fact that a particle cannot suddenly change its direction of movement

Question 18

Q

The Social and Cognitive components have constant factors c_1, and c_2. What is the purpose of these two constants?

Answer

A

The c_1 and c_2 factors balance the weights with each particle.
 
 c_1: trusts its own experience, cognitive component
 
 c_2: trusts the swarm experience, social experience

Question 19

Q

The 3 components of the PSO motion equation can be thought of similarly to a mathematical \_\_\_\_\_\_\_, in which the overall next velocity is the \_\_\_\_\_\_\_ \_\_\_\_\_\_ of the \_\_\_\_\_\_\_

Answer

A

vector
 weighted
 sum
 components

Question 20

Q

After finding the next position, each particle updates its own \_\_\_\_\_\_ best, according to the minimum/maximum of the \_\_\_\_\_\_ function with the \_\_\_\_\_\_ best and the \_\_\_\_\_ \_\_\_\_\_\_

Answer

A

personal
 fitness
 personal
 current position

Question 21

Q

After updating the personal best, each \_\_\_\_\_ updates its \_\_\_\_\_\_ best, which is the best solution of all \_\_\_\_\_\_\_ bests

Answer

A

swarm
 global
 personal

Question 22

Q

Under what condition is Nbest = Lbest? what about Nbest = Gbest?

Answer

A

Nbest = Lbest whenever the neighbourhood is restricted to a few particles
 
 Nbest = Gbest whenever the neighbourhood is the entire swarm

Question 23

Q

If the neighbourhood is the whole swarm, what is the best solution achieved by the whole swarm called?

Answer

A

any of:
 - Global best
 - Gbest_i
 - p_g

Question 24

Q

In PSO, an important factor to set is the maximum velocity V_max. What happens if V_max is too high or too low?

Answer

A

- If V_max is too high, then particles can fly past optimal solutions
 - if V_min is too low, then particles can get stuck in local optima

Question 25

Q

In PSO, what is V_max set in accordance to?

Answer

A

V_max is set according to the domain of the search space

Question 26

Q

Describe the PSO simple algorithm step-by-step

Answer

A

1. initialize the swarm
 2. Repeat the following steps while the termination criteria is not met
 3. For each particle, update the velocity, position, and personal best
 4. Update NBest (will be in or out the loop for each particle depending on the type of PSO)
 5. Repeat step 2 onwards

Question 27

Q

What is the difference between Synchronous PSO and Asynchronous PSO?

Answer

A

In Synchronous PSO, the NBest is updated after all the population has been updated (per iteration of the algorithm).
 
 In Asynchronous PSO, the NBest update is applied for each particle (updated with each updating velocity & position)

Question 28

Q

Does Asynchronous PSO produce better results? or Synchronous PSO? why?

Answer

A

Asynchronous PSO produces better results as it causes the particles to use more up-to-date information

Question 29

Q

What are the typical termination criteria for PSO?

Answer

A

- Max number of iterations reached
 - Max number of function evaluations
 - Acceptable solution has been found
 - No improvement over a number of iterations

Question 30

Q

In PSO, each \_\_\_\_\_\_ shares its \_\_\_\_\_\_ best information with other \_\_\_\_\_\_

Answer

A

particle
 personal
 particles

Question 31

Q

What effect does selecting a proper neighbourhood have on the PSO algorithm?

Answer

A

- affects convergence
 - Helps in avoiding getting stuck at local minima

Question 32

Q

In PSO, what is the difference between the Star topology neighbourhood and the Ring topology neighbourhood?

Answer

A

In Star topology, all particles are neighbours of each other, Nbest = Gbest
 
 In Ring topology, particles have very few neighbours. Nbest = Lbest

Question 33

Q

What are characteristics of the GBest model?

Answer

A

- Each particle is influenced by all the other particles
 - The fastest propagation of information in a population
 - Particles get stuck at local minima

Question 34

Q

What are characteristics of the LBest model?

Answer

A

- Each particle is influenced only by particles in its own neighbourhood
 - The propagation of information is the slowest
 - Doesn't easily get stuck in the local minima
 - Might have higher computational cost

Question 35

Q

The most obvious way to select \_\_\_\_\_\_\_ for a particle is to choose the particles that are \_\_\_\_\_\_ to it in the search space. This approach might be \_\_\_\_\_ \_\_\_\_\_, since \_\_\_\_\_\_ have to be computed each time the particle changes its position

Answer

A

neighbours
 closest
 computationally expensive
 distances

Question 36

Q

In PSO neighbourhood selection, what is the advantage of keeping particles in a matrix data structure?

Answer

A

- Particles can be picked as adjacent cells in the matrix
 - Performance is significantly better than using closest distance

Question 37

Q

What is the square topology neighbourhood structure for PSO? (The Von Neumann model)

Answer

A

It is formed by arranging the particles in a grid and connecting the neighbours in all 4 adjacent directions.

Question 38

Q

To initialize PSO, what 3 parameters need to be initialized?

Answer

A

- Position
 - Velocity
 - Personal best (which is position at initialization)

Question 39

Q

In PSO, how is position initialized?

Answer

A

The Position are initialized randomly in a range

Question 40

Q

In PSO, how is velocity initialized? Why is it so?

Answer

A

Velocity is initialized to zero, or small values.
 
 Large values will result in large updates which can lead to divergence

Question 41

Q

In PSO, how is the personal best position initialized?

Answer

A

It is the initial position - which is a random number in a range

Question 42

Q

Recall the PSO equation of motion for velocity. What effect does initializingc_1 = 0 have on the algorithm? what about c_2 = 0?

Answer

A

Using c_1 = 0 reduces the velocity model to a Social-only model. Particles are all attracted to the Neighbourhood Best.

Using c_2 = 0 reduces the velocity model to a cognition-only model. Particles are all independent hill climbers, they do not consider the neighbourhood.

Question 43

Q

Recall the PSO velocityequation. In most applications, we initialize c_1 = c_2. What tradeoffs are there when we choose small values vs large values for these constants?

Answer

A

- Small values will result in smooth trajectories

- High values cause more acceleration with abrupt movement towards or past good regions

Question 44

Q

Recall the PSO velocity equation. How can the constant `w` be initializedin order to balance exploration and exploitation?

Answer

A

Exploration: use large `w`

Exploitation: use small w

Question 45

Q

To guarantee convergence in PSO, we need to tunec_1, c_2, and w at initialization.Under what values do these initialization parameters lead to a PSO which converges?

Answer

A

Suppose that c = (c_1 + c_2)/2

Then the 3 conditions for convergence are (they must all be true):
 
 w < 1,
 
 c > 0,
 
 2 * w - c +2 > 0

Question 46

Q

PSO was originally developed for \_\_\_\_\_\_\_ valuued spaces, however it can be modified for \_\_\_\_\_\_ valued spaces.

Answer

A

continous
 distrcrete

Question 47

Q

How can PSO be modified to make it solvable for discrete problems (such as TSP)?

Answer

A

- The position vector can be discretized (by taking the floor)
 - The arithmetic operations can be redefined (addition, multiplication)

Question 48

Q

What are the two Discrete versions of PSO?

Answer

A

Binary PSO and Permutation PSO

Question 49

Q

In Binary PSO, each _____ represents a position in the binary space which can take the values of ___ or ___

Answer

A

position
zero
one

Question 50

Q

In Binary PSO, \_\_\_\_\_\_ are defined as \_\_\_\_\_\_\_ that one element will be in one state or the other

Answer

A

velocities
 probabilities

Question 51

Q

In Binary PSO, how are velocities represented? what is the range of possible values?

Answer

A

velocities are probabilities that an element is in one state or another, so the velocity must be in the range [0,1]

Question 52

Q

In Binary PSO, what is the sigmoid function used for?

Answer

A

- To polarize a continuous value into a probability between 0 and 1
 - To update the position of the particle

Question 53

Q

In Binary PSO, how is the position updated?

Answer

A

A random number r is generated between 0 and 1.

The next position value becomes 1 if r < sig(v_t+1), and 0 otherwise.

Question 54

Q

In Binary PSO, what is the probability that the next position x_t+1 is 1?

Answer

A

equal to 0.5 if v_t+1 = 0
less than 0.5 if v_t+1 < 0
greater than 0.5 if v_t+1 > 0

Question 55

Q

In Binary PSO, the velocity components can be ______ numbers as long as they are fed into the ______ function before updating the ______

Answer

A

continuous/real
sigmoid
position

Question 56

Q

Compare PSO to GA. Under what condition is PSO better? what about GA?

Answer

A

if the problem size is small, PSO yields better solutions

- if the problem size is large, then PSO will be faster but GA will yield better solutions

Question 57

Q

In Permutation PSO, how can a solution be represented for solving TSP?

Answer

A

The position of a particle can be the solution to a TSP instance (permutation of cities)

Question 58

Q

Suppose Permutation PSO is being used to solve TSP. How can swapping two cities in a permutation be represented?

Answer

A

The set of swaps can be abstracted as the velocity of a particle (or a solution). The velocity is defined as the set of swaps to be performed on a particle

Question 59

Q

In Permutation PSO, three operations on the solution space are re-defined from regular PSO. What are they?

Answer

A

The following are re-defined for Permutation PSO:

Adding a velocity to a position
Subtracting two position
Multiplying a velocity by a constant

Question 60

Q

How is the operation of Adding a velocity to a position re-defined for Permutation PSO?

Answer

A

This operation is performed by applying a sequence of swaps defined by the velocity to the position vector

Question 61

Q

How is the operation of subtracting two positions performed in Permutation PSO?

Note that subtracting two positions should produce a velocity

Answer

A

We take the two permutations, and generate the sequence of permutations to get from one to the other.

The subtraction of the two is the sequence of swaps that would transform one permutation to the other.

Question 62

Q

How is the operation of multiplying a velocity by a constant performed in Permutation PSO?

Recall that the velocity in Permutation PSO is a sequence of swaps

Answer

A

The operation of multiplying the velocity by a constant is re-defined as changing the length of the velocity vector according to the constant which it is being multiplied by (call it c):

if c = 0, then the length of swaps is set to zero
if c < 1, then the sequence of swaps are truncated
if c > 1, then the sequence swaps are increased and repeated

Question 63

Q

In Permutation PSO, whenever the sequence of swaps (velocity) is multiplied by a constant, how does the new sequence of swaps (new velocity) inherit its next swaps?

Answer

A

The sequence of swaps grows, and the new elements added are taken from the beginning of the velocity vector.

Brainscape's Knowledge GenomeTM

Week 9: Particle Swarm Optimization #1 Flashcards

Brainscape's Knowledge Genome^TM