遺伝的アルゴリズムとやらで遊ぼう!

最近巷で人工知能が流行っているらしいですね!私は流行に疎いので知りませんが。
んでんで、調子に乗ってその一種である「遺伝的アルゴリズム」とやらを使って遊んでみました。

遺伝的アルゴリズムとは(他大学の資料をのせるのはあれですが)ここを見ればなんとかわかると思います。

んでんで、この遺伝的アルゴリズムを応用したのが↓

すごいですね。私みたいな素人でもできるかしら。
ではつべこべ言う前にやってみましょうか。

この遺伝的アルゴリズムとやらは、簡単に言うと次のようなプロセスだそうです。

1,遺伝子を作る
2,適合度がトップクラスの幾つかの遺伝子(親)を使って、子供遺伝子を作る(交叉)
3,子供遺伝子以外を消す(汚物は消毒 淘汰)
4,たまに遺伝子を一部変化する(突然変異)
5,2にもどる。

ここでの適合度というのは、例えば「遺伝子Aは生きやすいけどBはすぐ死ぬからAのほうが適合度高いよね」みたいな感じです。
このプロセスを繰り返す(世代を増やす)といつかはサラブレット的なものができるそうです。
遺伝的アルゴリズムは、交叉(遺伝子を組み合わせる)、突然変異(遺伝子の一部が突然書き換わる)、淘汰(下位なものは消す)が主なプロセスです。
実装マンドクセ(‘A`)
これは生物の進化プロセスと同じ仕組みだそうです。

んで私が考えた奴としては、
0〜100の要素を20個持った遺伝子配列で、要素の合計ができるだけ高い遺伝子配列を遺伝的アルゴリズムで作ろう!
というもの。これを遺伝的アルゴリズムでやる必要は無いとかいわないの。

というわけで作りました。以下のコードです

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <ctime>
#define GENERATION 500 //世代数
#define NUM_DNA 200 //群中の遺伝子データの数
#define NUM_DNA_LENGTH 20 //一つの遺伝子データの長さ
#define NUM_DNA_TOP 4 //どれだけの遺伝子を親にするか
#define NUM_DNA_KIND 101 //遺伝子の要素の種類
using namespace std; //今回は表記が紛らわしくなるのでstd名前空間指定略
int main(void) {
vector<vector<int>> data; //遺伝子データ群
//乱数初期化
srand((unsigned int)time(NULL));
//遺伝子データ生成
for (int i = 0; i < NUM_DNA; i++) {
// 0から100までのランダムな数を入力
vector<int> temp;
for (int j = 0; j < NUM_DNA_LENGTH; j++)
temp.push_back(rand() % NUM_DNA_KIND);
data.push_back(temp);
}
//指定された世代数まで作る
for (int gene = 0; gene < GENERATION; gene++) {
cout << gene + 1 << "世代" << endl; //世代表記
map<int, int> score; //トップスコア(適合度)な遺伝子の情報を入れるコンテナ
//現在の遺伝子データ群出力
for (int i = 0; i < data.size(); i++) {
int sum = 0; //遺伝子の合計格納
//遺伝子のデータと合計を出力
for (int j = 0; j < data[i].size(); j++) {
cout << data[i][j] << " ";
sum += data[i][j];
}
cout << " " << sum << endl;
}
cout << endl;
//トップスコア判定
for (int i = 0; i < data.size(); i++) {
int sum = 0;
//合計計算
for (int j = 0; j < data[i].size(); j++)
sum += data[i][j];
//最初のトップデータ数回以内のループに一応データを入力
if (i < NUM_DNA_TOP) {
score[i] = sum;
} else
//トップスコア度遺伝子データの順位が変わるのなら書き換え
for (auto j = score.begin(); j != score.end(); j++)
if (score[j->first] < sum) {
score[i] = sum;
score.erase(score.find(j->first));
break;
}
}
//トップスコア遺伝子をデータ群に入力
auto temp_itr = score.begin();
for (int i = 0; i < NUM_DNA_TOP; i++)
data.push_back(data[(temp_itr++)->first]);
//群中のトップ遺伝子以外を削除(淘汰)
data.erase(data.begin(), data.end() - NUM_DNA_TOP);
//群中のトップ遺伝子出力
for (int i = 0; i < data.size(); i++) {
int sum = 0; //トップ遺伝子の合計格納
//トップ遺伝子のデータと合計を出力
for (int j = 0; j < data[i].size(); j++) {
cout << data[i][j] << " ";
sum += data[i][j];
}
cout << " " << sum << endl;
}
cout << endl;
//限界値を迎えたら終了
bool max = false; //限界値用のフラグ
for (int i = 0; i < data.size(); i++) {
int sum = 0;
for (int j = 0; j < data[0].size(); j++)
sum += data[i][j];
if (sum == (NUM_DNA_LENGTH * (NUM_DNA_KIND - 1))) {
cout << gene + 1<< "世代で終了" << endl;
max = true;
break;
}
}
if (max)
break;
//遺伝子の交叉
for (int i = 0; i < NUM_DNA; i++) {
vector<int> tmp; //組み換えた遺伝子を置く
int a, b; //組み替える2つの遺伝子の番号を格納
//無作為に2つの遺伝子を選別
do {
a = rand() % NUM_DNA_TOP;
b = rand() % NUM_DNA_TOP;
} while (a == b); //親の遺伝子がそれぞれ同じなら選別しなおし。
//交叉を始める
for (int j = 0; j < NUM_DNA_LENGTH;) {
int length; //交叉の時の引き継ぐ長さ
//引き継ぐ長さをランダムで決定する
do {
length = rand() % 5;
} while (NUM_DNA_LENGTH <
length + j); //長さが異常(範囲超え等)の場合、やり直す
//交叉する。どの遺伝子を引き継ぐかはランダム
int parent = (rand() % 2) ? a : b;
for (int k = 0; k < length; k++) {
tmp.push_back(data[parent][j + k]);
}
j += length;
}
//子の遺伝子データを20%の確率で1箇所ランダムに変える(突然変異)
if (rand() % 10 + 1 <= 2)
tmp[rand() % NUM_DNA_LENGTH] = rand() % NUM_DNA_KIND;
data.push_back(tmp);
}
//子供遺伝子以外を削除(淘汰)
data.erase(data.begin(), data.begin() + NUM_DNA_TOP);
}
return 0;
}

こんな感じです。そのまま上のプロセスを写したという感じ。
流れとしては、

1.最初に0〜100の数字から、内容はランダムで長さ20の遺伝子配列を200個作る
2.配列の中身をそれぞれ全て足して、200個から合計(適合度)のTOP4を出す。この時合計2000が出たらプログラムは終わる。
3.TOP4(親)を元に、200個新しく遺伝子配列(子)を作る。
4.たまに子供の遺伝子配列を一部ランダムで書き換える(突然変異)。
5.2に戻る。

という感じでしょうか。
では結果(何世代でプログラムは終わるか)を見ましょう。5回プログラムを起動した結果、以下のようになりました。(実行結果は長いので省略)

1
2
3
4
5
305世代で終了
227世代で終了
174世代で終了
214世代で終了
255世代で終了

こんな感じ。結果だけ出してもわからんので、ある時の一部の実行結果プロセスを見せますね。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//1世代
//データの表し方は基本 遺伝子の中身 その合計 の順
//作ったデータ(1世代は全てランダム)
73 64 55 42 75 12 88 37 71 42 49 60 25 49 15 53 17 1 95 90 1013
31 95 31 38 7 89 63 9 34 26 47 77 39 42 66 84 98 44 65 99 1084
46 55 13 74 63 49 82 29 10 44 24 94 26 38 4 52 23 37 6 15 784
46 5 36 65 60 81 99 38 51 87 27 33 95 69 79 27 10 11 28 82 1029
26 75 24 1 49 23 60 18 64 46 85 44 81 33 90 13 51 97 14 43 937
42 84 60 43 44 37 14 72 61 88 86 67 18 39 53 80 0 44 72 37 1041
//200個あるので以下略
//トップデータ
36 64 9 38 90 83 91 93 24 89 7 83 25 44 100 94 99 79 43 47 1238
8 95 92 4 42 4 40 94 38 30 98 92 90 64 85 21 65 85 73 83 1203
72 78 68 100 45 39 69 53 98 57 100 50 14 47 40 71 60 75 43 87 1266
66 59 92 41 98 99 23 82 72 71 67 57 62 60 97 92 4 62 64 84 1352
//2世代
//作ったデータ(2世代は1世代トップデータの交叉+突然変異) 
//前回と同じトップデータの元になってるのもわかるし、ちょくちょく変わってるのもわかる(はず)
72 95 68 4 45 39 40 53 38 57 100 92 14 64 85 21 60 85 43 83 1158
36 64 92 38 90 4 40 93 24 30 98 83 25 44 100 21 65 79 73 47 1146
8 95 92 41 98 4 40 82 38 30 67 92 7 60 97 92 4 62 73 83 1165
36 59 9 38 98 99 23 82 72 71 67 57 25 60 97 94 4 79 43 84 1197
8 95 92 4 42 4 91 94 24 30 7 92 90 44 100 21 65 79 73 83 1138
72 59 92 100 45 3 69 82 72 71 100 50 14 47 97 71 60 62 64 84 1314
//200個あるので以下略
//トップデータ(前回より若干大きくなった)
66 64 92 41 98 83 91 82 72 71 67 57 62 44 97 92 99 79 64 84 1505
36 95 92 38 90 83 91 94 24 30 7 92 90 64 100 94 99 79 73 83 1454
72 78 68 100 90 83 91 93 24 89 100 83 25 47 100 94 60 75 43 87 1502
66 78 68 100 98 99 69 82 98 71 67 50 14 60 97 92 60 75 64 87 1495
//飛んで78世代
//子遺伝子の合計が多くなってきたが、ちょくちょく変化が鈍くなる。ここらへんで突然変異が本領を発揮
99 100 100 100 100 100 100 99 99 100 100 98 100 100 100 100 99 100 97 100 1991
99 100 100 100 100 100 100 99 99 100 100 98 100 100 100 100 99 100 97 100 1991
99 100 100 100 100 100 100 99 99 100 100 98 100 100 100 100 99 100 97 8 1899
99 100 100 100 100 100 100 99 99 100 100 98 100 100 100 100 99 100 97 100 1991
99 100 100 100 100 100 100 99 99 100 100 98 100 100 100 100 99 100 97 100 1991
99 100 100 100 100 100 100 99 99 100 100 98 100 100 100 100 99 100 97 100 1991
//200個あるので以下略
//トップデータ(ほぼ同じ)
99 100 100 100 100 100 100 99 99 100 100 98 100 100 100 100 99 100 97 100 1991
99 100 100 100 100 100 100 99 99 100 100 98 100 100 100 100 99 100 97 100 1991
99 100 100 100 100 100 100 99 99 100 100 98 100 100 100 100 99 100 97 100 1991
99 100 100 100 100 100 100 99 99 100 100 98 100 100 100 100 99 100 97 100 1991
//さらに飛んで266世代
//突然変異で2000が出る、終了!
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 99 100 100 100 1999
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 57 100 100 100 1957
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 2000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 99 100 100 100 1999
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 99 100 100 100 1999
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 99 100 30 100 1929
//200個あるので以下略

見ての感じです。途中で進化が滞ってきたのが分かりますでしょうか?既存の遺伝子だけでの交叉だと、進化は必ず滞ります。
そのために突然変異というものは有ります。突然変異によって、たまにベストな値が出るのです。

しかし、このプログラムには問題点があります。コードが糞とかそういう問題ではなく、遺伝的アルゴリズムの使い方です。
例えるなら「遺伝子が有用かどうかではなく、遺伝子の原子量で良し悪し決めてるよね」という感じでしょうか。
つまり遺伝的アルゴリズムをもうちょっと有用に使おうということです。

みなさんでこのアルゴリズムを改造したりして、ゲームのAIとか作ってみてください(最後投げやり)。