Artificial Intelligence

Dr. Sanga Chaki

Assistant Professor
Department of Computer Science and Engineering
Indian Institute of Information Technology Pune
Problem Solving by Searching – IV
Local Search Algorithms and
Optimization Problems
Contents
1. Global Search in AI
2. Concept of Local Search
3. Simple Hill climbing
4. Advantages/ Disadvantages
Global Search in AI
1. The entire state space of the problem is explored to find
solution – which is a path to the goal node
2. This requires storage of relevant information for us to
backtrack – if necessary (imagine BFS, DFS, A* etc)
3. Computational Cost: Typically, more computationally
expensive due to the wider exploration of the solution
space.
4. Higher Likelihood of Global Optimum: More likely to escape
local optima and find the global optimum, especially in
complex or high-dimensional search spaces.
5. Preferred when finding the true global optimum is critical,
especially in problems with many local optima or complex
landscapes.
Global Search in AI
1. Global searches are more appropriate when the environments are
observable, deterministic, known environments where the solution is a
sequence of actions.
2. What happens when these assumptions are relaxed?
3. What if we are interested only in the solution state and not how we reach
it? – we use local search algorithms
Global Search vs Local Search
1. The search algorithms that we have seen so far are designed to explore
search spaces systematically.
2. This systematicity is achieved by keeping one or more paths in memory
3. And by recording which alternatives have been explored at each point
along the path.
4. When a goal is found, the path to that goal also constitutes a solution to
the problem.
5. But, in many problems, the path to the goal is irrelevant.
6. For example, in the 8-queens problem, what matters is the final
configuration of queens, not the order in which they are added.
7. This applies to many other problems as well.
Global Search vs Local Search
1. If the path to the goal does not matter, we might consider a class of
algorithms that do not worry about paths at all.
2. Local search algorithms operate using a single current node (rather than
multiple paths) and generally move only to neighbors of that node.
3. Typically, the paths followed by the search are not retained.
4. Although local search algorithms are not systematic, they have two key
advantages:
a) they use very little memory—usually a constant amount
b) they can often find reasonable solutions in large or infinite (continuous)
state spaces for which systematic algorithms are unsuitable.
Local Search & Optimization
1. Local search algorithms are useful for two purposes:
a) finding goal states (as is done by other search algorithms)
b) solving optimization problems: in which the aim is to find the best state
according to an objective function.
2. What is an optimization problem?
3. What is an objective function?
4. Example: Gradient Descent Optimization is a local search technique
Optimization Problem & Objective Function
1. In mathematics, engineering, computer science and economics, an
optimization problem is the problem of finding the best solution (for a given
problem) from all feasible solutions.
2. The selection of a best element, with regard to some criteria, from some set of
available alternatives
3. General approach: an optimization problem consists of
• Maximizing a function or Minimizing a function
• By systematically choosing input values from within an allowed set and computing the
value of the function.
4. An Objective Function in AI, also known as a loss function or cost function of a
model, is a function that the model aims to minimize or maximize.
5. Whichever input satisfies the optimization, is the result of the optimization
problem.
Local Search & Optimization
Maximum possible value
1. To understand local search, we of this objective function
consider the state-space landscape
2. A landscape has
• location - defined by the state and
• elevation – defined by the value of
the cost function or objective
function.
3. If elevation corresponds to cost,
then the aim is to find the lowest
valley—a global minimum – for cost
function
4. If elevation corresponds to
profit/gain, then the aim is to find
the highest peak—a global
maximum – for objective function State at which objective
function is maximized
Local Search & Optimization
Local Search & Optimization
1. Local search algorithms explore this
landscape.
2. A complete local search algorithm
always finds a goal
(minimum/maximum), if one exists;
3. An optimal local search algorithm
always finds the global
minimum/maximum.
Local Search Summary
1. Explores the immediate vicinity (neighborhood) of the current solution.
2. It iteratively moves from the current state to a "better" neighboring state
based on an objective function.
3. Computational Efficiency: Generally, faster per iteration as it only considers
a limited set of nearby options.
4. Risk of Local Optima: Prone to getting stuck in local optima, which are
solutions that are optimal within their neighborhood but not necessarily
the overall best solution in the entire search space.
5. Effective for problems with well-defined neighborhoods and when finding a
near-optimal solution quickly is sufficient.
Simple Hill-Climbing Search
Simple Hill-climbing search
1. Three important points:
a) Local search – no information about
global problem – paths not retained
b) Greedy approach – it goes on till it is
able to find best next move.
Otherwise, it will stop
c) No backtrack
2. It is an algorithm that continually
moves in the direction of increasing
value or decreasing cost
3. It terminates when it reaches a
“peak” (in the state-space landscape)
where no neighbor has a higher
value or lower cost
Simple Hill-climbing search
1. The algorithm does not maintain a
search tree
2. The data structure for the current
node only records the state and the
value of the objective function.
3. Simple Hill climbing does not look
ahead beyond the immediate
neighbors of the current state.
Simple Hill-climbing search
Simple Hill-climbing search – Example 1
1. Start at A, find the best (least
heuristic) node next = B
2. At B, find the best (least
heuristic) node next = G
3. At G, find the best (least
heuristic) node next = J
4. Path = A-B-G-J
Simple Hill-climbing search – Example 1
1. What is the issue here?
2. Path = A-B-G-J → Length = 3
3. If we consider path length as a
measure of optimality, this is a
locally optimal solution
4. The globally optimal solution
would be A-D-L → Length = 2
5. Note: No backtracking is
possible
Simple Hill-climbing search – Example 2
1. Start at A, find the best (least heuristic)
node next = F
2. At F, find the best (least heuristic) node
next = G
3. No more nodes to explore – stop –
algo fails to return path to goal state
4. If we had started from B, find the best
(least heuristic) node next = C
5. At C, find the best (least heuristic)
node next = H – At least a path to a
goal is achieved
Simple Hill-climbing search – Example 3
1. What is the
problem here?
Simple Hill-climbing search – Example 4
1 2 4 1 4 7

