0

遺伝的アルゴリズム DLLを使用して、 DARP 問題を解決しようとしています。

問題は、正しい解決策を思いつくこともあれば、そうでないこともあります。私は問題の本当に単純なバージョンを使用していますが。アルゴリズムが評価したゲノムを調べたところ、同じゲノムを数回評価していることがわかりました。

同じ評価を何度もするのはなぜですか？そうしない方が効率的ではないでしょうか？

4

5 に答える 5

2

同じ染色体を 2 回評価することと、集団 (または異なる集団) で同じ染色体を複数回使用することには違いがあります。最初のものはおそらく回避できるでしょう。2番目は、そうではないかもしれません。

検討：

ある世代 G1 では、0011 と 1100 を交配し、それらを真ん中で交配し、幸運にもどの遺伝子も変異させることができず、最終的に 0000 と 1111 になります。生成し、アルゴリズムを続行します。

その後、後の世代の G2 では、最初のインデックスで 0111 と 1001 を結合し、(再び突然変異を無視して) 1111 と 0001 になります。そのうちの 1 つが既に評価されているのに、なぜ再度評価する必要があるのでしょうか? 特に、その関数の評価に非常にコストがかかる場合は、メモリに余裕がある場合は、以前の評価の結果を格納するためにハッシュ テーブル (またはそのようなもの) を保持することをお勧めします。

しかし！染色体の値をすでに生成したからといって、それを今後の結果に自然に含めてはならないというわけではありません。これにより、さらに変異したり、同じ集団の他のメンバーと交配したりできます。そうしないと、成功を事実上罰することになります。これは、やりたいこととは正反対です。染色体が世代から世代へと存続または再出現する場合、それはそれが適切な解決策であることを示す強い兆候であり、適切に選択された突然変異演算子は、それがグローバル最大値ではなくローカル最大値である場合、それを追い出すように行動します。

于 2012-10-02T18:05:35.680 に答える
1

なぜ GA が同じ個人を評価するのかについての基本的な説明は、GA が誘導されていないためであり、以前に見られた (または同時に見られた) ゲノムの再現は期待されるものです。

さらに便利なことに、あなたの質問は次の2つの異なるものとして解釈できます。

  1. フィットネス関数の評価に関連する高コスト。これは、ゲノムをハッシュすることで軽減できますが、メモリをトレードオフします。これは考えられますが、私はそれを見たことがありません。通常、GA は高次元空間を検索するため、非常にまばらなハッシュになってしまいます。

  2. 多くまたはすべてのメンバーが単一または少数のパターンに収束した集団: ある時点で、ゲノムの多様性は 0 に近づく傾向があります。これは、アルゴリズムが見つけた最適な解に収束したため、予想される結果です。これがあまりにも早く発生し、平凡な結果が得られた場合は、局所的最小値にとどまり、多様性を失うのが早すぎることを示しています。

この状況では、出力を調べて、2 つのシナリオのどちらが発生したかを判断します。

  1. 多様性を失うのは、特に健康な個人が親の宝くじの大部分を獲得するからです。または、
  2. 時間の経過に伴う人口は非常に静的であるため、多様性は得られません。

前者の場合、多様性を維持する必要があります。ターンオーバーを減らしたり、フィットネス関数をスケーリングしたりすることで、不適格な個人がより多くのチャンスを得られるようにします。

後者の場合、多様性を増やさなければなりません。おそらく突然変異率を上げたり、回転率を上げたりして、母集団により多くのランダム性を注入するようにしてください。

(もちろん、どちらの場合も、最終的には、GA が解空間に収束するにつれて多様性が減少することを望んでいます。そのため、「すべてのダイヤルを上げて」、モンテカルロ探索に移行したくないだけです。)

于 2012-09-30T18:20:11.157 に答える
0

基本的に遺伝的アルゴリズムは

  • 初期母集団（サイズN）
  • 適応度関数
  • 突然変異操作
  • クロスオーバー操作（通常、2人の個体に対して、ゲノムの一部を取得し、それを新しい個体に結合することによって実行されます）

すべてのステップでそれ

  1. ランダムな個人を選択します
  2. クロスオーバーを実行して、新しい個人を作成します
  3. おそらく突然変異を実行します（ランダムな個体のランダムな遺伝子を変更します）
  4. 適応度関数を持つすべての新旧の個人を評価する
  5. 次の反復で新しい母集団になるのに最適なNを選択します

適応度関数のしきい値に達するか、最後のK回の反復で母集団に変化がない場合、アルゴリズムは停止します。

したがって、それは最良の解決策ではなく、極大で停止する可能性があります。

人口の一部は、適応度関数の値が高い可能性があるため、反復ごとに変化しない可能性があります。また、突然変異のために以前のゲノムに「フォールバック」することも可能です。

遺伝的アルゴリズムをより良く機能させるための秘訣はたくさんあります。ゲノムにエンコードする適切な母集団を選択し、優れた適応度関数を見つけ、クロスオーバーと突然変異率で遊んでください。

于 2012-09-30T15:05:16.070 に答える
0

GA の詳細によっては、連続した集団で同じゲノムを持つ場合があります。たとえば、エリート主義は、各集団から最良のゲノムまたはn個の最良のゲノムを保存します。

ゲノムの再評価は、計算の観点からは非効率的です。これを回避する最も簡単な方法はHasFitness、各ゲノムにブール値フラグを設定することです。また、ゲノム エンコーディングごとに一意の文字列キーを作成し、すべての適合値を辞書に保存することもできます。このルックアップは非常に高価になる可能性があるため、これは、フィットネス関数がルックアップの追加費用を正当化するのに十分なほど高価な場合にのみ推奨されます。

于 2012-09-30T18:45:34.273 に答える
0

エリート主義は別として、GA は同じゲノムを繰り返し評価しません。あなたが見ているのは、同一のゲノムが再生成され、再評価されていることです。これは、各世代が新しいゲノムのセットであり、以前に評価されている場合とされていない場合があるためです。

再評価を避けるために、既に生成されたゲノムのリストを適合性とともに保持する必要があります。フィットネスにアクセスするには、新しい母集団のそれぞれをリストと比較する必要があります。リストにない場合は、それを評価してリストに追加する必要があります。

実際のアプリケーションには数千のパラメーターがあるため、最終的には数百万のゲノムが保存されます。これは、検索と維持に莫大な費用がかかります。そのため、毎回ゲノムを評価する方がおそらく速いでしょう。

于 2012-10-09T14:32:15.100 に答える