Swarm Intelligence

Ant Colonies

Social insects, i. e. ant colonies, show many interesting behavioral aspects, such as self-organization, chain formation, brood sorting, dynamic and combinatorial optimization, etc. The coordination of an ant colony is of local nature, composed mainly of indirect communication through pheromone (also known as stigmergy, the term has been introduced by Grasse et al. [ref]), although direct interaction communication from ant to ant (in the form of antennation) and direct communication have also been observed [ref].

The high number of individuals and the decentralized approach to task coordination in the studied species means that ant colonies show high degree of parallelism, self-organization and fault tolerance. In studying these paradigms, we have high chance to discover inspiration concepts for many successful metaheuristics.

Ant Colony Optimization

Ant Colony Optimization (ACO) [ref] is an optimization technique that is inspired by the foraging behavior of real ant colonies. Originally, the method was introduced for the application to discrete and combinatorial problems. K. Socha presented variant for optimization in continuous domain [ref] which is closest to the ACO approach.

Ant Colony Optimization [ref] is a metaheuristic approach, inspired by the ability of ants to discover shortest path between nest and food source. The process is guided by deposition of a chemical substance (pheromone). As the ants move, they deposit the pheromone on the ground (amount of the pheromone deposited is proportional to the quality of the food source discovered). The pheromone is sensed by other ants and the amount of pheromone changes the decision behavior of the ant individual. The ant will more likely follow a path with more pheromone.

The ants communicate indirectly through their environment. The basic idea of ACO can be described as follows:

  • Repeat until stopping criterion is reached
    1. Create ants
    2. Construct solutions
    3. Evaporate Pheromone
    4. Daemon Actions (pheromone deposit)
  • End Repeat

New solutions are constructed continuously. It is a stochastic decision process based on the pheromone amount sensed by the ants. In the same way as it does in nature, the pheromone slowly evaporates over time (over iterations) in order to avoid getting stuck in local minimum and to adapt to dynamically changing environment. Daemon actions represent background actions which consist mainly of pheromone deposition. The amount is proportional to the quality of solution (and appropriate adaptive steps).

binary bridge experiment

Several versions of the ACO strategy have been proposed, but they all follow the same basic ideas:

  • search performed by a population of individuals
  • incremental construction of solutions
  • probabilistic choice of solution components based on stigmergic information
  • no direct communication between the individuals

A review of ACO-related methods can be found in [ref].

Ant Colony Methods for Clustering

Several species of ant workers have been reported to form piles of corpses (cemeteries) to clean up their nests. This aggregation phenomenon is caused by attraction between dead items mediated by the ant workers. The workers deposit (with higher probability) the items in the region with higher similarity (when more similar items are present within the range of perception). For example, the Messor sancta ants organize dead corpses into clusters; brood sorting has been studied in ant colony of Leptothorax unifasciatus.

ant clustering

This approach has been modeled in the work of Deneubourg et~al. [ref] and in the work of Lumer and Faieta [ref] to perform a clustering of data. The approach (as all the clustering methods) is very sensitive to the similarity measure used (e. g. Euclidean distance, etc.) and the range of agent perception. Note, that no pheromone is used in this method.

Methods using pheromone also exist, namely A2CA [ref]. Another approach can be found the work of J. Handl in [ref] (an ATTA algorithm), which introduce modified neighborhood function (penalizing high dissimilarities), short-term memory with lookahead (jumping ants), increasing radius of perception, time-dependent modulation of the neighborhood function.

ACO_DTree Method

The ACO_DTree method is a hybrid evolutionary approach for binary decision tree construction [ref]. The tree is induced using the known data and it can be used for unsupervised clustering later: each leaf of the classification tree can be interpreted as a cluster. The algorithm uses a population of classification trees that is evolved using an evolutionary approach. Creation of the trees is driven by a pheromone matrix, which uses the ACO paradigm. An application to the neonatal sleep classification (which is used to study the maturation stage of neonatal brain) can be found in [ref].

decision tree
pheromone matrix

The pseudo-code of the ACO_DTree method is shown below:

  • Generate initial population of solutions
  • Repeat until stopping criterion is reached
    1. Create new solutions (pheromone driven)
    2. Evolve population (mutation)
    3. Evaluate population (determine classif. error)
    4. Select best individuals
    5. Pheromone evaporation
    6. Daemon actions (pheromone laying, param. adapt.)
  • End Repeat

Particle Swarm Optimization

birds_illustrative

Swarm intelligence forms an inherent part of artificial intelligence discipline that provides very interesting results in many tasks.

Particle Swarm Optimization (PSO) [ref] is an optimization technique inspired by the behavior of the flocks of birds, schools of fish, or swarms of bees, and even human social behavior. PSO is a population-based optimization tool, which could be implemented and applied easily to solve various function optimization problems, or the problems that can be transformed to continuous optimization problems.

You can try a live demo: Particle swarm optimization

Opens PSO Flash animation in new window

PSO based segmentation of eye movement signals

Our goal was to divide the EOG signal to disjunctive subsets containing compact parts of the signal with the same or at least partially the same interpretation.

Segmentation og EOG

PSO based training of Hidden Markov Models

Constrained optimization of the stochastic finite state automata. We proposed the method and applied it in signal classification:

  • detection of traumatic brain injury from intracranial pressure
  • sleep EEG classification
Training and simulated time series

PSO based robot path planning

A path is represented by Ferguson splines and is optimized using PSO.

Path planned by different methods