ごめんなさい、これで最後です!遺伝的アルゴリズムの質問

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
mikamika33

ごめんなさい、これで最後です!遺伝的アルゴリズムの質問

#1

投稿記事 by mikamika33 » 5年前

さきほど質問させて頂いたのに何度も申し訳ございませんがこれで最後です!!
巡回セールス問題を遺伝的アルゴリズムを使って解こうとしていて、一通りコード書き終えたのですが、
どこが違うのか、結果を出力すると何カ所か同じ場所を巡回してしまっています、、、
もうずーーっと考えているのですがどこが間違っているのか分かりません、、、
ざっくりした質問で申し訳ないのですが、もしよければ間違いをご指摘ください!!
よろしくお願い致します(>_<)

コード:

#include <iostream>
#include <math.h>

#define SIZE 38
#define NUM_OF_GENES 12
//店舗のデータを格納するオブジェクトのクラス定義
class shops
{
private:
    double x;
    double y;
    char name[40];
public:
    void set_x(double x);
    void set_y(double y);
    void set_name(char *name);
    double get_x();
    double get_y();
    char* get_name();
};

//shopsクラスのメソッド定義
void shops::set_x(double _x) {
    x = _x;
}
void shops::set_y(double _y) {
    y = _y;
}
void shops::set_name(char *_name) {
    strcpy(name, _name);
}
double shops::get_x() {
    return x;
}
double shops::get_y() {
    return y;
}
char* shops::get_name() {
    return name;
}

//各店舗のデータを格納するshopsクラスのインスタンス生成
shops shop[SIZE];


////ランダムに巡回ルートを作成する関数
void makeRoute(int *gene);
//2店舗間の距離を返す関数
float getDistance(shops *shop1, shops *shop2);
//巡回ルートの合計距離を返す関数
float getTotalDistance(int *gene);
//遺伝子同士を交配する関数
void getNextGeneration(int (*genes)[SIZE]);

int main(void)
{
    printf("ラーメン二郎全店を巡回する最短ルートを探索しています...\n");
    //二郎全店舗名を入力する配列
    char names[SIZE][40] = {"三田本店", "目黒店", "品川店", "新橋店", "神田神保町店", "亀戸店", "環七一之江店", "小岩店", "千住大橋駅前店", "赤羽店", "西台駅前店", "桜台駅前店", "荻窪店", "環七新代田店", "上野毛店", "新宿小滝橋通り店", "歌舞伎町店", "池袋東口店", "仙川店", "ひばりヶ丘駅前店", "新小金井街道店", "府中店", "立川店", "八王子野猿街道店2", "めじろ台法政大学前店", "京急川崎店", "鶴見店", "横浜関内店", "中山駅前店", "相模大野店", "湘南藤沢店", "松戸駅前店", "京成大久保店", "茨城守谷店", "大宮店", "栃木街道店", "仙台店", "札幌店"};
    //各店舗のx座標
    double cordinates_x[SIZE] = {35.6480801, 35.6341918, 35.6238941, 35.6656255, 35.6963775, 35.7019335, 35.6840881, 35.7349536, 35.7425936, 35.7798005, 35.7868841, 35.7388065, 35.7035931, 35.6619732, 35.612421, 35.6964591, 35.6957565, 35.7282785, 35.6617852, 35.7500101, 35.7084359, 35.6720481, 35.6965106, 35.6295148, 35.6294833, 35.5349024, 35.4970884, 35.4421385, 35.5130707, 35.5299308, 35.3429086, 35.7860021, 35.6914847, 35.9240496, 35.9034403, 36.4236329, 38.26171009999999, 43.0673949};
    //各店舗のy座標
    double cordinates_y[SIZE] = {139.74161430000004, 139.70705120000002, 139.74299569999994, 139.75057130000005, 139.75646989999996, 139.82667820000006, 139.88195110000004, 139.88001039999995, 139.7970037, 139.72084730000006, 139.6748096, 139.66185940000003, 139.62628870000003, 139.66042670000002, 139.63897769999994, 139.69845810000004, 139.70192450000002, 139.7138357, 139.58388289999994, 139.54379649999998, 139.4962084, 139.47725300000002, 139.40952679999998, 139.40136670000004, 139.31035739999993, 139.705734, 139.66126680000002, 139.63070389999996, 139.53857500000004, 139.4329335, 139.48232830000006, 139.8994156, 140.04961500000002, 140.00057889999994, 139.62628459999996, 139.7956385, 140.86612300000002, 141.34382140000002};
    //店舗データの設定
    int i, j;
    for (i = 0; i < SIZE; i++) {
        shop[i].set_x(cordinates_x[i]);
        shop[i].set_y(cordinates_y[i]);
        shop[i].set_name(names[i]);
    }
    //巡回ルートのデータを持つ遺伝子の宣言
    int genes[NUM_OF_GENES][SIZE];
    //乱数の種を初期化
    srand((unsigned)time(NULL));
    //geneに巡回ルートを組み込む
    for (i = 0; i < NUM_OF_GENES; i++) {
        makeRoute(genes[i]);
    }
    //遺伝子の交配を繰り返す
    for (i = 0; i < 1000; i++) {
        getNextGeneration(genes);
    }
    //それぞれのルートの合計距離のソート
    float distance[NUM_OF_GENES]; //巡回ルートの合計距離を記録
    int rank[NUM_OF_GENES]; //ソート結果を記録
    for (i = 0; i < NUM_OF_GENES; i++) {
        rank[i] = i;
    }
    for (i = 0; i < NUM_OF_GENES; i++) {
        distance[i] = getTotalDistance(genes[i]);
    }
    int tmp;
    for (i = 0; i < NUM_OF_GENES; i++) {
        for (j = i + 1; j < NUM_OF_GENES - 1; j++) {
            if (distance[i] < distance[j]) {
                tmp = rank[i];
                rank[i] = rank[j];
                rank[j] = tmp;
            }
        }
    }
    printf("結果は以下のようになりました\n");
    for (i = 0; i < SIZE; i++) {
        printf("%d.%s\n", i + 1, shop[genes[rank[0]][i]].get_name());
    }
    printf("(合計距離:%f)\n", distance[rank[0]]);
    
    return 0;
}

