informed search algorithms (slides4)

Question 1

Local search algorithms

Answer 1

in many optimization problems, the path is irrelevant and the goal state is all that matters

• state space = set of “complete” configurations
• find configurations satisfying constraints e.g.,

-local search keep a single “current” state and try to improve it

Question 2

Hill climbing search

Answer 2

kind of like greedy local search
picks a neighbor with the highest value
usually chooses at random among neighbors with maximum value
Problem: depending on initial state, can get stuck on local maxima

Question 3

hill climbing search implmentation

Answer 3

function Hill-climbing(problem) reeturns a state that is a local maximum
inputs: problem, a problem
local variables: current: a node
neighbor, a node

current<– neighbor

Question 4

Hill Climbing variants

Answer 4

Stochastic hill climbing
first-choice hill climbing
random-restart hill climbing

Question 5

stochastic hill climbing

Answer 5

choose at random from the set of all improving neighbors

Question 6

first choice hill climbing

Answer 6

jumps to the first improving neighbor found

Question 7

random restart hill climbing

Answer 7

series of hill climbing runs until a goal is found

Question 8

simulated annealing search

Answer 8

escape local maxima by allowing some “bad” moves but gradually decrease their frequency

Question 9

simulated annealing search implementation

Answer 9

function simulated-annealing(problem, schedule) returns a solution state

• inputs:
• -problem, a problem
• -schedule, a mapping from time to “temperature”
• local variables:
• -current: a node
• -next: a node
• -T, a “temperature controlling probe of downard steps

current 0 then current <– next only w/ probability e^((del) E/T)
HIgher temp makes higher probability for non-improving move

Question 10

simulated annealing search properties

Answer 10

If T decreases slowly enough, then simulated annealing search will find a global optimum with probability approaching 1

Question 11

Local beam search

Answer 11

keep track of k states rather than just one

start with k randomly generated states

at each iteration all the successors of all k states are generated

if any one is a goal state, stop; else select the k best successors from the complete list and repeat(they could be all successors from the same node)

Question 12

Genetic algorithms

Answer 12

• A successor state is generated by combining two parent states
• start with k randomly generated states

-state represented as a string over a finite alphabet (often 0s and 1s or digits)
-evaluation function (fitness function). higher values for better states
produce the next generation of states by selection, crossover, and mutation