Ant Colony Optimization: An overview

Author(s): Chinmay Bhalerao

Originally published on Towards AI the World’s Leading AI and Technology News and Media Company. If you are building an AI-related product or service, we invite you to consider becoming an AI sponsor. At Towards AI, we help scale AI and technology startups. Let us help you unleash your technology to the masses.

population-based metaheuristic nature-inspired optimization algorithm

“It is the ant, not the lion, which the elephant fears.”
― Matshona Dhliwayo

A group of unique problem-solving techniques and approaches that are inspired by natural processes are known as “nature-inspired algorithms.” The ant colony optimization algorithm (ACO), used in computer science and operations research, is a probabilistic method for resolving computing issues that may be simplified to finding appropriate paths through graphs.

In this blog, we will go through the following topics:

• Real-life Ants
• Foraging behavior
• The inspiration behind the ant colony optimization algorithm
• What is actually happening with ants and food in real life
• Steps for Ant colony optimization

Real-life Ants

Along with the closely related wasps and bees, ants are eusocial members of the family Formicidae in the order Hymenoptera. Ants have an estimated 22,000 species, and more than 13,800 have been classified. An ant goes through a complete metamorphosis, which means ants have four stages — egg, larva, pupa, and adult in the course of their life cycle. Lifespan: Black garden ant: 1–2 years, Pharaoh ant: 4–12 months. Ants are usually divided into three types: reproductive females, reproductive males, and non-reproductive females. This translates to queens, males, and workers.

Ant colonies and social insect societies, more generally, are distributed systems that, Despite the simplicity of their individual members, they display a highly organized social system. Ant colonies are organized in such a way that they can carry out complicated tasks. that, in some situations, significantly outweigh an individual ant’s capacity. what transpires in humans and other higher species whose primary senses are auditory or visual. The trail pheromone is particularly significant for the social behavior of some ant species. The root of ACO is this collective trail-laying and trail-following activity, in which an ant is influenced by a chemical path left by other ants.

Ants don't have ears. they can sense vibrations. they communicate using their antennas and pheromone.

Problems involving discrete optimization are particularly well-suited for ACO. For instance, a route or path is encoded as a solution for routing issues. When ants take different paths, the paths they’ve traveled are marked with pheromone deposits that eventually disappear. The amount of pheromone present on a path (or in a solution) is correlated with its fitness or quality. At a junction, routes with higher pheromone concentrations will be preferred or selected more frequently.

Foraging behavior

ACO is inspired by the forging behavior of ants searching for a suitable path between their colonies and food source. If you want to reach in minimum time towards food, then you have to find a path that is closest to a food source. the shortest path will give you food within lesser time.

The inspiration behind the ant colony optimization algorithm

How do ants find the shortest path between their food source and nest?

Watch the above figure. I circled one ant, and that will be our agent for searching for food. Now there can be numerous ways by which ants can search for food. from that all ways, I highlighted random 4 tentative ways named A, B, C, D. As we can see in the figure, C is the shortest and A is the longest path. While going on any road for searching food, ant releases a chemical known as a pheromone. According to this, while going from all routes, ants will release pheromones.

when the ant reaches the food, every route has some amount of pheromone deposited on it, as shown in the above figure. the one who finds food or forager will mark trails on the way using pheromones while going back to the colony. the shorter route will have more amount of pheromone levels on it. Other ants will follow the route which has more amounts of pheromones as a signal representing the shortest route for reaching the food. The pheromone is updated in each movement of an ant from one location to another on the basis of Ant Density & Ant Quantity.

the pheromone has some evaporation rate. it means that the deposited pheromone will get vanished after a certain time. So as you can see in the above figure, the route by which most ants are going following the leading ant’s pheromone has the most amount of pheromone deposited, whereas other longer routes have very less pheromone due to evaporation.

When the food source is finished, no new marks on the way are marked by returning ants.

What is actually happening with ants and food in real life?

All ants are in their nest. There are no pheromone marks on the ground.

Foraging starts and 50% ANTS will take the shortest path and 50% will take a longer path.

Ants used the shortest path and arrived earlier at the food source.

Pheromone marks on the shorter paths have strong pheromone signals. Probability of this path being selected by other ants increases.

Steps for Ant colony optimization:

1. Initialize ACO parameters

We can initialize many initial parameters like Population size, the maximum number of iterations, initial pheromone value, pheromone exponential weights, pheromone evaporation rate, etc.

2. Solution Construction

In the Correct way, formulation of the Problem statement and iteration count.

3. Position of each agent/ant at starting node

It is also known as transition probability.

Here, kth ant will move from i to j with this probability.

4. Each ant will select the next node by applying the transition rule.

5. Repeat until ant builds the best solution

6. compute fitness value

7. update the best solution

If ant4(solution) < best solution:

consider ant4(solution)=best solution

8. Apply external pheromone update

Increase in levels of pheromone trials =For the Best solution

Decrease in levels of pheromone trails = For Worst solution

Pheromone deposition and evaporation calculation are also important.

9. best solution

Looping up to maximum iterations to conclude the best solution. that can be again a hyperparameter.

An interesting experiment was given in the book Ant Colony Optimization by Marco Dorigo and Thomas Stützle.

The bridge in the first experiment had two branches that were of the same length. Ants were initially allowed to wander freely between the nest and the food supply, and the proportion of ants that preferred one of the two branches over the other was measured. over time, ants were noticed. The result was that, even though initial choices were made at random, eventually, every ant chose to use the same branch. The following explanation explains this outcome. There is no pheromone on the two branches when a trial begins. The ants choose any branch with the same probability since they have no preference. However, a few more ants will choose one branch over the other due to random variations. Since ants deposit pheromones as they move, a branch with more ants on it will have more pheromones there.

This bigger amount of pheromone will then encourage additional ants to choose that branch again, and so on, until the ants finally congregate on one of the two branches.

You can get this simulation HERE.

Anylogic cloud has a lot of different and interesting simulations based on real-life scenarios you can check it HERE.

Final words:

By incorporating swarm behavior, the ACO and Particle swarm optimization[PSO] algorithms are both data clustering methods. The ACO, though, is more relevant. addressing issues where the source and destination are clearly identified and preset. In addition, PSO is a multiobjective, dynamic optimization, and constraint management clustering technique. ACO is more appropriate for issues that call for precise solutions. Ant colony optimization algorithms have been applied to many combinatorial optimization problems, ranging from quadratic assignment to fold protein or routing vehicles, and a lot of derived methods have been adapted to dynamic problems in real variables, stochastic problems, multi-targets, and parallel implementations.

This was just a theoretical overview of ACO, but I am planning to take a case study to implement ACO on it. I already wrote one blog on a nature-inspired algorithm on GENETIC ALGORITHM OPTIMIZATION. You can read that.

If you have found this article insightful

If you found this article insightful, follow me on Linkedin and medium. you can also subscribe to get notified when I publish articles. Let’s create a community! Thanks for your support!

If you want to support me :

As Your following and clapping is the most important thing, but you can also support me by buying coffee. COFFEE.

• 10 AI Websites That Will Excite You to The Core!
• Genetic Algorithm Optimization
• Feature selection techniques for data
• Simultaneous Localization And Mapping [SLAM] systems

Signing off,

Chinmay Bhalerao

---

Ant Colony Optimization: An overview was originally published in Towards AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

Join thousands of data leaders on the AI newsletter. It’s free, we don’t spam, and we never share your email address. Keep up to date with the latest work in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI