Search as Optimization
AIMA 4.1 – 4.2
CMPSC 442
Week 3, Meeting 9, Three Segments
Outline
● Search as Optimization: Hill-Climbing (a Local Search Method)
● Other Local Search Methods
○ Simulated Annealing
○ Beam Search
○ Genetic Algorithms
● Search in Continuous Spaces
2Outline, Wk 3, Mtg 9
Search as Optimization
AIMA 4.1 – 4.2
CMPSC 442
Week 3, Meeting 9, Segment 1 of 3: Search as Optimization;
Hill Climbing
Local Search
● Local search
○ When path to goal doesn’t matter
○ Iterate
■ Remember only current state
■ Move to best neighboring state, forget the past
● Idea: incrementally improve an initial guess
4Search as Optimization
Search as Optimization
● Advantages:
○ Low memory usage!
○ Often finds reasonable solutions in large or infinite state spaces
● Useful for pure optimization problems
○ Find or approximate best state according to some objective function
○ Optimal if the space to be searched is convex
5Search as Optimization
Optimization
● Maximize (or minimize) a real function
○ Choose input values from the domain
○ Compute the value of the (objective) function
● Given: a function F: A ➝
○ Define an objective x
0
in A such that
■ f(x
0
) ≤ f(x) for all x in A (minimization)
○ Or
■ f(x
0
) ≥ f(x) for all x in A (maximization)
6Search as Optimization
Convex Functions
● A function f is convex when, for any two
points (x, f(x)) and (y, f(y)), a line segment
connecting the two points lies above the
curve for f
● Use of an arbitrary function g as your
objective function means to use g as the
criterion for achieving the problem goal
● If the objective function g is convex, then the
goal can be identified as z such that g(z)=0
7
z
State Space Landscape
Two points of view
● Hill-climbing:
Maximize an
objective function
(global maximum)
● Gradient descent:
Minimize a loss
function (global
minimum)
8Search as Optimization
Hill Climbing in a Few Words
● Like trying to find the top of Mount Everest in a fog while suffering from
amnesia
9Hill Climbing
Hill Climbing Details
● Given the current state n, an evaluation function f(n) and snext equal to
n’s successor state s that maximizes f(s):
○ If f(snext) ≥ f(n), then move to snext
○ Else halt at n
● Terminates when a peak is reached
● Has no look-ahead at the immediate neighbors of the current state
● Chooses a random best successor, if there is more than one
● Cannot backtrack, since it doesn’t remember where it’s been
10Hill Climbing
Hill Climbing Pseudo Code
11Hill Climbing
Hill Climbing Illustration with 8-puzzle
12
3 1 2
4 5 8
6 7
hoop=5
3 1 2
4 5 8
6 7
hoop=4
3 1 2
4 5
6 7 8
3 1 2
4 5
6 7 8
3 1 2
4 5
6 7 8
1 2
3 4 5
6 7 8
hoop=3 hoop=2 hoop=1 hoop=0
Evaluation function: # out-of-place tiles
1. First move: f(7) = 4; f(5) = 5; f(6) = 6
2. Second move: f(8) = 3; f(7) = 5
3. Third move: f(5) = 2; f(8) = 3; f(2) = 3
4. Fourth move: f(4) = 1; f(7) = 3; f(1) = 3
5. Fifth move: f(3) = 0; f(4) = 1; f(7) = 3
Hill Climbing
Start 1 2 3 4 5
Local Maximum with 8-Puzzle
13
4 1 2
3 5
6 7 8
hoop= 1
All successor states have higher OOP:
4 1 2
3 5
6 7 8
4 2
3 1 5
6 7 8
4 1 2
3 7 5
6 8
hoop= 2
Hill Climbing
No possible move, stuck in local maximum
4 1 2
3 5
6 7 8
Hill Climbing with N-Queens
● Problem: Place n queens on an n ✕ n board with no two queens on
the same row, column, or diagonal (no attacking pairs)
● Good heuristic: h = number of pairs of queens that are attacking each
other
14Hill Climbing
h = 5 h = 3 h = 2
Example with 8-Queens
● Board 1: Each cell shows the h-value (number of queens attacking each
other) for successors where a queen moves within its column
● Board 2: A local minimum of h = 1
○ Why?
15
h = 17
Hill Climbing
h = 1
Hill Climbing Variants
● Stochastic
○ Choose at random from uphill moves
○ When would this improve over choosing best-valued successor?
● Random-restart
○ Trivially complete: If at first you don’t succeed, try, try again
○ Where each search has probability of success p, there is a high probability
of success after 1/p trials
○ Works very well with few local maxima and few plateaux
16Hill Climbing
Test Your Understanding
17Hill Climbing
How would hill climbing perform in these
state-space landscapes?
● Convex
● Bumpy convex
● Undulating convex
● Ridge
● Spiky
● Rough steeple
What about random-restart with hill-climbing?
What about stochastic hill-climbing?
Search as Optimization
AIMA 4.1 – 4.2
CMPSC 442
Week 3, Meeting 9, Segment 2 of 3: Other Local Search
Methods
Other Local Search Methods
● Simulated Annealing
● Beam Search
● Genetic Algorithms
19Other Local Search Methods
Motivation for Simulated Annealing
● Pros/Cons of hill climbing (including stochastic HC, random restart HC)
○ If landscape is convex, can be very fast
○ Real problems are rarely convex
■ If “downhill” moves are not allowed, cannot escape local maxima
■ Stochastic HC allows downhill moves with low probability
○ Random restart is complete but very inefficient
● Simulated annealing makes HC both efficient and complete
○ Combines completeness of random restart with efficiency of stochastic
methods
○ Basic idea: Diminish the randomness as search progresses
20Other Local Search Methods
Simulated Annealing
● Annealing: the process by which a metal cools slowly and as a result
freezes into a minimum-energy crystalline structure
● Adopt a control parameter T, which by analogy with metallurgy is
known as the system “temperature”
○ T controls the amount of randomness in picking a successor
○ T starts out high to promote escape from local maxima early on
○ T gradually decreases toward 0 over time to avoid getting thrown off track
late in the search (where efficiency of a greedy method comes in)
21Other Local Search Methods
Acceptance Probability (ap)
ap close to 1 if new solution is better
ap decreases as new solution is increasingly worse
ap decreases as T decreases if cost(new)> cost(old)
● Can accept mildly bad but not terrible next moves
● Accepts any bad jumps earlier rather than later
22Other Local Search Methods
Simple Python Implementation
23Other Local Search Methods
From Katrina Ellison Geltman
Beam Search
● Keep track of k states
○ Memory usage is already low, so tracking multiple
states is not an issue
● Find successors of all k
● Take top k successors across all k beams
○ Shares information across beams
○ Only the computation of successor states is
pursued in parallel
● Stochastic variant: pick a successor with
probability proportional to the successor’s value.
24Other Local Search Methods
Why?
Evolutionary Algorithms
● Variants of stochastic beam search, natural selection as metaphor
● Many varieties, with differences in
○ Size of the population (analogus to k in beam search)
○ What counts as an individual (a sequence of reals; a computer program)
○ Mixing number ρ (or number of parents)
○ Selection of parents for next generation, e.g., based on fitness score
○ Recombination procedure: How are the offspring produced?
○ Mutation rate, to introduce randomness
○ Makeup of next generation: children alone; children + best parents; culled
selection of children
25Other Local Search Methods
Genetic Algorithm: Pseudo Code
26Other Local Search Methods
Example 1: 8-Queens
Digits represent location of queen’s row, for each column
27Other Local Search Methods
Benefits of Crossover
● Crossover can be beneficial given an advantageous pattern (schema)
on one side of the crossover point
○ 246 is a schema for Queens in rows 2, 4 and 6 of columns 1, 2 and 3
○ If the average fitness of instances of a schema is above the mean, then
the number of instances of the schema grows in successive generations
28Other Local Search Methods
Example 2: Box Car Simulation (not in AIMA)
● Each car is a set of 8 random vectors (direction and magnitude). All
vectors radiate from (0,0) and are connected into triangles
● Each car has two wheels
○ Zero to 2 vectors randomly chosen as axles
○ Axle angle is randomly set in [0, 2π]
○ Each wheel has a random radius
○ Two wheels can go on same axle
29
www.boxcar2d.com
Other Local Search Methods
Individual Box Cars (Chromosomes)
Length 22 Vector
● First sixteen numbers represent the angle, magnitude pairs for each
angle
● Next six numbers represent the axle location, axle angle and wheel
radius of the two wheels
30Other Local Search Methods
Box Car Representation
● Strengths
○ Vector angles and magnitudes are adjacent, so unlikely to be separated
during crossover
○ Adjacent vectors are adjacent
● Weakness
○ Wheel info (vertex, axle angles & wheel radius) is not linked to the vector
the wheel is associated with
31Other Local Search Methods
Box Car Fitness Function and Reproduction
● Each Car Scored by distance traveled
● Best scoring members of a generation mate, eg
○ for each car A
■ pick a random car B (excluding A)
■ highest score of A and B wins tournament
■ put winner in mating pool
○ randomly pick pairs from mating pool for crossover
Visit the website to watch the simulation or design your own cars
32Other Local Search Methods
Example 4th Generation Box Car
33Other Local Search Methods
Search as Optimization
AIMA 4.1 – 4.2
CMPSC 442
Week 3, Meeting 9, Segment 3 of 3: Search in Continuous
Spaces
Search in Continuous Spaces: Brief Introduction
● Problem: a continuous action space has an infinite branching factor
○ Many local search methods developed for discrete action spaces would
not generalize to continuous action spaces
○ Search methods with random selection of successor states will work
■ Simulated annealing:
■ First-choice hill climbing: stochastic HC that picks the first random successor
that improves on the current state
○ Or, in convex spaces, follow the gradient of the evaluation function f
■ The gradient ▽f is a vector with magnitude and direction of steepest slope
■ Solve for ▽f = 0
35Search in Continuous Spaces
Empirical Gradient Methods
● Used when the equation ▽f = 0 has no closed form solution
● Search progress depends on comparing the values of the objective
function f for the current state x and a successor state x’
● Progress is measured by change in the value of f
36Search in Continuous Spaces
Empirical Gradient Example
● Problem: Place three new airports in Romania in locations that
minimize the straight line distance to the nearest cities
○ Objective function, given a state x consisting of three x, y locations, and
given the sets Ci of cities closest to each candidate airport location i:
● One approach: discretize the way successors are found
○ Add a small amount 𝜹 to each dimension in turn
○ Move in a random direction by a small amount 𝜹
● Choose a successor state x’ if f(x’) < f(x) 37Search in Continuous Spaces Alternative: Gradient Descent ● Given a locally correct formula for the gradient, perform steepest ascent hill climbing to move in the direction of ▽f = 0 ○ Example motivation: given the 3 airport locations, the objective function has no closed form solution; it can be solved locally (given 3 hypothetical locations), but not globally (the globally best 3 locations) ○ Update the current state x in steps that add the current gradient (which should be decreasing with each next step) multiplied by a small weight (step size): ○ Inefficient if α is too small, can overshoot the maximum if α is too big 38Search in Continuous Spaces Visualizing Gradient Descent in 3D State Space ● If f(x) is differentiable near xi find argx that minimizes f(x) ○ Choose x0 randomly, use small weight η ○ Repeat update rule until convergence 39Search in Continuous SpacesSearch in Continuous Spaces Newton-Raphson Method ● Produces successively better approximations to the root (zero) of a real-valued function: ● Substituting ▽f(x) for g(x) and its derivative (second derivative of f(x)) for g’(x) can be written in matrix form, where Hf(x) is the Hessian matrix of second derivatives, as: 40Search in Continuous Spaces Newton-Raphson Method is More Efficient Newton-Raphson method is a more direct route ● Blue circles: contour lines of a function ● Green line: Gradient descent ● Red line: Newton’s method ● The 2nd order information ○ More expensive to compute ○ Converges much faster 41Search in Continuous Spaces Summary ● Hill climbing: a local search method (ignores past steps/path) that selects successors that improve on the current state (optimize an objective function) ○ Can easily get stuck in local maxima, or plateaus ○ Random restart is complete but very inefficient ○ Adding controlled randomness (e.g., simulated annealing) can preserve completeness and improve efficiency ● Other local search methods take successors of multiple states (beam search), or adopt evolutionary/genetic methods to benefit from multiple successors ● Search in continuous spaces often relies on gradient methods ○ Gradient descent updates the state using a small step size weight on the current gradient to produce the successor state ○ Newton’s method using second-order information is more direct 42Summary Wk 3, Mtg 9