Sintflutalgorithmus

Der Sintflutalgorithmus (englisch great deluge algorithm) ist ein heuristisches Optimierungsverfahren der Informatik. Es ist verwandt mit der simulierten Abkühlung und wird meist für Optimierungsprobleme eingesetzt, die durch ihre hohe Komplexität das vollständige Ausprobieren aller Möglichkeiten und 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 $W$ (Wasserstand) und eine Konstante $R$ (Regen) definiert. Von einem zufälligen Startwert $x$ ausgehend wird nun iterativ ein neuer Wert $x'$ im Suchraum erzeugt und genau dann akzeptiert, wenn er oberhalb von $W$ liegt, d. h., er muss besser sein als $W$. Er darf aber schlechter sein als $x$. $W$ wird dabei regelmäßig um $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 auch die simulierte Abkühlung ist der Sintflutalgorithmus in der Regel hinsichtlich des gefundenen (lokalen) Optimums weniger effizient als etwa Evolutionsstrategien, dafür aber nicht so aufwändig.

Siehe auch

• Deterministic Annealing

Literatur

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