Local Search and Optimization

Question 1

optimization problem

Answer 1

a problem where we must return a solution but our actions are unconstrained and we can numerically measure how much we like any state

Question 2

How can some search problems be viewed as optimization problems?

Answer 2

if we are willing to accept an imperfect goal state

Question 3

transition model in local search

Answer 3

• it is arbitrary
• just make one up, the model is irrelevant to the solution

Question 4

local search

Answer 4

• frontier is replaced with a single best node
• not every possibility is explored

Question 5

neighbourhood of S (A(s))

Answer 5

the set of adjacent states to some state s

Question 6

what are the performance properties of local search?

Answer 6

Complete: trivially, yes because sub-optimal states are accepted as solutions
Optimal: no
Time: O(inf) or O(1)
Space: O(1)

Question 7

random guessing

Answer 7

• ignore transition model and keep generating random states
• remember only the best one and return when time runs out

Question 8

random search

Answer 8

• choose a state from A(s) at random, keep chosen state if better than previous best state otherwise stay with previous best

Question 9

when is a state good enough in random search?

Answer 9

when you run out of time

Question 10

hill-climbing

Answer 10

• choose the state in A(s) that’s the best using f
  -> if maximizing: f(s) is biggest
  -> if minimizing: f(s) is smallest

Question 11

When is a state good enough in hill-climbing?

Answer 11

when no adjacent state is better

Question 12

local max/min

Answer 12

when no adjacent state is better than where we are now

Question 13

random restart hill-climbing

Answer 13

repeat hill-climbing, with new random initial state
- restart at any local optimum state or after a time limit

Question 14

simulated annealing

Answer 14

combines hill-climbing with a limited random walk
- go up hill when you can, risk down hill moves based on size of downhill move