Name: Towards AI Legal Name: Towards AI, Inc. Description: Towards AI is the world's leading artificial intelligence (AI) and technology publication. Read by thought-leaders and decision-makers around the world. Phone Number: +1-650-246-9381 Email: [email protected]
228 Park Avenue South New York, NY 10003 United States
Website: Publisher: https://towardsai.net/#publisher Diversity Policy: https://towardsai.net/about Ethics Policy: https://towardsai.net/about Masthead: https://towardsai.net/about
Name: Towards AI Legal Name: Towards AI, Inc. Description: Towards AI is the world's leading artificial intelligence (AI) and technology publication. Founders: Roberto Iriondo, , Job Title: Co-founder and Advisor Works for: Towards AI, Inc. Follow Roberto: X, LinkedIn, GitHub, Google Scholar, Towards AI Profile, Medium, ML@CMU, FreeCodeCamp, Crunchbase, Bloomberg, Roberto Iriondo, Generative AI Lab, Generative AI Lab Denis Piffaretti, Job Title: Co-founder Works for: Towards AI, Inc. Louie Peters, Job Title: Co-founder Works for: Towards AI, Inc. Louis-François Bouchard, Job Title: Co-founder Works for: Towards AI, Inc. Cover:
Towards AI Cover
Logo:
Towards AI Logo
Areas Served: Worldwide Alternate Name: Towards AI, Inc. Alternate Name: Towards AI Co. Alternate Name: towards ai Alternate Name: towardsai Alternate Name: towards.ai Alternate Name: tai Alternate Name: toward ai Alternate Name: toward.ai Alternate Name: Towards AI, Inc. Alternate Name: towardsai.net Alternate Name: pub.towardsai.net
5 stars – based on 497 reviews

Frequently Used, Contextual References

TODO: Remember to copy unique IDs whenever it needs used. i.e., URL: 304b2e42315e

Resources

Unlock the full potential of AI with Building LLMs for Productionβ€”our 470+ page guide to mastering LLMs with practical projects and expert insights!

Publication

Ant Colony Optimization: An overview
Latest

Ant Colony Optimization: An overview

Last Updated on November 7, 2022 by Editorial Team

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

Image by author created byΒ Dalle.2

β€œ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.

Photo by Jimmy Wong onΒ Unsplash

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?

Ants and different random routes toward food sources [Image byΒ author]

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.

levels of pheromones on the way of ants [Image byΒ author]

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.

Evaporation and deposition of pheromone [Image byΒ author]

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.

Transition probability [ImageΒ source]

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 update equation [ImageΒ source]

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.

how ants choose routes [ImageΒ source]

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.

Simulation of ACO [Credits: HERE]

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.

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

Feedback ↓