Artificial Intelligence

Search
 Search
• Search permeates all of AI
• What choices are we searching through?
– Problem solving
Action combinations (move 1, then move 3, then move 2...)
– Natural language
Ways to map words to parts of speech
– Computer vision
Ways to map features to object model
– Machine learning
Possible concepts that fit examples seen so far
– Motion planning
Sequence of moves to reach goal destination
• An intelligent agent is trying to find a set or sequence of actions to
achieve a goal.
• This is a goal-based agent
Problem-solving Agent
 Assumptions
• Static or dynamic?

Environment is static
 Assumptions
• Static or dynamic?
• Fully or partially observable?

Environment is fully observable

 Assumptions
• Static or dynamic?
• Fully or partially observable?
• Discrete or continuous?

Environment is discrete
 Assumptions
• Static or dynamic?
• Fully or partially observable?
• Discrete or continuous?
• Deterministic or stochastic?

Environment is deterministic
 Assumptions
• Static or dynamic?
• Fully or partially observable?
• Discrete or continuous?
• Deterministic or stochastic?
• Episodic or sequential?
Environment is sequential
 Assumptions
• Static or dynamic?
• Fully or partially observable?
• Discrete or continuous?
• Deterministic or stochastic?
• Episodic or sequential?
• Single agent or multiple agent?
 Assumptions
• Static or dynamic?
• Fully or partially observable?
• Discrete or continuous?
• Deterministic or stochastic?
• Episodic or sequential?
• Single agent or multiple agent?
Search Example
Formulate goal: Be in
Bucharest.

Formulate problem:
states are cities, operators
drive between pairs of
cities

Find solution: Find a

sequence of cities (e.g.,
Arad, Sibiu, Fagaras,
Bucharest) that leads
from the current state to
a state meeting the goal
condition
 Search Space Definitions
• State
– A description of a possible state of the world
– Includes all features of the world that are pertinent to the
problem
• Initial state
– Description of all pertinent aspects of the state in which the
agent starts the search
• Goal test
– Conditions the agent is trying to meet
• Goal state
– Any state which meets the goal condition
• Action
– Function that maps (transitions) from one state to another
 Search Space Definitions
• Problem formulation
– Describe a general problem as a search problem
• Solution
– Sequence of actions that transitions the world from the initial state
to a goal state
• Solution cost (additive)
– Sum of the cost of operators
– Alternative: sum of distances, number of steps, etc.
• Search
– Process of looking for a solution
– Search algorithm takes problem as input and returns solution
– We are searching through a space of possible states
• Execution
– Process of executing sequence of actions (solution)
 Problem Formulation
A search problem is defined by the

1. Initial state (e.g., Arad)

2. A description of the possible actions available to
the agent ({Go(Sibiu), Go(Timisoara), Go(Zerind)}.
3. Transition model : RESULT(In(Arad),Go(Zerind)) =
In(Zerind) .
4. Goal test (e.g., at Bucharest)
5. Path cost (e.g., step cost)

S:{ S,A, ACTION(S),RESULT(S,A), COST(S,A)}

Example Problems – Eight Puzzle
States: tile locations

Initial state: one specific tile configuration

Operators: move blank tile left, right, up, or

down

Goal: tiles are numbered from one to eight

around the square

Path cost: cost of 1 per move (solution cost

same as number of most or path length)

Eight puzzle applet

Example Problems – Robot Assembly
States: real-valued coordinates of
• robot joint angles
• parts of the object to be assembled

Operators: rotation of joint angles

Goal test: complete assembly

Path cost: time to complete assembly

Example Problems – Towers of Hanoi
States: combinations of poles and disks

Operators: move disk x from pole y to pole z

subject to constraints
• cannot move disk on top of smaller disk
• cannot move disk if other disks on top

Goal test: disks from largest (at bottom) to

smallest on goal pole

Path cost: 1 per move

Towers of Hanoi applet

Example Problems – Rubik’s Cube
States: list of colors for each cell on each face

Initial state: one specific cube configuration

Operators: rotate row x or column y on face

z direction a

Goal: configuration has only one color on

each face

Path cost: 1 per move

Rubik’s cube applet

Example Problems – Eight Queens
States: locations of 8 queens on chess board

Initial state: one specific queens

configuration

Operators: move queen x to row y and

column z

Goal: no queen can attack another (cannot

be in same row, column, or diagonal)

Path cost: 1 per placing Queen

Eight queens applet

Example Problems –
Missionaries and Cannibals
States: number of missionaries, cannibals,
and boat on near river bank

Initial state: all objects on near river bank

Operators: move boat with x missionaries

and y cannibals to other side of river
• no more cannibals than missionaries on
either river bank or in boat
• boat holds at most m occupants

Goal: all objects on far river bank

Path cost: 1 per river crossing

Missionaries and cannibals applet

Example Problems –Water Jug
States: Contents of 4-gallon jug and 3-gallon
jug

Initial state: (0,0)

Operators:
• fill jug x from faucet
• pour contents of jug x in jug y until y full
• dump contents of jug x down drain

Goal: (2,n)

Path cost: 1 per fill

Saving the world, Part I

Saving the world, Part II

Sample Search Problems
• Graph coloring
• Protein folding
• Game playing
• Airline travel
• Proving algebraic equalities
• Robot motion planning
 Visualize Search Space as a Tree
• States are nodes
• Actions are edges
• Initial state is root
• Solution is path
from root to goal
node
• Edges sometimes
have associated
costs
• States resulting
from operator are
children.
Search Problem Example (as a tree)
 Search Strategies
• Search strategies differ only in QueuingFunction
• Features by which to compare search strategies
– Completeness (always find solution)
– Cost of search (time and space)
– Cost of solution, optimal solution
– Make use of knowledge of the domain
• “uninformed search” vs. “informed search”
 Uninformed Search vs. Informed Search
• Uninformed(blind) • Informed(Heuristic)
– Search without information. – Search with information.
– No Knowledge. – Use knowledge to find
– Time consuming. steps to solution
– Time&Space Complexity – Quick solution
is more – Time&Space Complexity is
less
– Eg: BFS,DFS
– Eg: A*, Heuristic DFS, Best
First Search.
 Search Function –
Uninformed Searches
Open = initial state // open list is all generated states
// that have not been “expanded”
While open not empty // one iteration of search algorithm
state = First(open) // current state is first state in open
Pop(open) // remove new current state from open
if Goal(state) // test current state for goal condition
return “succeed” // search is complete
// else expand the current state by
// generating children and
// reorder open list per search strategy
else open = QueueFunction(open, Expand(state))
Return “fail”
 Breadth-First Search
• Explore all the nodes at given depth before
proceeding to the next level
• Level-by-level search
• In tree, assume children are considered
left-to-right unless specified differently.
• Number of children is “branching factor” b
• Uses Queue to implement
 Breadth-First Search
Algorithm:
I. Enter staring nodes on Queue
II. If Queue is empty then return fail and stop
III. If first element on Queue is Goal then return
success and stop
Else
IV. Remove and expand the first element from Queue
and place its children at end of Queue.
V. Goto step II
BFS Example

Branch Factor = 2
 Analysis
• Assume goal node at level d with constant branching factor b

• Time complexity (measured in #nodes generated)

 b0 (1st level ) + b1 (2nd level) + b2 (3rd level) + … + bd (goal level)=O(bd+1)

• This assumes goal on far right of level

• Space complexity
 At most majority of nodes at level d + majority of nodes at level d+1 = O(bd+1)
 Exponential time and space

• Advantages
 Simple to implement
 Complete
 Finds solution[optimal solution]

• Disadvantages
 More Memory
 Analysis
• See what happens with b=10
– expand 1 Million nodes/second
– 1,000 bytes/node
Depth Nodes Time Memory
2 110 .11 mseconds 107Kilobytes
4 11,110 11 mseconds 106 megabytes
6 106 1.1 Seconds 10 gigabytes
8 108 2 Minutes 1 terabyte
10 1010 3 Hours 101 terabytes
12 1012 13 days 10 petabytes
16 1016 3,50 years 1 exabyte
 Depth-First Search
• Starts from root node and follows each path to its
greatest depth node before moving to the next path.
• Recursive algorithm
• Implemented using Stack

Algorithm:
I. Enter root node on stack
II. Do until stack is not empty
a) Remove node
i) if node= Goal stop
ii) Push all children of node in stack
DFS Examples
 Analysis
