Local Search

Question 1

What does local search return?

Answer 1

A state, not a path like normal search algorithms

Question 2

What are stopping criteria for local search?

Answer 2

Heuristic value, goal test and number of runs.

Question 3

What is iterative best improvement strategy?

Answer 3

A local search strategy that always selects a successor that minimises a heursitic function which is typically the loss or gain. It performs greedy choice.

Question 4

What is hill climbing?

Answer 4

Maximising a goal value.

Question 5

What is greedy descent?

Answer 5

Minimising a goal value.

Question 6

How does hill climbing work?

Answer 6

Start wherever and iteratively move to the next best neighbouring state. Quit when no better nieghbours exist.

Question 7

What are the drawbacks of hill-climbing?

Answer 7

Depending on inital state, can get stuck in a local maxima

Question 8

What is hill climbing with sideways moves?

Answer 8

Uses the same procedure as hill climbing, except when there are no uphill successors, the algorithm moves sideways. Introduce a parameter m so that only m sideways moves can be performed.

Question 9

How does sideways moves perform on n-queens problem.

Answer 9

With no sideways moves, the algorithm succeeds only 14% of the time. With sideways moves, the algorithm succeeds 94% of the time, but takes more moves to find a solution.

Question 10

What is enforced hill climbing?

Answer 10

Performs breadth-first search from a local optima to find the next state with better h function. Good at escaping local optima.

Question 11

What is tabu search?

Answer 11

It maintains a fixed-length queue of the most recent states. IT never makes a step to a state that is on the tabu list.

Question 12

What is stochastic search?

Answer 12

Local search strategies where randomization plays a prominent role.

Question 13

What is random-restart hill climbing?

Answer 13

Series of hill climbing searches with random restarts. If stuck or taking too long, restart from a random starting candidate.

Question 14

How to calculate the expected number of runs of random-restart hill climbing?

Answer 14

Suppose a single attempt of greedy descent has a success rate of p. Then the expected number of tries is 1/p.

Question 15

What is first-choice hill climbing?

Answer 15

An implementation of stochastic hill climbing. Generating successors randomly until it finds one that is uphill. Doesn’t waste time generating all successors.

Question 16

What is stochastic hill climbing?

Answer 16

Can randomly select amongst the uphill moves. The selection probability can vary with the steepness of the uphill move. Can still get stuck in local maxima.

Question 17

What is random walk hill climbing?

Answer 17

Assumes that adding randomisation may avoid the search getting stuck in local optima.
1. pick a parameter (walk probability)
2. At every step, with probability p, make an uninformed random walk. With probability 1-p, make a greedy choice.
This search strategy is PAC.

Question 18

What is PAC (probabilistic approximately complete)?

Answer 18

A search strategy is probabilistic approximately complete is the probability that a try fails to find an optimal solution can be made arbitrarily small when the search runs for sufficiently long.

Question 19

What is probabilistic hill-climbing?

Answer 19

It allows worsening search steps with a probability that depends on the respective deterioration in evaluation function value.

Question 20

How does annealing work?

Answer 20

As the algorithms proceed, the probability of accepting a worse successor. The temperature parameter determines the probability of accepting a worse variable. A high temperature means the probability of a locally bad move is higher. A low temperature is when the probability of locally bad move is lower. Typically the algorithm starts at a high temperature and exponentially decreases.

Question 21

What are the properties of simulated annealing?

Answer 21

If t decreased slowly enough, the algorithm will converge to an optimal state. This gives us a theoretical guarantee. Convergence may take a very very long time.

Question 22

What is gradient descent?

Answer 22

Used on continuous functions where we want to minimize over continuous variables. Compute the gradients for all directions. Take a small step downhill in the direction of the chosen gradient. Repeat.