Beyond Classical Search

Chapter 4
 Some real world problems
• Suppose you had to solve VLSI layout
problems (minimize distance between
components, unused space, etc.)…
• schedule airlines
• schedule workers with specific skills sets to do
tasks that have resource and ordering
constraints
 Common to all such problems
Characteristics of these problems are:

• The path to the goal is irrelevant -- all you care

about is the final configuration
• These are often optimization problems in
which you find the best state according to an
objective function
• These problems are examples of local search
problems
Iterative Improvement Algorithms

• Hill climbing
• Simulated annealing
• Genetic algorithms
 Iterative Improvement Algorithms
• In the most problems the solution is the
path. For example, the solution to the 8-
puzzle is a series of movements for the
“blank tile.” The solution to the traveling in
Romania problem is a sequence of cities
to get to Bucharest.
• For many optimization problems, solution
path is irrelevant
–Just want to reach goal state
 Iterative Improvement Algorithms
• State space / search space
– Set of “complete” configurations
– Want to find optimal configuration (or at least
one that satisfies goal constraints)
• For these cases, use iterative improvement
algorithm
– Keep a single current state
– Try to improve it
• Constant memory: The space complexity is
constant!
 Example: Travelling Salesperson Problem
Start with any complete tour, perform pairwise exchanges
B C B C

D D
A E A E

ACBDE AB C DE

Variants of this approach get within 1% of optimal very

quickly with thousands of cities.
 Example: n-queens
Put n queens on an n × n board with no two queens
on the same row, column, or diagonal. Move a queen
to reduce the number of conflicts (h).

Almost always solves n-queens problems almost

instantaneously for very large n, e.g., n = 1
million.
 Example: n-queens (cont’d)

5 Steps
from (a)
to (b)

(a) shows the value of h for each possible successor obtained by

moving a queen within its column. The marked squares show the
best moves.
(b) shows a local minimum: the state has h = 1 but every successor has higher
cost. A Local Minima
 Hill-climbing (or gradient ascent/descent)