• Time complexity
 In the worst case, search entire space
 Goal may be at level d but tree may continue to level m, m>=d
 O(bm)
 Particularly bad if tree is infinitely deep

• Space complexity
 Only need to save one set of children at each level
 1 + b + b + … + b (m levels total) = O(bm)
 For previous example, DFS requires 118kb instead of 10 petabytes for d=12 (10
billion times less)

• Benefits
 May not always find solution
 Solution is not necessarily shortest or least cost
 If many solutions, may find one quickly (quickly moves to depth d)
 Simple to implement
 Space often bigger constraint, so more usable than BFS for large problems
Comparison of Search Techniques
DFS BFS
Complete N Y
Optimal N N
Heuristic N N
Time bm bd+1
Space bm bd+1
Uniform Cost Search (Branch&Bound)
• Used for Weighted Tree/Graph
• Node expansion is based on path cost
• Goal is to path finding to goal node with lowest
cumulative cost[ optimal path]
• Priority Queue is used for Implementation.
• Involves Backtracking
• Gives optimal solution
• There is possibility to struck in infinite loop
UCS Example
Comparison of Search Techniques
DFS BFS UCS
Complete N Y Y
Optimal N N Y
Heuristic N N N
Time bm bd+1 bm
Space bm bd+1 bm
 Depth-Limited Search

• Working is similar to DFS but with

predetermined depth limit.
• Helps in solving the problem of DFS with infinite
loop.
• Termination Conditions
– Failure: no solution
– Cut off failure: on reaching the predetermined depth
• Memory efficient
• Incomplete and not optimal
Depth-Limited Search Example
Comparison of Search Techniques
DFS BFS UCS DLS
Complete N Y Y N
Optimal N N Y N
Heuristic N N N N
Time bm bd+1 bm bm
Space bm bd+1 bm bm
 Iterative Deepening Search
• DFS with depth bound
• Best depth limit is found out by gradually
increasing depth limit
– Expand(state) only returns children such that
depth(child) <= threshold
– This prevents search from going down infinite path
• First threshold is 1
• If do not find solution, increment threshold and repeat
• Incorporates benefits of both DFS and BFS
• Main disadvantage is repeat the work process
Iterative Deepening Search Example
Examples
 Analysis
• What about the repeated work?
• Time complexity (number of generated nodes)
[b] + [b + b2] + .. + [b + b2 + .. + bd]
(d)b + (d-1) b2 + … + (1) bd
O(bd)
 Analysis
• Repeated work is approximately 1/b of total
work
Negligible
Example: b=10, d=5
N(BFS) = 1,111,100
N(IDS) = 123,450
• Features
– Shortest solution, not necessarily least cost
– Is there a better way to decide threshold? (IDA*)
Comparison of Search Techniques
DFS BFS UCS IDS
Complete N Y Y Y
Optimal N N Y N
Heuristic N N N N
Time bm bd+1 bm bd
Space bm bd+1 bm bd
 Bidirectional Search

• Search forward from initial state to goal AND backward from

goal state to initial state
• Can prune many options
• Considerations
– Which goal state(s) to use
– How determine when searches overlap
– Which search to use for each direction
– Here, two BFS searches
• Time and space is O(bd/2+bd/2)
Comparison of Search Techniques
Informed Searches
 Informed Searches
