遺伝的アルゴリズムとか

ちょっと興味があったので、小高 知宏 著 『はじめての機械学習』 を読んでみた。

で。 5 章 2 節 「遺伝的アルゴリズムによる知識獲得」には、簡単な GA （SGA: Simple GA）の実装例が掲載されている。

今回は、その挙動を Processing で可視化してみた。

完成品はこんな感じ。

各世代における適応度の推移グラフをProcessingで可視化したもの。
赤はエリート個体の適応度、青は当該世代における適応度の平均値。

---

【例題】

下の表に示した 20 個の整数から 1 つ以上の整数を選び出し、それらの合計値が 499 にもっとも近くなる組合せを求めよ。

番 号       数 値    1 31 2 41 3 59 4 26 5 53 6 58 7 97 8 93 9 23 10 84		番 号       数 値    11 -62 12 -64 13 -33 14 -83 15 -27 16 -95 17 -2 18 -88 19 -41 20 -97

たとえば、1 番目の数値である 31 と 6 番目の数値の 58 を選ぶと、合計値は 31 + 58 = 89 となる。

これが、目標値である 499 に近いほど優良な解となるため、適応度のパラメータには、499 との差の絶対値 |499 - s| を用いる。ただし、このままでは値の小さい方が適応度が高くなるため、以下のように充分に大きな数 f_max から差の絶対値を引くことにする。

適応度 =  f_max - |499 - s|

遺伝子座の設計に関する詳細は、当該書籍を参照するか、ソースコードを解読してほしい（あまり詳しく書くと著者に迷惑がかかるため）。

---

【実装】

Processing で動くように適当に書き換えたところ、こんな感じになった（ただしコンソール）。

+ expand sourceview plainprint?

