Chapter 2: Problem Solving
● Uninformed search techniques
Contents ●
●
Informed search techniques
Local search Algorithm and
optimization
● Adversarial search techniques
Local Search
In many optimization problems, we care only about the final state, not the path to
get there.
Then state space is the set of “complete” configurations, and our goal is to find
optimal configurations.
For example, in the 8-queens problem, our goal is to find a valid final configuration of
8 queens satisfying all the constraints.
In such cases, local search algorithms can be applied, which search from a start state
to neighboring states, without keeping track of the paths, nor the set of states that
have been reached.
Example: N-Queens Problem
Put n queens on an n × n board with no two queens on the same row, column, or
diagonal
Move a queen to reduce number of conflicts
Local Search and Optimization Problems
In optimization problems, the aim is to find the best state according to an objective
function.
Local Search and Optimization Problems
Each point in this state-space landscape has an “elevation” defined by the value of
the objective function.
If elevation corresponds to an objective function, then the aim is to find the highest
peak (a global maximum).
This process is called hill climbing.
If elevation corresponds to cost, then the aim
is to find the lowest valley (a global minimum).
This process is called gradient descent.
Hill-Climbing Search
“Like climbing Everest in thick fog with amnesia”
Idea: Keep track of one current state and on each iteration move to the neighboring state
with the highest value; Terminate when no neighbor has a higher value (“peak”).
Example: 8-Queens Problem
Complete-state formulation (every state has all the components of a solution, but
they might not all be in the right place) for 8-Queens problem:
Every state has 8 queens on the board, one per column.
An example of a state:
Example: 8-Queens Problem
The initial state is chosen at random.
The successors of a state are all possible states generated by moving a queen to
another square in the same column. How many successors does each state have?
Heuristic cost function h is the number of pairs of queens that are attacking each
other.
Example: 8-Queens Problem
Hill-Climbing Search
It is also called greedy local search because it grabs a good neighbor state without
thinking ahead about where to go next.
It is mostly used when a good heuristic is available.
We don't need to maintain and handle the search tree or graph as it only keeps a
single current state.
Problems in Hill Climbing
Local Maxima: A local maximum is a peak that is higher than each of its
neighboring states but lower than the global maximum.
Example:
In this state, every move of a single queen
makes the situation worse. Therefore this
state is a local maximum.
One possible solution:
Random-restart hill climbing
Problems in Hill Climbing
Plateaus: 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.
One possible solution:
Keep going when we reach a plateau.
Problems in Hill Climbing
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.
Possible solution:
Bidirectional search or
by moving in different directions
Variants of Hill Climbing
Stochastic hill climbing:
Choose at random from among the uphill moves; the probability of selection can vary
with the steepness of the uphill move.
First-choice hill climbing:
It is an implementation of stochastic hill climbing, by generating successors
randomly until one is generated that is better than the current state.
Random-restart hill climbing:
Conduct a series of hill-climbing searches from randomly generated initial states,
until a goal is found.
Simulated Annealing
This algorithm combines hill climbing with a random walk.
Idea: escape local maxima by allowing some “bad” moves but gradually decrease
their size and frequency
In metallurgy, annealing is the process used to temper or harden metals and glass by
heating them to a high temperature and then gradually cooling them.
Simulated Annealing
Note: Here we consider gradient descent
Local Beam Search
Idea: Keep track of best n nodes.
In hill-climbing, we keep track of only one node, i.e. n = 1, whereas in best first
search, n = ∞, i.e. we keep track of all successors.
● Local Beam Search starts with k randomly generated states.
● At each step, all the successors of all k states are generated.
● If any one is a goal, the algorithm halts. Otherwise, it selects the k best
successors from the complete list and repeats.
Variant: Stochastic beam search chooses successors with probability proportional to
the successor’s value.
Evolutionary Algorithms
Evolutionary algorithms are motivated by the metaphor of natural selection (in
biology).
They are variants of stochastic beam search.
Idea: From a population of states (individuals), the states with the highest value
(fittest ones) produce successor states (offspring) that populate the next generation.
Evolutionary Algorithms
Parameters:
● Population size
● Representation of each individual (state). In genetic algorithms, each individual is a
string over a finite alphabet, just as DNA is a string over the alphabet ACGT.
● The number of parents that come together to form offspring (the mixing number)
● Selection process for selecting the individuals who will become the parents of the next
generation; e.g. select based on their fitness score, select randomly..
● The recombination procedure
● The mutation rate
● The makeup of the the next generation; e.g., elitism, culling
Genetic Algorithms
A genetic algorithm (or GA) is a variant of stochastic beam search in which
successor states are generated by combining two parent states rather than by
modifying a single state.
Like beam searches, GAs begin with a set of k randomly generated states, called the
population. Each state, or individual, is represented as a string over a finite
alphabet—most commonly, a string of 0s and 1s.
Genetic Algorithm Example: 8-Queens Problem
Genetic Algorithm Example: 8-Queens Problem
Genetic Algorithm Example: 8-Queens Problem
Genetic Algorithm Example: 8-Queens Problem
Genetic Algorithm Example: 8-Queens Problem