巡回セールスマン問題(by. GA)

[Mr. Wing]

初めて投稿します. 実験レポートの課題です.
課題1が

Individual *create_generation(void) {
    return (Individual *)malloc(sizeof(Individual) * num_ind);
}

というのはわかったのですが, 課題2以降から手も足も出ず, 四苦八苦しています.
ほぼ丸投げのような状態で大変恐縮ですが, どうか皆さんのお力添えを頂きたく存じます.
長くなりますので, プログラム本体は別で投稿いたします.
長文で申し訳ないですが, 何卒宜しくお願い申し上げます.

遺伝的アルゴリズムで巡回セールスマン問題を解く

・ 遺伝的アルゴリズムにおける処理の流れ
Step0: 巡回セールスマン問題を遺伝的アルゴリズムで解くための前処理(課題2)
        ↓
Step1: 親の世代に属する全個体と、子の世代に属する全個体を生成(課題1)
        ↓
Step2: 親の世代に属する各個体の遺伝子型(都市の巡回経路)、適応度を設定(課題3,4,5)
        ↓
Step3: 交叉(両親の遺伝子型を混ぜ合わせる)に参加する親(2個体)を選択(課題6,7)
        ↓
Step4: 交叉を実行し、子(2個体）の遺伝子型を仮決定(課題10)
        ↓
Step5: 子の遺伝子を突然変異させ(課題8)、子の遺伝子型を最終決定
        ↓
Step6: 複数の親に対してStep3-5を実行し、次世代の子(子の世代）を決定(課題11)
        ↓
Step7: 子を新たな親にする(copy_generation関数)
        ↓
Step8: 新たな親の世代で適応度が最大、最小の個体を決定(課題9)
        ↓
Step9: Step3へ (Step3-9の処理を１世代。これをN世代繰り返す)

・ 巡回セールスマン問題
課題は各都市を0から9で表し, 都市iと都市j間の距離をdouble型配列distの(i, j)要素に格納する(i, jは0から9).

・ 配列dist
     0     1     2      3     4     5     6     7     8     9   → j
 0  0.0   0.2   0.001  1.4   2.1   9.1   20.1  29.0  9.0   10.0
 1  0.2   0.0   45.5   1.0   0.1   0.01  22.1  2.1   0.1   120.0
 2  0.001 45.5  0.0    55.0  10.0  0.01  0.002 0.01  2.01  200.1 
 3  1.4   1.0   55.0   0.0   4.0   2.1   0.01  1.1   20.1  40.0
 4  2.1   0.1   10.0   4.0   0.0   22.1  90.0  22.0  1.0   1.0
 5  9.1   0.01  0.01   2.1   22.1  0.0   79.0  2.1   0.1   2.0
 6  20.1  22.1  0.002  0.01  90.0  79.0  0.0   0.1   4.1   0.01
 7  29.0  2.1   0.01   1.1   22.0  2.1   0.1   0.0   3.1   30.1
 8  9.0   0.1   2.01   20.1  1.0   0.1   4.1   3.1   0.0   10.1
 9  10.0  120.0 200.1  40.0  1.0   2.0   0.01  30.1  10.1   0.0
↓
i

・ 最短巡回経路
都市0→都市1→都市5→都市8→都市4→都市9→都市6→都市3→都市7→都市2→都市0

・ 巡回経路距離の例
ある個体のgenoが|0|2|3|5|1|9|4|7|8|6|のとき
セールスマンの巡回径路: 都市0→都市2→都市3→都市5→都市1→都市9→都市4→都市7→都市8→都市6(→都市0)
巡回経路距離 ＝ dist[0][2] + dist[2][3] + dist[3][5] + dist[5][1] + dist[1][9] + dist[9][4] + dist[4][7] + dist[7][8] + dist[8][6] + dist[6][0]

・ 距離データファイル
データの区切り: ホワイトスペース
データの並びと距離データd[j]の関係:
・ 1行目から始める. i,jの初期値は0.  
・ 左端から右端に向けて, データがある毎にjを1ずつ増加する.
・ jがNum_City-1なったら, iを1増やし, jは0にする.
・ 行末まで来たら, 次の行の左端へ行く.

・ 距離データファイルの例(Num_City = 10)
   0.0   0.2   0.001  1.4   2.1   9.1   20.1  29.0  9.0   10.0   0.2
   0.0   45.5  1.0   0.1   0.01  22.1  2.1   0.1   120.0   0.001
   45.5  0.0   55.0  10.0  0.01  0.002 0.01  2.01  200.1
   1.4   1.0   55.0   0.0   4.0   2.1   0.01  1.1   20.1  40.0
   2.1   0.1   10.0   4.0   0.0   22.1  90.0  22.0  1.0   1.0    9.1   0.01
   0.01   2.1   22.1  0.0   79.0  2.1   0.1   2.0
   20.1  22.1  0.002  0.01  90.0  79.0  0.0   0.1   4.1   0.01
   29.0  2.1   0.01   1.1   22.0  2.1   0.1   0.0   3.1   30.1
   9.0   0.1   2.01   20.1  1.0   0.1   4.1   3.1   0.0   10.1
   10.0  120.0 200.1  40.0  1.0   2.0   0.01  30.1  10.1   0.0

・ 突然変異
二つの遺伝子(都市)をランダムに選び交換する操作
例.
         遺伝子2,6に突然変異
            ↓    ↓
遺伝子型: |0|2|4|3|6|1|7|5|8|9| → |0|6|4|3|2|1|7|5|8|9|
                      遺伝子(都市)2と6を交換

以上が課題の説明文です. 加えて, 適応度に関する画像も添付しておきます.

[Mr. Wing]

/* 
** fitness = 1/巡回経路距離** コマンド行のオプション
** 第1オプション: 距離データ保存ファイルを指定
** 第2オプション: 出力用ファイルを指定
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

#define Num_City 10                // 全都市数

/* Individual型(Individual型のオブジェクト: 個体) */
typedef struct {
    unsigned short geno[Num_City]; // 遺伝子型: セールスマンが巡回する都市の経路
    double fitness;                // 個体の適応度: 個体が持つ遺伝子型(巡回経路)の優秀さ(巡回経路距離の短さ)を示す指標
} Individual;

/* グローバル変数 */
double dist[Num_City][Num_City]; // ２都市間の距離を納める配列
int num_ind;                     // 全個体数

/* 関数プロトタイプ宣言 */
int set_city(FILE *);
Individual *create_generation(void);
double sum(Individual *);
void set_geno(Individual *);
void set_fitness(Individual *);
void initialize_population(Individual *);
int compare(unsigned short, unsigned short, unsigned short *);
void bubble(unsigned short *, unsigned short *, unsigned short *);
void cross_over(Individual *, Individual *, Individual *, Individual *);
Individual *pick_up(Individual *, double);
void next_generation(Individual *, Individual *, double, double);
void copy_generation(Individual **, Individual **);
void statistics(Individual *, int *, int *);
void mutation(Individual *);

プログラム自体も長くなるので何度かに分けて投稿します.

[Mr. Wing]

int main(int argc, char *argv[/url]) {
    int i;
    int seed;           // 乱数の種
    int num_generation; // 世代数
    int imax;           // 適応度が最大の個体番号
    int imin;           // 適応度が最小の個体番号
    double sum_fitness; // 各個体の適応度の和
    double mu_rate;     // 突然変異率
    
    FILE *fl[2] = {NULL};
    char *mode[2] = {"r", "w"};
    char f_name[20] = {'\0'};
    char line[100] = {'\0'};
    
    Individual *old_pop = NULL; // 親の世代を指すポインタ
    Individual *new_pop = NULL; // 子の世代を指すポインタ
    
    /*  ファイルをオープン */
    if (argc == 3) {
        for (i = 0; i < argc - 1; ++i) {
            sprintf(f_name, "%s", argv[i + 1]);
            
            if ((fl = fopen(f_name, mode)) == NULL) {
                printf("ファイルを開けません\n");
                return 1;
            }
        }
    } else {
        printf("コマンドオプションは2つです");
        return 1;
    }

    /* 個体数を入力(偶数－>親は二人必要) */
    printf("個体数を入力[偶数]:");
    if (fgets(line, sizeof(line), stdin) != NULL) {
        if ((sscanf(line, "%d", &num_ind) != 1) || (num_ind <= 0) || (num_ind % 2 != 0)) {
            printf("個体数の入力が正しくありません。");
            return 1;
        }
    } else {
        printf("個体数の入力でエラー。");
        return 1;
    }
    
    /* 世代数を入力 */
    printf("世代数を入力:");
    if (fgets(line, sizeof(line), stdin) != NULL){
        if ((sscanf(line, "%d", &num_generation) != 1) || (num_generation <= 0)){
            printf("世代数の入力が正しくありません。");
            return 1;
        }
    } else {
        printf("世代数の入力でエラー。");
        return 1;
    }
    
    /* 突然変異率を入力 */
    printf("突然変異率を入力[0以上1.0以下]:");
    
    if (fgets(line, sizeof(line), stdin) != NULL){
        if ((sscanf(line, "%lf", μ_rate) != 1) || (mu_rate < 0) || (mu_rate > 1)) {
            printf("突然変異率の入力が正しくありません。");
            return 1;
        }
    } else {
        printf("突然変異率の入力でエラー。");
        return 1;
    }
    
    /* 乱数の種を決める */
    printf("乱数の種を入力[整数値]:");
    if (fgets(line, sizeof(line), stdin) != NULL) {
        if (sscanf(line, "%d", &seed) != 1) {
            printf("乱数値の入力が正しくありません。");
            return 0;
        }
    } else {
        printf("乱数値の入力でエラー。");
        return 1;
    }
    
    /* 乱数の種を設定 */
    srand(seed);
    
    /* 親の世代の個体を生成 */
    if ((old_pop = create_generation()) == NULL) {
        printf("メモリを確保できません\n");
        return 1;
    }
    
    /* 子の世代の個体を生成 */
    if ((new_pop = create_generation()) == NULL) {
        printf("メモリを確保できません\n");
        return 1;
    }
    
    /* 都市間の距離データを入力 */
    if (set_city(fl[0]) == 1) {
        printf("ファイルからのデータ入力に失敗しました\n");
        return 1;
    }
    
    /* 親の個体を初期化(遺伝子型および適応度の設定) */
    initialize_population(old_pop); 
    
    for(i = 0; i < num_generation; ++i) {
        /* 親の世代における適応度(フィットネス)の合計値を計算 */
        sum_fitness=sum(old_pop); 
        
        /* 交叉により親の世代から子の世代を作る */
        next_generation(old_pop, new_pop, sum_fitness, mu_rate);
        
        /* 世代を更新 */
        copy_generation(&old_pop, &new_pop);
        
        /* 新しい親の世代で適応度が最大、または最小の個体を探査 */
        statistics(old_pop, &imax, &imin);
        
        /* 新しい親個体の適応度の合計値を計算 */
        sum_fitness=sum(old_pop);
        
        /* 世代iで最大の適応度を出力 */
        //fprintf(fl[1], "%lf\n", old_pop[imax].fitness);
    }
    
    /* ファイルをクローズ */
    fclose(fl[0]);
    fclose(fl[1]);
    
    /* 確保した記憶域を開放 */
    free(new_pop);
    free(old_pop);
    
    return 0;
}

Individual *create_generation(void) {
    return (Individual *)malloc(sizeof(Individual) * num_ind);
}

int set_city(FILE *fp) {
    /* 課題 2 */
}

void set_geno(Individual *ind) {
    /* 課題 3 */
}

void set_fitness(Individual *ind) {
    /* 課題 4 */
}

void initialize_population(Individual *pop) {
    /* 課題 5 */
}

double sum(Individual *pop) {
    /* 課題 6 */
}

Individual* pick_up(Individual *pop, double sum_fitness) {
    /* 課題 7 */
} 

void mutation(Individual *ch) {
    /* 課題 8 */
}

void statistics(Individual *pop, int *imax, int *imin) {
    /* 課題 9 */
}

void cross_over(Individual *p1, Individual *p2, Individual *c1, Individual *c2) {
    /* 課題 10 */
}

void next_generation(Individual *old_pop, Individual *new_pop, double sum_fitness, double mu_rate) {
    /* 課題 11 */
}

void copy_generation(Individual **old_pop, Individual **new_pop) {
    Individual *tmp;
    tmp = *old_pop;
    *old_pop = *new_pop;
    *new_pop = tmp;
}

プログラムの続きです.

[Mr. Wing]

課題の内容は以上です.
月曜日が締め切りなので, できればこの土日に答えていただけたら幸いです.
皆さん, どうか宜しくお願い申し上げます.

[たいちう]

> 月曜日が締め切りなので, できればこの土日に答えていただけたら幸いです.

課題を代わりにやってあげるための掲示板ではないので、
Mr. Wingさんが課題を解く力を付けるためのアドバイスならできます。
頑張り次第ですが、締め切りに間に合わない可能性も高いですね。
それでよければ、課題2から始めましょう。

テキストファイルから数値を読む部分です。
fscanfを使うのが最も簡単でしょう。
データのテキストファイルを用意して、出来るところまで書いてください。
また、正しく読みこめたことを確認するために、set_cityの処理が終わってから、
distの内容を全てprintfしてください。

[Mr. Wing]

たいちうさん、お答えいただきありがとうございます。
課題2の部分は、

int set_city(FILE *fp) {
    int i, j;
    
    for (i = 0; i < Num_City; i++) {
        for (j = 0; j < Num_City; j++) {
            fscanf(fp, "%f", &dist[j]);
        }
    }
    
    for (i = 0; i < Num_City; i++) {
        for (j = 0; j < Num_City; j++) {
            printf("%f ", dist[j]);
        }
        printf("\n");
    }
}

としてみたのですが、distの中身が全部ゼロで出力されてしまいました。
それに、「このような書き方では文字判定ができないので、エラー処理ができないのでは？」
という疑問もあり、行き詰っている状態です。
いいわけになるかもしれませんが、自分はC言語を勉強しているときに
ファイルリダイレクトばかり使っていたので、ファイル入出力に関してかなり疎いようです。

[たいちう]

> としてみたのですが、distの中身が全部ゼロで出力されてしまいました。

scanf系の書式指定を確認してください。


> それに、「このような書き方では文字判定ができないので、エラー処理ができないのでは？」
> という疑問もあり、行き詰っている状態です。

まずは理想的なデータだけを処理できるプログラムを作ってはどうですか？
時間的余裕があれば、その後でエラー処理を追加することもできます。

[Mr. Wing]

返信が遅くなりまして、申し訳ないです。

> scanf系の書式指定を確認してください。
書式指定が間違っているということでしょうか？
fscanfの文法的には問題ないと思うのですが・・・。

ちなみに・・・、紛らわしい書き方をしてしまって恐縮ですが、
「ゼロ」というのは0.0のことです。


> まずは理想的なデータだけを処理できるプログラムを作ってはどうですか？
上記のfor文はそのつもりで作っていたものです。
while文にしてみたり、fgetsを使ってみたり、
こちらにお聞きする前に色々試してみたのですが、全部ダメでした。

[たいちう]

> 書式指定が間違っているということでしょうか？
> fscanfの文法的には問題ないと思うのですが・・・。

間違っているから確認を促しているのです。