1. final int    DATANO   =    20;     // データ数  
2. final int    POOLSIZE =    30;     // プールサイズ  
3. final int    LASTG    =   200;     // 打ち切り世代  
4. final double MRATE    =     0.01;  // 突然変異の確率  
5. final int    YES      =     1;     // yesに対応する整数値  
6. final int    NO       =     0;     // noに対応する整数値  
7. final int    VALUE    =   499;     // 目標値  
8. final int    MAXFIT   =  1000;     // 適応度の計算に用いる数値  
9.   
10. /* 問題の数値の設定 */  
11. int[] q = { 31,  41,  59,  26,  53,  58, 97,  93,  23,  84,  
12.            -62, -64, -33, -83, -27, -95, -2, -88, -41, -97};  
13.              
14. void setup() {  
15.   int[][] pool = new int[POOLSIZE][DATANO];  // 遺伝子プール  
16.   int generation;                            // 現在の遺伝子数  
17.       
18.   /* 初期集団の生成 */  
19.   initpool(pool);  
20.     
21.   /* 打ち切り世代まで繰り返し */  
22.   for(generation = 0; generation < LASTG; ++generation) {  
23.     println(generation + "世代");  
24.     mating(pool);  
25.     mutation(pool);  
26.     printp(pool);  
27.   }  
28. }  
29.   
30. /* ======================================== */  
31. /*            select() メソッド             */  
32. /*                   選択                   */  
33. /* ======================================== */  
34. int select(int[] roulette, int totalfitness) {  
35.   int ball;     // 玉（選択位置の数値）  
36.   int acc = 0;  // 適応度の積算値  
37.     
38.   ball = (int)random(totalfitness);  
39.   int i;  
40.   for(i = 0; i < POOLSIZE; ++i) {  
41.     acc += roulette[i];    // 適応度を積算  
42.     if(acc > ball) break;  // 対応する遺伝子  
43.   }  
44.   return i;  
45. }  
46.   
47. /* ======================================== */  
48. /*            mating() メソッド             */  
49. /*                   交叉                   */  
50. /* ======================================== */  
51. void mating(int[][] pool) {  
52.   int totalfitness = 0;  // 適応度の合計値  
53.   int[][] nextpool = new int[POOLSIZE][DATANO];  
54.                          // 子の世代  
55.   int[] roulette = new int[POOLSIZE];  
56.                          // 適応度を格納  
57.   int mama, papa;        // 親の遺伝子の番号  
58.     
59.   /* ルーレットの作成 */  
60.   for(int i = 0; i < POOLSIZE; ++i) {  
61.     roulette[i] = evalfit(pool[i]);  
62.     /* 適応度の合計値を計算 */  
63.     totalfitness += roulette[i];  
64.   }  
65.     
66.   /* 選択と交叉を繰り返す */  
67.   for(int i = 0; i < POOLSIZE / 2; ++i) {  
68.     do {  /* 親の選択 */  
69.       mama = select(roulette, totalfitness);  
70.       papa = select(roulette, totalfitness);  
71.     } while (mama == papa);  // 重複の削除  
72.     /* 特定の2遺伝子の交叉 */  
73.     crossing(pool[mama],    pool[papa],  
74.              nextpool[i*2], nextpool[i*2+1]);  
75.   }  
76.   /* 次世代のプールをコピー */  
77.   copypool(pool, nextpool);  
78. }  
79.   
80. /* ======================================== */  
81. /*           crossing() メソッド            */  
82. /*           特定の2遺伝子の交叉            */  
83. /* ======================================== */  
84. void crossing(int[] m, int[] p, int[] c1, int[] c2) {  
85.   int cp;    // 交叉する点  
86.     
87.   /* 交叉点の決定 */  
88.   cp = (int)random(DATANO);  
89.     
90.   int j;  
91.   /* 遺伝子の前半部分をコピー */  
92.   for(j = 0; j < cp; ++j) {  
93.     c1[j] = m[j];  
94.     c2[j] = p[j];  
95.   }  
96.     
97.   /* 遺伝子の後半部分をコピー */  
98.   for(; j < DATANO; ++j) {  
99.     c2[j] = m[j];  
100.     c1[j] = p[j];  
101.   }  
102. }  
103.   
104. /* ======================================== */  
105. /*           copypool() メソッド            */  
106. /*          次世代のプールをコピー          */  
107. /* ======================================== */  
108. void copypool(int[][] pool, int[][] nextpool) {  
109.   for(int i = 0; i < POOLSIZE; ++i) {  
110.     for(int j = 0; j < DATANO; ++j) {  
111.       pool[i][j] = nextpool[i][j];  
112.     }  
113.   }  
114. }  
115.   
116. /* ======================================== */  
117. /*            evalfit() メソッド            */  
118. /*               適応度の計算               */  
119. /* ======================================== */  
120. int evalfit(int[] g) {  
121.   int fitness = 0;          // 適応度の途中値  
122.   for(int i = 0; i < DATANO; ++i) {  
123.     fitness += g[i] * q[i];  
124.   }  
125.   return MAXFIT - abs(VALUE - fitness);  
126. }  
127.   
128. /* ======================================== */  
129. /*            printp() メソッド             */  
130. /*                 結果出力                 */  
131. /* ======================================== */  
132. void printp(int[][] pool) {  
133.   int    fitness;           // 適応度  
134.   double totalfitness = 0;  // 適応度の合計値  
135.   int    elite        = 0;  // エリート遺伝子の処理用変数  
136.   int    bestfit      = 0;  
137.     
138.   for(int i = 0; i < POOLSIZE; ++i) {  
139.     for(int j = 0; j < DATANO; ++j) {  
140.       print(pool[i][j]);  
141.     }  
142.     fitness = evalfit(pool[i]);  
143.     println("\t" + fitness);  
144.     if(fitness > bestfit) { /* エリート解 */  
145.       bestfit = fitness;  
146.       elite = i;  
147.     }  
148.     totalfitness += fitness;  
149.   }  
150.     
151.   /* エリート解の適応度を出力 */  
152.   print(elite + "\t" + bestfit + "\t");  
153.     
154.   /* 平均の適応度を出力 */  
155.   println(totalfitness / POOLSIZE);  
156. }  
157.   
158. /* ======================================== */  
159. /*           initpool() メソッド            */  
160. /*              初期集団の生成              */  
161. /* ======================================== */  
162. void initpool(int[][] pool) {  
163.   for(int i = 0; i < POOLSIZE; ++i) {  
164.     for(int j = 0; j < DATANO; ++j) {  
165.       pool[i][j] = (int)random(2);  
166.     }  
167.   }  
168. }  
169.   
170. /* ======================================== */  
171. /*           mutation() メソッド            */  
172. /*                 突然変異                 */  
173. /* ======================================== */  
174. void mutation(int[][] pool) {  
175.   for(int i = 0; i < POOLSIZE; ++i) {  
176.     for(int j = 0; j < DATANO; ++j) {  
177.       if(random(100) / 100.0 <= MRATE) {  
178.         /* 反転の突然変異 */  
179.         pool[i][j] = notval(pool[i][j]);  
180.       }  
181.     }  
182.   }  
183. }  
184.   
185. /* ======================================== */  
186. /*            notval() メソッド             */  
187. /*               真理値の反転               */  
188. /* ======================================== */  
189. int notval(int v) {  
190.   if(v == YES) return NO;  
191.   else return YES;  
192. }  

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 メソッドを改造してこんなものを作った。

