VMEG Soft computing

Particle Swarm Optimization

Dr. Saroja Kumar Rout

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

Unit-4
( Particle Swarm Optimization )

Course contents:
• Introduction to PSO

• Implementation of PSO,

• Variants of PSO,

• Hybrid Model of PSO,

• Applications

Faculty Name: Dr. Saroja Kumar Rout

Department: Information Technology
Course Name: Soft Computing
Course Code: A7710

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

Chapter-4

4.1 Introduction to Particle Swarm Optimization

• Inspired from the nature social behavior and dynamic movements with communications of
insects, birds and fish.
• Particle Swarm Optimization was proposed by Kennedy and Eberhart in 1995. As
mentioned in the original paper, sociobiologists believe a school of fish or a flock of
birds that moves in a group “can profit from the experience of all other members”. In
other words, while a bird flying and searching randomly for food, for instance, all birds
in the flock can share their discovery and help the entire flock get the best hunt.
• Uses a number of agents (particles) that constitute a swarm moving around in the
search space looking for the best solution
• Each particle in search space adjusts its “flying” according to its own flying experience
as well as the flying experience of other particles.
• Each particle has three parameters position, velocity, and previous best position,
particle with best fitness value is called as global best position.

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

• Collection of flying particles (swarm) - Changing solutions Search area - Possible

solutions  Movement towards a promising area to get the global optimum.
• Each particle adjusts its travelling speed dynamically corresponding to the flying
experiences of itself and its colleagues.
• Each particle keeps track: its best solution, personal best, pbest. the best value of any
particle, global best, gbest.
• Each particle modifies its position according to:
• its current position
• its current velocity
• the distance between its current position and pbest.
• the distance between its current position and gbest.
4.2 Mathematical Formulation of an Optimization Problem PSO

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

6. Iterative Process

• Steps 3 to 5 are repeated iteratively until a stopping criterion is met (e.g., maximum
iterations, convergence tolerance).

This mathematical formulation allows PSO to iteratively search for the optimal solution by balancing
the influence of individual experiences (cognitive component) and social sharing of knowledge (social
component).

4.3 Particle Swarm Optimization (PSO) algorithm:

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

4.4 Implementation of PSO

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

Explanation:
• Objective Function: The function we are optimizing.
• Particle Initialization: Positions and velocities are initialized randomly.
• PSO Loop: Updates particles' velocities and positions, finds the personal best and
global best, and continues until reaching the maximum number of iterations.
• Parameters: w, c1, and c2 control the balance between exploration and exploitation.
Tuning these values can improve convergence.

Program-1

import numpy as np
import random
def objective_function(x):
# Example objective function (sphere function)
return sum(x**2)
num_particles = 30 # Number of particles in the swarm
num_dimensions = 2 # Number of dimensions (variables)
iterations = 100 # Number of iterations

# PSO parameters
w = 0.5 # Inertia weight

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

c1 = 1.5 # Cognitive parameter (personal best)

c2 = 1.5 # Social parameter (global best)

# Initialize particle positions and velocities

positions = [Link](low=-10, high=10, size=(num_particles,
num_dimensions))
velocities = [Link](low=-1, high=1, size=(num_particles,
num_dimensions))

# Initialize personal best and global best

personal_best_positions = [Link]()
personal_best_scores = [Link]([objective_function(pos) for pos in
positions])
global_best_position =
personal_best_positions[[Link](personal_best_scores)]

num_particles = 30 # Number of particles in the swarm

num_dimensions = 2 # Number of dimensions (variables)
iterations = 100 # Number of iterations

# PSO parameters
w = 0.5 # Inertia weight
c1 = 1.5 # Cognitive parameter (personal best)
c2 = 1.5 # Social parameter (global best)

# Initialize particle positions and velocities

positions = [Link](low=-10, high=10, size=(num_particles,
num_dimensions))
velocities = [Link](low=-1, high=1, size=(num_particles,
num_dimensions))

# Initialize personal best and global best

