Introduction to

Artificial Intelligence
Chapter 2: Solving Problems
by Searching (5)
Local Search Algorithms &
Optimization Problems
Nguyễn Hải Minh, Ph.D
nhminh@fit.hcmus.edu.vn
Outline
1. Optimization Problems
2. Hill-climbing search
3. Local beam search
4. Genetic algorithm
5. Issues with local search

7/12/2020 Nguyễn Hải Minh @ FIT 2

Local search and optimization
❑Global search: systematic exploration of search
space.
o Can solve n-queen problems for n = 200

❑Different algorithms can be used

o Local search
o Can solve n-queen for n = 1,000,000

7/12/2020 Nguyễn Hải Minh @ FIT 3

Local search and optimization
❑Local search
o Keep track of single current state
o Move only to neighboring states
o Ignore paths

❑Advantages:
o Use very little memory
o Can often find reasonable solutions in large or infinite
(continuous) state spaces.

7/12/2020 Nguyễn Hải Minh @ FIT 4

Local search and optimization
❑“Pure optimization” problems
o All states have an objective function
o Goal is to find state with max (or min)
objective value
o Local search can do quite well on these
problems.

7/12/2020 Nguyễn Hải Minh @ FIT 5

Examples of optimization problems
❑N-queens
❑Machine Allocation
❑Office Assignment
❑Travelling Saleperson Problem
❑Boolean Satisfiability
❑…

7/12/2020 Nguyễn Hải Minh @ FIT 6

 QUIZ
Give an example of a real life optimization
problem that you know. Explain clearly
what should be optimized in your problem.

*Do not use the ones that have been discussed on the slide
**Go to Moodles from 20:00 to 22:00 today (Jun 5th) to submit
your answer (bonus credit)

7/12/2020 Nguyễn Hải Minh @ FIT 7

“Landscape” of search for max value

7/12/2020 Nguyễn Hải Minh @ FIT 8

Hill-climbing search

This version of HILL-CLIMBING found local maximum.

7/12/2020 Nguyễn Hải Minh @ FIT 9

Hill-climbing search
❑“a loop that continuously moves in the direction of
increasing value”
o terminates when a peak is reached
o Aka greedy local search
❑Value can be either
o Objective function value
o Heuristic function value (minimized)
❑Hill climbing does not look ahead of the immediate
neighbors of the current state.
❑Can randomly choose among the set of best successors, if
multiple have the best value
❑Characterized as “trying to find the top of Mount Everest
while in a thick fog”
7/12/2020 Nguyễn Hải Minh @ FIT 10
Hill climbing and local maxima
❑When local maxima exist, hill climbing is suboptimal
❑Simple (often effective) solution
o Multiple random restarts

7/12/2020 Nguyễn Hải Minh @ FIT 11

Hill-climbing example
❑8-queens problem, complete-state formulation
o All 8 queens on the board in some configuration
❑Successor function:
o move a single queen to another square in the same
column.
❑Example of a heuristic function h(n):
o the number of pairs of queens that are attacking
each other (directly or indirectly)
o (so we want to minimize this)

7/12/2020 Nguyễn Hải Minh @ FIT 12

Hill-climbing example
❑(c1 c2 c3 c4 c5 c6 c7 c8) = (5 6 7 4 5 6 7 6)
The best moves

❑An 8-queens state with heuristic cost estimate h=17, showing the
value of h for each possible successor obtained by moving a queen
within its column.
Hill-climbing example
❑(c1 c2 c3 c4 c5 c6 c7 c8) = (8 3 7 4 2 5 1 6)

❑A local minimum in the 8-queens state space; the state has h=1 but
every successor has a higher cost.
Hill-climbing drawbacks
❑Ridge = sequence of local maxima difficult for greedy
algorithms to navigate
❑Plateau = an area of the state space where the evaluation
function is flat.
Performance of hill-climbing on 8-queens
❑Randomly generated 8-queens starting states
o 14% the time it solves the problem
o 86% of the time it get stuck at a local minimum

❑However…
o Takes only 4 steps on average when it succeeds
o And 3 on average when it gets stuck
o (for a state space with ~17 million states)

7/12/2020 Nguyễn Hải Minh @ FIT 16

Possible solution: sideways moves
❑If no downhill (uphill) moves, allow sideways
moves in hope that algorithm can escape
o Need to place a limit on the possible number of
sideways moves to avoid infinite loops
❑For 8-queens
o Now allow sideways moves with a limit of 100
o Raises percentage of problem instances solved
from 14 to 94%
o However….
• 21 steps for every successful solution
• 64 for each failure

