Artificial Intelligence

LOCAL SEARCH ALGORITHMS

AND OPTIMIZATION PROBLEMS

Nguyễn Tiến Huy

ntienhuy@[Link]
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

6
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.

7
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.

8
Hill-climbing search
9
Hill-climbing search

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

current ← MAKE-NODE([Link]-STATE)
loop do
neighbor ← a highest-valued successor of current
if [Link] ≤ [Link] then return [Link]
current ← neighbor

A version of HILL-CLIMBING that finds local maximum.

10
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

11
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

12
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
13
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.

14
Hill climbing and local maxima

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

15
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.

16
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
17
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

18
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.”

19
Simulated annealing
20
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)

21
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([Link]-STATE)
for t = 1 to ∞ do
T ← schedule(t)
if T = 0 then return current
next ← a randomly selected successor of current
ΔE ← [Link] – [Link]
if ΔE > 0 then current ← next
else current ← next only with probability eΔE/T

22
Local beam search
23
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

24
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

25
Genetic algorithms
26
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

27
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
28
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

29
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.
30
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.

31
Reproduction: Roulette wheel

32
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.

33
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)
34
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

35
A workflow of Genetic algorithms

Initial Fitness Yes

STOP? End
Population calculation

No
Start

Selection Cross-over Mutation

New population

Next generation building

36
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 37
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))

38
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

39
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!

40
THE END

41