personal_best_positions = [Link]()
personal_best_scores = [Link]([objective_function(pos) for pos in
positions])
global_best_position =
personal_best_positions[[Link](personal_best_scores)]

4.5 PSO Variants

Particle Swarm Optimization (PSO) has undergone various modifications and enhancements
since its introduction, leading to numerous variants tailored to specific optimization
challenges. Here is a detailed overview of some significant PSO variants:

1. Standard Particle Swarm Optimization (SPSO)

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

• Overview: The original version introduced by Kennedy and Eberhart in 1995.

• Mechanism: Each particle in a swarm adjusts its position based on its own
experience (cognitive component) and that of the swarm's best performer (social
component).
• Applications: Used widely for continuous optimization problems.
2. Global Best PSO (gBest) vs. Local Best PSO (lBest)
• gBest: In this variant, all particles are attracted toward the position of the globally
best particle found so far. While it converges quickly, it is prone to getting trapped in
local optima.
• lBest: Each particle is influenced by the best particle within its neighborhood. This
encourages better exploration and is less likely to become trapped in local optima.
3. Inertia Weight PSO
• Purpose: Introduces an inertia weight parameter (w) to balance exploration
(searching new areas) and exploitation (refining solutions).
• Mechanism: The inertia weight scales the contribution of the previous velocity to the
new velocity. Larger inertia favors exploration, while smaller values focus on
exploitation.
• Adaptation Strategies: The inertia weight can be linearly decreased or dynamically
adjusted to adapt to the optimization process.
4. Constriction Factor PSO
• Goal: Introduced to ensure convergence stability by using a constriction factor that
scales velocity updates.
• Effect: This modification improves the algorithm's stability and convergence rate,
preventing particles from overshooting optimal solutions.
5. Adaptive PSO (APSO)
• Overview: Adjusts parameters such as inertia weight, cognitive, and social
coefficients dynamically during the optimization process.
• Advantage: This adaptability enables the swarm to transition from global exploration
to local exploitation more effectively based on the optimization phase.
6. Hybrid PSO
• Definition: Combines PSO with other optimization methods such as Genetic
Algorithms (GA), Differential Evolution (DE), or Simulated Annealing (SA).
• Motivation: The hybrid approach leverages the strengths of different algorithms to
overcome specific weaknesses, such as PSO's susceptibility to premature
convergence.

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

7. Quantum-behaved PSO (QPSO)

• Inspiration: Based on quantum mechanics, particles' positions are updated according
to a probabilistic distribution rather than deterministic velocity equations.
• Features: Exhibits strong global exploration capabilities, making it effective for
complex, multimodal optimization problems.
8. Discrete and Binary PSO (DPSO and BPSO)
• Application: Useful for problems where variables take discrete or binary values.
• BPSO Mechanism: Particle positions represent binary values (0 or 1), and velocity
updates are interpreted as probabilities using a sigmoid transformation.
9. Multi-Objective PSO (MOPSO)
• Purpose: Designed for optimization problems with multiple conflicting objectives.
• Mechanism: Uses Pareto dominance and maintains an archive of non-dominated
solutions.
• Example: Finding a trade-off between cost and performance in engineering design.
10. Dynamic and Neighborhood-Based PSO (DNPSO)
• Concept: Allows particles to dynamically change their neighborhoods during the
optimization process.
• Advantage: Improves adaptability to the optimization landscape, especially in
complex and multimodal problems.
11. Chaotic PSO (CPSO)
• Feature: Incorporates chaotic sequences or maps to introduce randomness into the
swarm’s behavior.
• Benefit: Enhances the exploration capacity, helping particles to escape local minima
and reach global optima.
12. Barebones PSO
• Simplification: Removes the velocity term entirely and samples new positions from a
distribution centered around the global and personal bests.
• Behavior: This variant often has fewer parameters to tune and can still achieve
effective results.
13. Multi-Swarm PSO (MSPSO)
• Structure: Consists of multiple swarms interacting with each other.
• Mechanism: Communication among swarms may be controlled or limited, ensuring
diverse search regions and robustness.

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

