Metaheuristic Optimization

Metaheuristic Optimization

What Are Metaheuristics?

Key characteristics shared by most metaheuristics:

• No gradient required — only function evaluations are needed
• Balances exploration (searching new regions) and exploitation (refining known good regions)
• Stochastic — randomness helps escape local minima but means results vary between runs
• Applicable to black-box functions — the objective function can be a simulation, neural network, or oracle

Simulated Annealing

The temperature schedule typically follows:

Genetic Algorithms

Core operators:

1. Selection — tournament, roulette wheel, or rank-based; chooses parents proportional to fitness
2. Crossover — single-point, multi-point, or uniform; recombines two parents to produce children
3. Mutation — bit-flip (binary), Gaussian perturbation (continuous); introduces genetic diversity
4. Elitism — preserves the best individuals across generations to prevent regression

Particle Swarm Optimization

Ant Colony Optimization

Pheromone update:

Tabu Search

Key components:

• Tabu list — FIFO queue of forbidden moves (size = tabu tenure)
• Aspiration criteria — override tabu if the move yields the best-known solution
• Neighborhood structure — defines what constitutes a single move (swap, insert, reverse)
• Diversification — periodically reset search to unexplored areas if stagnation is detected
• Intensification — revisit the neighborhood of the best-known solution periodically

Random Restart Hill Climbing

Comparison of Methods

Python Implementation

import numpy as np
from typing import Callable, List, Tuple

# ============================================================
# Simulated Annealing
# ============================================================
def simulated_annealing(
    f: Callable,
    x0: np.ndarray,
    T0: float = 100.0,
    alpha: float = 0.95,
    n_iter: int = 5000,
    step_size: float = 0.5,
    seed: int = None
) -> Tuple[np.ndarray, float]:
    """Simulated annealing for continuous optimization."""
    if seed is not None:
        np.random.seed(seed)

    current = x0.copy()
    current_val = f(current)
    best = current.copy()
    best_val = current_val
    T = T0

    for i in range(n_iter):
        neighbor = current + np.random.randn(len(current)) * step_size
        neighbor_val = f(neighbor)
        delta = neighbor_val - current_val

        if delta < 0 or np.random.rand() < np.exp(-delta / T):
            current = neighbor
            current_val = neighbor_val

        if current_val < best_val:
            best = current.copy()
            best_val = current_val

        T *= alpha

    return best, best_val

# ============================================================
# Genetic Algorithm
# ============================================================
def genetic_algorithm(
    f: Callable,
    n_vars: int,
    bounds: Tuple[float, float] = (-5.0, 5.0),
    n_pop: int = 100,
    n_gen: int = 200,
    crossover_rate: float = 0.8,
    mutation_rate: float = 0.1,
    seed: int = None
) -> Tuple[np.ndarray, float]:
    """Genetic algorithm with tournament selection and blend crossover."""
    if seed is not None:
        np.random.seed(seed)

    lo, hi = bounds
    pop = np.random.uniform(lo, hi, (n_pop, n_vars))
    fitness = np.array([f(ind) for ind in pop])
    best_idx = np.argmin(fitness)
    best = pop[best_idx].copy()
    best_val = fitness[best_idx]

    for gen in range(n_gen):
        # Tournament selection (size 3)
        def tournament():
            idx = np.random.choice(n_pop, 3, replace=False)
            return pop[idx[np.argmin(fitness[idx])]]

        new_pop = []
        # Elitism: keep best
        new_pop.append(best.copy())

        while len(new_pop) < n_pop:
            p1, p2 = tournament(), tournament()
            if np.random.rand() < crossover_rate:
                beta = np.random.rand(n_vars)
                child = beta * p1 + (1 - beta) * p2
            else:
                child = p1.copy()

            if np.random.rand() < mutation_rate:
                child += np.random.randn(n_vars) * 0.3
                child = np.clip(child, lo, hi)

            new_pop.append(child)

        pop = np.array(new_pop[:n_pop])
        fitness = np.array([f(ind) for ind in pop])
        gen_best = np.argmin(fitness)
        if fitness[gen_best] < best_val:
            best = pop[gen_best].copy()
            best_val = fitness[gen_best]

    return best, best_val

