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 (Wasserstand) und eine Konstante Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} (Regen) definiert. Von einem zufälligen Startwert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} ausgehend wird nun iterativ ein neuer Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x'} im Suchraum erzeugt und genau dann akzeptiert, wenn er oberhalb von liegt, d. h., er muss besser sein als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W} . Er darf aber schlechter sein als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} . Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W} wird dabei regelmäßig um Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 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
Literatur
- Gunter Dueck, Das Sintflutprinzip. Ein Mathematik-Roman, Springer Verlag Berlin, 2. Auflage, 2006, ISBN 354033873X
