imported>Aka: ISBN-Format, Kleinkram

2024-12-23T14:49:00Z

ISBN-Format, Kleinkram

Neue Seite

Der '''Sintflutalgorithmus''' (englisch ''great deluge algorithm'') ist ein [[Heuristik|heuristisches]] [[Optimierungsalgorithmus|Optimierungsverfahren]] der [[Informatik]]. Es ist verwandt mit der [[Simulierte Abkühlung|simulierten Abkühlung]] und wird meist für [[Optimierungsproblem]]e 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 <math>W</math> (''Wasserstand'') und eine Konstante <math>R</math> (''Regen'') definiert. Von einem zufälligen Startwert <math>x</math> ausgehend wird nun iterativ ein neuer Wert <math>x'</math> im Suchraum erzeugt und genau dann akzeptiert, wenn er oberhalb von <math>W</math> liegt, d. h., er muss besser sein als <math>W</math>. Er darf aber schlechter sein als <math>x</math>. <math>W</math> wird dabei regelmäßig um <math>R</math> erhöht. Bildlich verkleinern sich dadurch die begehbaren Regionen des Suchraums, so dass der Algorithmus zwar anfänglich [[Extremwert|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 [[Evolutionärer Algorithmus|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 3-540-33873-X

[[Kategorie:Optimierungsalgorithmus]]

Sintflutalgorithmus - Versionsgeschichte

imported>Aka: ISBN-Format, Kleinkram