#include
#include
#include
//袋が耐えられる重量の最大値を定義
#define OMOSA_MAX 100
//一つの品物の重量の最大値を定義
#define ITEM_OMOSA_MAX 15
//一つの品物の価値の最大値を定義
#define VARUE_MAX 30
//全ての品物の数を定義
#define ITEM_MAX 20
//一度に詰める品物の数を定義
#define GENE_LEN 10
//一つの世代を構成する個体数を定義
#define KOTAISUU 100
//ＧＡの処理を終える世代数を定義
#define SEDAI_MAX 10000
//何世代ごとにエリート（その世代で最優秀の個体
#define SEDAI_REC 1000
//交叉率を定義
#define CROS_RATE 0.95
//突然変異率を定義
#define MUTA_RATE 0.05
//乱数発生関数のプロトタイプ宣言
int rando (int);
//ここからメイン関数
void main () {
//変数宣言
int i , j , m , counter; //カウンター変数
int omosa[ITEM_MAX]; //各品物の重さを表す配列
int value[ITEM_MAX]; //各品物の価値を表す配列
int gene[KOTAISUU][GENE_LEN]; //個体群を表す配列
int temp_gene[KOTAISUU][GENE_LEN]; //ルーレット選択で用いる個体群の退避用配列
double total , rulet_value , rulet_cf;
int rulet_num;
int pos; //交叉における切断点を表す変数
int temp;
double d_ret;
double seiseki[KOTAISUU]; //各個体の成績を表す配列
double best_seiseki;
int elite_num;
int elite[GENE_LEN]; //エリート個体を保存のため待避する配列
FILE *fp;
time_t t;
srand((unsigned) time(&t));
//まずこのケースにおける各品物の重さを乱数で決める
for (i = 0 ; i < ITEM_MAX ; i ++) {
omosa[i] = rando (ITEM_OMOSA_MAX);
}
//次にこのケースにおける各品物の価値を乱数で決める
for (i = 0 ; i < ITEM_MAX ; i ++) {
value[i] = rando (VARUE_MAX);
}
//第一世代の個体群（初期個体群）を生成
for (i = 0 ; i < KOTAISUU ; i ++) {
for (j = 0 ; j < GENE_LEN ; j ++) {
//品物番号の割り当て（重複を許している）
gene[i][j] = rando (ITEM_MAX);
}
}
//進化の過程に入る
counter = 0;
while (1) {
//各個体の成績（選んだ品物の価値の合計）を算出
for (i = 0 ; i < KOTAISUU ; i ++) {
seiseki[i] = 0.0; temp = 0;
for (j = 0 ; j < GENE_LEN ; j ++) {
seiseki[i] += value[gene[i][j]];
temp += omosa[gene[i][j]];
}
//ただし、袋が耐えられる重さを超えている組合せは最低点
if (temp > OMOSA_MAX) {
seiseki[i] = 0.0;
}
}
//エリートの番号を探す
elite_num = 0; best_seiseki = seiseki[0];
for (i = 1 ; i < KOTAISUU ; i ++) {
if (best_seiseki < seiseki[i]) {
elite_num = i;
best_seiseki = seiseki[i];
}
}
//エリート配列に入れる
for (i = 0 ; i < GENE_LEN ; i ++) {
elite[i] = gene[elite_num][i];
}
//ルーレット方式による次世代選択
total = 0.0;
for (i = 0 ; i < KOTAISUU ; i ++) {
total += seiseki[i];
}
for (i = 0 ; i < KOTAISUU ; i ++) {
rulet_cf = (double) (rando (10000)) / 10000.0 *
total;
rulet_value = 0.0;
for (j = 0 ; j < KOTAISUU ; j ++) {
rulet_value += seiseki[j];
if (rulet_value > rulet_cf) {
rulet_num = j;
break;
}
}
for (j = 0 ; j < GENE_LEN ; j ++) {
temp_gene[i][j] = gene[rulet_num][j];
}
}
for (i = 0 ; i < KOTAISUU ; i ++) {
for (j = 0 ; j < GENE_LEN ; j ++) {
gene[i][j] = temp_gene[i][j];
}
}
//交叉処理。番号の若い個体から順に２つずつペアとする
for (i = 0 ; i < KOTAISUU ; i += 2) {
d_ret = (double) rando (101) / 100.0;
if (d_ret < CROS_RATE) {
pos = rando (GENE_LEN);
for (j = pos ; j < GENE_LEN ; j ++) {
temp = gene[i][j];
gene[i][j] = gene[i + 1][j];
gene[i + 1][j] = temp;
}
}
}
//突然変異
for (i = 0 ; i < KOTAISUU ; i ++) {
for (j = 0 ; j < GENE_LEN ; j ++) {
d_ret = (double) rando (101) / 100.0;
if (d_ret < MUTA_RATE) {
gene[i][j] = rando (ITEM_MAX);
}
}
}
//待避しておいた前世代のエリートを新しい世代の最初の番号の
for (i = 0 ; i < GENE_LEN ; i ++) {
gene[0][i] = elite[i];
}
counter ++;
//もし世代交代数が記録すべき世代数であればエリートの点数を
if (counter % SEDAI_REC == 0) {
printf ("counter = %d best = %lf\n" , counter ,
best_seiseki);
}
//もし世代交代数が終了すべき世代数であれば、whileを抜
if (counter == SEDAI_MAX) {
break;
}
}
//最終世代のエリートの遺伝子の値をファイルに書き出す
fp = fopen ("kiroku.dat" , "w");
for (i = 0 ; i < GENE_LEN ; i ++) {
fprintf (fp , "%d " , gene[0][i]);
}
fprintf (fp , "\n");
fclose (fp);
}
//乱数発生関数。整数Ｎを受け取り０から(Ｎ－１
int rando (int num) {
int ret;
ret = rand ();
ret = ret % num;
return ret;
}
