シミュレートされたアニーリングと遺伝的アルゴリズムの違いは何ですか？

Question

パフォーマンスとユースケースの観点から、シミュレートされたアニーリング（Bean検索）と遺伝的アルゴリズムの間に関連する違いは何ですか？

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

また、私はSAがGAまたはGAよりも優れている状況を考えようとしています。私が理解するのに役立つ簡単な例のほんの1つで十分です。

Answer 1

厳密に言えば、これら2つのこと -焼き鈍し法 （sa）と 遺伝的アルゴリズム アルゴリズムでも、目的の「データマイニング」でもありません。

どちらもです メタフルーリスティック- 抽象化スケールの「アルゴリズム」を上回るレベルのいくつか。言い換えれば、どちらの用語も高レベルのメタファーを指します。それは冶金から、もう1つは進化生物学から借りたものです。メタヒューリスティックの分類法では、saはaです 単一状態の方法 およびgaはaです 人口法 （PSO、Aco、et alとともにサブクラスで、通常 生物学的にインスパイアされたメタフルーリスティック).

これらの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つの方法のいずれかで作成されます。 1つ目は通常「エリート主義」と呼ばれ、実際には、通常、最高ランクの候補ソリューションを取得し、次世代にまっすぐに通過するだけで、それらをまっすぐに渡すことを指します。人口の新しいメンバーが通常「突然変異」と「クロスオーバー」と呼ばれる他の2つの方法。変異は通常、現在の母集団からの候補ソリューションベクトルの1つの要素の変化を伴い、新しい母集団に溶液ベクトルを作成します。 、2]。クロスオーバー操作の結果は、ベクターがセックスをすることができた場合に起こるようなものです。IEは、2人の親のそれぞれからの要素が構成されている新しい子ベクターです。

したがって、これらはGAとSAのアルゴリズムの違いです。パフォーマンスの違いはどうですか？

実際には：（私の観察結果は組み合わせの最適化の問題に限定されています）GAはほぼ常にSAを打ち負かします（コスト関数から低い「最高の」リターン値を返します - IE、ソリューションスペースのグローバル最小値に近い値）が、計算コスト。私が知る限り、教科書と技術出版物は解決に関する同じ結論を暗唱しています。

しかし、ここにあります：GAは本質的に並行可能です。さらに、各集団を含む個々の「検索エージェント」はメッセージを交換する必要がないため、そうするのは些細なことです。明らかにそれは意味します GA計算は分散できます, 、それは意味します 実際には、より良い結果（グローバル最小値に近い）とパフォーマンスの向上（実行速度）を得ることができます。

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

Answer 2

彼らは異なるドメインからインスピレーションを受けたので、2つを比較することは本当に難しいです。

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

一方、シミュレーションアニーリングは、可能なソリューションの空間で1つのソリューションのみを追跡します。各反復では、隣接するソリューションに移動するか、現在のソリューションにとどまるか（時間の経過とともに減衰する）かどうかを検討します。これは、すべての隣接するソリューションが現在のソリューションで最悪の場合から立ち止まる可能性があるため、ローカルオプティムの問題に悩まされないという点で、ヒューリスティック検索（たとえば貪欲な検索）とは異なります。

Answer 3

私はこれらのアルゴリズムの専門家からはほど遠いですが、私は手伝ってみます。

2つの最大の違いは、GAのクロスオーバーのアイデアであると思います。したがって、SAよりもGAに適した学習タスクの例は、その状況でクロスオーバーが意味するものとそれがどのように実装されるかについて依存しています。

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

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