Lecture 11.1: Population-Based Approaches and Swarm Intelligence

While algorithms like A* or local search generally operate on a single "current" state (or a single path), Population-Based Approaches maintain a large set of candidate solutions simultaneously. This allows them to explore massive, complex, non-linear search spaces by simulating biological evolution or social behavior.

---

Genetic Algorithms (GAs)

A Genetic Algorithm is an optimization and search technique inspired by natural evolution. It applies the concept of "survival of the fittest" computationally.

The GA Lifecycle

Core Concepts

1. Representing Solutions (Chromosomes)

A solution must be encoded in a format that genetic operators can manipulate:

• Binary Representation: Used for problems like feature selection where a gene is either active or inactive (e.g., 101100).
• Permutation Representation: Used for sequence-dependent problems like the Traveling Salesperson Problem (TSP) (e.g., Dhaka ➔ Rajshahi ➔ Sylhet ➔ Barishal).
• Value-Based Representation: Used for parameter optimization where genes store actual floating-point parameters (e.g., neural network weights).

2. Measuring Fitness

The Fitness Function scores how close a candidate solution is to the goal.

• Route Optimization (TSP): $\text{Fitness} = 1 / \text{total distance}$ (shorter paths yield higher fitness).
• Machine Learning: $\text{Fitness} = \text{Validation Accuracy}$.

3. Selecting Parents

Better solutions must have a higher chance of reproducing, while still preserving some diversity:

• Roulette Wheel Selection: Probability of selection is directly proportional to fitness.
• Tournament Selection: A small group is randomly chosen, and the best individual among them becomes a parent (balances selection pressure).
• Rank-Based Selection: Individuals are ranked, and selection probability is based on rank rather than raw fitness (prevents dominant individuals from taking over too quickly).

4. Crossover & Mutation

• Crossover (Exploitation): Combines genetic material from two parents to construct offspring that inherit their good traits (e.g., single-point crossover where parent strings are cut and swapped).
• Mutation (Exploration): Randomly alters parts of an offspring's chromosome (e.g., flipping a bit in a binary string). This injects new genetic diversity and prevents the algorithm from getting stuck in local optima (premature convergence).

---

Swarm Intelligence

Swarm Intelligence is inspired by the collective behavior of simple agents in nature (like ants, birds, and bees). The key idea is Emergent Intelligence: Simple individuals following simple decentralized rules produce highly intelligent group-level behavior.

1. Ant Colony Optimization (ACO)

ACO is inspired by how ants discover the shortest path between their nest and food sources by leaving chemical trails called pheromones.

Path Selection Probability

An artificial ant at node $i$ chooses to move to node $j$ with a transition 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}$ where:

• $\tau_{ij}$ is the pheromone density on the edge between $i$ and $j$.
• $\eta_{ij}$ is the heuristic desirability of the edge (typically $1/d_{ij}$, where $d$ is distance).
• $\alpha$ and $\beta$ control the relative influence of historical pheromones vs. immediate visibility.

Pheromone Update & Evaporation

To prevent stagnation on early sub-optimal paths, pheromones evaporate over time: $\tau_{ij} \leftarrow (1 - \rho)\tau_{ij} + \Delta\tau_{ij}$ where:

• $\rho \in [0, 1]$ is the evaporation rate.
• $\Delta\tau_{ij}$ is the new pheromone deposited by ants that traversed edge $(i, j)$ in this iteration.

---

2. Particle Swarm Optimization (PSO)

PSO is inspired by bird flocking. Candidate solutions are represented as particles moving through a multi-dimensional search space, adjusting their positions dynamically based on personal and social experience.

The PSO Update Equations

For each particle $i$ at time step $t$, its Velocity ($v$) and Position ($x$) are updated as follows:

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

Variable Explanations

• $x_t$: The particle's current position (representing the current solution vector).
• $v_t$: The particle's current velocity (representing the direction and step size of search).
• $pbest$ (Personal Best): The best position found by this specific particle so far.
• $gbest$ (Global Best): The best position found by the entire swarm so far.
• $w$: The Inertia Weight, governing the tendency to continue in the same direction.
• $c_1$: The Cognitive (Personal) Learning Factor, pulling the particle toward its own best past solution.
• $c_2$: The Social (Global) Learning Factor, pulling the particle toward the swarm's best overall solution.
• $r_1, r_2$: Random variables uniformly distributed in $[0.0, 1.0]$, maintaining dynamic exploration.