Swarm Intelligence (AI)

Introduction

This project explores the fascinating world of Swarm Intelligence, a branch of Artificial Intelligence inspired by the collective behavior of decentralized, self-organized systems in nature. We implemented, analyzed, and rigorously benchmarked several swarm algorithms against traditional optimization techniques across both continuous and discrete problem spaces.

Summary (Algorithms Investigated)

Swarm Intelligence Algorithms:

Cuckoo Search (CS) with Lévy Flights
Artificial Bee Colony (ABC)
Firefly Algorithm (FA)
Ant Colony Optimization (ACO)
Particle Swarm Optimization (PSO)

Traditional Algorithms:

Hill Climbing (HC)
Simulated Annealing (SA)
Genetic Algorithm (GA)
A* Search

Continuous Optimization

To evaluate the algorithms in a continuous space, we utilized two standard benchmark functions: Sphere (unimodal) and Rastrigin (multimodal, highly complex).

Cuckoo Search (CS) & Lévy Flights

The core of the Cuckoo Search algorithm relies on generating new solutions via Lévy flights—a random walk characterized by frequent short steps and occasional long jumps. This helps the algorithm escape local optima effectively.

The new solution $x_i^{(t+1)}$ is generated using:

x_i^{(t+1)} = x_i^{(t)} + \alpha \oplus \text{Lévy}(\beta)

Note (Experimental Findings)

On the complex Rastrigin function, Cuckoo Search and the Firefly Algorithm demonstrated superior convergence speeds and final solution qualities compared to traditional methods like Hill Climbing and Simulated Annealing. CS was particularly robust against getting trapped in local minima.

Artificial Bee Colony (ABC)

ABC simulates the foraging behavior of honey bees, dividing the population into Employed Bees, Onlooker Bees, and Scout Bees.

Tip (Scalability)

Our tests revealed that ABC scales exceptionally well. When the dimensionality (complexity) of the problem increased, the quality of the solutions provided by ABC degraded the least compared to other algorithms, making it highly suitable for large-scale continuous problems.

Discrete Optimization (TSP)

For discrete optimization, we tackled the classic Travelling Salesman Problem (TSP), an NP-hard problem seeking the shortest possible route that visits every city exactly once and returns to the origin.

Ant Colony Optimization (ACO)

ACO is a probabilistic technique inspired by ants finding paths to food using pheromone trails. The probability $p_{ij}^k$ of an ant $k$ moving from city $i$ to city $j$ is calculated based on the pheromone amount $\tau_{ij}$ and a heuristic value $\eta_{ij}$ (usually the inverse of the distance).

1
# Simplified conceptual representation
2
def calculate_probability(pheromone, distance, alpha, beta):
3
    return (pheromone ** alpha) * ((1.0 / distance) ** beta)

Solution (TSP Results)

ACO proved to be the most effective and appropriate algorithm for the TSP among those tested. It consistently found the highest quality solutions (shortest paths) with remarkable stability across multiple runs, significantly outperforming PSO (which struggles in discrete spaces) and GA.

A* Search vs. Swarm Methods

We also applied the A algorithm* to the TSP using the Minimum Spanning Tree (MST) as an admissible heuristic.

Warning (A* Limitations)

While A* guarantees finding the optimal solution, its time complexity grows exponentially. In our tests, A* became computationally unfeasible for $m \ge 25$ cities, highlighting the absolute necessity of meta-heuristic swarm algorithms for larger instances of the TSP.

Visualization and Analysis

A significant portion of the project involved building automated evaluation pipelines using NumPy and developing 2D/3D visualizations using Matplotlib and Imageio. This allowed us to dynamically analyze algorithm convergence, parameter sensitivity, and create animation curves demonstrating the search process in real-time.