particle swarm optimization
In plain wordsAn optimization method inspired by flocking birds: candidate solutions 'fly' through the space of possibilities, each pulled toward the best spot it has found and the best spot its neighbors have found.
A population-based optimization method for continuous search spaces in which each particle has a position (a candidate solution) and a velocity. At each step a particle's velocity becomes a weighted sum of its previous velocity (inertia), a randomly scaled pull toward the best position it has personally found, and a randomly scaled pull toward the best position found by its neighborhood or the whole swarm; the particle then moves by that velocity. Parameters such as the inertia weight or a constriction coefficient balance exploration against convergence. Particle swarm optimization needs no gradients and is simple to implement and parallelize; it is used for engineering design, controller tuning, feature selection and hyperparameter search, though it can converge prematurely and lacks general convergence guarantees.
Origin
Introduced by the social psychologist James Kennedy and the electrical engineer Russell Eberhart at the 1995 IEEE International Conference on Neural Networks, growing out of simulations of bird flocking and social behavior; Yuhui Shi and Eberhart added the inertia weight in 1998.
Usage note
In the formula, x_i and v_i are particle i's position and velocity, p_i its personal best, g the neighborhood or global best, w the inertia weight, c_1 and c_2 acceleration constants and r_1, r_2 fresh random numbers in [0, 1].
Related
- swarm intelligenceswarm intelligence, n.: The teamwork that appears when crowds of simple creatures or machines, such as ants, bees or small robots, each respond only to what is nearby, with nobody in charge, yet together solve problems.
- ant colony optimizationant colony optimization, n.: A method for finding good routes and schedules inspired by how ants find short paths to food: simulated ants leave 'scent' on good paths, which attracts other ants, so the best routes gradually stand out.
- evolutionary computationevolutionary computation, n.: Problem-solving by simulated evolution, much as breeders improve crops: keep many candidate answers, let the better ones produce slightly altered offspring, drop the worse, and repeat for many rounds.
- metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one.
- genetic algorithmgenetic algorithm, n.: A problem-solving method that copies natural evolution: many candidate solutions compete, the best are 'bred' by mixing and randomly tweaking them, and over many generations the solutions improve.
Sources
- Kennedy, J. & Eberhart, R. (1995). Particle Swarm Optimization. Proceedings of the IEEE International Conference on Neural Networks, Perth, 1942–1948.
Mentioned in
swarm intelligenceswarm intelligence, n.: The teamwork that appears when crowds of simple creatures or machines, such as ants, bees or small robots, each respond only to what is nearby, with nobody in charge, yet together solve problems., ant colony optimizationant colony optimization, n.: A method for finding good routes and schedules inspired by how ants find short paths to food: simulated ants leave 'scent' on good paths, which attracts other ants, so the best routes gradually stand out., metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one., swarm roboticsswarm robotics, n.: Coordinating large groups of simple robots that follow local rules and talk only to their neighbors, so useful group behavior emerges without a central controller, as in ant colonies or bird flocks.