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

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

ただいまの
回答率

88.36%

Cでナップザック問題を遺伝的アルゴリズムで解くときに問題がありました。

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 4,849

wanntinntyann

score 12

前提・実現したいこと

遺伝的アルゴリズムでナップザック問題を解こうとしてます。
しかし遺伝的アルゴリズムをプログラムするのは初めてだし、
プログラムが正しいか自信がないのでわからないところを質もします。
Visual Studio 2015でやりました。

発生している問題・エラーメッセージ

エラーはでていませんが、実行して「初期集団決め→評価→選択→交叉→変異→評価→・・・」
の順にやっているんですが、実行結果を見ると所々で値が小さくなったりしてます。
これは問題ありということでしょうか?
 例えば5世代目の値が「価:174」なのに6世代目になると「価値:150」みたいに落ちているということです。

該当のソースコード

C言語とC++を併用してコーディングしました。交叉のところは一点交叉で行いました。
またそれ以外の欠陥、改善点があったらどうか教えてください。

include <iostream>

include <stdio.h>

include <cmath>

include <algorithm>

include <ctime>

using namespace std;

const int N = 100;  //ナップザックの容量
const int M = 30;   //品物の数
const int MAN = 10;  //子孫の数

int Child[MAN][M];  //子孫の遺伝子情報
int Kati[MAN];      //子孫のそれぞれの価値
int Ryou[MAN];      //子孫のそれぞれの容積

//ナップザックに入れる物の情報。価値と大きさ
struct Mono {
    int Money;
    int ryou;
};
Mono mono[M];

void init();                    //初期集団を決める
void hyoka();                    //それぞれの個体の価値を集計
void sentaku(int *oya);         /*集団から次の世代を作るための親を決める。
                                引数のoya配列には親の添え字を保存する*/
void Sex(int *oya);                //sentaku関数で選んだ親から子孫を作る
void heni();                    //突然変異を起こす
void show();                    //それぞれの価値と大きさを表示

int main()
{
    init();
    hyoka();

    int oya[2];
    for (int i = 0; i < 1000; i++) {
        sentaku(oya);
        Sex(oya);
        heni();
        hyoka();
        show();
    }

    return 0;
}

void init()
{
    //価値と大きさはランダムで決める
    srand((unsigned int)time(NULL));

    for (int i = 0; i < M; i++) {
        mono[i].Money = rand() % 20 + 1;
        mono[i].ryou = rand() % 10 + 1;
    }

    cout << "価値: ";
    for (int i = 0; i < M; i++) {
        cout << mono[i].Money << ",";
    }
    cout << endl;

    cout << "大きさ: ";
    for (int i = 0; i < M; i++) {
        cout << mono[i].ryou << ",";
    }
    cout << endl;

    for (int i = 0; i < MAN; i++) {
        for (int j = 0; j < M; j++) {
            Child[i][j] = rand() % 2;
        }
    }
}

void hyoka()
{

    for (int i = 0; i < MAN; i++) {
        Kati[i] = 0;
        Ryou[i] = 0;
    }

    int sum = 0;
    for (int i = 0; i < MAN; i++) {
        for (int j = 0; j < M; j++) {
            if (Child[i][j] == 1) {
                sum += mono[j].ryou;
                if (sum > N) {
                    Kati[i] = 0;
                    break;
                }
                else {
                    Kati[i] += mono[j].Money;
                    Ryou[i] += mono[j].ryou;
                }
            }
        }
        sum = 0;
    }
}

//ルーレット方式で親を決定する
void sentaku(int* oya)
{
    int total = 0;
    for (int i = 0; i < MAN; i++) {
        total += Kati[i];
    }

    int k = 0;
    int kazu = 0;
    int kazu2 = 0;
    for (int i = 0; i < 2; i++) {
        //同じ親を選ばないように同じなら別を選ぶようにする
        while (kazu == kazu2) {
            kazu = rand() % total;
        }
        kazu2 = kazu;
        for (int j = 0; j < MAN; j++) {
            //ルーレットなので乱数より大きくなったらその遺伝子を親にする
            if (kazu < Kati[j]) {
                //親の遺伝子がある配列の添え字を保存
                oya[k] = j;
                k++;
                break;
            }
        }
    }
}

void Sex(int *oya)
{
    for (int i = 2; i < MAN; i += 2) {
        /*一点交叉する境界をランダムに求める。
        その境界をもとに子孫を2人作る*/
        int line = rand() % M + 2;
        for (int j = 0; j < line; j++) {
            Child[i][j] = Child[oya[0]][j];
        }
        for (int j = line; j < M; j++) {
            Child[i][j] = Child[oya[1]][j];
        }
        for (int j = 0; j < line; j++) {
            Child[i + 1][j] = Child[oya[1]][j];
        }
        for (int j = line; j < M; j++) {
            Child[i + 1][j] = Child[oya[0]][j];
        }
    }
}

void show()
{
    cout << "価値: ";
    for (int i = 0; i < MAN; i++) {
        cout << Kati[i] << ",";
    }
    cout << endl;

    cout << "量:   ";
    for (int i = 0; i < MAN; i++) {
        cout << Ryou[i] << ",";
    }
    cout << endl;

    int max = Kati[0];
    int ryou = Ryou[0];
    for (int i = 1; i < MAN; i++) {
        if (max < Kati[i]) {
            max = Kati[i];
            ryou = Ryou[i];
        }
    }

    cout << "(" << max << "," << ryou << ")" << endl;
}

void heni()
{
    for (int i = 0; i < MAN; i++) {
        int kazu = rand() % 100;
        if (kazu < 3) {
            int kazu2 = rand() % M;
            Child[i][kazu2] = (Child[i][kazu2] + 1) % 2;
        }
    }
}

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 2

checkベストアンサー

+1

値が一度小さくなるのは親世代での最適値がうまくコピーされてないからだと思います。自分がよく使うGAは
1.配列にランダムデータ作成
2.評価
3.評価の良い順で一定確率Aで配列内に適宜コピー
4.一定確率Bで交差
5.一定確率Cで突然変異
6.2.に戻る
こんな感じです。A,B,Cのパラメータ変えると収束率が変わります。整数型の最適化問題では解の空間が滑らかではないので局所最大化問題とは別に、局所の山に崖があって、崖から転げ落ちる状態が発生します。現状では前世代での最適な遺伝子が(交差や突然変異で)死亡するので解の値が悪くなっています。つまり死亡率が高いので要素の数を増やし優秀な遺伝子が生き残る確率を上げたほうがいいでしょう。
すごく単純な解決としては前回最適な値を無傷で次世代に残したら解が後退することはないですね。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

+1

Priceの要素を全部を足したものをTotalとし、
0-Totalからランダムで値を取っていますが、
それをPriceの個別の要素と比較していますね。

この状態では、殆どの確立でif文内部を通りません。
よって、oya配列に親となるはずの要素番号は入らず、
oya配列の初期化されていない値で、配列にアクセスすることになります。

また、一度でもif文内を通った場合においても同様に、
前の親として使われた要素番号がそのまま使われるということが起こり、
意図した挙動とは違う挙動になっていると思います。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

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