-1

各変数が範囲 [-n, n] に属する n 個の整数変数 x1..xn の関数を最大化するための遺伝的アルゴリズムを実装しようとしています。染色体を表現するためにバイナリエンコーディングを使用することを考えていますが、負の整数をエンコードする方法がわかりません。かなり長い間検索してきましたが、バイナリ エンコーディングの一般的な式に出くわしませんでした。遺伝的アルゴリズムで [-n,n] の範囲の整数をエンコードする最も一般的な方法は何ですか? クロスオーバーとミューテーションの複雑さを軽減したい (条件チェックを減らしたい)。初期母集団で、-n から n の間の数値を生成する代わりに、0 から 2n までの数値を生成してバイナリでエンコードし、デコード中に毎回 (後続の世代ごとに) n を減算するとうまくいきますか?

4

1 に答える 1

2

user1765444の答えは理にかなっています...そして、sashkelloの提案を読んだだけです(オフセットバイナリを使用すると、GA内の符号付きintを気にする必要がなくなります)。shashkello と user1765444 の両方の回答の組み合わせを使用すると、クロスオーバーや変異などを行うのは簡単です。問題は、データ型の幅が範囲よりも大きい場合、クロスオーバーによって無効な子が生成される可能性があることです。

int32 が必要な幅を持っているとしましょう。次にint32配列[n]。32n ビットあることがわかっているので、m >=0 かつ m < 32n のランダムな m でクロスオーバー ポイントを取得できます。ビット m が配列 [m/n] で発生し、ビット位置 m%n が msb から始まることがわかっています (配列が 1 つの長いバイナリ文字列であると想像してください)。

次に、2 つの親 int32 parent1[n] と int32 parent2[n] があるとします。次の疑似的なコードのようなものですか？このクロスオーバーでは、クロスのために文字列は単なるバイナリ文字列です (つまり、符号ビットは別のビットとして扱われます)...

免責事項: 申し訳ありませんが、以下のコードは大まかな準備ができており、コンパイルされていないため、エラーが含まれている可能性があります...ただの考えです!

int child1[n];
uint32 m = rand_like_func(); // random cross over point, a bit position
                             // in the binary string of length n*32;
uint32 arraySlotForCrossOvr = (uint32)(m / n);
uint32 bitInSlotForCrossOvr = 31 - m % n;
uint32 maskForCrossOvrP2 = (1 << bitInSlotForCrossOvr) - 1;
uint32 maskForCrossOvrP1 = ~maskForCrossOvrP2;

// crossover to create child 1
memcpy(child1, parent1, arraySlotForCrossOvr);
child1[arraySlotForCrossOvr] = 
    (int32)( ((uint32)parent1[arraySlotForCrossOvr] & maskForCrossOverP1) |
             ((uint32)parent2[arraySlotForCrossOvr] & maskForCrossOvrP2) )
memcpy(
    child1, 
    parent2 + arraySlotForCrossOvr + 1, 
    total_num_slots - arraySlotForCrossOvr);

次に、範囲外の子供を検出するか、次のラウンドで範囲外の子供のスコアをゼロにする必要があります。おそらく、無効な値を最も近い有効な値に制限するなどのインテリジェンスでクロスオーバーを強化できますか?

それが役に立ったことを願っていますか？

また、問題のエンコーディングなどを理解しようとするときに、「それを解決する方法: Z. Michalewicz と D Fogel による最新のヒューリスティック」が非常に役立つことがわかりました :)

于 2013-04-22T23:25:37.213 に答える