Swarm Intelligence: Particles, Ants and Bees

Collective behaviour as computation

A flock of birds turns as one body although no bird leads it. Reynolds reproduced this with three local rules for each simulated bird: avoid crowding neighbours, align with their heading, and move towards their centre [1]. Ant colonies find short paths between nest and food without a map, because ants deposit pheromone and prefer trails with more of it; shorter trails are completed faster and accumulate pheromone sooner. Honeybee colonies allocate foragers to flower patches in proportion to their quality through the waggle dance. These systems share decentralised control, simple agents, local interaction and emergent global behaviour, which Bonabeau, Dorigo and Theraulaz summarised as swarm intelligence [2].

Particle swarm optimisation

Kennedy and Eberhart introduced particle swarm optimisation in 1995, inspired by bird flocking and social behaviour [3]. Each particle i has a position x, which is a candidate solution, and a velocity v. It remembers the best position p it has visited, and the swarm shares the best position g found by any particle. In every iteration, the velocity is updated as v = w v + c1 r1 (p - x) + c2 r2 (g - x), and the position as x = x + v, where r1 and r2 are random numbers between 0 and 1 drawn for each dimension.

The three terms have clear meanings. The inertia weight w keeps part of the previous motion; Shi and Eberhart introduced it to balance global and local search, with values around 0.4 to 0.9 [4]. The cognitive term, weighted by c1, pulls a particle back towards its own best experience. The social term, weighted by c2, pulls it towards the best experience of the swarm. Clerc and Kennedy analysed the dynamics and derived a constriction factor that guarantees convergence; the widely used setting w = 0.7298 with c1 = c2 = 1.49618 follows from it [5]. Particle swarms are easy to implement, need no gradients, and work well on continuous problems of moderate dimension, but like every metaheuristic they can stagnate in a local optimum.

Tuning a PID controller with a swarm

The proportional-integral-derivative controller is the workhorse of industrial control. Its three gains shape the response: The proportional gain speeds up the reaction, the integral gain removes steady-state error, and the derivative gain damps oscillation [6]. Tuning them by hand is tedious, and classical rules assume simple process models. Controller tuning can instead be formulated as optimisation: Choose the gains that minimise a cost computed from a simulated step response, such as the integral of the time-weighted absolute error (ITAE), with penalties for overshoot and limits on the actuator. Particle swarms have been used in this way for automatic voltage regulators and many other loops [7].

The notebook applies the method to the speed control of a DC motor, using the standard model and parameters of the Control Tutorials for MATLAB and Simulink [8]. The armature voltage is limited to 24 volts, which makes the problem nonlinear, and the swarm evaluates all particles in one vectorised simulation. The cost function is part of the design: A cost that rewards speed alone drives the gains to their bounds, and adding a penalty on overshoot or control effort changes the optimum. The optimiser serves the engineer's definition of good behaviour; it cannot supply that definition.

Ant colony optimisation

Dorigo, Maniezzo and Colorni turned the pheromone mechanism into the Ant System for the travelling salesman problem [9]. Each artificial ant builds a complete tour city by city. From city i, it chooses the next unvisited city j with a probability proportional to the pheromone on edge (i, j) raised to a power alpha, times a heuristic desirability, usually the inverse distance, raised to a power beta. After all ants have finished, pheromone evaporates on every edge by a factor rho, and each ant deposits pheromone on the edges of its tour in inverse proportion to the tour length. Short tours therefore reinforce their edges, while evaporation forgets poor early choices.

The Ant Colony System added a stronger exploitation rule and local pheromone updates and was competitive on benchmark instances [10]; the monograph by Dorigo and Stützle presents the family and its applications to routing, scheduling and assignment [11]. Drilling holes in a printed circuit board is a classical travelling salesman application: The drill head must visit every hole once, and the travel time between holes is wasted production time. Benchmark libraries such as TSPLIB include instances that come from drilling problems [12].

Artificial bee colony and the metaphor question

Karaboga and Basturk's artificial bee colony algorithm assigns roles to solutions [13]. Employed bees search around their food sources, onlooker bees choose sources in proportion to their quality and search around them, and scout bees replace sources that have not improved for a number of trials with random new ones. The scout phase gives the algorithm a built-in restart mechanism. Many further algorithms followed, inspired by fireflies, bats, wolves, whales and others, including the ant lion optimiser used to train neural networks for chaotic signal prediction in earlier work [14].

Sörensen argued that the flood of metaphor-based algorithms often hides old ideas behind new vocabulary and weak experiments [15]. The no free lunch theorems add that no algorithm can be best on all problems [16]. Engineers should therefore judge a metaheuristic by its search mechanism rather than its metaphor, compare it with established methods on the problem at hand, report results over many independent runs with statistics, and count function evaluations, not iterations, because a single evaluation of an engineering simulation may take minutes.

Review cards

Select a card to turn it over.

References