ACO in Hindi ~xRay Pixy

ACO in Hindi

Learn Ant Colony Optimization Algorithm (ACO) in Hindi.

Video Chapters: ACO Algorithm

00:00 Introduction

00:27 Topics Covered

00:53 About Ant Colony Optimization

01:07 ACO Applications

01:57 ACO Inspiration 

07:06 Real Ants Simulation as Artificial Ants

10:00 ACO Mathematical Models

10:26 ACO Steps

19:09 Conclusion

How ACO Works

Ant Colony Optimization is inspired by how real ants find the shortest path to food. Ants deposit pheromones on paths they travel, and other ants tend to follow paths with stronger pheromone trails. Over time, this leads to finding the most efficient route. To explain the Ant Colony Optimization (ACO) applied to the Traveling Salesman Problem (TSP) in a simple and concise way within 2 minutes, here's an approach:

Introduction to TSP

The Traveling Salesman Problem asks: "Given a set of cities, find the shortest route that visits every city exactly once and returns to the starting point."

How ACO Works

Ant Colony Optimization is inspired by how real ants find the shortest path to food. Ants deposit pheromones on paths they travel, and other ants tend to follow paths with stronger pheromone trails. Over time, this leads to finding the most efficient route.

Steps to Solve TSP with ACO

1. Ants Explore:
   Imagine a colony of ants starting from different cities. Each ant constructs a route by visiting cities one by one, choosing based on:

   • Pheromone Level: How strong the trail is on a path.
   • Visibility: The inverse of the distance between cities (shorter distances are more attractive).

2. Update Pheromones:
   After all, ants complete their tours:

   • Trails used by shorter routes receive more pheromone deposits.
   • Pheromones on less optimal routes evaporate over time.

3. Convergence:
   Over many iterations, ants increasingly follow the stronger pheromone trails, which represent the shortest path.

In Ant Colony Optimization (ACO), updating pheromone trails is essential to reinforce desirable paths and fade less favorable ones. Here’s how the process works:

1. Pheromone Evaporation: After all ants complete their tours, pheromone levels on each path (or arc) decrease by a factor of $(1 - \rho)$, where $0 < \rho < 1$ is the evaporation rate. The evaporation equation can be written as:

   $$\tau_{ij} = (1 - \rho) \tau_{ij}$$

   where $\tau_{ij}$is the pheromone level on the path between nodes $i$ and $j$. This prevents unlimited pheromone accumulation, helping the algorithm "forget" poor paths over time.

2. Pheromone Deposit: After evaporation, additional pheromone is deposited on arcs that ants have traversed in their tours. This reinforces paths that led to shorter tours, as more pheromone is added to these paths, making them more attractive in future iterations.

3. Exponential Decay: If a path is rarely chosen, its pheromone level decreases exponentially across iterations, gradually eliminating paths that are less optimal.

Key steps in Ant System, focusing on how ants build solutions, update pheromones, and choose paths based on pheromone and heuristic information.

1. Pheromone Update

After all ants construct a tour, pheromone levels on each edge are updated by both evaporation and new deposits:

$$\tau_{ij} \leftarrow (1 - \rho) \cdot \tau_{ij} + \sum_{k=1}^{m} \Delta \tau_{ij}^k$$

• $rho$: Evaporation Rate to reduce pheromone levels, preventing over-concentration.
• $m$: Number of ants.
• $\Delta \tau_{ij}^k$: Pheromone laid by ant $k$ on edge $(i, j)$: $$\Delta \tau_{ij}^k = \begin{cases} \frac{Q}{L_k}, & \text{if ant } k \text{ used edge } (i, j) \text{ in its tour} \\ 0, & \text{otherwise} \end{cases}$$

where $Q$ is a constant and $L_k$ is the length of the tour created by ant $k$.

2. Probabilistic Path Selection

When choosing the next city, an ant follows a probabilistic rule based on pheromone level and heuristic information:

$$p_{ij}^k = \frac{\tau_{ij}^\alpha \cdot \eta_{ij}^\beta}{\sum_{l \in N(s_p)} \tau_{il}^\alpha \cdot \eta_{il}^\beta}$$

where:

• $p_{ij}^k$: Probability that ant $k$ moves from city $i$ to city $j$.
• $alpha$ and $\beta$: Parameters controlling the influence of pheromone and heuristic information $\eta_{ij}$.
• Heuristic Information $\eta_{ij} = \frac{1}{d_{ij}}$: Inverse of distance $d_{ij}$ between cities $i$ and $j$, favoring shorter paths.
• $N(s_p)$: Set of feasible next cities (not yet visited).

#optimization #algorithm #metaheuristic #robotics #deeplearning #ArtificialIntelligence #MachineLearning #computervision #research #projects #thesis #Python