Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

ECE 457A - Cooperative & Adaptive Algorithms > Week 9: Particle Swarm Optimization #1 > Flashcards

Week 9: Particle Swarm Optimization #1 Flashcards

You may prefer our related Brainscape-certified flashcards:
Early Childhood Education flashcards
1
Q

<p></p>

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

A

<p>optimizes<br></br>
iteratively<br></br>
solutions</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

<p></p>

<p>Particle Swarm Optimization are \_\_\_\_\_\_\_ inspired algorithms</p>

A

<p></p>

<p>nature</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

<p></p>

<p>What is a "Swarm" in PSO?</p>

A

<p></p>

<p>It is the population of solutions that the algorithms processes</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

<p></p>

<p>Do the less fit individuals in PSO die?</p>

A

<p></p>

<p>no. The less fit particles don't die</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

<p></p>

<p>What does PSO use to improve the fitness of the population?</p>

A

<p></p>

<p>PSO uses past experience and relationships to neighbours to improve the existing set of solution</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

<p></p>

<p>Is PSO stochastic or deterministic?</p>

A

<p></p>

<p>Stochastic</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

<p></p>

<p>PSO manipulates a \_\_\_\_\_\_\_ of solutions at once</p>

A

<p></p>

<p>number/population</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

<p></p>

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

A

<p></p>

<p>particle
<br></br>swarm</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

<p></p>

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

A

<p></p>

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

<p></p>

<p>If the neighbourhood is restricted to a few particles, what is the best solution called?</p>

A

<p></p>

<p>any of:
<br></br>- local best
<br></br>- Lbest
<br></br>- p_i</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

<p></p>

<p>Each particle adjust its \_\_\_\_\_\_ to move towards its personal \_\_\_\_\_\_ and the \_\_\_\_\_\_ neighbourhood \_\_\_\_\_\_</p>

A

<p></p>

<p>velocity
<br></br>best
<br></br>swarm
<br></br>best</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

<p></p>

<p>After the \_\_\_\_\_\_ is updated, the particle adjusts its \_\_\_\_\_</p>

A

<p></p>

<p>velocity
<br></br>position</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

<p></p>

<p>in PSO, what are the equations of motion?</p>

A

<p></p>

<p></p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

<p></p>

<p>in PSO, random numbers are generated for each \_\_\_\_\_\_\_ and not for each \_\_\_\_\_\_\_</p>

A

<p></p>

<p>dimension/variable
<br></br>particle</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

<p></p>

<p>What is linear PSO? what is the disadvantage of linear PSO?</p>

A

<p></p>

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

<p></p>

<p>The PSO motion equation is composed of 3 components, what are they?</p>

A

<p></p>

<p>- Inertia component
<br></br>- Cognitive component
<br></br>- Social component</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

<p></p>

<p>What is the purpose of the inertia component in the PSO motion equation?</p>

A

<p></p>

<p>it accommodates the fact that a particle cannot suddenly change its direction of movement</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

<p></p>

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

A

<p></p>

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

<p></p>

<p>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 \_\_\_\_\_\_\_</p>

A

<p></p>

<p>vector
<br></br>weighted
<br></br>sum
<br></br>components</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

<p></p>

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

A

<p></p>

<p>personal
<br></br>fitness
<br></br>personal
<br></br>current position</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

<p></p>

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

A

<p></p>

<p>swarm
<br></br>global
<br></br>personal</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

<p></p>

<p>Under what condition is Nbest = Lbest? what about Nbest = Gbest?</p>

A

<p></p>

<p>Nbest = Lbest whenever the neighbourhood is restricted to a few particles
<br></br>
<br></br>Nbest = Gbest whenever the neighbourhood is the entire swarm</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

<p></p>

<p>If the neighbourhood is the whole swarm, what is the best solution achieved by the whole swarm called?</p>

A

<p></p>

<p>any of:
<br></br>- Global best
<br></br>- Gbest_i
<br></br>- p_g</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

<p></p>

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

A

<p></p>

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

<p></p>

<p>In PSO, what is V_max set in accordance to?</p>

A

<p></p>

<p>V_max is set according to the domain of the search space</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

<p></p>

<p>Describe the PSO simple algorithm step-by-step</p>

A

<p></p>

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

27
Q

<p></p>

<p>What is the difference between Synchronous PSO and Asynchronous PSO?</p>

A

