Catalogue of Artificial Intelligence Techniques
Local Beam Search
Keywords: beam, local, search
Categories: Search
Author(s): Jonathan Lockhart
A cross between Beam Search and Local Search. Normally used to maximize an objective function.
The algorithm holds 'k' number of states at any given time. Initially these k states are randomly generated. The successors of these k states are calculated using the objective function. If any of these successors is a 'goal', that is, the maximum value of the objective function, then the algorithm halts.
Otherwise the initial k states and k number of successors are placed in a pool. This pool has a total of 2k states. The pool is numerically sorted and the best (highest) k states are selected as new initial states. This process repeats until a maximum value is reached.
This algorithm is particularity effective at quickly abandoning 'dead end' searches, so maximum resources can be used on the promising successors.
However when using the Local Beam Searching algorithm, the k states can easily become concentrated over a very small amount of state space. This leads to the algorithm being nothing more than a more resource intensive Hill Climbing algorithm.
References:
- Stuart Russell, Artificial Intelligence - A Modern Approach.
Comments:
No comments.