view plainprint?

1. /* ======================================== */  
2. /*    getFitnessValueOfElite() メソッド     */  
3. /*        エリート個体の適応度を得る        */  
4. /* ======================================== */  
5. int getFitnessValueOfElite(int[][] pool) {  
6.   int    fitness;           // 適応度  
7.   int    elite        = 0;  // エリート遺伝子の処理用変数  
8.   int    bestfit      = 0;  
9.     
10.   for(int i = 0; i < POOLSIZE; ++i) {  
11.     fitness = evalfit(pool[i]);  
12.     if(fitness > bestfit) { /* エリート解 */  
13.       bestfit = fitness;  
14.       elite = i;  
15.     }  
16.   }  
17.   return bestfit;  
18. }  

/* ======================================== */
/*    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;
}

view plainprint?

1. /* ======================================== */  
2. /*    getAvarageFitnessValue() メソッド     */  
3. /*            適応度の平均を得る            */  
4. /* ======================================== */  
5. float getAvarageFitnessValue(int[][] pool) {  
6.   double totalfitness = 0;  // 適応度の合計値  
7.     
8.   for(int i = 0; i < POOLSIZE; ++i) {  
9.     totalfitness += evalfit(pool[i]);  
10.   }  
11.     
12.   /* 平均の適応度を出力 */  
13.   return (float)totalfitness / POOLSIZE;  
14. }  

/* ======================================== */
/*    getAvarageFitnessValue() メソッド     */
/*            適応度の平均を得る            */
/* ======================================== */
float getAvarageFitnessValue(int[][] pool) {
  double totalfitness = 0;  // 適応度の合計値
  
  for(int i = 0; i < POOLSIZE; ++i) {
    totalfitness += evalfit(pool[i]);
  }
  
  /* 平均の適応度を出力 */
  return (float)totalfitness / POOLSIZE;
}

---

各世代における適応度を配列に保存しておき、draw メソッドで描画する。

view plainprint?

