BIOLOGICALLY INSPIRED ALGORITHMS 1(PSO).
I had never heard of PSO OR GA till recently when I was working on a project where I was tasked with building an intrusion detection model for industrial Internet of Things purposes. I used the hybrid algorithm of these two algorithms as my feature selection method after experimenting with both of them separately, for this blog post, I have replaced the problem we are trying to solve with general mathematical optimisation problems instead of the client’s data. I’ll discuss each of the topics independently before briefly discussing a hybrid approach in a series of blog posts. There is a GitHub repo attached that contains the codes in the post.
PARTICLE SWARM OPTIMIZATION(PSO)
Particle swarm optimization is a computational method used for optimizing different types of functions. It is inspired by the social behaviour of birds flocking or fish schooling. In a problem space, PSO explores a group of candidate solutions called particles, they move around in the search space to find optimal or near-optimal solutions, to say the least. PSO particles adjust their positions by following the best-performing particles in the swarm, just like when a flock of birds are looking for food, they are likely to follow the bird that is closest or knows the food source.
Key Concepts
Particle: individual agent representing a potential solution to the optimization problem at hand.
Position: the current location of a particle in the search space
Velocity: the rate of change of the particle’s position
Personal best position: the best: the best position a particle has visited so far, based on the fitness value.
Global best position: the best position discovered by any particle in the swarm.
Fitness function: a function that evaluates how close a given solution is to the optimum.
Algorithm Steps
Initialization: the first thing to be done is to randomly initialize the particle’s positions and velocities within the given search space.
Evaluation: compute the fitness value for each particle’s position. The fitness value depends on the problem or task at hand(e.g. minimizing a mathematical function).
Update Personal Bests: yes, you guessed right, after the evaluation stage, the next thing to do is to update the personal best for particles whose current position yields a better fitness value than their personal best.
Update Global Bests: in this stage, just as you thought, the particle with the best fitness value is identified, if it’s better than the current global best, the global best is updated.
Update Velocities and Positions: two things occur at this stage:
-update each particle velocity based on its own personal best and the global best.
-update positions by adding the new velocity to the current position.
Termination conditions: a predefined number of iterations is the one I used in my sample code for this post, other methods include: an acceptable fitness value reached, no improvement over a certain number of iterations etc.
THE ROSENBROCK FUNCTION
It is a non-convex function which is used as a performance test problem for optimization algorithms. The global minimum is inside a long, narrow, parabolic-shaped flat valley. Finding the valley is trivial, converging to the global minimum, however, is difficult.
The function is defined by :
f(x,y) = (a-x)² + b(y-x²)²
Get Funboy Ea’s stories in your inbox
Join Medium for free to get updates from this writer.
However, for the purpose of this tutorial, there is a slight difference between the function above and the one in my code. While the one defined in the tutorial above is the two-dimensional function, the one in my code is of the nth dimension.
Where in my code, what the function does is to sum over all consecutive pairs in the input vector \(x\), allowing the function to enable handle vectors with any length \(n\).
PSO Parameters
Inertia weight (w):
-balances exploration and exploitation.
-a higher (w) encourages exploration while a lower (w) encourages exploitation.
Personal and social coefficients(c1,c2):
-In c1, the cognitive component encourages particles to move towards their personal best.
-c2, the social component encourages particles to move towards the global best.
Velocity clamping:
-limits the maximum velocity to prevent particles from moving too fast.
Advantages of PSO
Simplicity
Flexibility
Efficient
Few parameters
Limitations of PSO
Local optima: may get trapped in local minima, especially in complex landscapes.
Parameter sensitivity: performance depends heavily on properly tuned parameters.
Diversity loss: swarm diversity may decrease over iterations, leading to premature convergence.
Applications of PSO
Machine learning: in training neural networks, and clustering data, to be more specific, I used PSO as a feature selection method.
Control systems: tuning controllers like PID controllers.
Particle Swarm Optimization is a robust and efficient Optimization algorithm inspired by the social behaviours observed in nature. By leveraging individual experiences and social interactions, it effectively navigates complex search spaces to find optimal solutions.
Here is the link to the GitHub repo that holds my sample code: “https://github.com/abeenoch/PARTICLE-SWARM-OPTIMIZTION-GENETIC-ALGORITHM/blob/main/PSO.py"