# ============================================================
# Particle Swarm Optimization
# ============================================================
def particle_swarm_optimization(
    f: Callable,
    n_vars: int,
    bounds: Tuple[float, float] = (-5.0, 5.0),
    n_particles: int = 30,
    n_iter: int = 200,
    omega: float = 0.7,
    c1: float = 1.5,
    c2: float = 1.5,
    seed: int = None
) -> Tuple[np.ndarray, float]:
    """Particle swarm optimization for continuous functions."""
    if seed is not None:
        np.random.seed(seed)

    lo, hi = bounds
    x = np.random.uniform(lo, hi, (n_particles, n_vars))
    v = np.random.uniform(-1, 1, (n_particles, n_vars))
    p_best = x.copy()
    p_best_val = np.array([f(p) for p in x])
    g_best = p_best[np.argmin(p_best_val)].copy()
    g_best_val = np.min(p_best_val)

    for t in range(n_iter):
        r1 = np.random.rand(n_particles, n_vars)
        r2 = np.random.rand(n_particles, n_vars)
        v = (omega * v
             + c1 * r1 * (p_best - x)
             + c2 * r2 * (g_best - x))
        x = x + v
        x = np.clip(x, lo, hi)

        vals = np.array([f(xi) for xi in x])
        for i in range(n_particles):
            if vals[i] < p_best_val[i]:
                p_best[i] = x[i].copy()
                p_best_val[i] = vals[i]

        best_idx = np.argmin(p_best_val)
        if p_best_val[best_idx] < g_best_val:
            g_best = p_best[best_idx].copy()
            g_best_val = p_best_val[best_idx]

    return g_best, g_best_val

# ============================================================
# Demo
# ============================================================
if __name__ == "__main__":
    rosenbrock = lambda x: (1 - x[0])**2 + 100*(x[1] - x[0]**2)**2
    x0 = np.array([-2.0, 3.0])

    sa_best, sa_val = simulated_annealing(rosenbrock, x0, seed=42)
    ga_best, ga_val = genetic_algorithm(rosenbrock, 2, seed=42)
    pso_best, pso_val = particle_swarm_optimization(rosenbrock, 2, seed=42)

    print(f"SA:  f({sa_best}) = {sa_val:.6f}")
    print(f"GA:  f({ga_best}) = {ga_val:.6f}")
    print(f"PSO: f({pso_best}) = {pso_val:.6f}")

Applications in AI/ML

Other applications:

• Hyperparameter tuning — PSO and genetic algorithms optimize learning rate, batch size, regularization strength
• Feature selection — binary GA selects subsets of features; reduces dimensionality without gradient computation
• Clustering — ACO and GA solve k-medoids and graph partitioning problems
• Reinforcement learning — evolutionary strategies (ES) optimize policy parameters without backpropagation (OpenAI ES)
• GAN training — NSGA-II balances generator and discriminator objectives in multi-objective GAN design

Common Mistakes

Interview Questions

Q1: When would you choose a genetic algorithm over simulated annealing?

A: GAs are preferred when the search space has many disjoint promising regions (multi-modal), because the population naturally explores multiple basins in parallel. SA, being single-solution, may get trapped unless the temperature is carefully managed. GAs also naturally handle discrete/combinatorial encodings (e.g., permutations for scheduling) via specialized crossover operators.

Q2: How does PSO differ from gradient descent?

A: PSO requires no gradient — it uses velocity updates based on personal and global best positions. Gradient descent follows the steepest local slope and converges faster on smooth convex functions. PSO excels when the objective is non-differentiable, noisy, or has many local minima where gradient methods stall.

Q3: What is the role of the cooling schedule in simulated annealing?

A: The cooling schedule controls the balance between exploration and exploitation. High accepts worse solutions (escaping local minima); low behaves greedily (refining). Too fast -> stuck in local optimum. Too slow -> wasteful computation. The geometric schedule with is a practical default.

Q4: Why is elitism important in genetic algorithms?

A: Without elitism, the best solution found so far can be lost due to crossover or mutation in the next generation. Elitism copies the top individuals directly to the next generation, ensuring monotonic improvement of the best fitness. Most practical GA implementations use elitism of 1–5% of the population.

Q5: How do you handle constraints in metaheuristics?

A: Common approaches: (1) penalty functions — add a cost for constraint violation to the objective; (2) repair operators — map infeasible solutions to the nearest feasible one; (3) Decoder-based — encode solutions such that they are always feasible (e.g., for TSP, use permutation encoding); (4) Lagrangian relaxation — incorporate constraints into the objective with multipliers updated adaptively.

Practice Problems

Quick Reference

Cross-References

• Gradient Descent (Topic: First-Order Methods) — use when gradients are available and the problem is smooth
• Newton's Method (Topic: Second-Order Methods) — faster convergence but requires Hessian computation
• Convex Optimization (Topic: Convexity) — when the problem is convex, exact methods are preferred
• Linear Programming (Topic: Linear Programming) — simplex or interior-point methods for linear objectives with linear constraints
• Constraint Programming (Topic: Constraint Satisfaction) — exact method for discrete combinatorial problems with complex constraints
• Bayesian Optimization (Topic: Sequential Model-Based Optimization) — sample-efficient alternative to grid/random search for hyperparameter tuning
• Reinforcement Learning (Topic: Policy Optimization) — evolutionary strategies (ES) as a gradient-free alternative to policy gradient methods
• Combinatorial Optimization (Topic: Graph Algorithms) — branch-and-bound, LP relaxation, and approximation algorithms as exact or near-exact alternatives to metaheuristics