Informed and Heuristic Search Questions and Answers

Answer: C

If each attempt succeeds with probability p, about one over p restarts are needed, and for many problems that is a very small number, so the crude expedient of trying again from somewhere else is remarkably effective. Occasional random moves are stochastic hill climbing and random neighbour choice is random walk. Turning an algorithm that usually fails into one that usually succeeds by repetition is a general and underrated technique.

Answer: D

Simulated annealing sometimes accepts a downhill move, with a probability falling as a temperature parameter is lowered, so the search explores widely at first and settles into a peak later. With a sufficiently slow cooling schedule it converges to the global optimum with probability approaching one. Step size reduction and combination of searches are different techniques. Borrowing a physical annealing process as an optimisation schedule is one of the field's more successful metaphors.

Answer: A

A strict climber cannot leave a local maximum, whereas one that occasionally goes downhill may cross a valley to a higher peak, and the falling temperature ensures it eventually settles. Evaluation cost, termination and memory are unaffected. Deliberately accepting a worse state, and controlling how often, converts a greedy procedure into a global one, which is a surprisingly general trick.

Answer: B

The probability follows an exponential in the ratio of the value decrease to the temperature, so small decreases are accepted readily and large ones rarely, and both become less likely as the temperature falls. That is exactly the Boltzmann factor from statistical mechanics. Neighbour counts, distance and iteration counts are not part of the rule. A rule borrowed intact from physics, and behaving in the intended way, is the reason the analogy is more than decorative.

Answer: C

Local beam search holds k states, generates all their successors and keeps the best k overall, so information is shared and effort concentrates where progress is being made. That sharing is what distinguishes it from k independent restarts. The risk is that all k states converge into one region, which stochastic beam search mitigates. Sharing information between parallel attempts, rather than running them independently, is the idea that also underlies population based methods.

Answer: D

Restarts are independent, so effort continues to be spent on hopeless starting points, whereas beam search abandons unproductive states and concentrates on the promising ones. Memory is comparable, no guarantee is obtained, and evaluation is identical. The distinction between parallel independent attempts and a population that reallocates effort is what separates restarts from every population based method, including genetic algorithms.

Answer: A

A genetic algorithm maintains a population, selects individuals in proportion to fitness, combines pairs by crossover and perturbs the results by mutation. It is a stochastic beam search with a recombination operator. Biological representation is incidental, and single state mutation without crossover is simply stochastic hill climbing. Recognising crossover as the distinctive ingredient identifies both what the method adds and when it is likely to help.

Answer: B

Crossover can bring together two good partial solutions discovered independently, which is a much larger jump than mutation makes and is the whole argument for the method. It helps only when the representation is such that partial solutions are meaningful and can be inherited together. Mutation can in principle reach any state, no improvement is guaranteed, and evaluation counts are not reduced. A technique whose benefit depends on the encoding is one whose encoding deserves as much thought as the algorithm.

Answer: C

If the parts of a solution that belong together are spread across the encoding, crossover disrupts them as often as it combines them, and the algorithm degenerates towards random search. Designing the encoding so that useful substructures are contiguous is the main craft in applying the method. Length, fitness definition and binary encoding are secondary. That an algorithm's performance depends more on the encoding than on its parameters is a lesson learned repeatedly in this area.

Answer: D

Fitness ranks individuals so that better ones reproduce more often, and it plays exactly the role of the objective function in any other optimisation method. Mutation rate, survival and similarity to a known target are different quantities, and the last would require the answer to be known already. Every population method needs a scalar by which to compare individuals, and specifying it carefully is subject to all the usual hazards of objective specification.