What is the difference between Local beam search and Stochastic beam search?

algorithm artificial-intelligence beam-search
user3880907 picture user3880907 · Oct 2, 2015 · Viewed 9.8k times · Source

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 to me if I am wrong

Answer

Ivaylo Strandjev picture Ivaylo Strandjev · Oct 2, 2015

Stochastic pretty much means randomized in some way. One of the major issues with beam search is that it tends to get stuck into local optima instead of the global optimum. To avoid that stochastic search gives some(most often small) probability of the solution to choose the step that is not optimal at a given moment. You can think of that as "adding randomness". A bit better approach would be simulated annealing where the chance to take suboptimal choice decreases with time.

Local search on the other hand will always choose the best K neighbours, never allowing to deviate from a local optimum if you happen to hit one.

Related questions

What does the beam size represent in the beam search algorithm?

I have a question about the beam search algorithm. Let's say that n = 2 (the number of nodes we are going to expand from every node). So, at the beginning, we only have the root, with 2 nodes that we expand from …

Read More
What is the optimal algorithm for the game 2048?

I have recently stumbled upon the game 2048. You merge similar tiles by moving them in any of the four directions to make "bigger" tiles. After each move, a new tile appears at random empty position with a value of either 2 …

Read More
What are good examples of genetic algorithms/genetic programming solutions?

Genetic algorithms (GA) and genetic programming (GP) are interesting areas of research. I'd like to know about specific problems you have solved using GA/GP and what libraries/frameworks you used if you didn't roll your own. Questions: What problems …

Read More