6

遺伝的アルゴリズムで解決しようとしている問題があります。問題は、100個の整数のサブセット（たとえば4）を選択することです（これらの整数は、他の何かを表す単なるIDです）。順序は重要ではありません。問題の解決策は、順序付きリストではなく整数のセットです。適応度関数は良いのですが、クロスオーバー関数に問題があります。

次の2つの染色体を交配できるようにしたいと思います。

[1 234]と[3456]を何か便利なものに。明らかに、通常のクロスオーバー関数を使用できません。これは、無効なソリューションを表す重複が子供に発生する可能性があるためです。この場合の最良のクロスオーバー方法は何ですか。

4

5 に答える 5

3

両方のセット (つまり、それらの共通部分) に出現する要素を無視します。つまり、そのような要素は両方のセットで変更されません。

要素の残りの部分は 2 つの互いに素なセットを形成し、複製を取得することなく、ほぼすべてのランダムな変換 (たとえば、いくつかのペアをランダムに交換) を適用できます。

これは、一致する要素が互いに向き合うように両方のセットを順序付けて整列し、標準的なクロスオーバー アルゴリズムの 1 つを適用することと考えることができます。

于 2010-12-14T11:21:38.283 に答える
2

検索がより迅速に収束するように、ソリューションを「範囲外」にすることが有益な場合があります。4つの一意の整数のセットを染色体の要件にするのではなく、整数の数（およびそれらの一意性）を適応度関数の一部にします。

于 2010-12-14T04:51:16.213 に答える
2

順序は関係ないので、すべての数値を配列に集め、配列をソートし、重複を捨てます (リンクされたリストからそれらを切断するか、負の数に設定するなどして)。配列をシャッフルして、最初の 4 つの数字を取得します。

于 2011-04-03T11:28:35.597 に答える
1

「典型的なクロスオーバー」の意味がよくわかりませんが、順列によく使用されるものと同様のクロスオーバーを使用できると思います。

  • 最初の親からm 個のint を取得します ( m < n、 n はセット内の int の数)
  • 2番目をスキャンし、そこからサブセットを（まだサブセットにない）空きの（ nm ）整数で埋めます。

このようにして、重複することなく、最初の親からn 個の ints と 2 番目の親からnm個の ints を持つことができます。

私にとって有効なクロスオーバーのように聞こえます:-)。

順序付きセットに対してどちらのステップも実行しないこと (または、返された要素の順序が int の自然な順序付けと何らかの形で相関するイテレータを使用すること) を行わないことが有益であると思います。子供があなたの検索を偏らせています。

それが最善の方法であるかどうかは、解決したい問題によって異なります...

于 2010-12-14T08:35:08.023 に答える
1

セット A と B を結合するために、x が S に含まれる確率が (x を含む A、B からのセットの数) / 2 になるように、結果のセット S を確率的に選択できます。交差点とユニオンに含まれ、カーディナリティ 4 が期待されます。

于 2010-12-14T11:46:30.907 に答える