この１コ前の更新では、
授業で、遺伝的アルゴリズム(GA)と進化的アルゴリズム(EA)を
C++で勉強していったことを述べましたが、
今日の更新では、その完成させた進化的アルゴリズム(EA)の
プログラムを添付したいと思います。
プログラムの知識はそこまで無いので完成させるのに苦労しました。
同じ授業を受けていた同期の方にいろいろ教えてもらいながら完成させました。
以下のプログラムを見てもらえればわかると思いますが、
このように、-1.28から1.27に乱数をばらまいて、
突然変異させています。
突然変異を排他的論理和により、すべてのビットにおいて行い、
100個体で確かめました。
そしてそれを100世代ループさせました。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <string.h>
#include <time.h>
#define TERM_NUM (2) // 目的関数の項数
#define GEN_NUM (100) // 世代数
#define IND_NUM (100) // 個体数
#define PROB_C (0.5) // 交叉確率
#define PROB_M (0.01) // 突然変異確率
#define AMPLITUDE (5.0) // J2の振幅A
// 個体の構造体
typedef struct {
//int x[TERM_NUM]; // 項(4バイト)(-1～1→-2147483648～2147483647に対応？)
//long gene; // 遺伝子(8バイト)
char x[TERM_NUM]; // 項(1バイト)(-1.28～1.27)
unsigned short gene; // 遺伝子(2バイト)
double J; // 目的関数の値
double f; // 適合度
} SIndividual;
// 世代の構造体
typedef struct {
SIndividual ind[IND_NUM];
} SGeneration;
// 目的関数 J1 = x1^2 + x2^2
//double J1(int x[TERM_NUM])
double J1(char x[TERM_NUM])
{
double x_d[TERM_NUM];
double J = 0.0f;
for (int i=0; i<TERM_NUM; i++) {
//x_d[i] = (double)x[i]/(double)INT_MAX; // -1～1に正規化
x_d[i] = (double)x[i]/100.0; // -1.28～1.27
J += pow(x_d[i]-0.1, 2); // 計算
}
return J;
}
// 目的関数 J2 = 2A + Σ_i=1^2 (xi^2 - Acos2πxi)
double J2(int x[TERM_NUM])
{
double x_d[TERM_NUM];
double J = 0.0f;
double A = AMPLITUDE;
J += (2*A);
for (int i=0; i<TERM_NUM; i++) {
x_d[i] = (double)x[i]/(double)INT_MAX; // -1～1に正規化
J += pow(x_d[i], 2) - A*cos(2.0*M_PI*x_d[i]); // 計算
}
return J;
}
// 適合度の計算 f = Jmax - J
//double f(double _J)
//{
//
//}
int main(int argc, char** argv)
{
// 初期設定
SGeneration curr_gen;
SGeneration next_gen;
memset(&curr_gen, 0, sizeof(curr_gen));
memset(&next_gen, 0, sizeof(next_gen));
// 遺伝子の初期値（乱数）
srand((unsigned int)time(NULL)); // ランダム性向上
for (int ind_i=0; ind_i<IND_NUM; ind_i++) { // 個体のループ
curr_gen.ind[ind_i].gene = (unsigned short)(rand() % (USHRT_MAX+1)); // 0x0000～0xFFFFまでの乱数
//double J1max = 3.2258;
// 変数へ変換
unsigned short gene = curr_gen.ind[ind_i].gene;
curr_gen.ind[ind_i].x[1] = gene;
gene >>= 8;
curr_gen.ind[ind_i].x[0] = gene;
printf("x[0] = %02X, x[1] = %02X\n", (unsigned char)curr_gen.ind[ind_i].x[0], (unsigned char)curr_gen.ind[ind_i].x[1]);
printf("gene[%d] = %04X\n", ind_i, curr_gen.ind[ind_i].gene);
}
//// 世代発展
double J1max = 3.2258;
for (int gen_i=0; gen_i<GEN_NUM; gen_i++) { // 世代のループ
double fmax=0.0;
unsigned short genemax;
int ind_imax;
// 全個体の適合度を計算
for (int ind_i=0; ind_i<IND_NUM; ind_i++) { // 個体のループ
curr_gen.ind[ind_i].J = J1(curr_gen.ind[ind_i].x); // 目的関数計算
curr_gen.ind[ind_i].f = J1max - curr_gen.ind[ind_i].J; // 適合度計算
if(curr_gen.ind[ind_i].f>fmax){
fmax=curr_gen.ind[ind_i].f;
genemax=curr_gen.ind[ind_i].gene;
ind_imax=ind_i;
}
//if (ind_i == 0) {
printf("[%d][%d] ", gen_i ,ind_i);
printf("x1 = %lf, x2 = %lf, ", (double)curr_gen.ind[ind_i].x[0]/100.0, (double)curr_gen.ind[ind_i].x[1]/100.0);
printf("J = %lf, f = %lf\n", curr_gen.ind[ind_i].J, curr_gen.ind[ind_i].f);
/*getchar();*/
//}
}
//getchar();
// 突然変異
for (int ind_i=0; ind_i<IND_NUM; ind_i++) { // 個体のループ
next_gen.ind[ind_i]= curr_gen.ind[ind_i];
if(ind_i==ind_imax){
continue;
}
for (int g_i=0; g_i<16; g_i++) { // 遺伝子ビット数分ループ
double dice = (double)rand() / (double)RAND_MAX; // 0-1
if (dice <= PROB_M) { // 突然変異確率より小さければ突然変異
unsigned short bit = (unsigned short)pow(2.0f, g_i); // 2^0～2^15 ←対応ビットを立てる
next_gen.ind[ind_i].gene ^= bit; // 排他的論理和でビット反転
}
}
}
// x項への配分
for (int ind_i=0; ind_i<IND_NUM; ind_i++) { // 個体のループ
unsigned short gene = next_gen.ind[ind_i].gene;
next_gen.ind[ind_i].x[1] = gene;
gene >>= 8;
next_gen.ind[ind_i].x[0] = gene;
/*printf("x[0] = %02X, x[1] = %02X, ", (unsigned char)next_gen.ind[ind_i].x[0], (unsigned char)next_gen.ind[ind_i].x[1]);
printf("gene[%d] = %04X\n", ind_i, next_gen.ind[ind_i].gene);*/
/*if (ind_i == 0) {
printf("[%d] ", gen_i);
printf("x1 = %lf, x2 = %lf, ", (double)curr_gen.ind[ind_i].x[0]/100.0, (double)curr_gen.ind[ind_i].x[1]/100.0);
printf("J = %lf, f = %lf\n", curr_gen.ind[ind_i].J, curr_gen.ind[ind_i].f);
}*/
}
curr_gen = next_gen; // 現在の世代を更新
memset(&next_gen, 0, sizeof(next_gen)); // メモリリセット
//getchar();
}
return 0;
}