19

シミュレーテッドアニーリング（Bean検索を使用）と遺伝的アルゴリズムのパフォーマンスとユースケースの点で、関連する違いは何ですか？

SAは人口サイズが1つしかないGAと考えることができることは知っていますが、2つの主な違いはわかりません。

また、SAがGAを上回ったり、GAがSAを上回ったりする状況を考えています。私が理解するのに役立つ簡単な例を1つだけで十分です。

4

3 に答える 3

72

厳密に言えば、シミュレーテッドアニーリング（SA）と遺伝的アルゴリズムの2つは、アルゴリズムでも、その目的である「データマイニング」でもありません。

どちらもメタヒューリスティックであり、抽象化スケールで「アルゴリズム」よりも2、3レベル上です。言い換えれば、両方の用語は、高レベルの比喩を指します。1つは冶金学から、もう1つは進化生物学から借用したものです。メタヒューリスティック分類法では、SAは単一状態の方法であり、GAは母集団の方法です（PSO、ACOなどとともにサブクラスで、通常は生物学的に着想を得たメタヒューリスティックと呼ばれます）。

これらの2つのメタヒューリスティックは、最適化問題を解決するために使用されます。特に（排他的ではありませんが）組み合わせ最適化（別名制約満足プログラミング）で使用されます。組み合わせ最適化とは、個別のアイテムのセットから選択することによる最適化を指します。つまり、最小化する連続関数はありません。ナップサック問題、巡回セールスマン問題、板取り問題はすべて組み合わせ最適化問題です。

データマイニングとの関連は、多くの（ほとんど？）監視対象の機械学習（ML）アルゴリズムのコアが、最適化問題の解決策であるということです（たとえば、多層パーセプトロンとサポートベクターマシン）。

アルゴリズムに関係なく、キャップの問題を解決するための解決手法は、基本的に次の手順で構成されます（通常、再帰ループ内の単一のブロックとしてコード化されます）。

  1. ドメイン固有の詳細をコスト関数でエンコードします（c / o問題の「解決策」を構成するのは、この関数から返される値の段階的な最小化です）。

  2. 最初の「推測」（反復を開始するため）を渡すコスト関数を評価します。

  3. コスト関数から返された値に基づいて、コスト関数の後続の候補解（またはメタヒューリスティックに応じて複数）を生成します。

  4. 引数セットでコスト関数に渡すことにより、各候補解を評価します。

  5. ある収束基準が満たされるか、最大反復回数に達するまで、ステップ（iii）と（iv）を繰り返します。

メタヒューリスティックは上記のステップ（iii）に向けられています。したがって、SAとGAは、コスト関数による評価のための候補ソリューションを生成する方法が異なります。言い換えれば、ここで、これら2つのメタヒューリスティックの違いを理解することができます。

非公式には、組み合わせ最適化の解に向けられたアルゴリズムの本質は、コスト関数から返される値がより悪い候補解をどのように処理するかです。現在の最良の候補解（コスト関数から最小値を返す解）よりも。最適化アルゴリズムがそのような候補解を処理するための最も簡単な方法は、それを完全に拒否することです-それが山登りアルゴリズムが行うことです。しかし、これを行うことにより、単純な山登り法は、丘によって現在の解決策から分離されたより良い解決策を常に見逃します。言い換えると、洗練された最適化アルゴリズムには、現在の最良の解よりも悪い（つまり、上り坂の）候補解を（一時的に）受け入れるための手法が含まれている必要があります。解決。

では、SAとGAはどのようにして候補ソリューションを生成するのでしょうか。

SAの本質は通常、より高コストの候補解が受け入れられる確率で表されます（二重括弧内の式全体は指数です。

p = e((-highCost - lowCost)/temperature)

またはPythonで：

p = pow(math.e, (-hiCost - loCost) / T)

「温度」項は、最適化の進行中に値が減衰する変数です。したがって、反復回数が増えると、SAがより悪い解を受け入れる確率が低下します。

言い換えると、アルゴリズムが反復を開始すると、Tが非常に大きくなります。これにより、アルゴリズムは、現在の最良のソリューションよりも良いか悪いかにかかわらず、新しく作成されたすべての候補ソリューションに移動します。ソリューション空間をランダムウォークします。反復回数が増えると（つまり、温度が下がるにつれて）、アルゴリズムによる解空間の検索は、T = 0になるまで、単純な山登りアルゴリズムと同じになります（つまり、現在の最良の解よりも優れた解のみ）。解決策は受け入れられます）。

