Artificial Intelligence

LOCAL SEARCH ALGORITHMS

AND OPTIMIZATION PROBLEMS

Nguyễn Ngọc Thảo – Nguyễn Hải Minh

{nnthao, nhminh}@fit.hcmus.edu.vn
Outline
• Optimization problems
• Hill-climbing search
• Simulated annealing
• Local beam search
• Genetic algorithm

2
Optimization problems
3
Global search algorithms
• Global search: explore search spaces systematically
• Keep one or more paths in memory and record which alternatives
have been explored at each point along the path
• Many problems do not fit the “standard” search model.
• The final configuration matters, not the order in which it is formed.
• No “goal test” and no “path cost”, e.g., Darwinian evolution with
“natural” reproductive fitness

4
Optimization problems
• Find the best state according to an objective function.
• E.g., the Knight’s tour, TSP, scheduling, integrated-circuit design,
factory-floor layout, automatic programming, vehicle routing, etc.

5
Local search algorithms
• Operate using a single current node and generally move
only to neighbors of that node
• Not systematic
• The paths followed by the search are typically not retained.
• Use very little memory, usually a constant amount
• Find reasonable solutions in large or infinite (continuous)
state spaces

Global search: 𝑛 = 200

vs.
Local search: 𝑛 = 1,000,000

6
Local search and Optimization

“Pure optimization” problems Local search can do quite well

on these problems.
All states have an objective function
Goal is to find state with max (or min)
objective value

7
State-space landscape
• A landscape has both “location” and “elevation”
• Location  state, elevation  heuristic cost or objective function

A 1D state-space landscape in which elevation corresponds to the objective function.

8
State-space landscape

Global minimum Global maximum

Elevation corresponds to cost Elevation corresponds to an
objective function
Find the lowest valley Find the highest peak

• A complete local search algorithm finds a goal if one exists.

• An optimal local search algorithm finds a global extremum.

9
Hill-climbing search
10
Hill-climbing search

function HILL-CLIMBING(problem) returns a state that is a local maximum

current ← MAKE-NODE(problem.INITIAL-STATE)
loop do
neighbor ← a highest-valued successor of current
if neighbor.VALUE ≤ current.VALUE then return current.STATE
current ← neighbor

A version of HILL-CLIMBING that finds local maximum.

11
Hill-climbing search
• A loop that continually moves in the direction of increasing
value and terminates when it reaches a “peak”.
• Peaks are where no neighbor has a higher value.
• Not look ahead beyond the immediate neighbors of the
current state
• No search tree maintained, only the state and the objective
function’s value for the current node recorded
• Sometimes called greedy local search
• Grab a good neighbor without thinking ahead about where to go next

12
Hill-climbing: 8-queens problem
• Complete-state formulation
• All 8 queens on the board, one per column
• Successor function
• Move a queen to another square in the same column → 8 × 7 = 56
successors
• Heuristic cost function ℎ(𝑛)
• The number of pairs of queens that are ATTACKING each other,
either directly or indirectly → global minimum has ℎ 𝑛 = 0
• Make rapid progress toward a solution
• 8-queens (88  17 million states): 4 steps on average when succeeds
and 3 when get stuck

13
Hill-climbing: 8-queens problem

The best moves

• Current state 𝑐1 𝑐2 𝑐3 𝑐4 𝑐5 𝑐6 𝑐7 𝑐8 = (5 6 7 4 5 6 7 6) ℎ 𝑛 = 17
• The best successors has ℎ = 12 → choose randomly among
the set of best successors if there is more than one
14
Hill climbing and local maxima
• Often suboptimal, due to local maxima, ridges and plateau
• E.g., 8-queens: steepest-ascent hill climbing gets stuck 86% of the
time, solving only 14% of problem instances

The grid of states (dark circles) is

superimposed on a ridge rising from left to
right, creating a sequence of local maxima
that are not directly connected to each other.
From each local maximum, all the available
actions point downhill.

NP-hard problems typically have an exponential number of local maxima to get stuck on.

15
Hill climbing and local maxima

• Current state (8 3 7 4 2 5 1 6) ℎ 𝑛 = 1
• Every successor has a higher cost → local minimum

16
Solutions: Sideways moves
• If no downhill (uphill) moves, the algorithm can escape with
sideways moves.
• A limit on the possible number of sideways moves required to avoid
infinite loops
• For example, 8-queens problem
• Allow sideways moves with a limit of 100 → percentage of problem
instances solved raises from 14 to 94%
• Success comes at a cost: the algorithm averages roughly 21 steps
for each successful instance and 64 for each failure.

17
Solutions: Hill-climbing variants
• Stochastic hill climbing
• Choose at random from among the uphill moves with a probability of
selection varied with the moves’ steepness
• Usually converge more slowly than steepest ascent, but find better
solutions in some cases
• First-choice hill climbing
• Generate successors randomly until one is generated that is better
than the current state
• Good strategy when a state has many successors (e.g., thousands)
• Random-restart hill climbing
• A series of hill-climbing searches from randomly generated initial
states until a goal is found
18
Random-restart hill climbing
• Find a good solution quickly after a small number of restarts
• The series of hill-climbing searches can be organized flexibly
• For each restart: run until termination vs. run for a fixed time
• Run a fixed number of restarts vs. run indefinitely
• If each search has a probability 𝑝 of success, the expected
number of restarts required is 1/𝑝
• Very effective indeed for 8-queens

19
Quiz 01: 4-queens problem
• Consider the following 4-queen problem

• Apply (first-choice) hill-climbing to find a solution, using the

heuristic “The number of pairs of queens ATTACKING each
other.”

20
Simulated annealing
21
Simulated annealing
• Combine hill climbing with a random walk in some way that
yields both efficiency and completeness
• Shake hard (i.e., at a high temperature) and then gradually
reduce the intensity of shaking (i.e., lower the temperature)

22
Simulated annealing
function SIMULATED-ANNEALING(problem, schedule)
returns a solution state
inputs: problem, a problem
schedule, a mapping from time to “temperature”
current ← MAKE-NODE(problem.INITIAL-STATE)
for t = 1 to ∞ do
T ← schedule(t)
if T = 0 then return current
next ← a randomly selected successor of current
ΔE ← next.VALUE – current.VALUE
if ΔE > 0 then current ← next
else current ← next only with probability eΔE/T

23
Local beam search
24
Local beam search
• Keep track of 𝑘 states rather than just one
• Begin with 𝑘 randomly generated states
• At each step, all successors of all 𝑘 states are generated
• If the goal is not found, select the 𝑘 best successors from the
complete list and repeat

25
Local beam search
• Useful information is passed among the parallel search
threads → major difference from random-restart search
• Possibly suffer from a lack of diversity among the 𝑘 states
• Quickly concentrate in a small region of the state space → an
expensive version of hill climbing
• Stochastic beam search
• Choose 𝑘 successors at random, with the probability of choosing a
given successor being an increasing function of its value

26
Genetic algorithms
27
Genetic algorithms
• A variant of stochastic beam search
• Successor states are generated by combining two parent
states rather than by modifying a single state
• The reproduction are sexual rather than asexual

28
Genetic algorithms: 8-queens

2 pairs of 2 states randomly New states

4 states for Random
selected based on fitness. after crossover
8-queens mutation
problem Random crossover points applied
selected
29
Genetic algorithms
• Population: a set of 𝑘 randomly generated states to begin with
• Fitness function: an objective function that rates each state
• Higher values for better state
• E.g., 8-queens: the number of non-attacking pairs of queens (min =
0, max = 8×7/2 = 28)

• Produce the next generation

by “simulated evolution”
• Random selection
• Crossover
• Random mutation

30
Representation of Individuals
• Each state, or individual, is represented as a string over a
finite alphabet – most commonly, a string of 0s and 1s.
• E.g., 8-queens: 8 × log 2 8 = 24 bits

• Alternatively, the state could be represented as 8 digits, each

in the range from 1 to 8.
31
Reproduction
• Pairs are selected at random for reproduction.
• The probability of being chosen for reproducing is directly
proportional to the fitness score.
• E.g., 24/(24+23+20+11) = 31%, 23/(24+23+20+11) = 29%, etc.
• One individual may be selected several times or not at all.

32
Reproduction: Roulette wheel

33
Quiz 02: Calculate fitness scores
• Consider the 4-queens problem, in which each state
has 4 queens, one per column, on the board. The
state can be represented in genetic algorithm as a
sequence of 4 digits, each of which denotes the
position of a queen in its own column (from 1 to 4).

• 𝑭𝒊𝒕 𝒏 = the number of non-attacking pairs of queens

• Let the current generation includes 4 states:
S1 = 2341; S2 = 2132; S3 = 1232; S4 = 4321.
• Calculate the value of 𝑭𝒊𝒕(𝒏) for the given states and the probability that
each of them will be chosen in the “selection” step.

34
Crossover operation
• For each pair to be mated, a crossover point is chosen
randomly from the positions in the string.

• Effectively “jump” to a completely different new part of the

search space (quite non-local)
35
Mutation operation
• Each location is subject to random mutation with a small
independent probability.
• E.g., 8-queens: choosing a queen at random and moving it to a
random square in its column

36
A workflow of Genetic algorithms

Initial Fitness Yes

STOP? End
Population calculation

No
Start

Selection Cross-over Mutation

New population

Next generation building

37
Genetic algorithms
function GENETIC-ALGORITHM(population, FITNESS-FN)
returns an individual
inputs: population, a set of individuals
FITNESS-FN, a function that measures the fitness of an individual
repeat
new_population ← empty set
for i = 1 to SIZE(population) do
x ← RANDOM-SELECTION(population, FITNESS-FN)
y ← RANDOM-SELECTION(population, FITNESS-FN)
child ← REPRODUCE(x , y)
if (small random probability) then child ← MUTATE(child)
add child to new_population
population ← new_population
until some individual is fit enough, or enough time has elapsed
return the best individual in population, according to FITNESS-FN 38
Genetic algorithms
function REPRODUCE(x , y) returns an individual
inputs: x , y, parent individuals
n ← LENGTH(x); c ← random number from 1 to n
return APPEND(SUBSTRING(x , 1, c), SUBSTRING(y, c + 1, n))

39
Comments on Genetic algorithms
• Random exploration find solutions that local search does not
• Via crossover primarily
• Can solve “hard” problem
• Rely on very little domain knowledge
• Appealing connection to human evolution

40
Comments on Genetic algorithms
• Large number of “tunable” parameters
• Difficult to replicate performance from one problem to another

• Lack of good empirical studies comparing to simpler methods

• Useful on some (small?) sets of problem, yet no convincing
evidence that GAs are better than hill-climbing w/random restarts
in general.
• Require careful engineering of the representation

• Application: Genetic Programming!

41
THE END

42