Intellipaat Back

Explore Courses Blog Tutorials Interview Questions
0 votes
in AI and Deep Learning by (50.2k points)

I know that both of them select K randomly, and then choose the best K, as I understand the best K call the others to find the goal, so what is the exact difference between Local beam search and Stochastic beam search? Please help me and correct it to me if I am wrong.

1 Answer

0 votes
by (108k points)

Beam search is a method very much similar to iterative best improvement, but it maintains up to k number of assignments instead of just one. It reports success when it finds a satisfying assignment. At each stage of the algorithm, it selects the k best neighbors of the current individuals (or all of them if there are less than k) and picks randomly in the case of ties. It then repeats the step with this new set of k total assignments.

Beam search can take multiple assignments at the same time. Beam search is useful where k can be selected depending on the memory available.

In the Stochastic beam search instead of choosing the best k individuals, it selects k number of the individuals at random; the individuals with a better evaluation are more likely to be chosen. This is done by making the probability of being chosen as a function of the evaluation function.

Stochastic beam search tends to allow more diversity in the k individuals than does plain beam search. In terms of evolution in biology, the evaluation function reflects the fitness of the individual; the fitter the individual, the more likely it is to pass that part of its variable task that is good over the next generation. Stochastic beam search is similar to asexual reproduction within which every individual offers slightly mutated children and then stochastic beam search proceeds with the survival of the fittest.

Note that under a stochastic beam search it is possible for an individual to be selected multiple times at random.

Browse Categories