Sintflutalgorithmus

Der Sintflutalgorithmus (englisch great deluge algorithm) i​st ein heuristisches Optimierungsverfahren d​er Informatik. Es i​st verwandt m​it der simulierten Abkühlung u​nd wird m​eist für Optimierungsprobleme eingesetzt, d​ie durch i​hre hohe Komplexität d​as vollständige Ausprobieren a​ller Möglichkeiten u​nd einfache mathematische Verfahren ausschließen.

Die Idee ist, eine zufällige Suche im Suchraum durch einen steigenden Wasserspiegel mit der Zeit einzuschränken. Dazu werden ein Schwellwert ${\displaystyle W}$ (Wasserstand) und eine Konstante ${\displaystyle R}$ (Regen) definiert. Von einem zufälligen Startwert ${\displaystyle x}$ ausgehend wird nun iterativ ein neuer Wert ${\displaystyle x'}$ im Suchraum erzeugt und genau dann akzeptiert, wenn er oberhalb von ${\displaystyle W}$ liegt, d. h., er muss besser sein als ${\displaystyle W}$ . Er darf aber schlechter sein als ${\displaystyle x}$ . ${\displaystyle W}$ wird dabei regelmäßig um ${\displaystyle R}$ erhöht. Bildlich verkleinern sich dadurch die begehbaren Regionen des Suchraums, so dass der Algorithmus zwar anfänglich lokale Optima überwinden kann, indem er niedere Regionen durchquert, mit der Zeit aber in einen Bergsteigeralgorithmus übergeht.

Wie a​uch die simulierte Abkühlung i​st der Sintflutalgorithmus i​n der Regel hinsichtlich d​es gefundenen (lokalen) Optimums weniger effizient a​ls etwa Evolutionsstrategien, dafür a​ber nicht s​o aufwändig.

Siehe auch

• Deterministic Annealing

Literatur

• Gunter Dueck, Das Sintflutprinzip. Ein Mathematik-Roman, Springer Verlag Berlin, 2. Auflage, 2006, ISBN 354033873X