Week 9: Particle Swarm Optimization #1 Flashcards
<p></p>
<p>Particle Swarm Optimizations are computational methods that \_\_\_\_\_\_\_ a problem by \_\_\_\_\_\_\_ trying to improve a population of \_\_\_\_\_\_\_</p>
<p>optimizes<br></br>
iteratively<br></br>
solutions</p>
<p></p>
<p>Particle Swarm Optimization are \_\_\_\_\_\_\_ inspired algorithms</p>
<p></p>
<p>nature</p>
<p></p>
<p>What is a "Swarm" in PSO?</p>
<p></p>
<p>It is the population of solutions that the algorithms processes</p>
<p></p>
<p>Do the less fit individuals in PSO die?</p>
<p></p>
<p>no. The less fit particles don't die</p>
<p></p>
<p>What does PSO use to improve the fitness of the population?</p>
<p></p>
<p>PSO uses past experience and relationships to neighbours to improve the existing set of solution</p>
<p></p>
<p>Is PSO stochastic or deterministic?</p>
<p></p>
<p>Stochastic</p>
<p></p>
<p>PSO manipulates a \_\_\_\_\_\_\_ of solutions at once</p>
<p></p>
<p>number/population</p>
<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>
<p></p>
<p>particle
<br></br>swarm</p>
<p></p>
<p>In PSO, each particle holds 6 pieces of information, which are essential for its movement</p>
<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>
<p></p>
<p>If the neighbourhood is restricted to a few particles, what is the best solution called?</p>
<p></p>
<p>any of:
<br></br>- local best
<br></br>- Lbest
<br></br>- p_i</p>
<p></p>
<p>Each particle adjust its \_\_\_\_\_\_ to move towards its personal \_\_\_\_\_\_ and the \_\_\_\_\_\_ neighbourhood \_\_\_\_\_\_</p>
<p></p>
<p>velocity
<br></br>best
<br></br>swarm
<br></br>best</p>
<p></p>
<p>After the \_\_\_\_\_\_ is updated, the particle adjusts its \_\_\_\_\_</p>
<p></p>
<p>velocity
<br></br>position</p>
<p></p>
<p>in PSO, what are the equations of motion?</p>
<p></p>
<p></p>
<p></p>
<p>in PSO, random numbers are generated for each \_\_\_\_\_\_\_ and not for each \_\_\_\_\_\_\_</p>
<p></p>
<p>dimension/variable
<br></br>particle</p>
<p></p>
<p>What is linear PSO? what is the disadvantage of linear PSO?</p>
<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>
<p></p>
<p>The PSO motion equation is composed of 3 components, what are they?</p>
<p></p>
<p>- Inertia component
<br></br>- Cognitive component
<br></br>- Social component</p>
<p></p>
<p>What is the purpose of the inertia component in the PSO motion equation?</p>
<p></p>
<p>it accommodates the fact that a particle cannot suddenly change its direction of movement</p>
<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>
<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>
<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>
<p></p>
<p>vector
<br></br>weighted
<br></br>sum
<br></br>components</p>
<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>
<p></p>
<p>personal
<br></br>fitness
<br></br>personal
<br></br>current position</p>
<p></p>
<p>After updating the personal best, each \_\_\_\_\_ updates its \_\_\_\_\_\_ best, which is the best solution of all \_\_\_\_\_\_\_ bests</p>
<p></p>
<p>swarm
<br></br>global
<br></br>personal</p>
<p></p>
<p>Under what condition is Nbest = Lbest? what about Nbest = Gbest?</p>
<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>
<p></p>
<p>If the neighbourhood is the whole swarm, what is the best solution achieved by the whole swarm called?</p>
<p></p>
<p>any of:
<br></br>- Global best
<br></br>- Gbest_i
<br></br>- p_g</p>
<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>
<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>
In PSO, what is V_max set in accordance to?
V_max is set according to the domain of the search space
Describe the PSO simple algorithm step-by-step
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
What is the difference between Synchronous PSO and Asynchronous PSO?
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)
Does Asynchronous PSO produce better results? or Synchronous PSO? why?
Asynchronous PSO produces better results as it causes the particles to use more up-to-date information
What are the typical termination criteria for PSO?
- Max number of iterations reached
- Max number of function evaluations
- Acceptable solution has been found
- No improvement over a number of iterations
In PSO, each ______ shares its ______ best information with other ______
particle
personal
particles
What effect does selecting a proper neighbourhood have on the PSO algorithm?
- affects convergence
- Helps in avoiding getting stuck at local minima
In PSO, what is the difference between the Star topology neighbourhood and the Ring topology neighbourhood?
In Star topology, all particles are neighbours of each other, Nbest = Gbest
In Ring topology, particles have very few neighbours. Nbest = Lbest
What are characteristics of the GBest model?
- Each particle is influenced by all the other particles
- The fastest propagation of information in a population
- Particles get stuck at local minima
What are characteristics of the LBest model?
- 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
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
neighbours
closest
computationally expensive
distances
In PSO neighbourhood selection, what is the advantage of keeping particles in a matrix data structure?
- Particles can be picked as adjacent cells in the matrix
- Performance is significantly better than using closest distance
What is the square topology neighbourhood structure for PSO? (The Von Neumann model)
It is formed by arranging the particles in a grid and connecting the neighbours in all 4 adjacent directions.
To initialize PSO, what 3 parameters need to be initialized?
- Position
- Velocity
- Personal best (which is position at initialization)
In PSO, how is position initialized?
The Position are initialized randomly in a range
In PSO, how is velocity initialized? Why is it so?
Velocity is initialized to zero, or small values.
Large values will result in large updates which can lead to divergence
In PSO, how is the personal best position initialized?
It is the initial position - which is a random number in a range
Recall the PSO equation of motion for velocity. What effect does initializing c_1 = 0 have on the algorithm? what about c_2 = 0?
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.
Recall the PSO velocity equation. In most applications, we initialize c_1 = c_2. What tradeoffs are there when we choose small values vs large values for these constants?
- Small values will result in smooth trajectories
- High values cause more acceleration with abrupt movement towards or past good regions
Recall the PSO velocity equation. How can the constant `w` be initialized in order to balance exploration and exploitation?
Exploration: use large `w`
Exploitation: use small `w`
To guarantee convergence in PSO, we need to tune c_1, c_2, and w at initialization. Under what values do these initialization parameters lead to a PSO which converges?
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
PSO was originally developed for _______ valuued spaces, however it can be modified for ______ valued spaces.
continous
distrcrete
How can PSO be modified to make it solvable for discrete problems (such as TSP)?
- The position vector can be discretized (by taking the floor)
- The arithmetic operations can be redefined (addition, multiplication)
What are the two Discrete versions of PSO?
Binary PSO and Permutation PSO
In Binary PSO, ______ are defined as _______ that one element will be in one state or the other
velocities
probabilities
In Binary PSO, how are velocities represented? what is the range of possible values?
velocities are probabilities that an element is in one state or another, so the velocity must be in the range [0,1]
In Binary PSO, what is the sigmoid function used for?
- To polarize a continuous value into a probability between 0 and 1
- To update the position of the particle
| The next position value becomes 1 if r < sig(v_t+1), and 0 otherwise.
