8-Puzzle Heuristics

• h1(N) = number of misplaced tiles = 6 is

5 8 1 2 3
admissible ??
4 2 1 4 5 6

7 3 6 7 8

STATE(N) Goal state

1
Artificial Intelligence (CS-2002)

Chapter 4: Local Search Algorithm and

Optimization
Objectives of the Chapter
• Local Search: Hill Climbing
• Escaping Local Maxima: Local Beam Search
• Genetic Algorithm
Local Search
• Use single current state and move to the neighboring state.
• Idea: Start with an initial guess at a solution and incrementally
improve it until it is one.
Local Search: Path Irrelevant

Search Problem
• integrated-circuit design
• factory-floor layout Informed Uninformed
• job-shop scheduling
• automatic programming
• telecommunications
A* Greedy Cheapest
BFS DFS
Search First FS
• network optimization
• vehicle routing Depth
• portfolio management Limited

Iterative
Deepening
Path Irrelevant:
Local Search , CSP Path Relevant:
Local Search
• Local search algorithms operate using a single current node rather
than multiple paths

• Move only to neighbors of that node.

• The paths followed by the search are not retained.

Local Search Advantages
• they use very little memory — usually a constant amount;

• they can often find reasonable solutions in large or infinite

(continuous) state spaces for which systematic algorithms are
unsuitable.
Visualizing Local Search
Hill Climbing Algorithm
(Local Search, Greedy Approach, No backtrack)
• In this algorithm, we don't need to maintain and handle the search tree
or graph as it only keeps a single current state
• Hill climbing algorithm continuously moves in the direction of increasing
elevation/value to find the peak or best solution to the problem.
• It terminates when it reaches a peak value where no neighbor has a
higher value.
• It is also called greedy local search as it only looks to its good immediate
neighbor state and not beyond that.
Algorithm
• Step 1: Evaluate the initial state, if it is goal state then return success
and Stop.
• Step 2: Loop Until a solution is found or there is no new operator left
to apply.
• Step 3: Select and apply an operator to the current state.
• Step 4: Check new state:
• If it is goal state, then return success and quit.
• Else if it is better than the current state then assign new state as a current
state.
• Else if not better than the current state, then return to step2.
• Step 5: Exit.
Example
1 2 4 1 4 7
5 5 7 Stat 2 5 8
e goal
3 6 8 3 6

5 6
4 5

5 5
Example
• Tic-Tac-Toe

Maximum number of winning lines

Problems in Hill
Climbing Global maximum

• 1. Local Maximum: A local

maximum is a peak state
in the landscape which is
better than each of its
neighboring states, but
there is another state also
present which is higher
than the local maximum.
Problems in Hill Climbing….

2 Plateau: A plateau is
the flat area of the
search space in which
all the neighbor states
of the current state
contains the same
value, because of this
algorithm does not find
any best direction to
move. A hill-climbing
search might be lost in
the plateau area.
Problems in Hill Climbing…
3. Ridges: A ridge is a
special form of the local
maximum. It has an area
which is higher than its
surrounding areas, but
itself has a slope, and
cannot be reached in a
single move.
Local Beam Search
• Start with k randomly generated states (ß= 2 or 3)
• At each iteration, all the successors of all k states are generated
• If any one is a goal state, stop; else select the k best successors from
the complete list and successors from the complete list and repeat

Greedy Local Local Beam

Simulated Annealing
• Conceptually SA exploits an Analogy between Annealing and the
Search for a minimum in a more general system
• Explore Successors wildly randomly: High temp
• As time goes by , explore less wildly: Cool Down
• Until there’s a time when things settle: Cold
Genetic Algorithm
Genetic Algorithm
• Twist on Local Search: successor is generated by combining two
parent states
• A state is represented as a string over a finite alphabet (e.g. binary)
• 8-queens
• State = position of 8 queens each in a column

20
Evolution

• Evolution is change in the heritable

characteristics of biological populations
over successive generations.

• Evolutionary processes give rise to

biodiversity at every level of biological
organization, including the levels of
species, individual organisms, and
molecules.

[Link]
Evolution for Problem Solving

• Evolution, in itself, is a mechanism of

incremental search, whereby more fit
solutions to problems propagate to future
generations, and less fit solutions gradually
fade away.

• This process of natural selection provides a

wonderful vehicle for finding solutions to
difficult multivariate optimization problems.
Salient Features
• Evolutionary Algorithms fall into the category of “generate and test” algorithms
• They are stochastic, population-based algorithms
• Variation operators (recombination and mutation) create the necessary diversity and
thereby facilitate novelty

• Selection reduces diversity and acts as a force pushing quality

Typical GA
• Step 1: Initialize the population randomly or with potentially good solutions.
• Step 2: Compute the fitness of each individual in the population.
• Step 3: Select parents using a selection procedure.
• Step 4: Create offspring by crossover and mutation operators.
• Step 5: Compute the fitness of the new offspring.
• Step 6: Select members of population to die using a selection procedure.
• Step 7: Go to Step 2 until termination criteria are met.
Genetic Algorithm
• START
• Generate the initial population
• Compute fitness
• REPEAT
Selection
Crossover
Mutation
Compute fitness
• UNTIL population has converged
• STOP
Nature of Computer Mapping
Computational Model
Encoding
Crossover
Crossover
Crossover
Crossover
Genetic Algorithm
• Fitness function= Pair of non-attacking queens
• That way higher scores are better

23 fitness 24748552 string

Fitness function

Probability= 24+23+20+11= 78
Probability

24/78= 0.307 Normalize 0.307× 100 =

30.7%
chance of being chosen probably
Reproduction
Crossover
Mutation
Knapsack Problem
• Let’s say, you are going to spend a month in the wilderness. Only thing
you are carrying is the backpack which can hold a maximum weight of 30
kg. Now you have different survival items, each having its own “Survival
Points” (which are given for each item in the table). So, your objective is
maximize the survival points.
• Here is the table giving details about each item.
• Choose an initial population of four. Then choose best three
subsequently (Encoding hint: 1 if item is chosen 0 otherwise)
• Decide crossover point.
• Chance of mutation = 50 items in 100 generations.
• Step by step solution ahead
You can do the
third iteration on
your own now.
First two iterations
have been done by
me.
Properties