Population-Based Approaches and Swarm Intelligence

While search algorithms like $A^*$ or Hill-Climbing generally operate on a single "current" state (or single trajectory), Population-Based Approaches maintain a set of candidate solutions simultaneously. This allows them to effectively explore massive, complex, non-linear search spaces where exact mathematical or gradient-based methods fail.

---

Genetic Algorithms (GAs)

A Genetic Algorithm (GA) is an optimization and search technique inspired by biological evolution and natural selection. GAs apply the computational equivalent of "survival of the fittest": over successive generations, favorable traits are preserved and combined while weaker solutions are eliminated.

Basic Intuition

A Genetic Algorithm relies on six foundational pillars:

1. The Problem: Optimizing a complex objective function over a large search space.
2. The Population: Maintaining a set of candidate solutions simultaneously instead of evaluating a single path.
3. The Individual (Chromosome): Encoding each individual candidate solution into a structured representation.
4. Fitness Function: Scoring each individual's quality to measure how well it solves the problem.
5. Survival of the Fittest: Allocating higher reproduction probabilities to fitter individuals while allowing weaker solutions a small chance to contribute.
6. Iterative Improvement: Combining and mutating solutions so that the overall population quality improves over generations.

The GA Lifecycle

---

Core Components of GAs

1. Representing Solutions (Chromosomes)

Every candidate solution must be encoded as a chromosome built from individual components called genes.

• Binary Representation: Used for discrete selection problems like feature selection, where each bit indicates whether a feature is active (1) or inactive (0) (e.g., 10110010).
• Permutation Representation: Used for sequence-dependent ordering problems like the Traveling Salesperson Problem (TSP) (e.g., Dhaka ➔ Rajshahi ➔ Khulna ➔ Sylhet).
• Value-Based Representation: Used for parameter optimization where genes store numerical values or hyperparameters (e.g., [learning_rate, batch_size, dropout]).

Quality Mandate: A good representation must express valid solutions and allow crossover and mutation operators to produce meaningful new candidates.

2. Measuring Fitness

The Fitness Function assigns a numerical score to each individual, guiding the direction of evolution:

• Route Optimization (TSP): $\text{Fitness} = \frac{1}{\text{Total Distance}}$ (shorter paths yield higher fitness).
• Machine Learning: $\text{Fitness} = \text{Validation Accuracy}$ (models with superior generalization score higher).
• Feature Selection: $\text{Fitness} = \text{Accuracy} - \text{Penalty}$ (balances prediction accuracy against the number of features to prevent model bloat).

Key Fitness Mandate: A good fitness function should reflect the true optimization goal, distinguish solutions accurately, and avoid misleading the search toward sub-optimal traps.

3. Selecting Parents

Parent selection determines which individuals reproduce to form the next generation. Fitter individuals receive higher selection probabilities, though weaker individuals are not completely ignored:

• Roulette Wheel Selection: Selection probability is directly proportional to raw fitness score. Higher-fitness individuals occupy larger segments of the selection wheel.
• Tournament Selection: A small random subset of individuals is picked, and the best among them is chosen as a parent. This easily adjusts selection pressure by changing tournament size.
• Rank-Based Selection: Individuals are ranked by fitness, and selection probability is based on rank rather than raw scores. This prevents dominant individuals from taking over the gene pool prematurely.

4. Crossover & Mutation

• Crossover (Exploitation): Combines genetic material from two parents to generate offspring. By splicing parent chromosomes (e.g., single-point crossover at index 3), offspring inherit advantageous traits from both parents.
  • Parent 1: 101 | 110
  • Parent 2: 011 | 001
  • Child 1: 101001
  • Child 2: 011110
• Mutation (Exploration): Randomly alters gene values within an individual (e.g., flipping bit 4 from 1 to 0). Mutation injects fresh genetic diversity into the population, preventing search stagnation.
  • Before Mutation: 101100
  • After Mutation: 101000

Balance is Key: Crossover refines promising solutions (exploitation), while mutation maintains diversity to explore new regions (exploration).

---

Preserving Diversity & Preventing Stagnation

A major challenge in Genetic Algorithms is premature convergence, where population individuals become too uniform before reaching the global optimum, trapping the search in a local minimum.

Signs of Stagnation

• The population becomes uniform (loss of genetic diversity).
• Fitness scores fail to improve over many consecutive generations.

