WK 7 Particle Swarm Oprimization Flashcards
Particle
– each particle is a candidate solution
— No mass or volume
— BUT! Velocity and acceleration do apply
Particle Swarm Optimization (PSO)
is a metaheuristic optimization algorithm inspired by the behavior of bird flocking or fish schooling.
It is commonly used to solve optimization problems where a global optimum needs to be found in a multidimensional search space.
Particle Swarm Optimization steps :
- Initialization & Evaluation
- Particle Movement
- Local and Global Best Update
- Iteration & Convergence
- Termination
Initialization & Evaluation:
Initialize a population of particles (also called “swarm”) randomly within the search space.
Evaluate the fitness or objective function value of each particle, which indicates how well the solution performs in the problem domain.
Particle Movement:
Update the velocity and position of each particle based:
- on its previous movement
- the best-known positions of both the particle itself and the entire swarm.
The velocity determines the particle’s direction and speed of movement in the search space.
Local and Global Best Update:
- Track the best fitness value achieved by each particle individually (local best)
- Track the best fitness value achieved by the entire swarm (global best).
Update these values whenever a particle finds a better solution.
Iteration & Convergence:
Repeat the process of particle movement and fitness evaluation for a certain number of iterations
As they progress, the particles tend to converge towards the global best position, indicating the optimal solution to the problem.
“Rooster Effect” or “Cornfield Vector”
The “Cornfield Vector” or “Rooster Effect” is a phenomenon observed in swarming or flocking behavior, where individual agents collectively move towards a near-optimal solution.
Position Updating
position of particle_i_j[t+1] = position of particle_i_j [t] + velocity_i_j[t]
Velocity Updating
velocity_i_j[t+1] = velocity_i_j[t] +
constant1rand()(previous local (paticle) best_i_j -current local best_i_j)
constant2rand()(previous global (population) best_i_j - current global best_i_j)
Why rand() in Velocity Updating?
to stop the swarm converging too quickly
Why c1 & c2 in Velocity Updating?
used to change the weighting between personal and
population experience/knowledge.
— Manage the relationship between pbest and gbest/lbest
— Too low values may mean slow progress
— Too high valuesfast convergence
Why particle best in velocity updating ?
This is the component which draws individuals back to their previous best situations
Why g ( population) best in velocity updating ?
This is the component where individuals compare themselves to others in their group
PSO and Social Behaviour
The pbest is the cognitive component:
— How well the individual is doing based on performance in the past
The gbest parameter is the social component
— How well the individual is doing based on the performance of other individuals
Neighbourhood Based PSO
Neighborhood-based Particle Swarm Optimization (PSO) is an extension of the traditional PSO algorithm that incorporates a notion of neighborhood within the swarm.
Particles are organized into smaller subgroups or neighborhoods, and interactions for position updates are limited to these local neighborhoods.
gbest vs lbest
— (neighbour best) lbest has larger diversity and less likely to get trapped in local minima
— (global) gbest will tend to converge earlier as every particle has access to the best individual
PSO Parameters
- Swarm size
- lbest algorithm uses a neighbourhood to calculate social component
- Neighbourhood size
- Number of iterations
- Acceleration coefficients (c1 & c2)
Binary PSO:
-Traditional BPSO: Interpret velocities as probabilities
-Geometric BPSO: Generalize motion to discrete spaces
Traditional Binary Particle Swarm Optimization (BPSO)
Velocity remains continuous. Instead of directly representing the velocity as a real-valued vector, each element of the velocity vector is considered as a probability threshold to determine if a particle of the corresponding bit is a zero or a one in the binary string
Geometric BPSO
No explicit velocity. Positions are updated by moving the particle towards personal best and global best proportionally to c1 and c2.
