You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
121 lines
3.7 KiB
121 lines
3.7 KiB
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <math.h>
|
|
#include <time.h>
|
|
#include "tsp.h"
|
|
|
|
#define PRINT_GENE NO /* 遺伝子を表示（本来はオプションで指示するもの） */
|
|
#define PRINT_PROCESS NO /* 途中経過を表示（本来はオプションで指示するもの） */
|
|
|
|
void print_usage(char *command) /* 使用方法を表示する関数 */
|
|
{
|
|
fprintf(stderr, "Usage: %s <filename>\n", command);
|
|
}
|
|
|
|
void print_data(Gene_set gene_group[GENE_NUM]) /* データの表示 */
|
|
{
|
|
double best, sum, worst;
|
|
int i;
|
|
|
|
sum = 0;
|
|
best = worst = gene_group[0].length;
|
|
for(i = 0; i < GENE_NUM; i++) {
|
|
sum += gene_group[i].length; /* 平均を出すため合計を求める */
|
|
if (best > gene_group[i].length) {
|
|
best = gene_group[i].length; /* 最良値 */
|
|
}
|
|
if (worst < gene_group[i].length) {
|
|
worst = gene_group[i].length; /* 最悪値 */
|
|
}
|
|
}
|
|
printf("best = %g, ave = %g, worst = %g\n", best, sum/GENE_NUM, worst);
|
|
//printf("%g, %g, %g\n", best, sum/GENE_NUM, worst);
|
|
}
|
|
|
|
int main(int argc, char *argv[])
|
|
{
|
|
int i; /* カウンタ用 */
|
|
Position city[CITY_NUM]; /* 都市座標 */
|
|
Gene_set gene_group[GENE_NUM]; /* 遺伝子集団 */
|
|
FILE *fp; /* 座標用ファイル */
|
|
char string[BUFSIZ]; /* ファイル入力用バッファ */
|
|
int trial; /* 試行回数カウンタ */
|
|
int best_index; /* 最良個体のインデックス */
|
|
double best_length; /* 最良経路長 */
|
|
int gen_to_best; /* 最良値に達した世代数 */
|
|
|
|
srand((unsigned int)time(NULL)); /* rand() の種 */
|
|
|
|
/* コマンド引数処理 */
|
|
if (argc > 2) { /* コマンド引数が多すぎる */
|
|
print_usage(argv[0]); /* 使用方法を表示 */
|
|
exit(1); /* 終了 */
|
|
}
|
|
/* コマンド引数が無い時 */
|
|
else if (argc == 1) {
|
|
print_usage(argv[0]); /* 使用方法を表示 */
|
|
exit(1); /* 終了 */
|
|
}
|
|
#if 0
|
|
else if (argc == 1) {
|
|
initial_city(city); /* ランダムに都市を生成 */
|
|
fprintf(stderr, "RANDOM COORDINATES ARE USED!!\n");
|
|
}
|
|
#endif
|
|
/* コマンド引数が 1つ */
|
|
/* ファイルから都市座標を読みこみ */
|
|
else if(argc == 2) {
|
|
if((fp = fopen(argv[1], "r")) == NULL) {
|
|
/* ファイルオープン失敗 */
|
|
fprintf(stderr, "%s: %s can not be found\n", argv[0], argv[1]);
|
|
exit(1);
|
|
}
|
|
for(i = 0; (i < CITY_NUM) && (fgets(string, BUFSIZ, fp) != NULL);) { /* ファイルの終わりか都市数が設定に達するまで */
|
|
if((string[0] == '#')||(string[0] == '\n')) {
|
|
/* コメント行および空行 */
|
|
continue; /* 何も処理しない */
|
|
}
|
|
/* データ読み込み */
|
|
sscanf(string, "%d %d", &(city[i].x), &(city[i].y));
|
|
i++; /* 読みこんだ都市数を増やす */
|
|
}
|
|
fclose(fp);
|
|
}
|
|
|
|
/* CSVヘッダーの出力 */
|
|
printf("# Trial, MutationRate, SelectNum, BestLength, GenToBest\n");
|
|
|
|
for(trial = 0; trial < 10; trial++) {
|
|
/* 各種データの初期化 */
|
|
initial_gene(gene_group); /* 遺伝子集団の生成 */
|
|
initial_fitness(gene_group, city); /* 初期適合度の計算 */
|
|
|
|
/* 初期状態での最良経路長を取得 */
|
|
best_index = get_best_gene(gene_group);
|
|
best_length = gene_group[best_index].length;
|
|
gen_to_best = 0; /* 初期状態で最良 */
|
|
|
|
for(i = 0; i < GENERATION; i++) {
|
|
/* 選択 */
|
|
selection(gene_group);
|
|
|
|
/* 突然変異を起こす */
|
|
mutation(gene_group);
|
|
|
|
/* 適合度計算 */
|
|
calculate_fitness(gene_group, city);
|
|
|
|
/* 最良値の更新チェック */
|
|
best_index = get_best_gene(gene_group);
|
|
if (gene_group[best_index].length < best_length) {
|
|
best_length = gene_group[best_index].length;
|
|
gen_to_best = i + 1; /* 1-indexed で世代数を記録 */
|
|
}
|
|
}
|
|
|
|
/* 試行結果をCSVフォーマットで出力 */
|
|
printf("%d, %.2f, %d, %.2f, %d\n", trial, MUTATION_RATIO, SELECT_NUM, best_length, gen_to_best);
|
|
}
|
|
|
|
return 0;
|
|
} |