質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.34%

  • C++

    3764questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

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

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 429

rosbergf1

score 5

 前提・実現したいこと

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

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

 発生している問題

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

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

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)の乱数を発生させる関数です.

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+2

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

親世代がN人の場合

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/16 22:19

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

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

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

    キャンセル

  • 2018/05/16 22:26 編集

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

    キャンセル

+2

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


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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/16 20:51

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

    キャンセル

  • 2018/05/16 22:17

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

    キャンセル

  • 2018/05/16 22:55

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.34%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • C++

    3764questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。