大洪水アルゴリズム

大洪水アルゴリズム( GD ) は、最適化問題に適用される汎用アルゴリズムです。これは、山登り法やシミュレーテッド アニーリング法のアルゴリズムと多くの点で似ています。

この名前は、大洪水の際、丘を登る人が水位が上昇するにつれて上る道を見つけようと、足が濡れない方向に進もうとするという例え話から来ています。

GD の一般的な実装では、アルゴリズムは最適解の劣った近似値Sから開始します。不良度と呼ばれる数値はSに基づいて計算され、初期の近似値がどれだけ望ましくないかを測定します。不良度の値が高いほど、近似解は望ましくないことを意味します。許容値と呼ばれる別の数値は、初期の不良度を含む多くの要因に基づいて計算されます。

Sに基づいて、Sの近傍と呼ばれる新しい近似解S'が計算されます。 S'の悪さ、b'が計算され、許容値と比較されます。b'が許容値よりも良い場合、アルゴリズムはS  : = S'、およびtolerance  := decay(tolerance)で再帰的に再開されます。ここでdecay は、許容値を下げる関数です (水位の上昇を表します)。b' がtolerance よりも悪い場合、 Sの別の近傍S*が選択され、プロセスが繰り返されます。 Sのすべての近傍がtolerance を超える近似解を生成する場合、アルゴリズムは終了し、得られた最良の近似解としてSが提示されます。

• de:ギュンター・デューク

• Gunter Dueck: 「新しい最適化ヒューリスティック: Great Deluge アルゴリズムとレコード間移動」、技術レポート、IBM ドイツ、ハイデルベルク科学センター、1990 年。
• グンター・デューク: 「新しい最適化ヒューリスティックス: 大洪水アルゴリズムとレコードからレコードへの移動」、計算物理学ジャーナル、第 104 巻、第 1 号、p. 86-92、1993 年