function H I L L - C L I M B I N G (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

The hill-climbing search algorithm, which is the most basic local

search technique. At each step the current node is replaced by
the best neighbor; in this version, that means the neighbor with
the highest VALUE, but if a heuristic cost estimate h is used, we
would find the neighbor with the lowest h
 Hill-climbing (cont’d)
“Like climbing Everest in thick fog with amnesia.”
Problem: depending on initial state, can get stuck on local maxima
Random-Restart HC: Overcomes local maxima
Random side ways moves: Escapes from shoulders but loops on flat maxima

objective
function global maximum

shoulder

local maximum
"flat" local maximum

state space
current state
 Difficulties with ridges
The “ridge” creates a sequence of local maxima that are not directly
connected to each other. From each local maximum, all the available
actions point downhill.
Variation of Hill-Climbing techniques
stochastic: choose randomly from uphill moves. The probability
of selection can vary with steepness. This variation
converges more slowly than steepest ascent, but in
some state landscapes it finds better solutions.
first-choice: generate successors randomly one-by- one until one
better than the current state is found. This is a good
strategy for states with many (e.g., thousands) of
successors.
Random-restart: restart with a randomly generated initial state
to escape from local maxima or plateau
Better fix: Instead of picking the best move pick any move
that produces an improvement. This is called randomized hill
climbing
 Random-Restart Hill-Climbing
Advice: If at first you don’t succeed, try, try again!
Random-restart hill-climbing conducts a series of hill-
climbing searches from randomly generated initial states,
stopping when a goal is found.
With probability approaching 1, we will eventually
generate a goal state as the initial state.
If each hill-climbing search has a probability p of success,
then the expected number of restarts required to reach a
solution is 1/p.
Random-Restart Hill-Climbing Cont’d.
Example: 8-queens As we saw earlier, p ≈ 0.14.
In this case we need roughly 7 iterations (6 failures and 1
success).
Random restart hill-climbing is very effective for 8-queens.
Even for three million queens, the approach can find
solutions in under a minute.
The success of random-restart hill-climbing depends very
much on the shape of the state space. There are practical
problems with state spaces with very bad shapes.
 Hill Climbing
Cost

States

16
Hill Climbing
Current
Solution

17
Hill Climbing
Current
Solution

18
Hill Climbing
Current
Solution

19
Hill Climbing
Current
Solution

20
Hill Climbing
Best

21
 Simulated annealing
function S i m u l a t e d A n n e a l i n g (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
The simulated annealing algorithm, a version of stochastic hill
climbing where some downhill moves are allowed. Downhill
moves are accepted readily early in the annealing schedule and
then less often as time goes on. The schedule input determines
the value of the temperature T as a function of time.
 Simulated Annealing

• A Hill-climbing algorithm that never makes “downhill" moves

towards states with lower value can be incomplete.

• A random walk, i.e., moving to a successor chosen at

random from the set of successors, is complete but extremely
inefficient.

• How can we combine both?

• This is a classical tradeoff between exploration of the search

space and exploitation of the imperfect solution at hand. How do
we resolve this tradeoff?
 Simulated Annealing
• Pure hill climbing is not complete, but pure random search is
inefficient.
• Allows some apparently “bad moves”, in the hope of escaping
local maxima
• Simulated annealing offers a compromise.
• Inspired by annealing process of gradually cooling a liquid until it
changes to a low-energy state.
• Very similar to hill climbing, except include a user-defined
temperature schedule.
• When temperature is “high”, allow some random moves.
• When temperature “cools”, reduce probability of random move.
• If T is decreased slowly enough, guaranteed to reach best state.
• Best solution ever found is always remembered
 Simulated Annealing

Physical System Optimization Problem

state feasible solution

energy evaluation function
ground state optimal solution
quenching local search
temperature control parameter T
careful annealing simulated annealing
 Simulated Annealing
Cost Best

States

26
 Simulated Annealing
Cost Best

States

27
 Simulated Annealing
Cost Best

States

28
 Simulated Annealing
Cost Best

States

29
 Simulated Annealing
Cost Best

States

30
 Simulated Annealing
Cost Best

States

31
 Simulated Annealing
Cost Best

States

32
 Simulated Annealing
Cost Best

States

33
 Simulated Annealing
Cost Best

States

34
 Simulated Annealing
Cost Best

States

35
 Simulated Annealing
Cost Best

States

36
 Simulated Annealing
Cost Best

States

37
 Simulated Annealing
Cost Best

States

38
 Simulated Annealing
Cost Best

States

39
 Simulated Annealing
Cost Best

States

40
 Simulated Annealing
Cost Best

States

41
 Simulated Annealing
Cost Best

States

42
 Simulated Annealing
Cost Best

States

43
 Simulated Annealing
Cost Best

States

44
 Simulated Annealing
Cost Best

States

45
 Simulated Annealing
Cost Best

States

46
 Simulated Annealing
Cost Best

States

47
 Simulated Annealing
Cost Best

States

48
 Local beam search

Idea: keep k states instead of 1; choose top k of all their

successors
Not the same as k searches run in parallel! Searches that
find good states recruit other searches to join them.
Problem: quite often, all k states end up on same local hill.
To improve: choose k successors randomly, biased towards
good ones.
Observe the close analogy to natural selection!
 Local Beam Search
Cost

States

50
Local Beam Search

51
Local Beam Search

52
Local Beam Search

53
Local Beam Search

54
Local Beam Search

55
Local Beam Search

56
Local Beam Search

57
Local Beam Search

58
Local Beam Search

59
Local Beam Search

60
Local Beam Search

61
Local Beam Search

62
Local Beam Search

63
Local Beam Search

64
Local Beam Search

65
 Genetic Algorithms
Genetic Algorithms are computer algorithms
that search for good solutions to a problem from
among a large number of possible solutions.
They were proposed and developed in the 1960s
by John Holland, his students, and his colleagues
at the University of Michigan. These
computational paradigms were inspired by the
mechanics of natural evolution, including
survival of the fittest, reproduction, and
mutation.
 Genetic Algorithms
Basic idea behind Gas

GAs begin with a set of candidate solutions

(chromosomes) called population. A new
population is created from solutions of an old
population in hope of getting a better population.
Solutions which are chosen to form new solutions
(offspring) are selected according to their fitness.
The more suitable the solutions are the bigger
chances they have to reproduce. This process is
repeated until some condition is satisfied.
 Genetic algorithms (GAs)
A genetic algorithm (GA) is a method for solving both constrained
and unconstrained optimization problems based on a natural
selection process that mimics biological evolution.

The algorithm repeatedly modifies a population of individual

solutions . GA is a variant of stochastic beam search in which
successor states are generated by combining two parent states
(sexual reproduction).
 Genetic algorithms (GAs)
Name and describe the main features of Genetic Algorithms (GA).
Answer: Genetic Algorithms (GA) use principles of natural evolution.
There are five important features of GA:
1. Encoding possible solutions of a problem are considered as
individuals in a population. If the solutions can be divided into a series
of small steps (building blocks), then these steps are represented by
genes and a series of genes (a chromosome) will encode the whole
solution. This way different solutions of a problem are represented in
GA as chromosomes of individuals.
2. Fitness Function represents the main requirements of the desired
solution of a problem (i.e. cheapest price, shortest route, most
compact arrangement, etc). This function calculates and returns the
fitness of an individual solution.
 Genetic algorithms (GAs)
Name and describe the main features of Genetic Algorithms (GA).
3. Selection operator defines the way individuals in the current
population are selected for reproduction. There are many strategies
for that (e.g. roulette–wheel, ranked, tournament selection, etc), but
usually the individuals which are more fit are selected.
4. Crossover operator defines how chromosomes of parents are
mixed in order to obtain genetic codes of their offspring (e.g. one–
point, two–point, uniform crossover, etc). This operator implements
the inheritance property (offspring inherit genes of their parents).
5. Mutation operator creates random changes in genetic codes of the
offspring. This operator is needed to bring some random diversity
into the genetic code. In some cases GA cannot find the optimal
solution without mutation operator (local maximum problem).
 The GA Procedure
1. Initialize a population (of solution guesses)
2. Do (once for each generation)
a. Evaluate each chromosome (String) in the
population using a fitness function
b. Apply GA operators to population to create a
new population
3. Finish when solution is reached or number of
generations has reached an allowable
maximum.
 The genetic algorithm
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

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))
 The genetic algorithm
