Particle swarm optimization (PSO) is a computational method in artificial intelligence and computational science that optimizes a problem by iteratively improving a population of candidate solutions with respect to a given measure of quality. It solves a problem through interactions among a population of candidate solutions, dubbed particles, moving them around in the search-space according to simple mathematical formulae that adjust each particle's position and velocity. Each particle's movement is influenced by its own best known position so far and by the best known position in its topological neighborhood, which may include the entire population if specified. Vectors are updated as better positions are found, and this is expected to move the swarm toward good solutions.
PSO is a metaheuristic because it makes few or no assumptions about the problem being optimized and can search very large spaces of candidate solutions. It does not use the gradient of the problem, so it does not require the optimization problem to be differentiable, unlike classic methods such as gradient descent or quasi-Newton methods. However, metaheuristics like PSO do not guarantee that an optimal solution will ever be found.
Origins and Development
PSO was originally attributed to Kennedy and Eberhart, who first intended it for simulating social behavior as a stylized representation of the movement of organisms in a bird flock or fish school, or the evolution of attitudes in a human population. The simulation of principles of social behavior was observed to be capable of solving hard mathematical problems. The book by Kennedy and Eberhart describes many philosophical aspects of PSO and swarm intelligence. An extensive survey of PSO applications was made by Poli, and in 2017 a comprehensive review on theoretical and experimental works on PSO was published by Bonyadi and Michalewicz.
Algorithm
A basic variant of the PSO algorithm is initialized with a connected population (called a swarm) of candidate solutions (called particles). A candidate solution is a vector of numeric values that can be considered as coordinates of a point in a search space; as an iteratively moving point, it can be conceptualized as a particle. The particles move around in the search-space according to a few simple formulae. Each particle has some neighbors it is connected to, where the neighborhood may be a few or all other population members. The next position of a particle is stochastically determined by its own best-so-far position in the search space as well as the particle's best neighbor's best-so-far position. When an improved position is discovered - one that produces a better result in the objective function - the best-so-far position of the particle is updated. The process is repeated, and by doing so it is expected, but not guaranteed, that a satisfactory solution will eventually be discovered.
Formally, let \( f: \mathbb{R}^n \to \mathbb{R} \) be the cost function to be minimized. The function takes a candidate solution as an argument in the form of a vector of real numbers and produces a real number as output indicating the objective function value. The gradient of \( f \) is not known. The goal is to find a solution \( a \) for which \( f(a) \le f(b) \) for all \( b \) in the search-space, meaning \( a \) is the global minimum.
Let \( S \) be the number of particles in the swarm, each having a position \( x_i \in \mathbb{R}^n \) and a velocity \( v_i \in \mathbb{R}^n \). Let \( p_i \) be the best known position of particle \( i \), and let \( g \) be the best known position of the particle's neighborhood. A basic PSO algorithm to minimize the cost function is:
- For each particle \( i = 1, \dots, S \):
- Initialize the particle's position with a uniformly distributed random vector: \( x_i \sim U(b_{lo}, b_{up}) \).
- Initialize the particle's best known position to its initial position: \( p_i \leftarrow x_i \).
- If \( f(p_i) < f(g) \), update the swarm's best known position: \( g \leftarrow p_i \).
- Initialize the particle's velocity: \( v_i \sim U(-|b_{up}-b_{lo}|, |b_{up}-b_{lo}|) \).
- While a termination criterion is not met:
- For each particle \( i = 1, \dots, S \):
- For each dimension \( d = 1, \dots, n \):
- Pick random numbers \( r_p, r_g \sim U(0,1) \).
- Update the particle's velocity: \( v_{i,d} \leftarrow w v_{i,d} + \phi_p r_p (p_{i,d} - x_{i,d}) + \phi_g r_g (g_d - x_{i,d}) \).
- Update the particle's position: \( x_i \leftarrow x_i + v_i \).
- If \( f(x_i) < f(p_i) \), update the particle's best known position: \( p_i \leftarrow x_i \).
- If \( f(p_i) < f(g) \), update the swarm's best known position: \( g \leftarrow p_i \).
The values \( b_{lo} \) and \( b_{up} \) represent the lower and upper boundaries of the search-space. The parameter \( w \) is the inertia weight. The parameters \( \phi_p \) and \( \phi_g \) are often called the cognitive coefficient and social coefficient. The termination criterion can be the number of iterations performed or a solution where an adequate objective function value is found. The parameters \( w \), \( \phi_p \), and \( \phi_g \) are selected by the practitioner and control the behavior and efficacy of the PSO method.
Parameter Selection
The choice of PSO parameters can have a large impact on optimization performance. Selecting parameters that yield good performance has been the subject of much research. To prevent divergence ("explosion"), the inertia weight must be smaller than 1. The two other parameters can be derived using the constriction approach or freely selected, but analyses suggest convergence domains to constrain them. Typical values are in the range [1, 3]. The PSO parameters can also be tuned by using another overlaying optimizer, a concept known as meta-optimization, or even fine-tuned during the optimization, e.g., by means of fuzzy logic. Parameters have also been tuned for various optimization scenarios.
Neighbourhoods and Topologies
The topology of the swarm defines the subset of particles with which each particle can exchange information. The basic version of the algorithm uses the global topology as the swarm communication structure. This topology allows all particles to communicate with all other particles, so the whole swarm shares the same best position \( g \) from a single particle. However, this approach might lead the swarm to be trapped in a local minimum, so different topologies have been used to control the flow of information among particles. For instance, in local topologies, particles only share information with a subset of particles. This subset can be a geometrical one - for example "the m nearest particles" - or, more often, a social one, i.e., a set of particles not depending on any distance. In such cases, the PSO variant is said to be local best (vs global best for the basic PSO). A commonly used swarm topology is the ring, in which each particle has just two neighbors, but there are many others. The topology is not necessarily static; it can change during the optimization process.
Applications and Related Methods
PSO has been applied to a wide range of optimization problems across fields such as engineering, economics, and machine learning. It is particularly useful when the search space is large and the objective function is non-differentiable or noisy. PSO shares similarities with other population-based metaheuristics, such as genetic algorithms and ant colony optimization, but it is distinguished by its velocity-update mechanism inspired by social behavior. In the context of machine learning, PSO can be used for hyperparameter tuning or training neural networks, though it is often compared with gradient-based methods. Its stochastic nature and lack of gradient requirements make it a versatile tool in the broader field of artificial intelligence.