Lecture on Local Search and Evolutionary Algorithms

Presented by: Dr. Amir Pourabdollah

Main Resources

• Textbooks: Chapters 4-5
• Wirsansky, Eyal (2020): Hands-on genetic algorithms with Python
  • Focus: Genetic algorithms applied to real-world deep learning and AI problems
• Eiben & Smith (2015): Introduction to Evolutionary Computing, 2nd ed.
  • Available at: Introduction to Evolutionary Computing Chapter 2
• DEAP Documentation: DEAP Documentation

Lecture Outline

1. Local Search Algorithms
2. Evolutionary Algorithms
3. Related Algorithms

Local Search

• Definition: A solution is just a final state; the sequence of actions or starting point may not be significant.
• Characteristics:
  • Large search space
  • Often non-deterministic and partially observable
  • Optimality testing is complex
  • Iterative improvement of solution candidates
• Applications: Logistics, Networking, VLSI design, drug design

Example: Traveling Salesperson Problem (TSP)

• Large search space: For n cities, (n-1)!/2 possible routes
• Fitness Function: Total journey length (to be minimized)

Local Search Algorithms

• Hill Climbing Algorithm:
  • Move to the neighbor with the highest fitness; stop if no better state is found.
  • Challenges: Stuck in local maxima
  • Solutions: Random-restart Hill Climbing, Tabu Search
• Simulated Annealing (SA):
  • Inspired by cooling of metal crystal structures
  • Involves temperature (T) variable influencing move probability
• Beam Search:
  • Multi-thread local search keeping track of multiple states
  • Variations: Stochastic Beam Search, Evolutionary Algorithm

Exploitation & Exploration

• Mixing orderly improvement and random exploration
• Balancing both can help in reaching global optimum

Constraint Satisfaction Problems (CSPs)

• Definition: Local search with a goal test
• Applications: Assignment, Timetabling, Job Scheduling
• Example: Map Colouring Problem
  • Constraint: No two adjacent regions share the same color
• Techniques: Backtracking, MRV, Degree Heuristic

Evolutionary Algorithms

• Concept: Inspired by biological evolution; population-based local search
• Key Features: Survival of the best, exploitation of solutions
• Examples: Genetic Algorithm (GA)

Genetic Algorithm (GA)

• Components:
  • Individual or Chromosome: Potential solution
  • Genes: Basic unit of a chromosome
  • Population: Set of individuals
  • Fitness Function: Measures solution quality
• Operators:
  • Selection, Crossover, Mutation
• Critical Mapping: Define genes, chromosomes, fitness, etc.

Genetic Programming (GP)

• Special form of GA for evolving computer programs
• Programs modelled as tree structures

Particle Swarm Optimization (PSO)

• Inspired by flocking behavior
• Particles move towards optimum based on position and velocity

Summary

• Part 1: Local Search Algorithms
  • Hill Climbing, Simulated Annealing, CSPs
• Part 2: Evolutionary Algorithms
  • Genetic Algorithms and related techniques
• Other Nature-inspired Algorithms: Memetic, Ant Colony, Bee Colony, and more

Next Week: Dive deeper into Evolutionary Algorithms, including more about Genetic Algorithms and related methods.