Particle Swarm Optimization (PSO) represents an optimization method that draws inspiration from the coordinated actions observed in natural entities such as birds or fish. Originally proposed by James Kennedy and Russell Eberhart in 1995, PSO involves a group of potential solutions known as particles, which navigate through the exploration area with the aim of uncovering the best possible solution. Every particle modifies its location by considering its individual encounters as well as the encounters of nearby particles.
These modifications are driven by two primary principles: investigating potential areas and capitalizing on effective solutions. PSO is distinguished by its simplicity and efficiency in addressing intricate optimization challenges. It eliminates the need for gradient computations, which is beneficial for scenarios where gradients are either unavailable or excessively expensive to determine. Its capacity to effectively navigate extensive search domains and rapidly reach optimal or nearly optimal outcomes has established it as a favored method across multiple sectors such as engineering, finance, and AI.
Key Concepts:
PSO simulates a group of particles, with each one symbolizing a possible solution within the exploration area. These particles navigate the space by adapting their locations according to their individual encounters and the shared knowledge from nearby particles. Key elements of PSO consist of:
Particles: Every individual particle within the search space is defined by both its position, which signifies a potential solution, and its velocity, indicating the direction in which it is moving.
A swarm refers to a group of particles collaborating to collectively navigate and investigate the search area.
The objective function refers to the function that needs to be optimized. The fitness of each particle is assessed according to this specific function.
The personal best (pBest) refers to the optimal position that a particle has attained up to that point.
Global Optimum (gBest): The optimal position discovered by any individual particle within the collective swarm.
The PSO algorithm involves the following steps:
Initialization: Start by randomly setting the positions and velocities of each particle within the search space.
Assessment: Determine the fitness of individual particles by applying the objective function.
Update pBest and gBest:
Update the pBest value for each particle if its current position is an improvement over its previous best position.
Update the global best (gBest) if the current position of any particle surpasses the current global best position.
Update Velocities and Positions:
Modify the speed of each particle according to its existing velocity, the proximity to its personal best (pBest), and the proximity to the global best (gBest).
Revise the position of each individual particle based on the updated velocity.
Repeat the assessment and modification procedures until reaching a stopping condition, such as achieving a predetermined number of iterations or reaching a satisfactory fitness level.
Approach-1: Using Vectors
This particle swarm optimization (PSO) implementation is versatile and can be utilized to enhance any objective function by specifying its definition in the objective function Method. Moreover, the parameters like the quantity of particles, dimensions, and iterations can be modified based on the needs of the problem.
This code showcases a fundamental application of the Particle Swarm Optimization (PSO) algorithm in C++, which can be expanded and tailored for different optimization challenges. The straightforward yet powerful nature of the PSO algorithm has made it a widely favored option for tackling intricate optimization problems across different fields.
Program:
#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
#include <cstdlib>
#include <ctime>
// Particle class representing an individual particle
class Particle {
public:
std::vector<double> position;
std::vector<double> velocity;
std::vector<double> best_position;
double fitness;
double best_fitness;
// Constructor to initialize a particle with a given number of dimensions
Particle(int dimensions) {
position.resize(dimensions);
velocity.resize(dimensions);
best_position.resize(dimensions);
fitness = std::numeric_limits<double>::max();
best_fitness = std::numeric_limits<double>::max();
}
};
// Swarm class representing the entire swarm of particles
class Swarm {
public:
std::vector<Particle> particles;
std::vector<double> global_best_position;
double global_best_fitness;
// Constructor to initialize the swarm with a given number of particles and dimensions
Swarm(int num_particles, int dimensions) {
particles.resize(num_particles, Particle(dimensions));
global_best_position.resize(dimensions);
global_best_fitness = std::numeric_limits<double>::max();
}
//Method to initialize particle positions and velocities randomly
void initialize() {
for (auto& particle : particles) {
for (size_t i = 0; i < particle.position.size(); ++i) {
particle.position[i] = static_cast<double>(rand()) / RAND_MAX;
particle.velocity[i] = (static_cast<double>(rand()) / RAND_MAX) - 0.5;
}
}
}
//Method to update the global best position
void update_global_best() {
for (const auto& particle : particles) {
if (particle.fitness < global_best_fitness) {
global_best_fitness = particle.fitness;
global_best_position = particle.best_position;
}
}
}
};
// Objective function to be optimized (example: Sphere function)
double objective_function(const std::vector<double>& position) {
double result = 0.0;
for (const auto& x : position) {
result += x * x;
}
return result;
}
// Method to update the velocity of a particle
void update_velocity(Particle& particle, const std::vector<double>& global_best_position, double w, double c1, double c2) {
for (size_t i = 0; i < particle.velocity.size(); ++i) {
double r1 = static_cast<double>(rand()) / RAND_MAX;
double r2 = static_cast<double>(rand()) / RAND_MAX;
particle.velocity[i] = w * particle.velocity[i] +
c1 * r1 * (particle.best_position[i] - particle.position[i]) +
c2 * r2 * (global_best_position[i] - particle.position[i]);
}
}
//Method to update the position of a particle
void update_position(Particle& particle) {
for (size_t i = 0; i < particle.position.size(); ++i) {
particle.position[i] += particle.velocity[i];
}
}
// Particle Swarm Optimization algorithm
void PSO(int num_particles, int dimensions, int max_iterations) {
Swarm swarm(num_particles, dimensions);
swarm.initialize();
for (int iter = 0; iter < max_iterations; ++iter) {
for (auto& particle : swarm.particles) {
particle.fitness = objective_function(particle.position);
if (particle.fitness < particle.best_fitness) {
particle.best_fitness = particle.fitness;
particle.best_position = particle.position;
}
}
swarm.update_global_best();
for (auto& particle : swarm.particles) {
update_velocity(particle, swarm.global_best_position, 0.5, 1.5, 1.5);
update_position(particle);
}
std::cout << "Iteration " << iter << ": Global Best Fitness = " << swarm.global_best_fitness << std::endl;
}
}
int main() {
srand(static_cast<unsigned int>(time(0))); // Seed the random number generator
PSO(30, 2, 10); // Run PSO for 10 iterations
return 0;
}
Output:
Iteration 0: Global Best Fitness = 0.0029762
Iteration 1: Global Best Fitness = 0.0029762
Iteration 2: Global Best Fitness = 0.000553463
Iteration 3: Global Best Fitness = 0.000553463
Iteration 4: Global Best Fitness = 0.000198333
Iteration 5: Global Best Fitness = 0.000198333
Iteration 6: Global Best Fitness = 0.000187206
Iteration 7: Global Best Fitness = 0.00016765
Iteration 8: Global Best Fitness = 3.14658e-05
Iteration 9: Global Best Fitness = 2.99408e-05
Explanation:
The Particle class defines a single particle within the swarm, encapsulating characteristics like location, speed, best personal position, health level, and optimal health level. These properties are managed as vectors to handle challenges across various dimensions.
The Swarm class oversees the grouping of particles, maintaining a vector of particles while monitoring the best position and fitness discovered by the swarm. To update the global best position and fitness, the class compares the fitness value of each particle with the current global best fitness.
The purpose of the objective function is to evaluate a particle's fitness by considering its current position. In this instance, a basic objective function called the Sphere function is employed. This function determines the fitness value by summing the squares of each dimension of the particle's position.
Initialization: The swarm class's initialize method effectively sets random positions and velocities for all particles, playing a vital role in navigating the search space.
Revise Velocity and Location: The updatevelocity and updateposition functions adjust the velocity and location of each particle according to the principles of PSO. These principles incorporate components related to inertia, cognition, and social behavior, influencing how particles converge towards the optimal global position and their individual best positions.
The Particle Swarm Optimization (PSO) Algorithm: The main role of the PSO function is to drive the optimization process. It kicks off by setting up the swarm, generating a group of particles with random velocities and positions. Following this, it assesses the fitness of each particle using the objective function. The function then revises the personal best position and fitness for each particle, along with identifying the global best position and fitness achieved by the entire swarm. These adjustments occur in a step-by-step manner over a defined number of iterations, enabling the swarm to efficiently navigate and capitalize on the search space.
The primary function acts as the starting point of the software. It initializes the random number generator to guarantee the reproducibility of outcomes and invokes the PSO function with defined parameters such as the quantity of particles, dimensions, and maximum iterations. By observing the global best fitness value displayed at every iteration, individuals can monitor the advancement of optimization and evaluate how well the PSO algorithm works in discovering optimal or close-to-optimal answers for the given optimization challenge.
Complexity Analysis:
Evaluating the time and space efficiency of the given Particle Swarm Optimization (PSO) algorithm requires a thorough comprehension of the tasks conducted during each phase of the algorithm and the types of data structures employed.
Time Complexity:
Initialization: The time complexity of setting up the swarm with random positions and velocities is O(N * D), with N representing the particle count, and D representing the dimensions. This is due to the requirement of initializing position and velocity vectors for each particle.
Calculating the health of every particle requires assessing the objective function, which operates at a time complexity of O(D), with D representing the number of dimensions. As this process is executed for every individual particle, the overall time complexity for fitness assessment amounts to O(N * D).
Global Optimal Update: The process of updating the global optimal position requires looping through all particles to assess their fitness values against the global optimal fitness. This process carries a time complexity of O(N).
Velocity and Location Adjustment: Modifying the velocity and position of individual particles requires basic mathematical calculations on the velocity and position vectors. As this process is carried out for every particle, the computational complexity is O(N * D), with N representing the quantity of particles and D denoting the dimensionality.
Iterations: The Particle Swarm Optimization (PSO) algorithm operates for a designated quantity of iterations. As a result, the computational complexity of the complete PSO algorithm can be expressed as O(iterations N D), where iterations represents the total number of iterations, N denotes the quantity of particles, and D signifies the number of dimensions.
Space Complexity:
Particle Data Structure: Every individual particle is defined by a data structure that includes vectors to store its position, velocity, and the best position it has achieved so far. The storage requirement for a single particle amounts to O(3 * D) in terms of space complexity, with D representing the total number of dimensions.
The swarm is comprised of a collection of particles, resulting in a spatial requirement of O(N 3 D) to store the swarm, with N representing the quantity of particles and D indicating the dimensionality.
The optimal global location is maintained as a vector, resulting in a storage complexity of O(D), with D representing the dimension count.
Additional Memory Usage: The algorithm necessitates extra memory for variables involved in calculations, like loop counters, temporary variables, and random number generation. Nonetheless, the space they occupy is minimal in comparison to the primary data structures.
Approach-2: Using Linked List
The example showcases the effective utilization of a linked list data structure to control particles within the PSO algorithm. This data structure offers flexible memory allocation and simplifies the process of adding and navigating elements, which is ideal for managing varying quantities of particles throughout the optimization procedure.
Program:
#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
#include <cstdlib>
#include <ctime>
// Define a structure for particle data
struct Particle {
std::vector<double> position;
std::vector<double> velocity;
std::vector<double> best_position;
double fitness;
double best_fitness;
};
// Define a structure for a linked list node
struct Node {
Particle data;
Node* next;
};
// Define a structure for the linked list
class LinkedList {
private:
Node* head;
public:
// Constructor to initialize an empty linked list
LinkedList() {
head = nullptr;
}
// Destructor to deallocate memory when the list is destroyed
~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* next = current->next;
delete current;
current = next;
}
}
//Method to insert a new particle at the beginning of the list
void insertAtBeginning(Particle particle) {
Node* newNode = new Node{particle, head};
head = newNode;
}
//Method to display the particles in the list
void display() {
Node* current = head;
while (current != nullptr) {
std::cout << "Position: ";
for (double pos : current->data.position) {
std::cout << pos << " ";
}
std::cout << "| Fitness: " << current->data.fitness << std::endl;
current = current->next;
}
}
};
// Objective function to be optimized (example: Sphere function)
double objective_function(const std::vector<double>& position) {
double result = 0.0;
for (const auto& x : position) {
result += x * x;
}
return result;
}
// Initialize a particle with random position and velocity
Particle initialize_particle(int dimensions) {
Particle particle;
for (int i = 0; i < dimensions; ++i) {
particle.position.push_back(static_cast<double>(rand()) / RAND_MAX);
particle.velocity.push_back((static_cast<double>(rand()) / RAND_MAX) - 0.5);
}
particle.fitness = objective_function(particle.position);
particle.best_position = particle.position;
particle.best_fitness = particle.fitness;
return particle;
}
// PSO algorithm using a linked list
void PSO(int num_particles, int dimensions, int max_iterations) {
LinkedList swarm; // Create a linked list to store particles
// Initialize particles and add them to the linked list
for (int i = 0; i < num_particles; ++i) {
Particle particle = initialize_particle(dimensions);
swarm.insertAtBeginning(particle);
}
// Display the initial state of the swarm
std::cout << "Initial state of the swarm:" << std::endl;
swarm.display();
// PSO iterations
for (int iter = 0; iter < max_iterations; ++iter) {
// Update each particle's position and velocity
// (omitted for brevity)
// Update each particle's fitness and best position
// (omitted for brevity)
// Update the global best position
// (omitted for brevity)
// Display the state of the swarm at each iteration
std::cout << "Iteration " << iter + 1 << ":" << std::endl;
swarm.display();
}
}
int main() {
srand(static_cast<unsigned int>(time(0))); // Seed the random number generator
int num_particles = 5;
int dimensions = 2;
int max_iterations = 3;
PSO(num_particles, dimensions, max_iterations);
return 0;
}
Output:
Initial state of the swarm:
Position: 0.134002 0.29139 | Fitness: 0.102865
Position: 0.963568 0.851058 | Fitness: 1.65276
Position: 0.717642 0.642082 | Fitness: 0.927279
Position: 0.885449 0.23609 | Fitness: 0.839758
Position: 0.838268 0.354988 | Fitness: 0.82871
Iteration 1:
Position: 0.134002 0.29139 | Fitness: 0.102865
Position: 0.963568 0.851058 | Fitness: 1.65276
Position: 0.717642 0.642082 | Fitness: 0.927279
Position: 0.885449 0.23609 | Fitness: 0.839758
Position: 0.838268 0.354988 | Fitness: 0.82871
Iteration 2:
Position: 0.134002 0.29139 | Fitness: 0.102865
Position: 0.963568 0.851058 | Fitness: 1.65276
Position: 0.717642 0.642082 | Fitness: 0.927279
Position: 0.885449 0.23609 | Fitness: 0.839758
Position: 0.838268 0.354988 | Fitness: 0.82871
Iteration 3:
Position: 0.134002 0.29139 | Fitness: 0.102865
Position: 0.963568 0.851058 | Fitness: 1.65276
Position: 0.717642 0.642082 | Fitness: 0.927279
Position: 0.885449 0.23609 | Fitness: 0.839758
Position: 0.838268 0.354988 | Fitness: 0.82871
Explanation:
Linked List Structure:
The setup employs a linked list to handle the particles within the swarm. Every individual particle in the PSO algorithm is symbolized by a node within the linked list, enabling convenient addition and navigation of particles.
Particle Structure:
A particle is a construct that holds properties like location, speed, health, and optimal location. These properties signify the current condition of each particle within the PSO algorithm.
Objective Function:
The goal of the objective function is to determine a particle's fitness by evaluating its position. Within the given code, a basic objective function known as the Sphere function is applied. This function determines the fitness value by summing the squares of each dimension of the particle's position.
Initialization of Particles:
The Particle Swarm Optimization (PSO) algorithm commences by setting up a designated quantity of particles with random positions and velocities. Every particle's position and velocity vectors are initialized in a random manner, and its fitness value is calculated by evaluating the objective function.
Insertion into Linked List:
Once each particle is initialized, it is placed at the start of the linked list. This insertion method facilitates the seamless addition of particles to the swarm while preserving their sequential arrangement within the list.
PSO Iterations:
The Particle Swarm Optimization (PSO) algorithm runs for a defined number of iterations. Throughout each iteration, the particles' positions and velocities are adjusted following the rules of the PSO. Moreover, the fitness values and optimal positions of the particles are recomputed according to their current locations.
Displaying Swarm State:
At every step of the PSO algorithm, the swarm's status, which encompasses the location and performance of each particle, is showcased through the linked list format. This grants visibility into the advancement of the optimization procedure and enables tracking of particle motions.
Memory Management:
Freeing up memory for the nodes in a linked list upon its destruction guarantees correct memory handling, preventing any memory leaks and promoting optimal utilization of system resources.
Main Function:
The primary function initiates the random number generator, sets the parameters for the PSO algorithm (such as the number of particles, dimensions, and maximum iterations), and invokes the PSO function to run the optimization procedure.
Complexity Analysis:
Time Complexity:
Initialization of Particles:
Creating the initial state of each particle requires the generation of random positions and velocities. This operation consumes O(D) time for every dimension, with D representing the total number of dimensions. As this procedure is conducted for each individual particle, the overall time complexity amounts to O(N * D), with N denoting the quantity of particles.
Insertion into Linked List:
Adding a node at the start of a linked list is an operation that takes constant time because it involves only updating the head pointer. Therefore, the computational complexity for inserting N nodes into the linked list is O(N).
PSO Iterations:
Each cycle of the PSO algorithm requires adjusting the positions and speeds of every particle, which consumes O(D) time per dimension. Furthermore, updating the fitness scores and optimal positions of particles also requires O(D) time for each dimension. Consequently, the time complexity for each cycle is O(N * D), with N representing the quantity of particles and D representing the number of dimensions.
The Particle Swarm Optimization (PSO) algorithm operates for a designated quantity of iterations, resulting in a time complexity of O(iterations N D). Here, iterations represent the total number of iterations, N denotes the quantity of particles, and D signifies the number of dimensions involved in the algorithm.
Displaying Swarm State:
Traversing through the entire linked list to showcase the swarm's status during each iteration requires printing the location and performance of every individual particle. This process consumes O(N) time for every iteration, with N representing the total particle count.
Space Complexity:
Particle Structure:
Each individual in the PSO algorithm is symbolized by a configuration that includes arrays for location, speed, and additional characteristics. The storage requirements for one individual particle amount to O(D), where D represents the dimensions involved.
Linked List:
The storage space required to hold the linked list is O(N), with N representing the quantity of particles. Every node within the linked list encompasses a particle configuration, causing the space complexity of the linked list to scale in accordance with the total number of particles in the group.
Objective Function and Auxiliary Variables:
Storing additional variables like loop counters and temporary variables in the PSO algorithm has a minimal impact on space complexity when compared to the primary data structures. Thus, the space complexity remains largely unaffected.