Basic elements of GAs
Most GAs methods are based on the following elements,
populations of chromosomes, selection according to fitness,
crossover to produce new offspring, and random mutation of new
offspring .
Chromosomes
The chromosomes in GAs represent the space of candidate
solutions. Possible chromosomes encodings are binary,
permutation, value, and tree encodings. For the Knapsack
problem, we use binary encoding, where every chromosome is a
string of bits, 0 or 1.
Fitness function
GAs require a fitness function which allocates a score to each
chromosome in the current population. Thus, it can calculate how
well the solutions are coded and how well they solve the problem.
 The genetic algorithm
Selection
The selection process is based on fitness. Chromosomes
that are evaluated with higher values (fitter) will most
likely be selected to reproduce, whereas, those with low
values will be discarded. The fittest chromosomes may
be selected several times, however, the number of
chromosomes selected to reproduce is equal to the
population size, therefore, keeping the size constant for
every generation. This phase has an element of
randomness just like the survival of organisms in nature.
The most used selection methods, are roulette-wheel,
rank selection, steady-state selection, and some others.
 The genetic algorithm
Crossover
Crossover is the process of combining the bits of one chromosome with those
of another. This is to create an offspring for the next generation that inherits
traits of both parents.
Crossover randomly chooses a locus and exchanges the subsequences before
and after that locus between two chromosomes to create two offspring [2]. For
example, consider the following parents and a crossover point at position 3:

Parent-1 100|0111 Offspring-1 1001000

Parent-2 111|1000 Offspring-2 1110111

In this example, Offspring 1 inherits bits in position 1, 2, and 3 from the left side
of the crossover point from Parent 1 and the rest from the right side of the
crossover point from Parent 2. Similarly, Offspring 2 inherits bits in position 1, 2,
and 3 from the left side of Parent 2 and the rest from the right side of Parent 1.
Crossover could be one- point, two-point and Uniform crossover.
 The genetic algorithm