遺伝的アルゴリズム非常に異なります。一つには、これは大きなことですが、単一の候補解ではなく、「それらの母集団」全体を生成します。これは次のように機能します。GAは、母集団の各メンバー（候補解）のコスト関数を呼び出します。次に、コスト関数から返された値の順に、それらを最良から最悪の順にランク付けします（「最良」は最も低い値を持ちます）。これらのランク付けされた値（および対応する候補ソリューション）から、次の母集団が作成されます。人口の新しいメンバーは、基本的に3つの方法のいずれかで作成されます。最初のものは通常「エリート主義」と呼ばれ、実際には通常、最高ランクの候補ソリューションを取得し、それらをそのまま（変更せずに）次世代に渡すことを指します。人口の新しいメンバーが通常呼ばれる他の2つの方法' 突然変異」と「クロスオーバー」。突然変異は通常、候補解ベクトルの1つの要素を現在の母集団から変更して、新しい母集団に解ベクトルを作成することを含みます。たとえば、[4、5、1、0、2] => [4、5、2、0 、2]。クロスオーバー操作の結果は、ベクトルが性別を持つことができる場合に何が起こるか、つまり、要素が2つの親のそれぞれからのいくつかで構成される新しい子ベクトルのようになります。

つまり、これらはGAとSAのアルゴリズムの違いです。パフォーマンスの違いはどうですか？

実際には:(私の観察は組み合わせ最適化の問題に限定されています）GAはほとんど常にSAを上回ります（コスト関数からより低い「最良の」戻り値を返します-つまり、ソリューションスペースのグローバル最小値に近い値）が、より高い計算コスト。私の知る限り、教科書と技術出版物は解決について同じ結論を述べています。

しかし、ここに問題があります。GAは本質的に並列化可能です。さらに、各母集団を構成する個々の「検索エージェント」はメッセージを交換する必要がないため、そうするのは簡単です。つまり、互いに独立して機能します。明らかに、これはGA計算を分散できることを意味します。つまり、実際には、はるかに優れた結果（グローバル最小値に近い）とパフォーマンス（実行速度）を得ることができます。

どのような状況でSAはGAを上回る可能性がありますか？私が思う一般的なシナリオは、SAとGAの結果が実質的に同じであるように、ソリューションスペースが小さい最適化問題ですが、実行コンテキスト（たとえば、バッチモードで実行される何百もの同様の問題）は、より高速なアルゴリズム（常にSAである必要があります）。

于 2010-11-04T20:42:23.703 に答える
6

異なるドメインからインスピレーションを得ているため、2つを比較することは非常に困難です。

遺伝的アルゴリズムは、可能な解決策の母集団を維持し、各ステップで、可能な解決策のペアを選択し、それらを結合し（クロスオーバー）、いくつかのランダムな変更を適用します（突然変異）。アルゴリズムは、選択プロセスが適合基準に従って行われる「適者生存」の概念に基づいています（通常、最適化問題では、現在のソリューションを使用して評価された目的関数の値です）。クロスオーバーは、2つの優れたソリューションを組み合わせると、さらに優れたソリューションが得られることを期待して行われます。

一方、シミュレーテッドアニーリングは、可能なソリューションの空間で1つのソリューションのみを追跡し、各反復で、いくつかの確率（時間の経過とともに減衰する）に従って、隣接するソリューションに移動するか、現在のソリューションにとどまるかを検討します。これは、ヒューリスティック検索（欲張り検索など）とは異なり、隣接するすべてのソリューションが現在のソリューションで最悪の場合から解放される可能性があるため、局所最適の問題に悩まされることはありません。

于 2010-11-04T18:38:33.940 に答える
3

私はこれらのアルゴリズムの専門家からはほど遠いですが、私は助けようとします。

この2つの最大の違いは、GAでのクロスオーバーの考え方であると思います。したがって、SAよりもGAに適した学習タスクの例は、その状況でのクロスオーバーの意味とその実装方法に依存します。

クロスオーバーの考え方は、2つのソリューションを有意義に組み合わせて、より良いソリューションを生み出すことができるということです。これは、問題の解決策が何らかの方法で構造化されている場合にのみ意味があると思います。たとえば、マルチクラス分類では、特定のクラスを分類するのに優れた2つ（または多数）の分類器を使用し、投票してそれらを組み合わせて、はるかに優れた分類器を作成することを想像できます。もう1つの例は、ソリューションをツリーとして表現できる遺伝的プログラミングですが、2つのプログラムを組み合わせてより良いものを作成できる良い例を思い付くのは難しいと思います。

それらは実際には非常に類似したアルゴリズムであり、おそらく非常に異なる出発点から開発されたものであるため、互いに説得力のあるケースを思い付くのは難しいと思います。

于 2010-11-04T13:14:58.893 に答える