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.
Back