14. Velocity-Free PSO

• Modification: Eliminates the velocity update mechanism, using random perturbation
or direct sampling of positions.
• Use Case: Often applied where velocity updates are less meaningful.

Choosing the Right Variant

Selecting an appropriate PSO variant depends on problem characteristics, such as the presence of local
optima, problem dimensionality, and solution space properties. While standard PSO is often used for
baseline comparisons, adaptive and hybrid approaches may yield better performance for challenging
optimization tasks.

4.6 Hybrid Model of PSO

The Hybrid Model of Particle Swarm Optimization (PSO) refers to integrating the PSO
algorithm with other optimization techniques to leverage the strengths of each approach and
address specific limitations. This hybridization aims to improve the algorithm's convergence
speed, solution quality, diversity maintenance, or ability to escape local optima. Hybrid
models are widely used in complex optimization tasks, including engineering design,
combinatorial optimization, and machine learning, where PSO alone may face challenges.

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

1. Combining PSO with Genetic Algorithms (GA):

o Mechanism: PSO handles exploration by updating particle positions, while GA
applies mutation and crossover to introduce variability and enhance diversity.
o Benefit: The hybrid can avoid premature convergence that may occur in
standard PSO and better explore the search space.
2. PSO with Differential Evolution (DE):
o Mechanism: The DE algorithm generates new candidate solutions using
differential operators, which helps diversify the search space.
o Benefit: Improves the global search capability, helping PSO escape local optima
by periodically applying DE-based operators.
3. Hybrid PSO-Simulated Annealing (SA):
o Mechanism: Combines PSO’s global search capability with SA’s local search
mechanism and probabilistic acceptance of worse solutions.
o Benefit: Enhances exploration and exploitation balance, avoiding stagnation
and enhancing convergence to the global minimum.
4. PSO with Local Search Algorithms (e.g., Hill Climbing, Gradient Descent):
o Mechanism: PSO performs the global search while local search methods refine
promising solutions in specific areas.
o Benefit: Provides faster convergence and higher precision in fine-tuning
solutions.
5. PSO-Tabu Search (TS):
o Mechanism: Integrates Tabu Search memory structures to guide the particle
search away from previously visited suboptimal solutions.
o Benefit: Reduces the chance of revisiting local optima, fostering a more diverse
and robust search process.
6. Hybrid PSO-Fuzzy Logic:
o Mechanism: Fuzzy logic is used to dynamically adapt the PSO parameters such
as inertia weight or acceleration coefficients based on current swarm behavior.
o Benefit: Allows more flexible and intelligent adaptation of the search strategy
in response to real-time search dynamics.

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

4.7 Applications of Genetic Algorithms (GAs)

Genetic Algorithms (GAs) are versatile tools widely used for solving optimization, search, and
learning problems. Here are key domains where GAs are applied:

1. Optimization Problems

• Function Optimization: GAs solve complex mathematical problems where traditional

optimization methods fail, such as high-dimensional, non-linear functions.

Example: Minimizing the error in machine learning models or optimizing parameters

in deep learning networks.

• Traveling Salesman Problem (TSP): GAs help in finding near-optimal routes for the
traveling salesman by considering all possible solutions and selecting the best route.

2. Machine Learning & AI

• Neural Network Training: GAs optimize neural network weights and architectures,
providing a robust approach to prevent getting trapped in local minima.

Example: Evolving deep neural network architectures to improve image recognition

accuracy.

• Feature Selection: GAs are used to select the most relevant features from large
datasets, improving model performance and reducing overfitting.

Example: Selecting key attributes for predicting diseases based on medical datasets.

• Hyperparameter Tuning: GAs tune hyperparameters for machine learning algorithms

like decision trees or support vector machines to maximize performance.

3. Scheduling and Resource Allocation

• Job Scheduling: GAs are applied in scheduling tasks in manufacturing, data centers,
or service industries to optimize machine usage, reduce downtime, and maximize
efficiency.

Example: Optimizing production schedules for manufacturing plants.