//ランダムに巡回ルートを作成する関数の定義
void makeRoute(int *gene) {
    //配列の初期化
    int i;
    for (i = 0; i < SIZE; i++){
        gene[i] = i;
    }
    //シャッフルする
    int tmp;
    int num;
    for (i = 0; i < 1000; i++) {
        num = rand() % SIZE;
        tmp = gene[num];
        if (num == SIZE - 1) {
            gene[num] = gene[0];
            gene[0] = tmp;
        } else {
            gene[num] = gene[num + 1];
            gene[num + 1] = tmp;
        }
    }
}
//2店舗間の距離を返す関数の定義
float getDistance(shops shop1, shops shop2) {
    return sqrt(pow(shop1.get_x() - shop2.get_x(), 2) + pow(shop1.get_y() - shop2.get_y(), 2));
};

//巡回ルートの合計距離を返す関数の定義
float getTotalDistance(int* gene) {
    float result;
    result = 0;
    int i;
    for (i = 0; i < SIZE - 2; i++) {
        result += getDistance(shop[gene[i]], shop[gene[i+1]]);
    }
    return result;
}

//遺伝子同士を交配する関数
void getNextGeneration(int (*genes)[SIZE]) {
    int i, j;
    //それぞれのルートの合計距離のソート
    float distance[12]; //巡回ルートの合計距離を記録
    int rank[12]; //ソート結果を記録
    for (i = 0; i < NUM_OF_GENES; i++) {
        rank[i] = i;
    }
    for (i = 0; i < NUM_OF_GENES; i++) {
        distance[i] = getTotalDistance(genes[i]);
    }
    int tmp;
    for (i = 0; i < NUM_OF_GENES; i++) {
        for (j = i + 1; j < NUM_OF_GENES - 1; j++) {
            if (distance[i] < distance[j]) {
                tmp = rank[i];
                rank[i] = rank[j];
                rank[j] = tmp;
            }
        }
    }
    
    //親を決める
    int winners[21];
    for (i = 0; i < 21; i++) {
        if (i < 6) {
            winners[i] = rank[0];
        } else if (i < 11) {
            winners[i] = rank[1];
        } else if (i < 15) {
            winners[i] = rank[2];
        } else if (i < 18) {
            winners[i] = rank[3];
        } else if (i < 20) {
            winners[i] = rank[4];
        } else {
            winners[i] = rank[5];
        }
    }
    int a, b;
    int flag;
    int parents[3][2];
    for (i = 0; i < 3; i++) {
        flag = 1;
        while (flag) {
            a = rand() % 21;
            b = rand() % 21;
            if (winners[a] == winners[b]) {
                continue;
            } else {
                parents[i][0] = winners[a];
                parents[i][1] = winners[b];
                flag = !flag;
            }
        }
    }
    /*親を交配させる*/
    //交叉点を決め、交叉させる
    int cross_points[2] = {12, 27};
    int cross_relation[cross_points[1] - cross_points[0] + 1][2];
    int notCrossedPoint[SIZE];
    int flag2;
    int k;
    for (i = 0; i < 3; i++) {
        for (j = cross_points[0]; j < cross_points[1]; j++) {
            genes[rank[NUM_OF_GENES - (i * 2 + 1)]][j] = genes[parents[i][0]][j];
            genes[rank[NUM_OF_GENES - (i * 2 + 2)]][j] = genes[parents[i][1]][j];
        }
        //交叉した点の関係を記録する
        
        for (j = 0; j < cross_points[1] - cross_points[0] + 1; j++) {
            cross_relation[j][0] = genes[parents[i][0]][cross_points[0] + j];
            cross_relation[j][1] = genes[parents[i][1]][cross_points[0] + j];
        }
        //交叉していない点を記録する
        
        for (j = 0; j < SIZE; j++) {
            flag = 0;
            for (k = cross_points[0]; k < cross_points[1]; k++) {
                if (j == genes[parents[i][0]][k] || j == genes[parents[i][1]][k]) {
                    flag = 1;
                } else {
                    continue;
                }
            }
            if (flag) {
                notCrossedPoint[j] = j;
            } else {
                notCrossedPoint[j] = 40;
            }
        }
        //子供の残りの遺伝子を埋めていく
        
        for (j = 0; j < SIZE; j++) {
            if (j >= cross_points[0] && j < cross_points[1]) {
                continue;
            }
            flag = 0;
            flag2 = 0;
            for (k = 0; k < SIZE; k++) {
                if (genes[parents[i][0]][j] == notCrossedPoint[k]) {
                    flag = 1;
                }
                if (genes[parents[i][1]][j] == notCrossedPoint[k]) {
                    flag2 = 1;
                }
            }
            if (flag) {
                //交叉していない遺伝子だったらそのまま親から引き継ぐ
                genes[rank[NUM_OF_GENES - (i * 2 + 1)]][j] = genes[parents[i][0]][j];
            } else {
                //交叉している遺伝子だったら、交叉関係に基づき修正する
                for (k = 0; k < cross_points[1] - cross_points[0] + 1; k++) {
                    if (genes[parents[i][0]][j] == cross_relation[j][0]) {
                        genes[rank[NUM_OF_GENES - (i * 2 + 1)]][j] = cross_relation[k][1];
                    }
                    if (genes[parents[i][0]][j] == cross_relation[k][1]) {
                        genes[rank[NUM_OF_GENES - (i * 2 + 1)]][j] = cross_relation[k][0];
                    }
                }
            }
            if (flag2) {
                //交叉していない遺伝子だったらそのまま親から引き継ぐ
                genes[rank[NUM_OF_GENES - (i * 2 + 2)]][j] = genes[parents[i][1]][j];
            } else {
                //交叉している遺伝子だったら、交叉関係に基づき修正する
                for (k = 0; k < cross_points[1] - cross_points[0] + 1; k++) {
                    if (genes[parents[i][1]][j] == cross_relation[k][0]) {
                        genes[rank[NUM_OF_GENES - (i * 2 + 2)]][j] = cross_relation[k][1];
                    }
                    if (genes[parents[i][1]][j] == cross_relation[k][1]) {
                        genes[rank[NUM_OF_GENES - (i * 2 + 2)]][j] = cross_relation[k][0];
                    }
                }
            }
        }
    }
    //子供のいずれかに突然変異を起こさせる
    int n;
    flag = 1;
    n = rand() % NUM_OF_GENES/2 + (NUM_OF_GENES/2);
    while (flag) {
        a = rand() % SIZE;
        b = rand() % SIZE;
        if (a == b) {
            continue;
        } else {
            tmp = genes[rank[n]][a];
            genes[rank[n]][a] = genes[rank[n]][b];
            genes[rank[n]][b] = tmp;
            flag = !flag;
        }
    }
}

