1
Introduction to
AI and ML
Instructors:
Dr. Nishant Gupta & Dr. Manoj Kumar
Local Search 2
Difference in problem Formulation
Past Discussions: path to a goal is solution to
problem
A State/node was some partial information
systematic exploration of search space (DFS,
BFS, etc.)
Now, not the path but a state is solution
to problem
Search is in solution space
For some problems path is irrelevant. –
E.g., 8-queens
Different algorithms can be used
Local Search
Local Search 3
Satisfaction – Find me a path to Goal
Goal Satisfaction (Optimal or not)
Reach the goal node
Constraint satisfaction
What is optimization problem?
Optimization
optimize(objective function) Constraint Optimization
Transformation of problems from Satisfaction to the Optimization
problem and Back Forth - Modelling
Local Search and Optimization 4
Local search
Keep track of single current state
Move only to neighboring states
Ignore paths
Advantages: –
Use very little memory
Can often find reasonable solutions in large or infinite (continuous) state
spaces
“Pure optimization” problems –
All states have an objective function
Goal is to find state with max (or min) objective value
Does not quite fit into path-cost/goal-state formulation
Local search can do quite well on these problems.
Example: N Queens 5
Put n queens on an n x n board with no two queens on the same
row, column, or diagonal
Is this a satisfaction or optimization problem?
Hill Climbing Search: 8 Queens 6
Need to convert to an optimization problem
Optimization: N Queens 7
Appropriate objective function?
Maximum number of pairs that can attack each
other?
Minimum number of pairs that can attack each
other?
Do we need maximization or minimization
problem?
h (Objective function) = number of pairs of
queens that are attacking each other
h = 17 for the above state
Search Space 8
State
All 8 queens on the board in some configuration
How many states or solutions?
Local search – we search among the solution space
Successor function/ Neighborhood function – We have to define
move a single queen to another square in the same column
Many others
Example of a objective function h(n): –
the number of pairs of queens that are attacking each other
(so we want to minimize this)
Now we have converted the N Queens problems into a local search formulation
Hill climbing search: 8 Queens 9
Is this a solution?
What is h?
Trivial Algorithms 10
Random Sampling
Generate a state randomly
Random Walk
Randomly pick a neighbor of the current state
Both algorithms asymptotically complete.
Hill-climbing (Greedy Local Search) 11
max version
Hill-climbing search 12
“a loop that continuously moves towards increasing value”
terminates when a peak is reached
Aka greedy local search
Value can be either
Objective function value
Heuristic function value (minimized)
Hill climbing does not look ahead of the immediate neighbors
Can randomly choose among the set of best successors
if multiple have the best value
Landscape of search 13
Hill Climbing gets stuck in local minima depending on?
Hill-climbing on 8-queens 14
Randomly generated 8-queens starting states
14% the time it solves the problem
86% of the time it get stuck at a local minimum
However
Takes only 4 steps on average when it succeeds
And 3 on average when it gets stuck
(for a state space with 8^8 =~17 million states)
Hill Climbing Drawbacks 15
Local Minima
Plateau
Diagonal Ridges
Escaping Shoulders: Sideways Move 16
If no downhill (uphill) moves, allow sideways moves in
hope that algorithm can escape
Need to place a limit on the possible number of sideways
moves to avoid infinite loops
For 8-queens
Now allow sideways moves with a limit of 100
Raises percentage of problem instances solved from 14 to
94%
However….
21 steps for every successful solution
64 for each failure
Problem?
Tabu Search 17
prevent returning quickly to the same state
Keep fixed length queue (“tabu list”)
add most recent state to queue; drop oldest
Never make the step that is currently tabu’ed
Properties: –
As the size of the tabu list grows, hill-climbing will asymptotically
become “non-redundant” (won’t look at the same state twice)
In practice, a reasonable sized tabu list (say 100 or so) improves
the performance of hill climbing in many problems
Escaping Shoulders/local Optima 18
Enforced Hill Climbing
Perform breadth first search from a local optima
to find the next state with better h function
Typically,
prolonged periods of exhaustive search
bridged by relatively quick periods of hill-climbing
Middle ground b/w local and systematic search
Hill Climbing: Stochastic Variations 19
Stochastic hill-climbing :
Random selection among the uphill moves.
The selection probability can vary with the steepness of the uphill
move.
To avoid getting stuck in local minima
Random-walk hill-climbing
Random-restart hill-climbing
Hill-climbing with both
Hill Climbing with random walk 20
When the state-space landscape has local minima, any search that
moves only in the greedy direction cannot be complete
Random walk, on the other hand, is asymptotically complete
Idea: Put random walk into greedy hill-climbing
At each step do one of the two
Greedy: With prob p move to the neighbor with largest value
Random: With prob 1-p move to a random neighbor
Hill Climbing with random restarts 21
If at first you don’t succeed, try, try again!
Different variations
For each restart: run until termination vs. run for a fixed time
Run a fixed number of restarts or run indefinitely
If you want to pick one local search algorithm, learn this
one!!
Hill Climbing with Both 22
At each step do one of the three
Greedy: move to the neighbor with largest value
Random Walk: move to a random neighbor
Random Restart: Resample a new current state
Simulated Annealing 23
Simulated Annealing = physics inspired twist on random walk
Basic ideas:
like hill-climbing identify the quality of the local improvements
instead of picking the best move, pick one randomly
say the change in objective function is delta (d)
if d is positive, then move to that state
otherwise:
move to this state with probability proportional to d
thus: worse moves (very large negative d) are executed less often
over time, make it less likely to accept locally bad moves
Simulated Annealing 24
Temperature T 25
High T: probability of “locally bad” move is higher
Low T: probability of “locally bad” move is lower
Typically, T is decreased as the algorithm runs longer
i.e., there is a “temperature schedule”
Local Beam Search 26
Idea: Keeping only one node in memory is an extreme reaction to memory
problems.
Keep track of k states instead of one
Initially: k randomly selected states
Next: determine all successors of k states
If any of successors is goal finished
Else select k best from successors and repeat
Problem: quite often, all k states end up on same local hill
Genetic Algorithms 27
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) – String
representation
8-queens - State = position of 8 queens each in a column – String represent the State
Start with k randomly generated states (population)
Evaluation function (fitness function):
Higher values for better states.
e.g., # non-attacking pairs in 8-queens
Produce the next generation of states by “simulated evolution”
Random selection
Crossover
Random mutation
Genetic Algorithms 28
Has the effect of “jumping” to a completely different new part of the search
space (quite non-local)
Genetic Algorithms 29
Positive Points
Random exploration can find solution that local search cannot (via
crossover)
Negative Points
Large number of tunable parameters
Useful on some set of problems but there is no proof that GA is better
than hill climbing with random restarts
Definition of AI 30
Up until now
“AI is Search”
Definition of AI 31
Up until now
“AI is Search”
“AI is Representation”
Definition of AI 32
Up until now
“AI is Search”
“AI is Representation”
Representation reduces the total search space
Constraint Satisfaction Problems (CSPs) 33
Standard search problem:
state is a “black box”—any old data structure
that supports goal test, eval, successor
CSP:
state is defined by variables X_i with values from domain D_i
goal test is a set of constraints specifying allowable combinations of values for
subsets of variables
Simple example of a formal representation language
Allows useful general-purpose algorithms with more power than standard
search algorithms
Constraint Satisfaction Problems (CSPs) 34
Constraint Satisfaction Problems (CSPs) 35
Constraint Graph 36
Binary CSP: each constraint relates at most two variables
Constraint graph: nodes are variables, arcs show constraints
Variety of Constraints 37
Real world CSPs 38
• Timetabling problems e.g., which class is offered when and
where?
• Hardware configuration
• Spreadsheets
• Transportation scheduling
• Factory scheduling
• Floor planning
Notice that many real-world problems involve real-valued variables
Backtracking Search 39
Backtracking Search 40
Backtracking Search 41
Improving Backtracking 42
Improving Backtracking 43
Improving Backtracking 44
This is variable order heuristic
Improving Backtracking 45
Forward Checking 46
Knowledge Representation 47
• represent knowledge about the world in a manner that facilitates
inferencing (i.e. drawing conclusions) from knowledge.
• Example: Arithmetic logic – x >= 5
• In AI: typically based on
• Logic – medium of conversation with the AI system
• Probability
• Logic and Probability
Knowledge Representation 48
• Basic idea of Logic – From true assumptions deduce true conclusions
KR Languages 49
• Propositional Logic
• Predicate Calculus
• Frame Systems
• Rules with Certainty Factors
• Bayesian Belief Networks
• Influence Diagrams
• Ontologies
• Semantic Networks
• Concept Description Languages
• Non-monotonic Logic