確率的最適化

確率的最適化( SO ) は、ランダム変数を生成して使用する最適化手法です。確率的最適化問題では、目的関数または制約がランダムです。確率的最適化には、ランダム反復法も含まれています。一部のハイブリッド手法は、確率的最適化の両方の意味を組み合わせて、ランダム反復法を使用して確率的問題を解決します。^{[ 1 ]} 確率的最適化手法は、決定論的問題に対する決定論的手法を一般化したものです。

部分的にランダムな入力データは、リアルタイム推定および制御、モンテカルロシミュレーションを実際のシステムの推定値として実行するシミュレーションベースの最適化^{[ 2 ] [ 3 ]}、および基準の測定に実験的（ランダム）誤差がある問題などの分野で発生します。このような場合、関数値がランダムな「ノイズ」によって汚染されているという知識は、統計的推論ツールを使用して関数の「真の」値を推定したり、次のステップについて統計的に最適な決定を下したりするアルゴリズムに自然につながります。この種のメソッドには、次のものがあります。

• 確率近似法（SA）、RobbinsとMonro（1951）^{[ 4 ]}
• 確率的勾配降下法
• キーファーとウォルフォウィッツによる有限差分SA（1952年）^{[ 5 ]}
• Spall (1992) による同時摂動 SA ^{[ 6 ]}
• シナリオ最適化

一方、データセットが精密な測定値から構成されている場合でも、一部の手法では探索プロセスにランダム性を導入して進行を加速させます。^{[ 7 ]}このようなランダム性によって、この手法はモデリングエラーに対する感度を低くすることもできます。もう1つの利点は、探索プロセスにランダム性を導入することで、極値統計を介して関数の最小値の区間推定値を取得できることです。^{[ 8 ] [ 9 ]} さらに、注入されたランダム性によって、この手法は局所最適解から脱出し、最終的に大域最適解に近づくことができます。実際、このランダム化原理は、多くのデータセットにわたって、多くの種類の問題に対してほぼ確実に良好なパフォーマンスを均一に実現するアルゴリズムを得るための、シンプルかつ効果的な方法であることが知られています。この種の確率的最適化手法には、次のものがあります。

• S. Kirkpatrick、CD Gelatt、MP Vecchiによるシミュレーテッドアニーリング（1983） ^{[ 10 ]}
• 量子アニーリング
• DH Wolpert、SR Bieniawski、DG Rajnarayanによる確率集団（2011） ^{[ 11 ]}
• ロベルト・バッティティ、G. テッキオリによるリアクティブサーチ最適化（RSO） （1994年） ^{[ 12 ]}は、最近参考書^{[ 13 ]でレビューされた。}
• ルビンシュタインとクローゼによる交差エントロピー法（2004）^{[ 14 ]}
• Anatoly Zhigljavskyによるランダム検索(1991) ^{[ 15 ]}
• 情報検索^{[ 16 ]}
• 確率的トンネル効果^{[ 17 ]}
• 並列テンパリング、別名レプリカ交換^{[ 18 ]}
• 確率的丘登り
• 群知能アルゴリズム
• 進化アルゴリズム
  • ホランドによる遺伝的アルゴリズム（1975年） ^{[ 19 ]}
  • 進化戦略
• カスケードオブジェクト最適化および変更アルゴリズム（2016）^{[ 20 ]}

対照的に、ランダム化は決定論的アルゴリズムがそもそも設計不良であった場合にのみ、決定論的アルゴリズムを改善できると主張する著者もいる。^{[ 21 ]} Fred W. Glover ^{[ 22 ]}は、ランダム要素への依存は、よりインテリジェントで優れた決定論的コンポーネントの開発を妨げる可能性があると主張している。確率的最適化アルゴリズムの結果が通常提示される方法（たとえば、N 回の実行のうち平均値、あるいは最良の結果のみを提示し、ばらつきについては一切言及しない）も、ランダム性に対する肯定的なバイアスにつながる可能性がある。

• グローバル最適化
• 機械学習
• シナリオ最適化
• ガウス過程
• 状態空間モデル
• モデル予測制御
• 非線形計画法
• エントロピー値が危険にさらされている

• Michalewicz, Z. および Fogel, DB (2000)、『How to Solve It: Modern Heuristics』、Springer-Verlag、ニューヨーク。

• COSP