• Timetable Scheduling: GAs help create optimal schedules for schools or universities
by balancing constraints like room availability and instructor schedules.

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

4. Robotics and Control Systems

• Path Planning: GAs assist robots in planning optimal paths in dynamic or unknown
environments by evolving solutions that avoid obstacles and meet objectives.

Example: Autonomous robots navigating through a maze.

• Controller Design: GAs are used to design control systems, optimizing parameters for
robotics, drones, and automated vehicles.

5. Engineering and Design

• Structural Design: GAs optimize the design of structures such as bridges or buildings
to minimize weight or maximize strength while meeting safety standards.

Example: Structural optimization of a bridge to withstand heavy traffic loads with

minimal material.

• Circuit Design: GAs are used in the optimization of electronic circuit designs for
minimal power consumption, cost, and material.

6. Bioinformatics

• Protein Folding: GAs help predict protein folding, a crucial task in understanding
biological functions and drug design.

Example: Evolving models for predicting protein structures based on amino acid
sequences.

• Gene Expression Analysis: GAs assist in identifying patterns in gene expression data,
crucial for cancer detection and treatment development.

7. Finance and Economics

• Portfolio Optimization: In finance, GAs optimize asset allocation in investment

portfolios to balance risk and maximize return.

Example: Designing investment portfolios that minimize risk while achieving the
desired returns.

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

• Algorithmic Trading: GAs evolve trading strategies to maximize profits in financial

markets, adjusting dynamically to market conditions.

8. Environmental and Ecological Modeling

• Wildlife Conservation: GAs help design conservation strategies, optimize resource

allocation, and protect endangered species.

Example: Optimizing the management of wildlife reserves to conserve biodiversity.

• Climate Modeling: GAs are used to model complex environmental systems and predict
the effects of climate change on ecosystems.

9. Game Theory and Strategy Design

• Game Strategy Evolution: GAs are used to evolve optimal strategies for games or
simulations by evaluating the fitness of different strategies over time.

Example: Evolving strategies for games like chess or poker to maximize winning
potential.

10. Marketing and Advertising

• Targeted Advertising: GAs optimize ad placement and targeting to increase click-

through rates and conversion in marketing campaigns.

Example: Designing personalized ad campaigns that optimize reach and engagement

based on customer preferences.

11. Telecommunications and Network Design

• Network Topology Optimization: GAs help design efficient communication networks

by optimizing the placement of routers, servers, and other network components.

Example: Optimizing the layout of a wireless network for maximum coverage and
performance.

• Routing Algorithms: GAs are applied to find the best routing paths in communication
networks to minimize delays and congestion.

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

12. Evolutionary Robotics

• Robot Behavior Evolution: GAs are used to evolve behaviors and actions in robots,
making them capable of completing tasks autonomously.

Example: Evolving robots to perform object manipulation tasks in dynamic

environments.

13. Creative Arts and Content Generation

• Art and Music Generation: GAs are used in the creative field to generate art, music,
and other creative content by evolving designs or compositions over time.

Example: Generating unique visual art or music compositions based on evolutionary

principles.

• Game Content Generation: GAs help create diverse game levels, character designs,
and other content dynamically for video games.

14. Genetic Programming

• Program Evolution: GAs evolve computer programs or algorithms that solve specific
tasks, optimizing them over multiple generations.

Example: Evolving a program to predict stock market trends or optimize a search

engine.

15. Healthcare and Medical Diagnosis

• Disease Diagnosis: GAs are used to optimize diagnostic models for disease prediction
and classification.

Example: Developing early-stage cancer detection models by analyzing medical data

and patient history.

16. Artificial Life and Simulation

• Simulating Evolution: GAs are employed in artificial life simulations to model

evolutionary processes and study the behavior of simulated organisms or systems.

Example: Simulating the evolution of species in a digital ecosystem.

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING

 Department of Information Technology, Vardhaman College of Engineering, Hyderabad.
Web:([Link])

SAROJA/LECTURE NOTE/VMEG/SOFT COMPUTING