Informed and Heuristic Search Questions and Answers

Q: How does local beam search differ from k random restarts?

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.

Q: What is a genetic algorithm?

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.

Q: What does crossover contribute that mutation does not?

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.

Q: Why does the choice of representation matter so much for a genetic algorithm?

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.

Q: What is the fitness function in a genetic algorithm?

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.

Q: What is the risk of premature convergence in a population based search?

If one moderately good individual dominates early, its descendants fill the population and the search explores nothing further, arriving quickly at a mediocre answer. Diversity preservation, larger populations and lower selection pressure are the usual remedies. Timing, fitness behaviour and memory are different concerns. A search that stops exploring before it has found anything good is failing in the same way a hill climber trapped on a local maximum is, and the remedies are analogous.

Q: What is online search?

An online search agent must act to discover what its actions do, since the state space is not known in advance, so it interleaves exploration with movement and cannot plan a route through territory it has never seen. Offline search computes a complete solution first. Network access and changing spaces are different notions, though a dynamic space raises related difficulties. Acting in order to learn what acting does is what makes exploration a search problem in its own right.

Q: Why can an online search agent not simply plan a route to the goal?

Without knowing what its actions do or where they lead, the agent has no model to plan over, and must build one by acting and observing. That is the reinforcement learning setting seen from the search direction. Time, goal knowledge and memory are secondary or absent. The distinction between an unknown environment and a merely large one determines whether exploration is a necessity or an inefficiency, and the two are frequently confused.

Q: What is the competitive ratio of an online search algorithm?

Comparing the distance actually travelled with what an omniscient agent would have walked gives a competitive ratio, and bounding it is the standard way of evaluating an online algorithm. In the worst case, with adversarially placed dead ends, the ratio can be unbounded. Running time, coverage and success rates are different measures. Judging an algorithm against what perfect knowledge would have achieved is the natural standard when the difficulty is ignorance rather than computation.

Q: What does learning real time A star do?

LRTA star acts greedily on its current estimates and raises the estimate of a state it leaves to reflect what it found there, so the heuristic improves with experience and the agent escapes from dead ends. Repeated searching, offline learning and radius limits describe other techniques. Updating an estimate towards the value of the best successor is exactly the update rule of value iteration, which connects online search directly to reinforcement learning.

41.

How does local beam search differ from k random restarts?

A.It uses less memory than running k searches separately
B.It is guaranteed to find the global optimum where restarts are not
C.It evaluates each state more accurately than a single climb does
D.The k states share information by pooling their successors

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.

Discuss in Forum

42.

What is a genetic algorithm?

A.A population based search using selection, crossover and mutation
B.A search that encodes the problem in a biological representation
C.An algorithm that learns the structure of the genetic code
D.A local search that mutates a single state repeatedly

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.

Discuss in Forum

43.

What does crossover contribute that mutation does not?

A.It reduces the number of fitness evaluations required
B.It combines useful substructures from two different solutions
C.It introduces variation that mutation cannot produce
D.It guarantees the population will improve at every generation

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.

Discuss in Forum

44.

Why does the choice of representation matter so much for a genetic algorithm?

A.The representation determines the fitness function that can be used
B.Binary representations are required for mutation to be defined
C.Crossover only helps if adjacent components form meaningful blocks
D.Longer representations always converge faster than short ones

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.

Discuss in Forum

45.

What is the fitness function in a genetic algorithm?

A.The probability that a given individual will be mutated
B.The number of generations an individual survives in the population
C.The similarity between an individual and the target solution
D.The measure by which individuals are selected for reproduction

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.

Discuss in Forum

46.

What is the risk of premature convergence in a population based search?

A.The population loses diversity and settles on a poor solution
B.The algorithm terminates before the population is initialised
C.The fitness function converges before the individuals do
D.The population grows too large for the available memory

Answer: A

If one moderately good individual dominates early, its descendants fill the population and the search explores nothing further, arriving quickly at a mediocre answer. Diversity preservation, larger populations and lower selection pressure are the usual remedies. Timing, fitness behaviour and memory are different concerns. A search that stops exploring before it has found anything good is failing in the same way a hill climber trapped on a local maximum is, and the remedies are analogous.

Discuss in Forum

47.

What is online search?

A.Computing a complete plan before any action is taken
B.Interleaving computation with action in an unknown space
C.Searching a database of solutions available over a network
D.Searching while the state space changes during the search

Answer: B

An online search agent must act to discover what its actions do, since the state space is not known in advance, so it interleaves exploration with movement and cannot plan a route through territory it has never seen. Offline search computes a complete solution first. Network access and changing spaces are different notions, though a dynamic space raises related difficulties. Acting in order to learn what acting does is what makes exploration a search problem in its own right.

Discuss in Forum

48.

Why can an online search agent not simply plan a route to the goal?

A.The goal is not known until the agent has explored the space
B.The agent has insufficient memory to store a complete plan
C.It does not know the transition model until it has acted
D.Planning would take longer than the environment allows

Answer: C

Without knowing what its actions do or where they lead, the agent has no model to plan over, and must build one by acting and observing. That is the reinforcement learning setting seen from the search direction. Time, goal knowledge and memory are secondary or absent. The distinction between an unknown environment and a merely large one determines whether exploration is a necessity or an inefficiency, and the two are frequently confused.

Discuss in Forum

49.

What is the competitive ratio of an online search algorithm?

A.The ratio of its running time to that of an offline algorithm
B.The proportion of the state space it explores before succeeding
C.The ratio of successful to unsuccessful exploration attempts
D.The cost of its path divided by the cost of the optimal path

Answer: D

Comparing the distance actually travelled with what an omniscient agent would have walked gives a competitive ratio, and bounding it is the standard way of evaluating an online algorithm. In the worst case, with adversarially placed dead ends, the ratio can be unbounded. Running time, coverage and success rates are different measures. Judging an algorithm against what perfect knowledge would have achieved is the natural standard when the difficulty is ignorance rather than computation.

Discuss in Forum

50.

What does learning real time A star do?

A.Updates its heuristic estimates as it explores
B.Runs A star repeatedly within a fixed time budget
C.Learns the transition model from a training set first
D.Applies A star only to the states within a fixed radius

Answer: A

LRTA star acts greedily on its current estimates and raises the estimate of a state it leaves to reflect what it found there, so the heuristic improves with experience and the agent escapes from dead ends. Repeated searching, offline learning and radius limits describe other techniques. Updating an estimate towards the value of the best successor is exactly the update rule of value iteration, which connects online search directly to reinforcement learning.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Informed and Heuristic Search Questions and Answers || Informed and Heuristic Search MCQ Questions and Answers || Informed and Heuristic Search GK Questions and Answers || Informed and Heuristic Search GK MCQ Questions || Informed and Heuristic Search Multiple Choice Questions and Answers || Informed and Heuristic Search GK || GK on Informed and Heuristic Search || Artificial Intelligence Questions and Answers || Artificial Intelligence MCQ Questions and Answers || Artificial Intelligence GK Questions and Answers || GK on Artificial Intelligence

Informed and Heuristic Search Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications