1

遺伝的アルゴリズムを使用して部分和問題を解決するプロジェクトを行う必要があります。残念ながら、アルゴリズムをコーディングしているときに大きな問題が見つかりました...

私のアルゴリズム:

  • 解決策が見つからず、ステップ数がステップ数よりも少ない限り:
  • 各染色体の確率と分布関数を計算する
  • 選択を行う（ルーレット）
  • 交差させるn個の染色体を選択する
  • 交差点を実行します（交差点はランダムに選択されます）
  • 突然変異させるm染色体を選択する
  • 突然変異を行う
  • 解決策を見つけた場合は停止します

(アルゴリズムは本「遺伝的アルゴリズム + データ構造 = 進化プログラム、第 2 章」から引用) （ステップ内の）交差点の数は、プログラムオプションで厳密に設定されています。

問題は、集団内で特定の (比較的少ない) 数のステップの後、すべての染色体が同一になることです。問題はこのグラフを示しています: http://imageshack.us/m/96/7693/wykresb.png

私が間違っていることは何ですか？修正方法は？前もって感謝します。

編集：

ここで、私のアプリからのログを見つけることができます: http://paste.pocoo.org/show/391318/

ルーレットは最善の解決策ではないと思います (deong が言ったように)。突然変異も改善する必要があります。

4

3 に答える 3

3

ここに（潜在的に）問題があります。免責事項はもちろん、バグのあるプログラムを持っている可能性があるということです。

ルーレットホイールの選択はひどいものです。問題は、実行の早い段階で、フィットネス値の分布がランダムであることです。いくつかのひどい解決策と、比較して妥当な解決策があります。それらのどれもが非常に優れているとは期待しませんが、いくつかは他のものよりもはるかに優れていると期待できます。

ルーレット ホイールの選択は、これらの確率の相対的な違いを取り、それらを増幅します。母集団のサイズが 100 で、1 人の個体のフィットネスが他の個体の 5 倍優れている場合、その個体は 5 倍の頻度で選択されます。典型的な軽度の突然変異率では、組換えのために同じ個体を 2 回選択し、いくつかの新しい同一の子孫を生成し、非常に小さな変更 (おそらく) を行ってから、それらを集団に戻すという状況にすぐに陥ります。あなたはまだ実行の初期段階にあるため、ほとんどのソリューションはまだ悪いので、平均以上のソリューションが 1 つあった場合、それを平均以上の 5 つのソリューションに選択し、それらを繁殖させて平均以上のソリューションを 10 個取得し、すべてのプロセスを開始しました。もう一度。これらのソリューションは、もしあなたが'

解決策は、より優れた選択演算子を使用することです。バイナリ トーナメントの選択は、より高速で、コーディングが容易であり、より許容できる選択圧力を適用します。絶対的な違いではなく、フィットネス ランキングによって比例して選択するランク バイアス選択もあります。

編集：これは、比例選択を使用できないと言っているわけではありません。収束が早すぎる傾向があり、それを効果的に使用するには、通常、それを念頭に置いて一連の演算子全体を構築する必要があります。

于 2011-05-18T10:57:20.903 に答える
1

遺伝的アルゴリズムを適用すると、アルゴリズムが局所的な最適値で動かなくなることがあります。ただし、大域的最適 (または、そのような最適の近似) に関心があります。

ローカル最適は、次の方法で回避できます。

  • より高い突然変異率
  • 別のクロスオーバー機能

さらに、クローンを殺すのに役立つ場合があります。つまり、反復ごとに母集団を「すばやく」見て、クローンを許可しないということです。簡単に言うと、正確なクローンを確認するには O(m*n^2) かかるため、おおよそのクローンを探すだけです。ここで、n は母集団のサイズで、m は染色体のサイズです。この方法は、クローンに直面していた別の問題にも役立ちました。

これが役に立てば幸いです、クリスチャン

編集

クロスオーバー関数を投稿できればそれもいいでしょう。できればコードとしてではなく、プレーンな英語のテキストで。交差関数は、遺伝的アルゴリズムの重要な部分です。

于 2011-05-18T10:56:51.343 に答える
1

私は以前に同様の問題を抱えていました。それがあなたのものと同じであることを願っています

まず、染色体 A が染色体 B よりも優れているかどうかを (任意の測定基準を使用して) チェックする必要があります。

次に、新しい染色体を (突然変異または交叉のいずれかによって) 生成するとき、集団内に既に存在する染色体を生成している可能性があります。これを人口リストに含めないでください。

言い換えれば、リストには常に異なる染色体が含まれており、常に最良のものから最悪のものへとソートされていることを確認してください!

注: 私が扱っている遺伝的アルゴリズムは通常、次のようなものです (これは最も一般的なアルゴリズムであり、最も使用されています)。

  • P 個の異なる染色体を作成し、リスト Pop に追加します。
    1. while (最適解が見つからない && 反復回数 < LIM)
    2. クロスオーバー、突然変異、またはその他の方法を使用して新しい染色体を作成します。
    3. 作成した染色体をリストに追加します Pop
    4. リストポップを並べ替えます（最適なものから最悪のものへ）
    5. 最初の P 個の異なる染色体を選択し、Pop から他のすべてを破棄します。
    6. 終了する
于 2011-05-19T04:57:34.590 に答える