Animal swarms in nature can adapt to dynamic changes in their environment, and through cooperation, they can solve problems that are crucial for their survival. Only through local interactions with other members of the swarm and with the environment, they can achieve a common goal more efficiently than a single individual can. This problem-solving behaviour resulting from the multiplicity of interactions is called Swarm Intelligence [1].

Swarm intelligence is the discipline that deals with natural and artificial systems composed of many individuals that coordinate using decentralized control and self-organization. The discipline focuses on the collective behaviours that result from the local interactions of the individuals with each other and with their environment [2].

Biological inspiration: Ants

A colony can solve problems unthinkable for individual ants, such as finding the shortest path to the best food source, allocating workers to different tasks, or depending a territory from neighbours. As individuals, ants might be tiny dummies, but as colonies, they respond quickly and effectively to their environment. The do swarm intelligence.

One key to an ant colony, for example, is that no one is in charge. Even with half million ants, a colony functions just fine with no management at all – at least none that it could be recognize. It relies instead upon countless interactions between individuals ants, each of which is following simple rules of thumb. Such a system is described as self-organizing.

Central to this are the concepts of stigmergy and self-organization. Stigmergy is a class of mechanism where individuals influence each other’s activities thanks to an indirect communication mediate modification of the environment. The pheromone trail laying behaviour of ants is a well-known example of stigmergy communication: an ant deposits on the ground a trail of pheromone that stimulates other ants to follow this trail towards the food source. The recruited ants also deposit pheromone during their way back to the nest and then reinforce the trail that becomes more and more attractive. As time goes on this positive feedback allows the emergence of a well-travelled path between the colony’s nest and a food source [4].

Cluster Analysis for image segmentation

Image segmentation is an important pre-processing step in applications of computer vision. The objective is to partition the image into homogeneous regions that share certain visual characteristics. The objective of the segmentation is to change the representation of the original image into something easier to analyse [1].

Clustering is a method of unsupervised learning; its objective is to find groups of pixels that are similar in terms of a predefined characteristic. A cluster of pixels is usually associated with a prototype, the most representative pixel, which is considered the centre of the cluster.

Clustering with swarm-based algorithms is emerging as an alternative to more conventional clustering methods, such as hierarchical clustering and k-means. Ant-based clustering stands out as the most widely used group of swarm-based clustering algorithms [5].

Ant system-based clustering algorithm

The novel Ant System-based clustering Algorithm (ASCA) proposed in [3] was inspired by the foraging behaviour of ant colonies in nature. When ants find a food source, they leave pheromone trails that attract other ants to follow their path. Pheromone trails evaporate over time, so a path that leads to a close food source accumulates more pheromone as it is crossed by ants more frequently.

Pheromone trails in the ASCA algorithm are accumulated in nodes to represent the density of the surrounding data. The process of pheromone accumulation is iterative and creates a pheromone map of the data set we want to cluster. High data-density areas accumulate more pheromone and they represent cluster centres. This is used to extract the number of clusters. Gradient of the pheromone trail is used to assign every node to a cluster by applying local search. The ASCA algorithm consists of three consecutive parts: pheromone accumulation, local pheromone summing and data labelling. It is important to emphasise that this algorithm extracts the number of clusters from the data set.

[thb_testimonial_parent thb_style=”style2″ thb_pagination=””][thb_testimonial quote=”he ASCA algorithm consists of three consecutive parts: pheromone accumulation, local pheromone summing and data labeling.”][/thb_testimonial_parent]

Conclusions

Ant-based clustering algorithms are an appropriate alternative to traditional clustering algorithms. The algorithm has many features that make it an interesting study of cluster analysis. It has the ability of automatically discovering the number of clusters. It linearly scales against the dimensionality of data and, it automatically generates a representation of the formed clusters that can be intuitively understood by humans. The nature of the algorithm makes it robust to the effects of outliers within the data. Research on ant-based clustering algorithms is still an on-going field of research.

References

1. Aleksandar Jevtic. Swarm Intelligence: Novel tools for optimization, feature extraction, and multi-agent system modelling. Tésis Doctoral, (2011), ETSIT (UPM)
2. Marco Dorigo and Mauro Birattari. Swarm Intelligence, (2007), Scholarpedia, 2(9):1469
3. Aleksandar Jevtic, Joel Quintanilla-Domínguez, José Miguel Barrón-Adame and Diego Andina. Image Segmentation Using Ant System-based Clustering Algorithm.
4. Pheromone trail networks in ants. Collective Animal Behavior. Couzin I.D (2009)
5. Julia Handl and Bernd Meyer. Ant-based and swarm-based clustering, (2007).