5 7 5 2 5 8 Goal
3 6 8 3 6

1 2 4 1 2 4 1 2 4 1 4
5 7 4 5 7 5 5 6 7 6 5 2 7
3 6 8 3 6 8 3 8 3 6 8

2 4 1 2 4
5 1 5 7 3 5 7 5 Algo is stuck here because 5>4
3 6 8 6 8 → No better neighbour state
Simple Hill-climbing search - Issues
Hill climbing often gets stuck for the
following reasons
1. Local maxima:
• A local maximum is a peak that is
higher than each of its neighboring
states but lower than the global
maximum.
• Hill-climbing algorithms that reach
the vicinity of a local maximum will
be drawn upward toward the peak
but will then be stuck with nowhere
else to go
Simple Hill-climbing search - Issues
2. Ridges:
• Ridges result in a sequence of local maxima
that is very difficult for greedy algorithms to
navigate.
• 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.
Simple Hill-climbing search - Issues
Hill climbing often gets stuck for the following
reasons
3. Plateau:
• A plateau is a flat area of the state-space
landscape. It can be a flat local maximum,
from which no uphill exit exists, or a
shoulder, from which progress is possible.
• A hill-climbing search might get lost on the
plateau – suboptimal solution returned.

In each case, the algorithm reaches a point at

which no progress is being made.
Simple Hill-climbing search - Issues
1. Many variants possible:
a) Stochastic hill climbing - chooses a random better state from all better
states in the neighbors
b) Random-restart hill climbing – If stuck in a local maxima, restart the algo
from a random starting point – better chance getting to global maximum
2. Some other options of local search algorithms are:
a) Simulated Annealing
b) Local beam search
c) Genetic algorithms
3. What do you think are some differences between Simple Hill-climbing search
and Greedy best first search?
Thank You