たいちう
記事: 418
登録日時: 8年前

Re: ごめんなさい、これで最後です!遺伝的アルゴリズムの質問

#2

投稿記事 by たいちう » 5年前

質問掲示板なので何度でも質問は歓迎されていますが、
新しいスレを立てる必要はないですね。
[解決!]になっていても継続できますが、あわてないで良いので、
納得できる結果を確認してから[解決!]にしてください。

ついでに、次回からはスレタイも適切なものに。
自己紹介やお詫びを書くスペースではありません。
これを機にフォーラムルールを読んでください。


で、本題。
交叉をコメントアウトすると重複が発生しないようです。
交叉の処理に重大な誤りがあるのでしょう。
交叉の処理が何をやっているつもりか、1行ずつ、あるいは、
ブロック毎に日本語で説明できますか?

各処理が意図したとおりに動いているかを
出力してしっかり確認しましょう。

mikamika33

Re:Re: ごめんなさい、これで最後です!遺伝的アルゴリズムの質問

#3

投稿記事 by mikamika33 » 5年前

>たいちうさん

フォーラムルール、きちんと読んでいませんでした、、
ちゃんと読んで、以降気をつけるようにします(´・ω・`)

はい、ご指摘頂いた通りよくよく交叉の箇所を見ると誤りがありました。
そこを訂正すると重複なく結果が出るようになりました!ありがとうございますヽ(*´∀`*)ノ
ただ、実行するたびに違う結果になってしまうので、ちゃんと最短距離が導きだせてないみたいですね、、
改善の余地がありそうです。頑張ります!!ヽ(。>д<)p