1. void draw() {  
2.   background(0);  
3.   smooth();  
4.     
5.   // 目盛り表示  
6.   stroke(50);  
7.   for(int i = 0; i < width; i += 50) {  
8.     line(i, 0, i, height);  
9.   }  
10.   for(int i = 0; i < height; i += 50) {  
11.     line(0, i, width, i);  
12.   }  
13.     
14.   for(int i = 0; i < LASTG-1; ++i) {  
15.     stroke(255, 0, 0);  
16.     line(i    , MAXFIT - eliteFitness[i],  
17.          i + 1, MAXFIT - eliteFitness[i+1]);  
18.       
19.     stroke(0, 0, 255);  
20.     line(i    , MAXFIT - avgFitness[i],  
21.          i + 1, MAXFIT - avgFitness[i+1]);  
22.   }  
23.     
24.   // ガイドライン表示  
25.   if(0 <= mouseX && mouseX < LASTG) {  
26.     stroke(255);  
27.     line(mouseX, mouseY,   
28.          mouseX, MAXFIT - eliteFitness[mouseX]);  
29.   
30.   // 結果文字列表示  
31.   if(mouseX < width / 2) textAlign(LEFT);  
32.   else textAlign(RIGHT);  
33.   text("第" + mouseX + "世代（適応度:" + eliteFitness[mouseX]+"）",  
34.        mouseX,   
35.        MAXFIT - eliteFitness[mouseX] + 12);  
36.   }  
37. }  

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);
  }
}

これでよし。

ちなみにフルバージョンのソースコードはこちら。

+ expand sourceview plainprint?

