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

Question

Monte-Carlo MethodとEvolutionary Algorithmsの関係はなんですか？その面では、複雑な問題を解決するために使用される無関係なシミュレーション方法であるように見えます。どのような種類の問題がそれぞれ最適ですか？彼らは同じ問題を解決することができますか？両者の関係は何か（もしあれば）？

Answer 1

「モンテカルロ」は、私の経験上、過度に負荷がかかる用語です。人々は、乱数ジェネレータ（グローバル最適化、シナリオ分析（Google "Excel Monte Carloシミュレーション"）、確率的統合（the Pi calculation、みんながMCを実証するために使用する）を使用するあらゆるテクニックにこれを使用するように思われます。あなたの質問では、あなたは数学的な最適化のためのモンテカルロのテクニックについて話しています：いくつかの入力パラメータを持つフィットネス関数をいくつか持っていて、その関数を最小限に抑えたい（または最大化したい）場合

関数がうまく動作する（あなたが最初に入力に関係なく到着する単一のグローバルな最小値があります）、共役勾配法のような確定的な最小化技法を使うのが最良です。多くの機械学習分類技法は、四角訓練セットに関する超平面の誤差。この場合最小化されている関数は、n次元空間で滑らかで、よく振舞われた放物線である。グラジエントを計算し、下り坂を下ります。簡単なピーシー。

ただし、入力パラメータが離散的（またはフィットネス機能に不連続性がある場合）の場合、勾配を正確に計算することはできません。これは、1つ以上の変数の表データを使用してフィットネス関数を計算した場合に発生します（変数Xが0.5未満の場合は、この表を使用します）。あるいは、バッチジョブとして実行する異なるチームによって書かれた20のモジュールで構成されているNASAのプログラムを持っているかもしれません。あなたはそれを入力し、数字を吐き出す（ブラックボックスと思う）。あなたが始める入力パラメータによっては、誤った最小値に終わることがあります。グローバル最適化技術は、これらのタイプの問題に対処しようとします。

進化的アルゴリズムは、global optimization技術の1つのクラスを形成します。グローバル最適化技術は、典型的には、ある種の「山登り」（より高い（悪い）フィットネス機能を持つ構成を受け入れる）ことを含む。この山登りには、通常、ランダム性/確率論的/モンテカルロ性が含まれます。一般に、これらの手法は、あまり最適でない構成を早期に受け入れる可能性が高く、最適化が進むにつれて、劣った構成を受け入れる可能性は低くなります。

進化的アルゴリズムは、進化論的類推に基づいている。シミュレーテッドアニーリングは、金属のアニーリングに類似しています。パーティクルスウォームのテクニックは、生物システムにも影響を受けます。すべての場合、結果を単純なランダム（モンテカルロ法など）の構成のサンプリングと比較する必要があります。これは、しばしば同等の結果をもたらします。

私は、確率的/モンテカルロ法よりもはるかに少ない関数評価しか必要としないので、決定論的勾配に基づく手法を使い始めることを勧めます。あなたは馬のステップがシマウマではないと思うと聞きます。いくつかの異なる出発点から最適化を実行し、特に厄介な問題に対処しない限り、ほぼ同じ最小値で終了する必要があります。そうでない場合は、シマウマを持っている可能性があり、グローバルな最適化方法の使用を検討する必要があります。

Answer 2

よく私はモンテカルロ法は最適化の問題を解決するために 乱数を使用するこれらのメソッドの一般的な名前だと思います。このように、 乱数を使用すると、進化的アルゴリズムさえもモンテカルロ法の一種です（実際にはそうです）。

他モンテカルロ法は：メトロポリス、ワン・ランダウ、レプリカ交換法など

OTOH、進化方法は使用「技術」性質から借用など 突然変異、クロスオーバーなど