• Information about goal state is present
• Better than uninformed search
• Finds an optimal solution to reach the goals using Heuristic
function.
• It is a search which tries to reduce amount of search that must
be done by making intelligent choices for the nodes that are
selected for expansion.
• New Terms
– Heuristics
– Optimal solution
– Informedness
• Best-first search, Hill climbing, Beam search, A*, IDA*, RBFS,
SMA*
 Informed Searches
• Informed search mainly includes Heuristic Search and Heuristic
Function
• Heuristic Search: Tries to optimize a problem using heuristic
function
• Heuristic Function: It is a function h(n), that gives an estimation
on the cost of getting from node ‘n’ to the goal state
• Search algorithms which use h(n) to guide search are heuristic
search algorithms
• New parameters
– g(n) = estimated cost from initial state to state n
– h(n) = estimated cost (distance) from state n to closest goal
– f(n)= g(n)+h(n)
– h(n) is our heuristic
• Robot path planning, h(n) could be Euclidean distance
• 8 puzzle, h(n) could be #tiles out of place
 Informed Searches
• Types of Heuristics:
• Admissible: In this heuristic function, never over estimates the
cost of reaching goal i.e h(n) is always less than or equal to
actual cost of lowest cost path from node ‘n’ to goal.
– h(n)<=h’(n) of goal
• Non - Admissible: Over estimates the cost of reaching goal.
– h(n)>h’(n) of goal
 Best-First Search
• Uses evaluation algorithm to decide which
adjacent node is most promising and then
explore
• Category of heuristic or informed search
• Priority Queue is used to store cost of nodes.
• Uses Greedy search(i.e BFS & DFS)
• Best-first search only as good as heuristic
– Example heuristic for 8 puzzle: Manhattan Distance
 Best-First Search- Algorithm
Priority Queue ‘PQ’ containing initial states in sorted order
Loop
If PQ= Empty return Fail
Else
Node Remove_First(PQ)
If Node=Goal
Return path from initial to Node
Else
Generate all successors of Node and insert
newly generated Node into PQ according to
cost value
End Loop
 Example
START
A 7 Euclidean distance:
11
14
D • AG=40
18 25 • BG=32
B C
• CG=25
10
15 8 F • DG=35
• EG=19
E 20
• FG=17
9 • GG=0
G
H
10 • HG=10
GOAL
 Example Euclidean distance:
START • AG=40
A 7 • BG=32
11 D • CG=25
14
• DG=35
18 25
B C • EG=19
• FG=17
10
15 8 F • GG=0
• HG=10
E 20

9
OPEN: CLOSED:
G [A] [ ]
H
10
GOAL [C,B,D] [A]
[F,E,B,D] [A,C]
[G,E,B,D] [A,C,F]
[E,B,D] [A,C,F,G]
Comparison of Search Techniques
DFS BFS UCS IDS Best
Complete N Y Y Y N
Optimal N N Y N N
Heuristic N N N N Y
Time bm bd+1 bm bd bm
Space bm bd+1 bm bd bm
 Beam Search
• Optimized version of Best First search
• Heuristic search algorithm
• Beam Value(β)(Only predetermined [Link] best partial
solutions are kept as candidates).
• Only keep best (lowest-h) n nodes on open list
• Explores a graph by expanding the most promising
node in a limited set.
• Reduces memory requirement
• Uses Greedy search(i.e BFS & DFS)
 Example
START
A 7 Euclidean distance:
11
14
D • AG=40
18 25 • BG=32
B C
• CG=25
10
15 8 F • DG=35
• EG=19
E 20
• FG=17
9 • GG=0
G
H
10 • HG=10
GOAL
 Example Euclidean distance:
START • AG=40
A 7 • BG=32
11 D • CG=25
14
• DG=35
18 25
B C • EG=19
• FG=17
10
15 8 F • GG=0
• HG=10
E 20

9
OPEN: CLOSED:
G [A] [ ]
H
10
GOAL [C,B,D] [A]
[F,E,B] [A,C]
Consider Beam Value(β)=2 [G,E] [A,C,F]
[E] [A,C,F,G]
Comparison of Search Techniques
DFS BFS UCS IDS Best Beam

Complete N Y Y Y N N

Optimal N N Y N N N

Heuristic N N N N Y Y

Time bm bd+1 bm bd bm nm
Space bm bd+1 bm bd bm bn
 Hill Climbing Search
• Variant of generate and test method in which feedback
from test procedure is used to help generator decide
which direction to move in search space.
• Always move in single direction.
• It is Like DFS
• Local search algorithm
• Uses Greedy search
• Hill climbing is irrevocable
• n is the “beam width”
– n = 1, Hill climbing
– n = infinity, Best first search
 Hill Climbing Search
Evaluate Initial State

Goal Return Solution

State Yes

No
Current state(CS)= Initial State

Apply operator and get New State(NS)

Goal Yes
Return Solution
state

NS is
better
Yes
CS=NS
than
CS
No
Hill Climbing (Greedy Search)
• Features
– Much faster
– Less memory
– Dependent upon h(n)
– If bad h(n), may prune away all goals
– Not complete
 Hill Climbing Issues
• Also referred to as gradient descent
• Foothill problem / local maxima / local minima
• Can be solved with random walk or more steps
• Other problems: ridges, plateaus

global maxima

local maxima
values

states
Comparison of Search Techniques
DFS BFS UCS IDS Best HC Beam

Complete N Y Y Y N N N

Optimal N N Y N N N N

Heuristic N N N N Y Y Y

Time bm bd+1 bm bd bm bm nm
Space bm bd+1 bm bd bm b bn
 A* Search
• Uses heuristics function h(n) and cost g(n) to reach the
node ‘n’ from initial state to goal state
– f(n)=g(n)+h(n)
• Finds shortest path through search space.
• Note that UCS and Best-first both improve search
– UCS keeps solution cost low
– Best-first helps find solution quickly
– A* combines these approaches
• It gives fast and optimal result.
• It is optimal and complete
• It solves complex problems
• Required more memory
 A* Search- Algorithm
i. Enter initial node in OPEN list
ii. If OPEN= Empty return Fail
iii. Select node from OPEN which has smallest value
(g+h) If
Node=Goal return Success
iv. Expand node ‘n’ Generate all successors of Node
and compute (g+h) for each successor
v. If node ‘n’ is already in OPEN/CLOSED attach to
back pointer
vi. Goto step (iii)
 Example
Solution Space:
7 START • SA=1+6=7
S • SB=4+2=6
1 4
• SBC=4+2+1=7
6 2 2
A B
• SBCD=4+2+3+0=9
12 5 2

• SAB=1+2+2=5
D C 1 • SAC=1+5+1=7
3
0 • SAD=1+12+0=13
GOAL
• SABC=1+2+2+1=6

• SABCD=1+2+2+3+0=8

• SACD==1+5+3+0=9
 Power of f
• If heuristic function is wrong it either
– overestimates (guesses too high)
– underestimates (guesses too low)
• Overestimating is worse than underestimating
• A* returns optimal solution if h(n) is admissible
– heuristic function is admissible if never
overestimates true cost to nearest goal
– if search finds optimal solution using admissible
heuristic, the search is admissible
Comparison of Search Techniques
DFS BFS UCS IDS Best HC Beam A*
Complete N Y Y Y N N N Y
Optimal N N Y N N N N Y
Heuristic N N N N Y Y Y Y
Time bm bd+1 bm bd bm bm nm bm
Space bm bd+1 bm bd bm b bn bm
 IDA*
• Iterative Deepening A* (IDA*) is graph
traversal and path finding method to
determine the shortest route in weighted
graph between a defined start node to any
goal node
• It is kind of series of Depth-First Searches
• Like Iterative Deepening Search, except
– Use A* cost threshold instead of depth threshold
– Ensures optimal solution
 IDA*
• Initialization
– Set the root node as the current node and find the f-score
• Set Threshold
– Set the cost limit as a threshold for a node i.e the maximum f-score
allowed for that node for further explorations
• Node Expansion
– Expand the current node to its children and find f-scores
• Pruning
– If for any node the f-score>threshold , prune that node because its
considered too expensive for that node and store it in the visited node
list
• Return path
– If the goal node is found then return the solution
• Update the threshold
– If the goal node is not found then repeat the above steps by changing
threshold
 Analysis
• Some redundant search
– Small amount compared to work done on last
iteration
• Dangerous if continuous-valued h(n) values or
if values very close
– If threshold = 21.1 and value is 21.2, probably only
include 1 new node each iteration
• Time complexity is O(bm)
• Space complexity is O(bm)
Comparison of Search Techniques
DFS BFS UCS IDS Best HC Beam A* IDA*
Complete N Y Y Y N N N Y Y
Optimal N N Y N N N N Y Y
Heuristic N N N N Y Y Y Y Y
Time bm bd+1 bm bd bm bm nm bm bm
Space bm bd+1 bm bd bm b bn bm bm
 RBFS
• Recursive Best First Search
• It is recursive i.e performs looping to previous
level for minimum f value
• Keep track of alternative (next best) sub tree
• Update f values before (from parent)
and after (from descendant) recursive call
 Analysis
• Optimal if h(n) is admissible
• Space is O(bm)
• Features
– Potentially exponential time in cost of solution
– More efficient than IDA*
– Keeps more information than IDA* but benefits
from storing this information
 SMA*
• Simplified Memory-Bounded A* Search
• It is very similar to A* search but has memory
limitation.
• When memory is full
– Discard worst leaf (largest f(n) value)
– Back value of discarded node to parent
• Optimal if solution fits in memory
 Example
• Let Memory size
MaxNodes = 3
• Initially B&G added to open
list, then hit max
• B is larger f value so discard
but save f(B)=15 at parent A
– Add H but f(H)=18. Not a
goal and cannot go deper, so
set f(h)=infinity and save at
G.
• Generate next child I with
f(I)=24, bigger child of A. We
have seen all children of G, so
reset f(G)=24.
• Regenerate B and child C.
This is not goal so f(c) reset to
infinity
• Generate second child D with
f(D)=24, backing up value to
ancestors
• D is a goal node, so search
 Heuristic Functions
• Q: Given that we will only use heuristic
functions that do not overestimate, what type
of heuristic functions (among these) perform
best?
• A: Those that produce higher h(n) values.
 Reasons
• Higher h value means closer to actual distance
• Any node n on open list with
– f(n) < f*(goal)
– will be selected for expansion by A*
• This means if a lot of nodes have a low
underestimate (lower than actual optimum
cost)
– All of them will be expanded
– Results in increased search time and space
 Informedness
• If h1 and h2 are both admissible and
• For all x, h1(x) > h2(x), then h1 “dominates” h2
– Can also say h1 is “more informed” than h2
• Example
– h1(x): | xgoal  x |
– h2(x): Euclidean distance ( x goal  x) 2  ( y goal  y ) 2
– h2 dominates h1
 Generating Heuristic Functions
• Generate heuristic for simpler (relaxed)
problem
– Relaxed problem has fewer restrictions
– Eight puzzle where multiple tiles can be in the
same spot
– Cost of optimal solution to relaxed problem is an
admissible heuristic for the original problem
• Learn heuristic from experience
 Local Search Algorithms
• Previous searches addressed a single category of
problems: observable, deterministic, known
environments where the solution is a sequence of
actions.
• perform purely local search in the state space,
evaluating and modifying one or more current states
rather than systematically exploring paths from an
initial state.
• The family of local search algorithms includes
methods inspired by statistical physics (simulated
annealing) and evolutionary biology (genetic
algorithms).
 Local Search Algorithms
• Local search algorithms operate using single current
node (rather than multiple paths) and generally move
only to neighbors of that node.
• Local search algorithms are not systematic, they have
two key advantages: (1) they use very little memory—
usually a constant amount; and (2) they can often find
reasonable solutions in large or infinite (continuous)
state spaces for which systematic algorithms are
unsuitable.
• Local search algorithms are useful for solving pure
optimization problems, in which the aim is to find the
best state according to an objective function.
 Iterative Improvement Algorithms
• For many optimization problems, solution path is
irrelevant
– Just want to reach goal state
• 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
Iterative Improvement Algorithms
• Hill climbing
• Simulated annealing
• Genetic algorithms
 Steepest Ascent Hill Climbing
• In Steepest –Ascent multiple check points are checked.
• Examining all neighbor nodes and selects nodes closest to goal
as next node.
• Stochastic hill climbing chooses at random from among the
uphill moves.
• First-choice hill climbing implements stochastic hill climbing by
generating successors randomly until one is generated that is
better than the current state.
• The hill-climbing algorithms described so far are incomplete—
they often fail to find a goal when one exists because they can
get stuck on local maxima.
• Random-restart hill climbing adopts the well-known adage, “If
at first you don’t succeed, try, try again.” It conducts a series of
hill-climbing searches from randomly generated initial
 Hill Climbing Search
Evaluate Initial State

Goal Return Solution

State Yes

No
Generate all successors

Select the best successor

Goal Yes
Return Solution
state

NO
better Return Solution

Yes
Hill Climbing (gradient ascent/descent)

• “Like climbing Mount Everest in thick fog with

amnesia”
 Simulated Annealing
• Annealing is a process in metallurgy where metals are
slowly cooled to make them to reach a state of low
energy where they are very strong.
• Pure hill climbing is not complete, but pure random
search is inefficient.
• Simulated annealing offers a compromise i.e
downward steps.
• 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.
 Algorithm
function SimulatedAnnealing(problem, schedule) // returns solution state
current = MakeNode(Initial-State(problem))
for t = 1 to infinity
T = schedule[t]
if T = 0
return current
next = randomly-selected child of current
E = Value[next] - Value[current]
if E > 0
current = next // if better than accept state

else  E
current = next with probability e T
 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
• What is a Genetic Algorithm (GA)?
– An adaptation procedure based on the mechanics of natural
genetics and natural selection
• GAs have 2 essential components
– Survival of the fittest
– Recombination
• Representation
– Chromosome = string
– Gene = single bit or single subsequence in string, represents 1
attribute
 GAs Exhibit Search
• Each attempt a GA makes towards a solution is called a
chromosome
– A sequence of information that can be interpreted as a
possible solution
• Typically, a chromosome is represented as sequence of
binary digits
– Each digit is a gene
• A GA maintains a collection or population of
chromosomes
– Each chromosome in the population represents a different
guess at the solution
 The GA Procedure
1. Initialize a population (of solution guesses)
2. Do (once for each generation)
a. Evaluate each chromosome 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.
 Common Operators
• Reproduction
• Crossover
• Mutation
 Reproduction
• Select individuals x according to their fitness
values f(x)
• Fittest individuals survive (and possibly mate)
for next generation
 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
Example
 Local search in continuous space
1. A local search is first conducted in the continuous
space until a local optima is reached. It then switches
to discrete space that represents a discretization of
the continuous model to find an improved solution
from there.
2. The process continuous switching between the two
problem formulations until no further improvement
can be found in either.
3. To perform local search in continuous space we need
techniques from calculus.
4. The main technique to find a minimum is called
Gradient descent
 Gradient Descent
1. A gradient measures how much the output of a function
changes if you change the inputs a little bit.
2. In ML, Gradient is a derivative of function that has more
than one input variable known as a slope of a function in
mathematical terms , the gradient simply measures the
change in all weights with regard to the change in error.
3. Gradient descent is an iterative optimization algorithm to
find the minimum of a function.
4. Gradient descent is an optimization algorithm to find a
local minimum of differentiable function. It is simply used
in ML to find the values of a function’s parameters
(coefficients)that minimize a cost function as far as
possible.