montecarlo - モンテカルロ法と進化的アルゴリズムの比較対照

Question

モンテカルロ法と進化的アルゴリズムの関係は? 一見すると、それらは複雑な問題を解決するために使用される、無関係なシミュレーション方法のように見えます。それぞれどの種類の問題に最適ですか? 彼らは同じ一連の問題を解決できますか? 2つの関係は何ですか（もしあれば）？

Answer 1

私の経験では、「モンテカルロ」は非常に過負荷な用語です。人々は、乱数発生器を使用するあらゆる手法 (グローバル最適化、シナリオ分析 (Google の「Excel モンテカルロ シミュレーション」)、確率的統合 (誰もが MC を実証するために使用するPi 計算) に使用しているようです)。数学的最適化のためのモンテカルロ法について話している質問の進化的アルゴリズム:いくつかの入力パラメーターを持つある種のフィットネス関数があり、その関数を最小化 (または最大化) したい。

関数の動作が適切である場合 (開始時の入力に関係なく到達する単一のグローバルな最小値がある場合)、共役勾配法などの確定最小化手法を使用することをお勧めします。多くの機械学習分類手法では、トレーニング セットに関して超平面の最小二乗誤差を最小化するパラメーターを見つける必要があります。この場合に最小化される関数は、n 次元空間の滑らかで適切に動作する放物面です。勾配を計算して坂を下ります。簡単です。

ただし、入力パラメーターが離散的である場合 (またはフィットネス関数に不連続性がある場合)、勾配を正確に計算することはできなくなります。これは、フィットネス関数が 1 つ以上の変数の表形式のデータを使用して計算されている場合に発生する可能性があります (変数 X が 0.5 未満の場合はこのテーブルを使用し、それ以外の場合はそのテーブルを使用します)。あるいは、バッチ ジョブとして実行するさまざまなチームによって作成された 20 個のモジュールで構成される、NASA から取得したプログラムを使用することもできます。入力を与えると、数字が吐き出されます (ブラックボックスを考えてください)。最初の入力パラメーターによっては、偽の最小値になる場合があります。グローバル最適化手法は、この種の問題に対処しようとします。

進化的アルゴリズムは、グローバル最適化手法の 1 つのクラスを形成します。グローバル最適化手法には、通常、ある種の「山登り」 (より高い (より悪い) 適合度関数を持つ構成を受け入れる) が含まれます。この山登りには通常、ランダム性/確率性/モンテカルロ性が含まれます。一般に、これらの手法は初期段階で最適でない構成を受け入れる可能性が高く、最適化が進むにつれて、劣悪な構成を受け入れる可能性は低くなります。

進化的アルゴリズムは、進化的アナロジーに大まかに基づいています。シミュレーテッド アニーリングは、金属のアニーリングとの類似性に基づいています。粒子群技術も生物系から着想を得ています。すべての場合において、構成の単純なランダム (別名「モンテカルロ」) サンプリングと結果を比較する必要があります。これにより、多くの場合、同等の結果が得られます。

私のアドバイスは、一般的に確率的/モンテカルロ手法よりもはるかに少ない関数評価を必要とするため、決定論的勾配ベースの手法を使用して開始することです。蹄の音を聞くと、シマウマではなく馬だと思います。いくつかの異なる開始点から最適化を実行すると、特に厄介な問題を扱っていない限り、ほぼ同じ最小値になるはずです。そうでない場合は、シマウマがいる可能性があり、グローバル最適化手法の使用を検討する必要があります。

Answer 2

モンテカルロ法は、最適化問題を解くために乱数を使用するこれらの方法の総称だと思います。このように、乱数を使用する進化的アルゴリズムでさえ、モンテカルロ法の一種です (実際に乱数を使用しています)。

その他のモンテカルロ法には、メトロポリス、ワンランダウ、パラレル テンパリングなどがあります。

OTOH、進化的方法は、突然変異、交差などの自然から借用した「技術」を使用します.