Chapter 5 - Local Search

5.1 Local Search Algorithms

Overview

• Purpose: In many search problems, the path from initial state to goal is not important
• Focus: Final configuration of the goal is the target
• Example: 8-queens problem
  • Initial state: empty board
  • Goal state: only conditions known (8 queens placed without attacking each other)

Applications

• IC design
• Factory floor layout
• Job scheduling
• Optimization problems

Key Characteristics

• Complete-state formulation: Each state has all variables assigned
  • Example: Every state has all 8 queens on the board for 8-queens problem
• Iterative improvement: Keep only one "current" state, try to improve it until goal state is reached
• Memory efficiency: Space complexity is O(1)
• Scalability: Can often find reasonable solutions in large state spaces

Optimization Problems

• Objective: Find state with best value (maximum or minimum) of an objective function
• Key concepts:
  • Global maximum: State with highest value in entire state space
  • Local maximum: State with highest value in its neighborhood
  • Shoulder: Region where function is relatively flat (values don't change significantly)
    • Can trap search process for many iterations
  • Flat local maximum: Region where all nearby states have equal or lower values, but maximum is not confined to single point

5.2 Hill Climbing Search

Algorithm Description

• Method: Repeatedly moves current node in direction that increases (or decreases) objective value
• Termination: Ends when current node reaches peak where no neighbor has higher (or lower) value

Example 5.1: 8-Queens Problem with Hill Climbing

• State representation: Complete-state formulation with 8 queens on board, one per column
• Successors: All states generated by moving one queen to another square in same column
• Heuristic cost function (h): Number of pairs of queens attacking each other
• Goal: Find state with global minimum value (h = 0)
• Starting point: Randomly generated board

[Note: There's a visual example showing states with h values of 4, 2, 3, 4, 5, etc., leading to next state with h = 1]

Example 5.2: Facility Location Problem

• Components:
  • Set of potential facility locations (L)
  • Set of client locations (D)
  • Distance function d(i,j) where i ∈ L and j ∈ D
  • Cost function f(i) where i ∈ L
• Objective: Find S ⊆ L that minimizes operation cost:
  • Σ(i∈S) f(i) + Σ(j∈D) min(k∈S) d(k,j)

Example 5.3: Coordinate-Based Search

• State representation: Ordered pair (x,y)
• Initial state: (0,0)
• Successors: (x-1,y), (x,y+1), (x+1,y), (x,y-1)
• Objective: Find state with maximum objective value using hill climbing

[Note: There's a grid showing objective function values from coordinates (0,0) to (9,9)]

5.2.1 Random-Restart Hill Climbing

Purpose

• Problem: Avoid getting stuck in local maximum (or minimum)
• Solution: Conduct hill climbing search multiple times from different random initial states

Algorithm Steps

1. Start from randomly generated state
2. Conduct hill climbing search until reaching local maximum
3. Generate new random state
4. Repeat process

Example 5.4: Random-Restart Implementation

• Setup: 5 HC searches starting from different points: (0,4), (9,7), (5,4), (9,2), (1,0)
• Benefit: Increases probability of finding global optimum

5.2.2 Evaluating Hill Climbing Algorithm

Limitations

• Incompleteness: Always moves uphill, never downhill → can get stuck at local maxima
• Guaranteed to be incomplete due to local maxima problem

Alternative: Pure Random Walk

• Method: Current state replaced by randomly chosen successor
• Characteristics:
  • Complete: Can eventually find global optimum
  • Extremely inefficient: May take very long time

Optimal Approach

• Combination: Effective local search should combine hill climbing with random walk
• Benefits: Gain efficiency of hill climbing + completeness of random exploration
• Example comparison:
  • Hill climbing: Reaches local maximum in 15 iterations
  • Random walk: Finds global maximum after 1,700 iterations

5.3 Simulated Annealing

Inspiration

• Source: Annealing process in metallurgy (technique to harden metals)
• Physical process:
  • Heat metal to high temperature
  • Gradually cool down to allow atoms to settle into low-energy crystalline state

Algorithm Adaptation

• Temperature parameter (t): Introduced into hill-climbing algorithm
• Process:
  • Start with high t → allows more random moves (including downhill moves)
  • Gradually decrease t → reduces randomness, focuses search on moving uphill
• Result: Broad exploration at start → convergence towards optimal state at end

5.3.1 Temperature and Probability

Decision Process

1. Candidate selection: Randomly select candidate successor from successors set
2. Better solution: If candidate has better value → always accepted
3. Worse solution: If candidate has worse value → may still be accepted with certain probability

Probability Formulas

Maximization Case

• Current state: s
• Candidate state: s'
• Temperature: t
• Probability of moving to worse state: p = e^(ω/t)
• Where ω = f(s') - f(s) (difference between new and current state values)

Minimization Case

• Probability of moving to worse state: p = e^(-ω/t)
• Where ω = f(s') - f(s)

Example 5.5: Probability Calculation

• Given: t = 90, f(s) = 10, f(s') = 5
• Maximization case: ω = 5 - 10 = -5, p = e^(-5/90)
• Minimization case: ω = 5 - 10 = -5, p = e^(5/90)

Temperature Effects Table

5.3.2 Cooling Schedule

Definition

• Purpose: Defines how temperature is gradually decreased during search

Common Schedules

• Exponential cooling: t ← εt, where 0 < ε < 1
• Linear cooling: t ← t - θ

Important Tip

• Balance: Cooling schedule should be:
  • Slow enough (ε close to 1) → allows effective state space exploration
  • Fast enough → avoids excessive computation time

5.3.3 Hill Climbing vs Simulated Annealing

Visual Comparison

[Note: The document shows three comparison images:]

1. Hill Climbing Search

   • Shows trajectory getting stuck at local optimum
   • Limited exploration capability

2. Random Restart Hill Climbing Search

   • Shows multiple search trajectories from different starting points
   • Better coverage but still limited by local optima

3. Simulated Annealing Search

   • Shows extensive exploration with ability to escape local optima
   • Broader coverage of search space
   • Eventually converges to better solutions

5.4 Genetic Algorithm

Overview

• Inspiration: Natural selection process in biology
• Unique characteristics:
  • Maintains population of states (individuals) rather than single state
  • Generates new states by combining two existing states (parents) through crossover and mutation
  • No successor function required → new states generated directly from pairs of existing states

State Representation

• Format: String over finite set of alphabets (e.g., {0,1})
• Biological analogy: Each string serves as chromosome of individual in population

Core Operations

Crossover

Process:

1. Randomly select two states (each represented by string of 8 digits)
2. Randomly pick cutting point
3. Select substring before cutting point from first state
4. Select substring after cutting point from second state
5. Connect them to form successor state

Example:

• Parent 1: 12345678
• Parent 2: 87654321
• Cutting point: after position 3
• Offspring: 12354321

Mutation

Process:

1. Randomly select value in state
2. Change value to random value (within valid range)

Example:

• Original: 6 7 2 5 1 4 4 7
• Mutated: 6 7 2 5 1 5 4 7 (position 6: 4→5)

Selection

Purpose: Ensure best states are selected for generating new states

Fitness Function: Objective function that quantifies quality of state

Selection Probability:

• Maximization case: Higher fitness → higher selection probability
• Minimization case: Lower fitness → higher selection probability
• Common practice: Transform minimization to maximization problems

Example 5.6: Selection Probability Calculation

Setup: 8-queens problem with fitness = number of non-attacking queen pairs

Population:

• Individual 1: f₁ = 24, p₁ = 0.31
• Individual 2: f₂ = 23, p₂ = 0.29
• Individual 3: f₃ = 20, p₃ = 0.26
• Individual 4: f₄ = 11, p₄ = 0.14

Formula: pᵢ = fᵢ / Σⱼ₌₁ⁿ fⱼ

Crossover results:

• Parent combination 1: f = 23
• Parent combination 2: f = 21

Example 5.7: Fitness Function Inversion

Problem: When fitness = number of attacking queen pairs (minimization)

Method 1: f'ᵢ = fₘₐₓ - fᵢ

• For 8-queens: fₘₐₓ = ₈C₂ = 28

Method 2: f'ᵢ = 1/(fᵢ + ε)

• Where ε is small positive constant to avoid division by zero

Example calculation (fᵢ = 4, ε = 10⁻⁶):

• Method 1: f'ᵢ = 28 - 4 = 24
• Method 2: f'ᵢ = 1/(4 + 0.000001) ≈ 0.25

Common Selection Methods

Roulette Wheel Selection

• Concept: Each individual assigned wheel segment proportional to fitness value
• Process: Spin wheel, select individual in segment where wheel stops
• Example segments: [0, 0.31], [0.31, 0.60], [0.60, 0.86], [0.86, 1]

Tournament Selection

• Process:
  1. Randomly select small group of individuals
  2. Choose one with highest fitness value as parent
• Example: Select 2 individuals, compare fitness, choose better one

Example 5.8: Continuous Optimization

Problem: Maximize f(x,y) = 100 - (x-1)² - (y-1)²
Constraints: x,y ∈ [-5, 5]
Challenge: How to represent individual for continuous variables?

Possible solutions:

• Binary encoding of discretized values
• Real-valued encoding
• Gray coding for better neighborhood properties