Techniques to Preserve Diversity

1. Mutation Rate Control: Injecting new genetic variations periodically.
2. Controlled Elitism: Preserving only a small percentage (e.g., 1–5%) of top individuals across generations so elite solutions are saved without dominating the population.
3. Selection Pressure Tuning: Moderating selection strength so lower-fitness individuals with unique genes survive.
4. Sufficient Population Size: Maintaining an adequate number of individuals to cover the search space.
5. Immigration (Random Injection): Introducing randomly generated individuals into the population when stagnation is detected.

---

Swarm Intelligence

Swarm Intelligence (SI) is an AI domain inspired by the collective behavior of decentralized, self-organized systems in nature:

• Ants: Discovering shortest paths between nests and food sources.
• Birds: Flocking seamlessly in synchronized formations.
• Fish: Schooling to evade predators.
• Bees: Foraging and selecting optimal nest sites.

The core principle behind SI is Emergent Intelligence: simple agents following basic local rules produce complex, highly intelligent global behavior without any central controller.

Why Swarm Intelligence Matters in AI

---

1. Ant Colony Optimization (ACO)

Ant Colony Optimization models how biological ants locate shortest paths using chemical trails called pheromones.

The Natural Process vs. AI Feedback Loop

1. Natural Process: Ants deposit pheromone trails as they travel. Other ants probabilistically follow trails with higher pheromone concentrations. Shorter paths allow faster round-trips, building up pheromone intensity faster and attracting more ants until the colony converges on the optimal path.
2. AI Implementation: Artificial ants construct solutions step-by-step over a graph. Paths forming higher-quality solutions receive stronger artificial pheromone deposits, while unused trails gradually decay.

Summary of the ACO Process

Core ACO Concepts: Pheromones & Evaporation

• Pheromone Concentration ($\tau_{ij}$): Represents accumulated experience. Higher values signify choices that yielded superior solutions in past iterations.
• Evaporation ($\rho$): Gradually reduces pheromone intensity over time, preventing early sub-optimal paths from dominating forever and maintaining exploration.

Mathematical Formulation

Transition Probability: An ant at node $i$ selects edge $(i, j)$ with probability $P_{ij}$: $P_{ij} = \frac{\tau_{ij}^\alpha \cdot \eta_{ij}^\beta}{\sum_{k \in \text{allowed}} \tau_{ik}^\alpha \cdot \eta_{ik}^\beta}$

• $\tau_{ij}$: Pheromone density on edge $(i, j)$.
• $\eta_{ij}$: Heuristic desirability (typically $1/d_{ij}$, where $d_{ij}$ is edge distance).
• $\alpha, \beta$: Weighting parameters controlling the relative influence of pheromone history vs. immediate visibility.

Pheromone Update Rule: $\tau_{ij} \leftarrow (1 - \rho)\tau_{ij} + \Delta\tau_{ij}$

• $\rho \in [0, 1]$: Evaporation rate.
• $\Delta\tau_{ij}$: Total new pheromone deposited by all ants that used edge $(i, j)$ in the current iteration.

Walkthrough: Shortest Path Problem

---

2. Particle Swarm Optimization (PSO)

Particle Swarm Optimization simulates bird flocking or fish schooling. Candidate solutions are modeled as particles moving through a continuous multi-dimensional search space (e.g., hyperparameter space [learning_rate, batch_size]).

Dual Experience Learning

Each particle updates its position and velocity based on two sources of knowledge:

1. Personal Best ($pbest$): The best position the individual particle has achieved so far.
2. Global Best ($gbest$): The best position achieved by any particle in the entire swarm so far.

Mathematical Formulas & Variable Definitions

Velocity Update Equation: $v_{t+1} = w v_t + c_1 r_1 (pbest - x_t) + c_2 r_2 (gbest - x_t)$

Position Update Equation: $x_{t+1} = x_t + v_{t+1}$

The 5-Step PSO Algorithm

1. Initialization: Initialize a swarm of particles with random positions and velocities.
2. Fitness Evaluation: Compute the fitness of each particle based on its position.
3. Best Tracking: Update each particle's $pbest$ and the overall swarm $gbest$.
4. Movement Update: Calculate new velocity $v_{t+1}$ and move particle to position $x_{t+1}$.
5. Iteration: Repeat steps 2–4 until termination criteria (e.g., max iterations or target fitness) are met.