1. final int    DATANO   =    20;     // データ数  
2. final int    POOLSIZE =    30;     // プールサイズ  
3. final int    LASTG    =   600;     // 打ち切り世代  
4. final double MRATE    =     0.01;  // 突然変異の確率  
5. final int    YES      =     1;     // yesに対応する整数値  
6. final int    NO       =     0;     // noに対応する整数値  
7. final int    VALUE    =   499;     // 目標値  
8. final int    MAXFIT   =  1000;     // 適応度の計算に用いる数値  
9.   
10. /* 問題の数値の設定 */  
11. int[] q = { 31,  41,  59,  26,  53,  58, 97,  93,  23,  84,  
12.            -62, -64, -33, -83, -27, -95, -2, -88, -41, -97};  
13.   
14. /* 適応度の推移を格納する配列 */  
15. int[] eliteFitness;  
16. float[] avgFitness;  
17.   
18. void setup() {  
19.   int[][] pool = new int[POOLSIZE][DATANO];  // 遺伝子プール  
20.   int generation;                            // 現在の遺伝子数  
21.       
22.   size(LASTG, VALUE);  
23.     
24.   /* 初期集団の生成 */  
25.   initpool(pool);  
26.     
27.   /* 配列を初期化 */  
28.   eliteFitness = new int[LASTG];  
29.   avgFitness   = new float[LASTG];  
30.     
31.   /* 打ち切り世代まで繰り返し */  
32.   for(generation = 0; generation < LASTG; ++generation) {  
33.     mating(pool);  
34.     mutation(pool);  
35.       
36.     eliteFitness[generation] = getFitnessValueOfElite(pool);  
37.     avgFitness[generation]   = getAvarageFitnessValue(pool);  
38.   }  
39. }  
40.   
41. void draw() {  
42.   background(0);  
43.   smooth();  
44.     
45.   // 目盛り表示  
46.   stroke(50);  
47.   for(int i = 0; i < width; i += 50) {  
48.     line(i, 0, i, height);  
49.   }  
50.   for(int i = 0; i < height; i += 50) {  
51.     line(0, i, width, i);  
52.   }  
53.     
54.   for(int i = 0; i < LASTG-1; ++i) {  
55.     stroke(255, 0, 0);  
56.     line(i    , MAXFIT - eliteFitness[i],  
57.          i + 1, MAXFIT - eliteFitness[i+1]);  
58.       
59.     stroke(0, 0, 255);  
60.     line(i    , MAXFIT - avgFitness[i],  
61.          i + 1, MAXFIT - avgFitness[i+1]);  
62.   }  
63.     
64.   // ガイドライン表示  
65.   if(0 <= mouseX && mouseX < LASTG) {  
66.     stroke(255);  
67.     line(mouseX, mouseY,   
68.          mouseX, MAXFIT - eliteFitness[mouseX]);  
69.   
70.   // 結果文字列表示  
71.   if(mouseX < width / 2) textAlign(LEFT);  
72.   else textAlign(RIGHT);  
73.   text("第" + mouseX + "世代（適応度:" + eliteFitness[mouseX]+"）",  
74.        mouseX,   
75.        MAXFIT - eliteFitness[mouseX] + 12);  
76.   }  
77. }  
78.   
79. /* ======================================== */  
80. /*            select() メソッド             */  
81. /*                   選択                   */  
82. /* ======================================== */  
83. int select(int[] roulette, int totalfitness) {  
84.   int ball;     // 玉（選択位置の数値）  
85.   int acc = 0;  // 適応度の積算値  
86.     
87.   ball = (int)random(totalfitness);  
88.   int i;  
89.   for(i = 0; i < POOLSIZE; ++i) {  
90.     acc += roulette[i];    // 適応度を積算  
91.     if(acc > ball) break;  // 対応する遺伝子  
92.   }  
93.   return i;  
94. }  
95.   
96. /* ======================================== */  
97. /*            mating() メソッド             */  
98. /*                   交叉                   */  
99. /* ======================================== */  
100. void mating(int[][] pool) {  
101.   int totalfitness = 0;  // 適応度の合計値  
102.   int[][] nextpool = new int[POOLSIZE][DATANO];  
103.                          // 子の世代  
104.   int[] roulette = new int[POOLSIZE];  
105.                          // 適応度を格納  
106.   int mama, papa;        // 親の遺伝子の番号  
107.     
108.   /* ルーレットの作成 */  
109.   for(int i = 0; i < POOLSIZE; ++i) {  
110.     roulette[i] = evalfit(pool[i]);  
111.     /* 適応度の合計値を計算 */  
112.     totalfitness += roulette[i];  
113.   }  
114.     
115.   /* 選択と交叉を繰り返す */  
116.   for(int i = 0; i < POOLSIZE / 2; ++i) {  
117.     do {  /* 親の選択 */  
118.       mama = select(roulette, totalfitness);  
119.       papa = select(roulette, totalfitness);  
120.     } while (mama == papa);  // 重複の削除  
121.     /* 特定の2遺伝子の交叉 */  
122.     crossing(pool[mama],    pool[papa],  
123.              nextpool[i*2], nextpool[i*2+1]);  
124.   }  
125.   /* 次世代のプールをコピー */  
126.   copypool(pool, nextpool);  
127. }  
128.   
129. /* ======================================== */  
130. /*           crossing() メソッド            */  
131. /*           特定の2遺伝子の交叉            */  
132. /* ======================================== */  
133. void crossing(int[] m, int[] p, int[] c1, int[] c2) {  
134.   int cp;    // 交叉する点  
135.     
136.   /* 交叉点の決定 */  
137.   cp = (int)random(DATANO);  
138.     
139.   int j;  
140.   /* 遺伝子の前半部分をコピー */  
141.   for(j = 0; j < cp; ++j) {  
142.     c1[j] = m[j];  
143.     c2[j] = p[j];  
144.   }  
145.     
146.   /* 遺伝子の後半部分をコピー */  
147.   for(; j < DATANO; ++j) {  
148.     c2[j] = m[j];  
149.     c1[j] = p[j];  
150.   }  
151. }  
152.   
153. /* ======================================== */  
154. /*           copypool() メソッド            */  
155. /*          次世代のプールをコピー          */  
156. /* ======================================== */  
157. void copypool(int[][] pool, int[][] nextpool) {  
158.   for(int i = 0; i < POOLSIZE; ++i) {  
159.     for(int j = 0; j < DATANO; ++j) {  
160.       pool[i][j] = nextpool[i][j];  
161.     }  
162.   }  
163. }  
164.   
165. /* ======================================== */  
166. /*            evalfit() メソッド            */  
167. /*               適応度の計算               */  
168. /* ======================================== */  
169. int evalfit(int[] g) {  
170.   int fitness = 0;          // 適応度の途中値  
171.   for(int i = 0; i < DATANO; ++i) {  
172.     fitness += g[i] * q[i];  
173.   }  
174.   return MAXFIT - abs(VALUE - fitness);  
175. }  
176.   
177. /* ======================================== */  
178. /*            printp() メソッド             */  
179. /*                 結果出力                 */  
180. /* ======================================== */  
181. void printp(int[][] pool) {  
182.   int    fitness;           // 適応度  
183.   double totalfitness = 0;  // 適応度の合計値  
184.   int    elite        = 0;  // エリート遺伝子の処理用変数  
185.   int    bestfit      = 0;  
186.     
187.   for(int i = 0; i < POOLSIZE; ++i) {  
188.     for(int j = 0; j < DATANO; ++j) {  
189.       print(pool[i][j]);  
190.     }  
191.     fitness = evalfit(pool[i]);  
192.     println("\t" + fitness);  
193.     if(fitness > bestfit) { /* エリート解 */  
194.       bestfit = fitness;  
195.       elite = i;  
196.     }  
197.     totalfitness += fitness;  
198.   }  
199.     
200.   /* エリート解の適応度を出力 */  
201.   print(elite + "\t" + bestfit + "\t");  
202.     
203.   /* 平均の適応度を出力 */  
204.   println(totalfitness / POOLSIZE);  
205. }  
206.   
207. /* ======================================== */  
208. /*    getFitnessValueOfElite() メソッド     */  
209. /*        エリート個体の適応度を得る        */  
210. /* ======================================== */  
211. int getFitnessValueOfElite(int[][] pool) {  
212.   int    fitness;           // 適応度  
213.   int    elite        = 0;  // エリート遺伝子の処理用変数  
214.   int    bestfit      = 0;  
215.     
216.   for(int i = 0; i < POOLSIZE; ++i) {  
217.     fitness = evalfit(pool[i]);  
218.     if(fitness > bestfit) { /* エリート解 */  
219.       bestfit = fitness;  
220.       elite = i;  
221.     }  
222.   }  
223.   return bestfit;  
224. }  
225.   
226. /* ======================================== */  
227. /*    getAvarageFitnessValue() メソッド     */  
228. /*            適応度の平均を得る            */  
229. /* ======================================== */  
230. float getAvarageFitnessValue(int[][] pool) {  
231.   double totalfitness = 0;  // 適応度の合計値  
232.     
233.   for(int i = 0; i < POOLSIZE; ++i) {  
234.     totalfitness += evalfit(pool[i]);  
235.   }  
236.     
237.   /* 平均の適応度を出力 */  
238.   return (float)totalfitness / POOLSIZE;  
239. }  
240.   
241. /* ======================================== */  
242. /*           initpool() メソッド            */  
243. /*              初期集団の生成              */  
244. /* ======================================== */  
245. void initpool(int[][] pool) {  
246.   for(int i = 0; i < POOLSIZE; ++i) {  
247.     for(int j = 0; j < DATANO; ++j) {  
248.       pool[i][j] = (int)random(2);  
249.     }  
250.   }  
251. }  
252.   
253. /* ======================================== */  
254. /*           mutation() メソッド            */  
255. /*                 突然変異                 */  
256. /* ======================================== */  
257. void mutation(int[][] pool) {  
258.   for(int i = 0; i < POOLSIZE; ++i) {  
259.     for(int j = 0; j < DATANO; ++j) {  
260.       if(random(100) / 100.0 <= MRATE) {  
261.         /* 反転の突然変異 */  
262.         pool[i][j] = notval(pool[i][j]);  
263.       }  
264.     }  
265.   }  
266. }  
267.   
268. /* ======================================== */  
269. /*            notval() メソッド             */  
270. /*               真理値の反転               */  
271. /* ======================================== */  
272. int notval(int v) {  
273.   if(v == YES) return NO;  
274.   else return YES;  
275. }  

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;
}