Mutation
Mutation is performed after crossover to prevent falling
all solutions in the population into a local optimum of
solved problem. Mutation changes the new offspring by
flipping bits from 1 to 0 or from 0 to 1. Mutation can
occur at each bit position in the string with some
probability, usually very small (e.g. 0.001). For example,
consider the following chromosome with mutation point
at position 2:
Not mutated chromosome: 1 0 0 0 1 1 1
Mutated: 1 1 0 0 1 1 1 The 0 at position 2 flips to 1 after
mutation.
 Genetic Algorithms
• What two requirements should a problem satisfy
in order to be suitable for
solving it by a GA?
Answer: GA can only be applied to problems that
satisfy the following requirements:

• The fitness function can be well–defined.

• Solutions should be decomposable into steps
(building blocks) which could be then encoded as
chromosomes.
 Genetic algorithm example

The genetic algorithm, illustrated for digit strings representing

8-queens states.
The initial population of four 8-digits string represent 8-queen
states
 Genetic algorithm example
In (b): States in (a) are ranked by the fitness function(FF) (FF: no
of non attacking queens, for a solution (a). The states with the
best values: 24, 23, 20, 11 are chosen. Probability of being
chosen is directly proportional to Fitness Score.
In (c) two pairs are selected at random from (b). One is selected
twice and one is not selected at all.
Each pair to be mated, a crossover point is chosen at random
from position in the string.
In (d): They produce offspring. This state may be far away from
either parent if parent states are quite different. If population is
diverse to start with. So crossover process takes large steps (like
SA) early and smaller steps when population is quite similar.
In (e) Random Mutation one digit was mutated in 1st, 3rd and 4th
offspring.
The genetic algorithm with the 8-queens problem

The 8-queens states corresponding to the first two parents

in previous fig. (c) and the first offspring in Fig. (d). The
shaded columns are lost in the crossover step and the un-
shaded columns are retained.
 Crossover
• Select two parents
• Select cross site
• Cut and splice pieces of one parent to those of
the other

11111 11000
00000 00111
 Mutation
• With small probability, randomly alter 1 bit
• Minor operator
• An insurance policy against lost bits
• Pushes out of local minima
Population: Goal: 0 1 1 1 1 1

110000 Mutation needed to find the goal

101000
100100
010000
 GA as Search
• Genetic algorithms are local heuristic search algorithms.

• Especially good for problems that have large and poorly

understood search spaces.

• Genetic algorithms use a randomized parallel beam

search to explore the state space.

• You must be able to define a good fitness function, and of

course, a good state representation.
 Solved Example of GA as Search
Suppose a genetic algorithm uses chromosomes of the form
x = abcdefgh
• with a fixed length of eight genes. Each gene can be any
digit between 0
• and 9. Let the fitness of individual x be calculated as:
f(x) = (a + b) − (c + d) + (e + f) − (g + h)
and let the initial population consist of four individuals with
the following
chromosomes:
x1 = 6 5 4 1 3 5 3 2 x2 = 8 7 1 2 6 6 0 1
x3 = 2 3 9 2 1 2 8 5 x4 = 4 1 8 5 2 0 9 4
 Solved Example of GA as Search
i) Evaluate the fitness of each individual, showing all your
workings, and arrange them in order with the fittest first
and the least fit last.
Answer:
f(x1) = (6 + 5) - (4 + 1) + (3 + 5) - (3 + 2) = 9
f(x2) = (8 + 7) - (1 + 2) + (6 + 6) - (0 + 1) = 23
f(x3) = (2 + 3) - (9 + 2) + (1 + 2) - (8 + 5) = -16
f(x4) = (4 + 1) - (8 + 5) + (2 + 0) - (9 + 4) = -19

The order is x2, x1, x3 and x4.

The average fitness = 9 + 23 – (16 + 19) = -3 /4 = -0.75
 Solved Example of GA as Search
Perform the following crossover operations:
ii) Cross the fittest two individuals using one-point crossover
at the middle point.
Answer: One–point crossover on x2 and x1:

iii) Cross the second and third fittest individuals using a

two–point crossover (points b and f).
Answer: Two–point crossover on x1 and x3
 Solved Example of GA as Search
iv) Cross the first and third fittest individuals (ranked 1st and
3rd) using a uniform crossover.

Answer: In the simplest case uniform crossover means just

