Swarm intelligence

Swarm intelligence: collective behavior of decentralized self-organized systems, made up of simple agents following simple rules

• global control is hard to define (larger systems lead to more errors)
• robust and relatively simple to use

Swarming - boids

Rules:

1. Collision avoidance: avoid collision with neighbors
   
2. Velocity matching: match the velocity of neighbors
   
3. Flock centering: stay near neighbors
   

Ant colony optimization (ACO)

Metaheuristic abstraction of a (probabilistic) graph construction using heuristic information of pheromone trails of ant colonies
Individual agents (ants) deposit more pheromone along shorter paths to goal (as they pass it quicker and because of that more times) than other possibly longer paths

• Agents still randomly choose one path of many (with probability based on pheromone density)
• Pheromone evaporation ensures new / frequently used paths overshadow older / less used ones

Generic ACO

Algorithm:

1. Initialize pheromones
2. For each ant, while stopping criteria (eg. leaderboard stagnation, max iterations, …) not satisfied:
   1. Select route (using pheromones and path cost)
   2. Apply local optimization
   3. Update pheromones - enforcement and evaporation
3. Return best solution

Pheromone updates:

$$\begin{array}{rl}{\tau }_{ij}& =(1-\rho ){\tau }_{ij}+\Delta {\tau }_{ij}\\ \Delta {\tau }_{ij}& =\{\begin{array}{ll}\frac{1}{C_{ij}}& ...\text{ant takes edge i-j}\\ 0& ...otherwise\end{array}\end{array}$$

• ${\tau }_{ij}$ … amount of pheromones on edge $i-j$
• $\Delta {\tau }_{ij}$ … newly added pheromones on edge $i-j$
• $\rho$ … speed of evaporation
• $C_{ij}$ … cost of edge $i-j$

Pros: greedy heuristic with distributed computation $\to$ rapid discovery of good solutions, avoiding premature convergence
Cons: possible slow convergence with no outside guidance towards good solutions

Particle swarm optimization (PSO)

Population-based stochastic optimization technique of optimal solution search with inspiration of swarms of insects, schools of fish, …

Individuals strive to improve themselves by learning from actions/behaviors of themselves and neighbors
Only one operation calculation - velocity: vector of position change

$$\begin{array}{rl}\overrightarrow{v+1}& =x(t+1)-x(t)\\ x(t+1)& =x(t)+\alpha \vec{v}+\beta (x^{\ast }-x(t))+\gamma (x^{+}-x(t))+\delta (x^{!}-x(t))\end{array}$$

• $x$ … particle’s location
• $x^{+}$ … best neighbor’s location
• $x^{\ast }$ … best historical location
• $x^{!}$ … best global location
• $\alpha$ … proportion of current velocity
• $\beta$ … proportion of best historical location: too large $\to$ swarm of greedy searchers without group dynamics
• $\gamma$ … proportion of best neighbor’s location: larger $\to$ emphasise globality / smaller $\to$ emphasise local information
• $\delta$ … proportion of best global location: too large $\to$ single greeedy search instead of several local searches

Algorithm:

1. Compute fitness for each particle, update $x^{+}$, $x^{\ast }$ and $x^{!}$
2. Update particle’s representation: velocity with added random noise
3. Move particle in direction of velocity

Pros: simple implementation (no derivatives) and easy parallelization
Cons: fast premature convergence and slow convergence in refined search space - weak local search ability