Deluge algorithm

The great deluge algorithm (english great deluge algorithm ) is a heuristic optimization techniques of computer science . It is related to simulated cooling and is mostly used for optimization problems which, due to their high complexity, exclude the complete testing of all possibilities and simple mathematical procedures.

The idea is to limit a random search in the search space by increasing the water level over time. For this purpose, a threshold value ( water level ) and a constant ( rain ) are defined. Starting from a random starting value , a new value is iteratively generated in the search space and accepted precisely when it is above , ie it must be better than . But it can be worse than . is regularly increased by. As a result, the accessible regions of the search area are visually reduced, so that the algorithm can initially overcome local optima by crossing lower regions, but over time it changes into a mountaineering algorithm . ${\displaystyle W}$ ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle x'}$ ${\displaystyle W}$ ${\displaystyle W}$ ${\displaystyle x}$ ${\displaystyle W}$ ${\displaystyle R}$

Like the simulated cooling , the deluge algorithm is usually less efficient with regard to the (local) optimum found than evolution strategies , but not as complex.

See also

• Deterministic annealing

literature

• Gunter Dueck , The Flood Principle. A mathematics novel , Springer Verlag Berlin, 2nd edition, 2006, ISBN 354033873X