で。 5 章 2 節 「遺伝的アルゴリズムによる知識獲得」には、簡単な GA （SGA: Simple GA）の実装例が掲載されている。
今回は、その挙動を Processing で可視化してみた。
完成品はこんな感じ。
 |
| 各世代における適応度の推移グラフをProcessingで可視化したもの。 赤はエリート個体の適応度、青は当該世代における適応度の平均値。 |
【例題】
下の表に示した 20 個の整数から 1 つ以上の整数を選び出し、それらの合計値が 499 にもっとも近くなる組合せを求めよ。
|
|
|---|
たとえば、1 番目の数値である 31 と 6 番目の数値の 58 を選ぶと、合計値は 31 + 58 = 89 となる。
これが、目標値である 499 に近いほど優良な解となるため、適応度のパラメータには、499 との差の絶対値 |499 - s| を用いる。ただし、このままでは値の小さい方が適応度が高くなるため、以下のように充分に大きな数 fmax から差の絶対値を引くことにする。
適応度 = fmax - |499 - s|
遺伝子座の設計に関する詳細は、当該書籍を参照するか、ソースコードを解読してほしい（あまり詳しく書くと著者に迷惑がかかるため）。
【実装】
Processing で動くように適当に書き換えたところ、こんな感じになった（ただしコンソール）。
final int DATANO = 20; // データ数
final int POOLSIZE = 30; // プールサイズ
final int LASTG = 200; // 打ち切り世代
final double MRATE = 0.01; // 突然変異の確率
final int YES = 1; // yesに対応する整数値
final int NO = 0; // noに対応する整数値
final int VALUE = 499; // 目標値
final int MAXFIT = 1000; // 適応度の計算に用いる数値
/* 問題の数値の設定 */
int[] q = { 31, 41, 59, 26, 53, 58, 97, 93, 23, 84,
-62, -64, -33, -83, -27, -95, -2, -88, -41, -97};
void setup() {
int[][] pool = new int[POOLSIZE][DATANO]; // 遺伝子プール
int generation; // 現在の遺伝子数
/* 初期集団の生成 */
initpool(pool);
/* 打ち切り世代まで繰り返し */
for(generation = 0; generation < LASTG; ++generation) {
println(generation + "世代");
mating(pool);
mutation(pool);
printp(pool);
}
}
/* ======================================== */
/* select() メソッド */
/* 選択 */
/* ======================================== */
int select(int[] roulette, int totalfitness) {
int ball; // 玉（選択位置の数値）
int acc = 0; // 適応度の積算値
ball = (int)random(totalfitness);
int i;
for(i = 0; i < POOLSIZE; ++i) {
acc += roulette[i]; // 適応度を積算
if(acc > ball) break; // 対応する遺伝子
}
return i;
}
/* ======================================== */
/* mating() メソッド */
/* 交叉 */
/* ======================================== */
void mating(int[][] pool) {
int totalfitness = 0; // 適応度の合計値
int[][] nextpool = new int[POOLSIZE][DATANO];
// 子の世代
int[] roulette = new int[POOLSIZE];
// 適応度を格納
int mama, papa; // 親の遺伝子の番号
/* ルーレットの作成 */
for(int i = 0; i < POOLSIZE; ++i) {
roulette[i] = evalfit(pool[i]);
/* 適応度の合計値を計算 */
totalfitness += roulette[i];
}
/* 選択と交叉を繰り返す */
for(int i = 0; i < POOLSIZE / 2; ++i) {
do { /* 親の選択 */
mama = select(roulette, totalfitness);
papa = select(roulette, totalfitness);
} while (mama == papa); // 重複の削除
/* 特定の2遺伝子の交叉 */
crossing(pool[mama], pool[papa],
nextpool[i*2], nextpool[i*2+1]);
}
/* 次世代のプールをコピー */
copypool(pool, nextpool);
}
/* ======================================== */
/* crossing() メソッド */
/* 特定の2遺伝子の交叉 */
/* ======================================== */
void crossing(int[] m, int[] p, int[] c1, int[] c2) {
int cp; // 交叉する点
/* 交叉点の決定 */
cp = (int)random(DATANO);
int j;
/* 遺伝子の前半部分をコピー */
for(j = 0; j < cp; ++j) {
c1[j] = m[j];
c2[j] = p[j];
}
/* 遺伝子の後半部分をコピー */
for(; j < DATANO; ++j) {
c2[j] = m[j];
c1[j] = p[j];
}
}
/* ======================================== */
/* copypool() メソッド */
/* 次世代のプールをコピー */
/* ======================================== */
void copypool(int[][] pool, int[][] nextpool) {
for(int i = 0; i < POOLSIZE; ++i) {
for(int j = 0; j < DATANO; ++j) {
pool[i][j] = nextpool[i][j];
}
}
}
/* ======================================== */
/* evalfit() メソッド */
/* 適応度の計算 */
/* ======================================== */
int evalfit(int[] g) {
int fitness = 0; // 適応度の途中値
for(int i = 0; i < DATANO; ++i) {
fitness += g[i] * q[i];
}
return MAXFIT - abs(VALUE - fitness);
}
/* ======================================== */
/* printp() メソッド */
/* 結果出力 */
/* ======================================== */
void printp(int[][] pool) {
int fitness; // 適応度
double totalfitness = 0; // 適応度の合計値
int elite = 0; // エリート遺伝子の処理用変数
int bestfit = 0;
for(int i = 0; i < POOLSIZE; ++i) {
for(int j = 0; j < DATANO; ++j) {
print(pool[i][j]);
}
fitness = evalfit(pool[i]);
println("\t" + fitness);
if(fitness > bestfit) { /* エリート解 */
bestfit = fitness;
elite = i;
}
totalfitness += fitness;
}
/* エリート解の適応度を出力 */
print(elite + "\t" + bestfit + "\t");
/* 平均の適応度を出力 */
println(totalfitness / POOLSIZE);
}
/* ======================================== */
/* initpool() メソッド */
/* 初期集団の生成 */
/* ======================================== */
void initpool(int[][] pool) {
for(int i = 0; i < POOLSIZE; ++i) {
for(int j = 0; j < DATANO; ++j) {
pool[i][j] = (int)random(2);
}
}
}
/* ======================================== */
/* mutation() メソッド */
/* 突然変異 */
/* ======================================== */
void mutation(int[][] pool) {
for(int i = 0; i < POOLSIZE; ++i) {
for(int j = 0; j < DATANO; ++j) {
if(random(100) / 100.0 <= MRATE) {
/* 反転の突然変異 */
pool[i][j] = notval(pool[i][j]);
}
}
}
}
/* ======================================== */
/* notval() メソッド */
/* 真理値の反転 */
/* ======================================== */
int notval(int v) {
if(v == YES) return NO;
else return YES;
}ここまではコンソールアプリケーションなので、実行してもあまり見栄えはよくない。
グラフ描画に必要なのは、各世代におけるエリート個体の適応度、および（各世代における）全個体の適応度の平均値なので、それらを得るべく printp メソッドを改造してこんなものを作った。
/* ======================================== */
/* getFitnessValueOfElite() メソッド */
/* エリート個体の適応度を得る */
/* ======================================== */
int getFitnessValueOfElite(int[][] pool) {
int fitness; // 適応度
int elite = 0; // エリート遺伝子の処理用変数
int bestfit = 0;
for(int i = 0; i < POOLSIZE; ++i) {
fitness = evalfit(pool[i]);
if(fitness > bestfit) { /* エリート解 */
bestfit = fitness;
elite = i;
}
}
return bestfit;
}
/* ======================================== */
/* getAvarageFitnessValue() メソッド */
/* 適応度の平均を得る */
/* ======================================== */
float getAvarageFitnessValue(int[][] pool) {
double totalfitness = 0; // 適応度の合計値
for(int i = 0; i < POOLSIZE; ++i) {
totalfitness += evalfit(pool[i]);
}
/* 平均の適応度を出力 */
return (float)totalfitness / POOLSIZE;
}
各世代における適応度を配列に保存しておき、draw メソッドで描画する。
void draw() {
background(0);
smooth();
// 目盛り表示
stroke(50);
for(int i = 0; i < width; i += 50) {
line(i, 0, i, height);
}
for(int i = 0; i < height; i += 50) {
line(0, i, width, i);
}
for(int i = 0; i < LASTG-1; ++i) {
stroke(255, 0, 0);
line(i , MAXFIT - eliteFitness[i],
i + 1, MAXFIT - eliteFitness[i+1]);
stroke(0, 0, 255);
line(i , MAXFIT - avgFitness[i],
i + 1, MAXFIT - avgFitness[i+1]);
}
// ガイドライン表示
if(0 <= mouseX && mouseX < LASTG) {
stroke(255);
line(mouseX, mouseY,
mouseX, MAXFIT - eliteFitness[mouseX]);
// 結果文字列表示
if(mouseX < width / 2) textAlign(LEFT);
else textAlign(RIGHT);
text("第" + mouseX + "世代（適応度:" + eliteFitness[mouseX]+"）",
mouseX,
MAXFIT - eliteFitness[mouseX] + 12);
}
}
これでよし。
ちなみにフルバージョンのソースコードはこちら。
final int DATANO = 20; // データ数
final int POOLSIZE = 30; // プールサイズ
final int LASTG = 600; // 打ち切り世代
final double MRATE = 0.01; // 突然変異の確率
final int YES = 1; // yesに対応する整数値
final int NO = 0; // noに対応する整数値
final int VALUE = 499; // 目標値
final int MAXFIT = 1000; // 適応度の計算に用いる数値
/* 問題の数値の設定 */
int[] q = { 31, 41, 59, 26, 53, 58, 97, 93, 23, 84,
-62, -64, -33, -83, -27, -95, -2, -88, -41, -97};
/* 適応度の推移を格納する配列 */
int[] eliteFitness;
float[] avgFitness;
void setup() {
int[][] pool = new int[POOLSIZE][DATANO]; // 遺伝子プール
int generation; // 現在の遺伝子数
size(LASTG, VALUE);
/* 初期集団の生成 */
initpool(pool);
/* 配列を初期化 */
eliteFitness = new int[LASTG];
avgFitness = new float[LASTG];
/* 打ち切り世代まで繰り返し */
for(generation = 0; generation < LASTG; ++generation) {
mating(pool);
mutation(pool);
eliteFitness[generation] = getFitnessValueOfElite(pool);
avgFitness[generation] = getAvarageFitnessValue(pool);
}
}
void draw() {
background(0);
smooth();
// 目盛り表示
stroke(50);
for(int i = 0; i < width; i += 50) {
line(i, 0, i, height);
}
for(int i = 0; i < height; i += 50) {
line(0, i, width, i);
}
for(int i = 0; i < LASTG-1; ++i) {
stroke(255, 0, 0);
line(i , MAXFIT - eliteFitness[i],
i + 1, MAXFIT - eliteFitness[i+1]);
stroke(0, 0, 255);
line(i , MAXFIT - avgFitness[i],
i + 1, MAXFIT - avgFitness[i+1]);
}
// ガイドライン表示
if(0 <= mouseX && mouseX < LASTG) {
stroke(255);
line(mouseX, mouseY,
mouseX, MAXFIT - eliteFitness[mouseX]);
// 結果文字列表示
if(mouseX < width / 2) textAlign(LEFT);
else textAlign(RIGHT);
text("第" + mouseX + "世代（適応度:" + eliteFitness[mouseX]+"）",
mouseX,
MAXFIT - eliteFitness[mouseX] + 12);
}
}
/* ======================================== */
/* select() メソッド */
/* 選択 */
/* ======================================== */
int select(int[] roulette, int totalfitness) {
int ball; // 玉（選択位置の数値）
int acc = 0; // 適応度の積算値
ball = (int)random(totalfitness);
int i;
for(i = 0; i < POOLSIZE; ++i) {
acc += roulette[i]; // 適応度を積算
if(acc > ball) break; // 対応する遺伝子
}
return i;
}
/* ======================================== */
/* mating() メソッド */
/* 交叉 */
/* ======================================== */
void mating(int[][] pool) {
int totalfitness = 0; // 適応度の合計値
int[][] nextpool = new int[POOLSIZE][DATANO];
// 子の世代
int[] roulette = new int[POOLSIZE];
// 適応度を格納
int mama, papa; // 親の遺伝子の番号
/* ルーレットの作成 */
for(int i = 0; i < POOLSIZE; ++i) {
roulette[i] = evalfit(pool[i]);
/* 適応度の合計値を計算 */
totalfitness += roulette[i];
}
/* 選択と交叉を繰り返す */
for(int i = 0; i < POOLSIZE / 2; ++i) {
do { /* 親の選択 */
mama = select(roulette, totalfitness);
papa = select(roulette, totalfitness);
} while (mama == papa); // 重複の削除
/* 特定の2遺伝子の交叉 */
crossing(pool[mama], pool[papa],
nextpool[i*2], nextpool[i*2+1]);
}
/* 次世代のプールをコピー */
copypool(pool, nextpool);
}
/* ======================================== */
/* crossing() メソッド */
/* 特定の2遺伝子の交叉 */
/* ======================================== */
void crossing(int[] m, int[] p, int[] c1, int[] c2) {
int cp; // 交叉する点
/* 交叉点の決定 */
cp = (int)random(DATANO);
int j;
/* 遺伝子の前半部分をコピー */
for(j = 0; j < cp; ++j) {
c1[j] = m[j];
c2[j] = p[j];
}
/* 遺伝子の後半部分をコピー */
for(; j < DATANO; ++j) {
c2[j] = m[j];
c1[j] = p[j];
}
}
/* ======================================== */
/* copypool() メソッド */
/* 次世代のプールをコピー */
/* ======================================== */
void copypool(int[][] pool, int[][] nextpool) {
for(int i = 0; i < POOLSIZE; ++i) {
for(int j = 0; j < DATANO; ++j) {
pool[i][j] = nextpool[i][j];
}
}
}
/* ======================================== */
/* evalfit() メソッド */
/* 適応度の計算 */
/* ======================================== */
int evalfit(int[] g) {
int fitness = 0; // 適応度の途中値
for(int i = 0; i < DATANO; ++i) {
fitness += g[i] * q[i];
}
return MAXFIT - abs(VALUE - fitness);
}
/* ======================================== */
/* printp() メソッド */
/* 結果出力 */
/* ======================================== */
void printp(int[][] pool) {
int fitness; // 適応度
double totalfitness = 0; // 適応度の合計値
int elite = 0; // エリート遺伝子の処理用変数
int bestfit = 0;
for(int i = 0; i < POOLSIZE; ++i) {
for(int j = 0; j < DATANO; ++j) {
print(pool[i][j]);
}
fitness = evalfit(pool[i]);
println("\t" + fitness);
if(fitness > bestfit) { /* エリート解 */
bestfit = fitness;
elite = i;
}
totalfitness += fitness;
}
/* エリート解の適応度を出力 */
print(elite + "\t" + bestfit + "\t");
/* 平均の適応度を出力 */
println(totalfitness / POOLSIZE);
}
/* ======================================== */
/* getFitnessValueOfElite() メソッド */
/* エリート個体の適応度を得る */
/* ======================================== */
int getFitnessValueOfElite(int[][] pool) {
int fitness; // 適応度
int elite = 0; // エリート遺伝子の処理用変数
int bestfit = 0;
for(int i = 0; i < POOLSIZE; ++i) {
fitness = evalfit(pool[i]);
if(fitness > bestfit) { /* エリート解 */
bestfit = fitness;
elite = i;
}
}
return bestfit;
}
/* ======================================== */
/* getAvarageFitnessValue() メソッド */
/* 適応度の平均を得る */
/* ======================================== */
float getAvarageFitnessValue(int[][] pool) {
double totalfitness = 0; // 適応度の合計値
for(int i = 0; i < POOLSIZE; ++i) {
totalfitness += evalfit(pool[i]);
}
/* 平均の適応度を出力 */
return (float)totalfitness / POOLSIZE;
}
/* ======================================== */
/* initpool() メソッド */
/* 初期集団の生成 */
/* ======================================== */
void initpool(int[][] pool) {
for(int i = 0; i < POOLSIZE; ++i) {
for(int j = 0; j < DATANO; ++j) {
pool[i][j] = (int)random(2);
}
}
}
/* ======================================== */
/* mutation() メソッド */
/* 突然変異 */
/* ======================================== */
void mutation(int[][] pool) {
for(int i = 0; i < POOLSIZE; ++i) {
for(int j = 0; j < DATANO; ++j) {
if(random(100) / 100.0 <= MRATE) {
/* 反転の突然変異 */
pool[i][j] = notval(pool[i][j]);
}
}
}
}
/* ======================================== */
/* notval() メソッド */
/* 真理値の反転 */
/* ======================================== */
int notval(int v) {
if(v == YES) return NO;
else return YES;
}
0 件のコメント:
コメントを投稿
ひとことどうぞφ(・ω・,,)