Search Algorithms

From Random Walks to Nature-Inspired Optimization

Random Processes

Master random walk and Lévy flight fundamentals

Nature-Inspired Methods

Explore genetic algorithms, PSO, and swarm intelligence

Modern Metaheuristics

Learn advanced search strategies and hybrid approaches

Practical Applications

Apply search algorithms to real-world optimization problems

Search Algorithms in Optimization

Search algorithms explore solution spaces to find optimal or near-optimal solutions, balancing exploration of new regions with exploitation of promising areas.

Core Concepts

  • Exploration: Searching new regions of solution space
  • Exploitation: Refining solutions in promising areas
  • Solution Space: All possible solutions to a problem
  • Fitness Landscape: Objective function over solution space
Applications: Hyperparameter tuning, neural architecture search, feature selection, scheduling, routing, and portfolio optimization.
Optimization Landscape with Search Paths

No Free Lunch Theorem: No single search algorithm performs best on all optimization problems. Algorithm selection depends on problem characteristics.

Random Walk Algorithms

Mathematical Foundation

$$X_{t+1} = X_t + \epsilon_t$$

Where εt is a random step drawn from a probability distribution.

Properties

  • Memoryless: Next step independent of history
  • Unbiased: No preferred direction
  • Diffusive: Spreads as √t over time
  • Ergodic: Eventually visits all accessible states

Brownian Motion

$$\langle X^2(t) \rangle = 2Dt$$

Mean squared displacement grows linearly with time (diffusion coefficient D).

Random Walk Trajectory
Optimization Use: Random walk provides baseline search behavior and can escape local optima through random perturbations, but convergence is typically slow.

Lévy Flight and Heavy-Tailed Distributions

Lévy flights use heavy-tailed step size distributions, enabling both local search and long-distance jumps for efficient exploration of complex landscapes.

Mathematical Formulation

$$P(s) \sim s^{-\alpha}$$

Power-law distribution with 1 < α ≤ 3

Superdiffusive Behavior

$$\langle X^2(t) \rangle \sim t^{\gamma}$$

Where γ > 1 (superdiffusive vs γ = 1 for normal diffusion)

  • Many small steps for local search
  • Occasional large jumps for exploration
  • Optimal foraging strategy in nature
  • Faster exploration than Brownian motion
Lévy Flight vs Random Walk Comparison
Natural Examples: Foraging patterns of albatrosses, shark movements, human mobility patterns, and stock market fluctuations.

Nature-Inspired Search Algorithms

Simulated Annealing

$$P(\text{accept}) = e^{-\Delta E / T}$$

Accept worse solutions with probability decreasing over time (cooling schedule).

Genetic Algorithms

  • Selection: Choose fittest individuals
  • Crossover: Combine parent solutions
  • Mutation: Random modifications
  • Evolution: Iterative improvement

Particle Swarm Optimization

$$v_{i}^{t+1} = w v_{i}^t + c_1 r_1 (p_i - x_i^t) + c_2 r_2 (g - x_i^t)$$

Particles move based on personal best (pi) and global best (g).

Ant Colony Optimization

  • Pheromone trail construction
  • Probabilistic path selection
  • Evaporation and reinforcement
  • Emergent shortest paths
Swarm Behavior Visualization

Genetic Algorithm Mechanics

Selection Methods

  • Tournament Selection: Random competition
  • Roulette Wheel: Fitness-proportional
  • Rank Selection: Rank-based probability
  • Elitism: Preserve best solutions

Crossover Operations

  • Single-point: Split at one position
  • Multi-point: Multiple split points
  • Uniform: Random bit selection
  • Arithmetic: Weighted combinations

Mutation Strategies

  • Bit-flip: Toggle binary values
  • Gaussian: Add normal noise
  • Swap: Exchange elements
  • Adaptive: Rate depends on diversity
Crossover and Mutation Visualization
Parameter Guidelines: Population size 50-200, crossover rate 0.6-0.9, mutation rate 0.01-0.1, selection pressure moderate to maintain diversity.

Advanced Metaheuristic Algorithms

Tabu Search

  • Memory-based search with forbidden moves
  • Tabu list prevents cycling
  • Aspiration criteria override taboos
  • Diversification and intensification

Harmony Search

$$x_i^{new} = \begin{cases} x_i^{random} & \text{with probability } HMCR \\ x_i^{memory} \pm \epsilon & \text{with probability } PAR \end{cases}$$

Mimics musical improvisation process.

Firefly Algorithm

$$I = I_0 e^{-\gamma r^2}$$

Light intensity decreases with distance, attracting less bright fireflies.

Cuckoo Search

  • Combines Lévy flights with cuckoo behavior
  • Nest abandonment for poor solutions
  • Efficient global search capability
  • Fewer parameters than other algorithms

Algorithm Selection: Choose based on problem dimensionality, constraint types, computational budget, and required solution quality.

Performance Analysis and Benchmarking

Algorithm
Strengths
Weaknesses
Best For
Random Walk
Simple, unbiased exploration
Very slow convergence
Baseline comparison
Lévy Flight
Efficient exploration, escapes local optima
Parameter tuning needed
Complex landscapes
Genetic Algorithm
Population diversity, robust
Many parameters, slow
Discrete optimization
PSO
Fast convergence, few parameters
Premature convergence
Continuous optimization
Simulated Annealing
Theoretical guarantees
Cooling schedule critical
Single-objective problems
Ant Colony
Good for graph problems
Pheromone tuning complex
Routing, scheduling
Benchmarking: Use standard test functions (Sphere, Rastrigin, Ackley) and report statistics over multiple runs. Consider convergence speed, solution quality, and robustness.

ML Applications and Hybrid Approaches

Hyperparameter Optimization

  • Grid/Random Search: Simple baselines
  • Genetic Algorithms: Complex parameter interactions
  • PSO: Continuous parameter spaces
  • Bayesian Optimization: Expensive evaluations

Neural Architecture Search

  • Evolutionary algorithms for architecture design
  • Reinforcement learning controllers
  • Differentiable architecture search
  • Multi-objective optimization (accuracy vs efficiency)

Feature Selection

  • Genetic algorithms for subset selection
  • PSO for feature weighting
  • Ant colony for sequential selection
  • Wrapper vs filter approaches
Hybrid Methods:
  • Memetic algorithms (GA + local search)
  • Multi-stage optimization
  • Ensemble of metaheuristics
  • Machine learning guided search
Search Algorithm Application Framework

Algorithm Selection Guidelines

Problem Characteristics

  • Dimensionality: Low (< 10): exhaustive, Medium (10-100): metaheuristics, High (> 100): specialized methods
  • Continuity: Discrete → GA, Continuous → PSO/DE
  • Multimodality: Many local optima → Lévy flights, diverse populations
  • Constraints: Heavy constraints → penalty methods, repair operators

Computational Constraints

  • Evaluation Cost: Expensive → Bayesian optimization, Cheap → population methods
  • Time Limits: Fast → PSO/DE, Thorough → GA
  • Memory: Limited → simple algorithms
  • Parallel Processing: Available → population methods

Best Practices: Start with simple baselines (random search), understand your problem landscape, tune algorithms properly, use multiple runs for statistical significance, and consider hybrid approaches for complex problems.

Future Directions: Integration with deep learning (neural architecture search), multi-objective optimization for real-world trade-offs, and adaptive algorithms that learn problem structure during search.
1 / 10