a random exchange of genes between two parents. For
example, we may swap genes at positions a, d and f of
parents x2 and x3:
 Solved Example of GA as Search
v) Suppose the new population consists of the six offspring
individuals received by the crossover operations in the
above question. Evaluate the fitness of the new population,
showing all your workings. Has the overall fitness
improved?

Answer: The new population is:

O1 = 8 7 1 2 3 5 3 2 O4 = 2 3 4 1 3 5 8 5
O2 = 6 5 4 1 6 6 0 1 O5 = 2 7 1 2 6 2 0 1
O3 = 6 5 9 2 1 2 3 2 O6 = 8 3 9 2 1 6 8 5
 Solved Example of GA as Search
Now apply the fitness function
f(x) = (a+b)−(c+d)+(e+f)−(g+h):
f(O1) = (8 + 7) − (1 + 2) + (3 + 5) − (3 + 2) = 15
f(O2) = (6 + 5) − (4 + 1) + (6 + 6) − (0 + 1) = 17
f(O3) = (6 + 5) − (9 + 2) + (1 + 2) − (3 + 2) = −2
f(O4) = (2 + 3) − (4 + 1) + (3 + 5) − (8 + 5) = −5
f(O5) = (2 + 7) − (1 + 2) + (6 + 2) − (0 + 1) = 13
f(O6) = (8 + 3) − (9 + 2) + (1 + 6) − (8 + 5) = −6
Average Fittness = 15+17 – (2+5) +13 -6 = + 5.33
The overall fitness has improved.
 Solved Example of GA as Search
vi) By looking at the fitness function and considering that
genes can only be digits between 0 and 9 find the
chromosome representing the optimal solution (i.e. with
the maximum fitness). Find the value of the maximum
fitness.
Answer: The optimal solution should have a chromosome
that gives the maximum of the fitness function
max f(x) = max *(a + b) − (c + d) + (e + f) − (g + h)]
Because genes can only be digits from 0 to 9, the optimal
solution should be:
xoptimal = 9 9 0 0 9 9 0 0 , and the maximum fitness is
f(xoptimal) = (9 + 9) − (0 + 0) + (9 + 9) − (0 + 0) = 36
 Solved Example of GA as Search
vii) By looking at the initial population of the algorithm can you say whether
it will be able to reach the optimal solution without the mutation operator?
Answer: No, the algorithm will never reach the optimal solution without
mutation. The optimal solution is xoptimal = 9 9 0 0 9 9 0 0. If mutation does
not occur, then the only way to change genes is by applying the crossover
operator. Regardless of the way crossover is performed, its only outcome is
an exchange of genes of parents at certain positions in the chromosome.
This means that the first gene in the chromosomes of children can only be
either 6, 8, 2 or 4 (i.e. first genes of x1, x2, x3 and x4), and because none of
the individuals in the initial population begins with gene 9, the crossover
operator alone will never be able to produce an offspring with gene 9 in the
beginning.
One can easily check that a similar problem is present at several other
positions. Thus, without mutation, this GA will not be able to reach the
optimal solution.
 Issues
• How to select original population?
• How to handle non-binary solution types?
• What should be the size of the population?
• What is the optimal mutation rate?
• How are mates picked for crossover?
• Can any chromosome appear more than once in a
population?
• When should the GA halt?
• Local minima?
• Parallel algorithms?
 Genetic Algorithms
Cost

States

93
Genetic Algorithms
Mutation

Cross-Over

94
Genetic Algorithms

95
Genetic Algorithms

96
Genetic Algorithms

97
Genetic Algorithms

98
Genetic Algorithms

99
Genetic Algorithms

100
Genetic Algorithms

101
Genetic Algorithms

102
Genetic Algorithms

103
Genetic Algorithms

104
Genetic Algorithms

105
Genetic Algorithms

106
Genetic Algorithms

107
Genetic Algorithms

108
Genetic Algorithms

109
Genetic Algorithms

110
Genetic Algorithms

111
 Summary
Hill climbing is a steady monotonous ascent to
better nodes.
Simulated annealing, local beam search, and genetic
algorithms are “random” searches with a bias towards
better nodes.
All needed very little space which is defined by the
population size.
None guarantees to find the globally optimal
solution.