7/12/2020 Nguyễn Hải Minh @ FIT 17

Hill-climbing variations
❑Stochastic hill-climbing
o Random selection among the uphill moves.
o The selection probability can vary with the steepness
of the uphill move.
❑First-choice hill-climbing
o stochastic hill climbing by generating successors
randomly until a better one is found
o Useful when there are a very large number of
successors
❑Random-restart hill-climbing
o Tries to avoid getting stuck in local maxima.

7/12/2020 Nguyễn Hải Minh @ FIT 18

Hill-climbing with random restarts
❑Different variations
o For each restart: run until termination vs run for a
fixed time
o Run a fixed number of restarts or run indefinitely
❑Analysis
o Say each search has probability p of success
• E.g., for 8-queens, p = 0.14 with no sideways moves
o Expected number of restarts?
o Expected number of steps taken?
Local beam search
❑Keep track of k states instead of one
o Initially: k randomly selected states
o Next: determine all successors of k states
o If any of successors is goal → finished
o Else select k best from successors and repeat.

❑Major difference with random-restart search

o Information is shared among k search threads.

❑Can suffer from lack of diversity.

o Stochastic beam search
• choose k successors proportional to state quality.

7/12/2020 Nguyễn Hải Minh @ FIT 20

Genetic algorithms
❑Different approach to other search algorithms
o A successor state is generated by combining two
parent states

❑A state is represented as a string over a finite

alphabet (e.g. binary)
o 8-queens
• State = position of 8 queens each in a column
=> 8 x log(8) bits = 24 bits (for binary
representation)

7/12/2020 Nguyễn Hải Minh @ FIT 21

Genetic algorithms
❑Start with k randomly generated states
(population)
❑Evaluation function (fitness function).
o Higher values for better states.
o Opposite to heuristic function, e.g., # non-attacking
pairs in 8-queens
❑Produce the next generation of states by
“simulated evolution”
o Random selection
o Crossover
o Random mutation

7/12/2020 Nguyễn Hải Minh @ FIT 22

 Genetic algorithms
Initial Fitness Yes
STOP? End
Population calculation

No

Start Cross-over
Selection

New population

Mutation
Next generation building
7/12/2020 Nguyễn Hải Minh @ FIT 23
Genetic algorithms
❑Genetic representation:
o Use integers
o Use bit string
❑Fitness function: number of non-attacking pairs
of queens (min = 0, max = 8×7/2 = 28)
o 24/(24+23+20+11) = 31%
o 23/(24+23+20+11) = 29% etc

7/12/2020 Nguyễn Hải Minh @ FIT 24

 Genetic algorithms

4 states for 2 pairs of 2 states New states Random

8-queens randomly selected based after crossover mutation
problem on fitness. Random applied
crossover points selected

7/12/2020 Nguyễn Hải Minh @ FIT 25

Genetic algorithms

Has the effect of “jumping” to a completely different new

part of the search space (quite non-local)

7/12/2020 Nguyễn Hải Minh @ FIT 26

Genetic algorithm pseudocode

7/12/2020 Nguyễn Hải Minh @ FIT 27

Genetic algorithm pseudocode

7/12/2020 Nguyễn Hải Minh @ FIT 28

Comments on genetic algorithms
❑Positive points
o Random exploration can find solutions that
local search can’t
• (via crossover primarily)
• Can solve “hard” problem
o Rely on very little domain knowledge
o Appealing connection to human evolution
• E.g., see related area of genetic programming

7/12/2020 Nguyễn Hải Minh @ FIT 29

Comments on genetic algorithms
❑Positive points

7/12/2020 Nguyễn Hải Minh @ FIT 30

Comments on genetic algorithms
❑Negative points
o Large number of “tunable” parameters
• Difficult to replicate performance from one problem to another
o Lack of good empirical studies comparing to simpler
methods
o Useful on some (small?) set of problems but no
convincing evidence that GAs are better than hill-
climbing w/random restarts in general

❑Application: Genetic Programming!

7/12/2020 Nguyễn Hải Minh @ FIT 31

Next class
❑Individual Assignment 2
❑Chapter 2: Solving Problems by
Searching (cont.)
o Adversarial Search (Games)

7/12/2020 Nguyễn Hải Minh @ FIT 32