Memetic Computing: Design Issues

Memetic Computing: Design Issues

Basic Principles Beam search is a heuristic search algorithm that is an optimization of best-first search that reduces its memory requirement. Best-first search is a graph search which orders all partial solutions (states) according to some heuristic which attempts to predict how close a partial solution is to a complete solution (goal state). In beam search, only a predetermined number of best partial solutions are kept as candidates. Beam search uses breadth-first search to build its search tree. At each level of the tree, it generates all successors of the states at the current level, sorting them in order of increasing heuristic values.However, it only stores a predetermined number of states at each level (called the beam width). The smaller the beam width, the more states are pruned. Therefore, with an infinite beam width, no states are pruned and beam search is identical to breadth-first search. Pros and Cons The beam width bounds the memory required to perform the search,

Read full article from Memetic Computing: Design Issues