たいちう
記事: 418
登録日時: 8年前

Re: ごめんなさい、これで最後です!遺伝的アルゴリズムの質問

#4

投稿記事 by たいちう » 5年前

> ただ、実行するたびに違う結果になってしまうので、ちゃんと最短距離が導きだせてないみたいですね、、
> 改善の余地がありそうです。頑張ります!!ヽ(。>д<)p

時間ができたので、よく見ようとしてみたところ、交叉だけでなく、ソートもできていませんね。
90行目のgetTotalDistanceの後に、次の行を追加してください。
ソートの結果は期待したとおりですか?

printf("遺伝子%dが表わすルートの合計距離 : %f\n", i, distance);


残念ながら、ソートもできていない現状では、
「一応できたけど改善の余地がある」というには程遠い状況です。
特に交叉の実装はかなり難しいでしょう。


その人の力量にもよりますが、この位の複雑さのプログラムになってくると、
「プログラムを変更して、その結果を確認」というプロセスでは無駄が多すぎます。
じっくり考えることも大事ですが、処理の途中の状態を表示したり、デバッガで確認したりして、
どこまで期待通りに動いているかを直接確認することが最重要です。
工夫してデバッグしましょう。


提案です。以下のステップを1つずつ試してはどうでしょうか。

1.ランダムで遺伝子を作成し、成績順に表示する

GAでもなんでもないのですが、現状ではこれができていません。


2.突然変異のみでGAを作成する

簡単な実装例ですが、親世代を評価して下位半数を捨て、上位半数をコピーして倍に増やします。
これに突然変異を発生させて子世代とします。

これが一番簡単なGAでしょう。突然変異の発生率や遺伝子数・世代数は、色々試して調整してください。


3.選択の仕方を改善する

4.交叉を実装する

閉鎖

“C言語何でも質問掲示板” へ戻る