<p></p>

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

28
Q

<p></p>

<p>Does Asynchronous PSO produce better results? or Synchronous PSO? why?</p>

A

<p></p>

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

29
Q

<p></p>

<p>What are the typical termination criteria for PSO?</p>

A

<p></p>

<p>- Max number of iterations reached
<br></br>- Max number of function evaluations
<br></br>- Acceptable solution has been found
<br></br>- No improvement over a number of iterations</p>

30
Q

<p></p>

<p>In PSO, each \_\_\_\_\_\_ shares its \_\_\_\_\_\_ best information with other \_\_\_\_\_\_</p>

A

<p></p>

<p>particle
<br></br>personal
<br></br>particles</p>

31
Q

<p></p>

<p>What effect does selecting a proper neighbourhood have on the PSO algorithm?</p>

A

<p></p>

<p>- affects convergence
<br></br>- Helps in avoiding getting stuck at local minima</p>

32
Q

<p></p>

<p>In PSO, what is the difference between the Star topology neighbourhood and the Ring topology neighbourhood?</p>

A

<p></p>

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

33
Q

<p></p>

<p>What are characteristics of the GBest model?</p>

A

<p></p>

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

34
Q

<p></p>

<p>What are characteristics of the LBest model?</p>

A

<p></p>

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

35
Q

<p></p>

<p>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</p>

A

<p></p>

<p>neighbours
<br></br>closest
<br></br>computationally expensive
<br></br>distances</p>

36
Q

<p></p>

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

A

<p></p>

<p>- Particles can be picked as adjacent cells in the matrix
<br></br>- Performance is significantly better than using closest distance</p>

37
Q

<p></p>

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

A

<p></p>

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

38
Q

<p></p>

<p>To initialize PSO, what 3 parameters need to be initialized?</p>

A

<p></p>

<p>- Position
<br></br>- Velocity
<br></br>- Personal best (which is position at initialization)</p>

39
Q

<p></p>

<p>In PSO, how is position initialized?</p>

A

<p></p>

<p>The Position are initialized randomly in a range</p>

40
Q

<p></p>

<p>In PSO, how is velocity initialized? Why is it so?</p>

A

<p></p>

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

41
Q

<p></p>

<p>In PSO, how is the personal best position initialized?</p>

A

<p></p>

<p>It is the initial position - which is a random number in a range</p>

42
Q

<p></p>

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

A

<p></p>

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

<br></br>
<br></br><p></p>
<br></br>
<br></br><p>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.</p>

43
Q

<p></p>

<p>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?</p>

A

<p></p>

<p>- Small values will result in smooth trajectories</p>

<br></br>
<br></br><p>- High values cause more acceleration with abrupt movement towards or past good regions</p>

44
Q

<p></p>

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

A

<p></p>

<p>Exploration: use large `w`</p>

<br></br>
<br></br><p>Exploitation: use small w</p>

45
Q

<p></p>

<p>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?</p>

A

<p></p>

<p>Suppose that c = (c_1 + c_2)/2</p>

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

46
Q

<p></p>

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

A

<p>continous
<br></br>distrcrete</p>

47
Q

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

A

<p>- The position vector can be discretized (by taking the floor)
<br></br>- The arithmetic operations can be redefined (addition, multiplication)</p>

48
Q

<p>What are the two Discrete versions of PSO?</p>

A

<p>Binary PSO and Permutation PSO</p>

49
Q

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

A

position
zero
one

50
Q

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

A

<p>velocities
<br></br>probabilities</p>

51
Q

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

A

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

52
Q

<p>In Binary PSO, what is the sigmoid function used for?</p>

A

<p>- To polarize a continuous value into a probability between 0 and 1
<br></br>- To update the position of the particle</p>

53
Q

In Binary PSO, how is the position updated?

A

A random number r is generated between 0 and 1.<br></br>

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

54
Q

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

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
55
Q

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

A

continuous/real
sigmoid
position

56
Q

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

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

57
Q

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

A

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

58
Q

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

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

59
Q

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

A

The following are re-defined for Permutation PSO:

  • Adding a velocity to a position
  • Subtracting two position
  • Multiplying a velocity by a constant
60
Q

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

A

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

61
Q

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

Note that subtracting two positions should produce a velocity

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.

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

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
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?

A

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

ECE 457A - Cooperative & Adaptive Algorithms (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions