AI Flashcards
Cons of Hill Climbing:
- No Guarantee to be COMPLETE or OPTIMAL
- Can get stuck on local maxima & plateaus
(RUN FOREVER IF NOT PROPERLY FORMULATED)
Pros of Hill Climbing:
- Rapidly find good solutions by Improving over bad initial state (GREEDY)
- Lower Time & Space Complexity compared to search algorithms
- No Requirements of problem-specific heuristics
(UNINFORMED) - Start from Candidate Solution, instead of building up step-by-step
(UNLIKELY BUT POSSIBLE, SOLUTION PICKED AT RANDOM )
Run algorithm for a Maximum number of iterations m
Variants of Hill climbing can sort out getting stuck on local maxima/ plateaus
Variants of Hill Climbing:
- Stochastic Hill Climbing
- First - Choice Hill Climbing
- Random - Restart Hill Climbing
Stochastic Hill Climbing :
- Variants Randomly selects a neighbour that involves an uphill move
- Probability of picking a specific move can depend on the steepness
- Converges slower than steepest ascent but can find higher solutions
First - Choice Hill Climbing
-Randomly generates a single SUCCESSOR neighbour solution & moves to it if it’s better than current solution
- No UPHILL, keeps randomly generating solutions until there is an uphill move
- After MAX num of tries OR generating all neighbours, hasn’t found UPHILL move, it gives up & assumes that it’s now at Optimal solution.
- Time complexity of this is lower as not all neighbours need to be generates before 1 is picked
(GOOD WHEN THERE ARE LOADS OF NEIGHBOURS FOR EACH SOLUTIONS)
Random - Restart Hill Climbing:
- Generates a series of different hill climbing searches of the same problem from random to initial states
- Stops when goal is found
- Can be parallelised / Threaded easily so does not take much time on modern Computers
- RARE to have to wait for this to happen
What is the only Complete variant of Hill Climbing?
Random - Restart Hill Climbing
It generates a solution if one exists, as eventually random start solution will be OPTIMAL SOLUTION
Pros of Simulating Annealing:
- Find near Optimal Solutions in reasonable time
(High Chance of going to GLOBAL MAX, But only
Good as the formulation of Optimisation Problem) - Avoids getting stuck in poor LOCAL MAX & PLATEAU by combining EXPLORATION & EXLIOTATION
(many solutions we concurrently work with at the end of EXPLORATION )
Cons of Simulating Annealing:
- Not Guaranteed to be complete OR OPTIMAL
(SENSITIVE TO FORMUALTION) - NOT reliable = can’t guarantee completeness
- Time & Space Complexity is problem & Representation- dependent
Formulating Optimisation Problems:
min / max f(x) => min/max objective functions
s.t g_i(x) <= 0, i = 1,…,m
h_i(x) <= 0, i = 1,…,n => Feasibility Constraint
==> x is the DESIGN VARAIBLE (can be anything)
SEARCH SPACE is space of all possible x values
What is Search Space of a Problem:
is the space of all possible x values ALLOWED by constraints in CANDIDATE SOLUTIONS
Define Explicit Constraint:
Explicitly mentioned
CANNOT BE ASSUMED
Define Implicit Constraint:
Rules that must be in place by the problem definitions in order for solutions to be CONSIDERED FEASIBLE
e.g: x,y > 0
Define A*:
Heuristic path finding algorithm & most used example of Informed Search
What is the Evaluation Function:
f(n) = g(n) + h(n)
g(n) cost to reach node n
h(heuristic from node n to goal)
It determines which node to expand next
Steps of A*:
BASIC
1) Expand the shallowest node in frontier with SMALLEST EVALUATION FUNCTION
2) Node is in the list of visited nodes, DON’T ADD TO FRONTIER
3) Stop when a GOAL node is visited
(KEEP EXPANDING OTHERWISE)
What is the Final Cost of A*?
Sum of g(n) along the paths
- DON’T INCLUDE HEURSITICS
Dijkstra’s:
- UNINFORMED
- Goes Through all the nodes of the graph
- No Heuristics / ADDITIONAL INFO
- Basic Attempt to find shortest distance from the nodes on the graph to the destination
what is h(n)?
Euclidean Distance from each node to destination
Heuristics measure of cost as if a node is physically closer to destination
Good Assumption the cost to the destination will be lower
Pros & Cons of A* :
Pros:
- Doesn’t go through all nodes
- safer to assume to expand node with lower straight line distance (LEAVE OUT OTHER NODES )
Cons:
- Can lead to non-optimal paths (UNLIKELY)
Uninformed Search ?
Define the set of strategies having no additional information about the State Space beyond what is give during Problem formulation
What does Uninformed Search do?
-Only generates successors
-Distinguish a goal state from a non goal-state
What is Breadth First Search ?
-An Uninformed Searching Strategy
FRONTIER NODES ARE EXPANDED LAYER BY LAYER
Expanding shallowest unexpanded node in frontier
Similar to a QUEUE (FIFO)
- Unless State otherwise, never add children that are already in the Frontier
Steps for BFS?
-Root node is expanded
- Then the successors of the root
- Repeatedly expand all the successors of the all children, till goal node reached