遺伝的アルゴリズムにおける親のルーレット選択

Question

前提・実現したいこと

遺伝的アルゴリズムでの親のルーレット選択において、対象が２つの親が被らないようにしたいのですが、うまくいきません。
下のようなコードを書いているのですが、無限ループ（もしくはものすごい回数の繰り返し）が発生していてうまく結果が出ません。

他の選択方法は都合上, 考えておりません。
うまいこと被すことなく親を選びたいのですが, どうすればよろしいでしょうか？

発生している問題

無限ループ（ものすごい回数の親の選択の繰り返し）

該当のソースコードの一部

void GA(int Agent, int AS[N_MAX], int N_AS, int N_TS, int cs[N_MAX], int cs_a[N_MAX], double cs_p[N_MAX], double cs_e[N_MAX], double cs_k[N_MAX], double cs_F[N_MAX], int cs_exp[N_MAX], double cs_as[N_MAX], int cs_ts[N_MAX])
{
 　  int v[2] = {0, 0};
    double s, k, F_sum = 0;
    /*1つ目の親の選択*/
    j = 0;
    k = 0;
    s = MT() * F_sum;

 /*AS内の適合度の合計を計算*/
    for (i = 0; i < n_cs; i++)
    {
        /*cs[i]とcs_F[i]は引数*/
        if (AS[i] == 1 && cs[i] != 0)
            F_sum += cs_F[i];
    }

    /*親の添え字を決定する*/
    while(k < s) {
        if (AS[j] == 1 && cs[j] != 0)
            k += cs_F[j];
        /*親の添字を記録*/
        v[0] = j;
        j++;
        if(j == n_cs)
            j = 0;
    }

    /*重複しないように2つ目の親を選択*/
    while(1)
    {
        j = 0;
        k = 0;
        s = MT() * F_sum;
        /*親の添え字を決定する*/
        while(k < s) {
            if (AS[j] == 1 && cs[j] != 0)
                k += cs_F[j];
            /*親の添字を記録*/
            if(v[1] != v[0])
                v[1] = j;
            j++;
            if(j == n_cs)
                j = 0;
        }
        /*親の対象がかぶってなければ終了*/
        if(v[0] != v[1])
            break;
    }
}

###　補足
MT()は(0,1)の乱数を発生させる関数です.

Answer 1

F_sumが常に0なのでsが常に0です
恐らくこれはあなたの意図した動作ではないと思います

---

実際のコードじゃありませんと言われた挙げ句、
変数名が暗号じみているので適当に動作を推測して回答します。

kにcs_F[]を足しこんで累積分布を作り、
kが初めてs=[0,F_sum)を超えるところを探して親を選択していると思いますが、
コード見る限り1回目と2回目で同じ分布を使って、
2回目は被ったら再抽選するという方法だと思います。
このように同じ分布を使うと、1回目で選択された親は当然2回目でも選択されやすくなります。
特にGAは世代が進むと特定の個体の適応度が著しく高くなりがちなので、再抽選が頻発します。

抽選2回目は、1回目で抽選した個体の適応度を抜いて、累積分布を作るようにしましょう。

Comments

[pepperleaf]

その結果、 v[0], v[1] が常に 0
> if(v[0] != v[1])
で、ループを抜けないですね。

[rosbergf1]

すみません、記述が抜けておりました。
実は、 F_sumにはcs_F[]の合計を入れる処理をやっていたためにこれがエラーの原因ではないです。

[pepperleaf]

22:55 現在のソースでも同様に、 s は常に 0のままです。
従って、無限ループのままです。

Answer 2

ソースは確認していませんが以下の手法ではいかがでしょう？

親世代がN人の場合

• 0～(N-1)から乱数'x'を得る。x=１人目の親の絶対位置
• 'x'番目を１人目の親とする。
• 1～(N-1)から乱数'y'を得る。y=１人目の親からの相対位置
• (x+y) % N 番目を２人目の親とする。

Comments

[rosbergf1]

ありがとうございます。参考になります。

1人目は乱数に決めると流石にまずいので, 1人目に関してはルーレット選択をしようと思います。
2人目は1人目の結果を利用してランダムに決めるというやり方みたいですが、どうも腑に落ちません。

2人目の決定でにっちもさっちもいかない場合はこの方法をとってみようと思います。

[can110]

ルーレット選択＝ランダムと勝手に解釈していましたが、正確には「適応度比例方式」のようですね。
であれば１人目は順当にルーレット選択で、２人目は、１人目を除いた適応度の降順に並べなおしたリストからランダムなり次点なりを選択すればよいかと思います。
肝は２人目を選ぶ対象から１人目を除くことです（よね？）。