遺伝的アルゴリズムやってみた

#概要
遺伝的アルゴリズムをやってみたというだけの記事です。いくつかパラメーターをいじるといい感じになると思います。今回は過学習や初期収束を避けた値になっています。

#応用
ゲームの敵キャラのパラメーターに応用すると「プレイヤーが98%の確率で勝つ」ような敵を作れると思います。もちろん人間が調整する必要はありますが、初期の適当な値を楽に決められます。

#結果

0~99のパラメータ×100の合計で判定

最低値　　　　　　　　平均値　　　　　　 　　　　 最高値
0―――――――――――5000―――――――――――10000

```
0世代：
最高値：5811
平均値：4986

10世代：
最高値：6138
平均値：5923

20世代：
最高値：6409
平均値：6256

30世代：
最高値：6624
平均値：6429

40世代：
最高値：6838
平均値：6557

50世代：
最高値：6909
平均値：6683

60世代：
最高値：7015
平均値：6806

70世代：
最高値：7106
平均値：6894

80世代：
最高値：7186
平均値：6919

90世代：
最高値：7208
平均値：6993

100世代：
最高値：7355
平均値：7128

200世代：
最高値：7707
平均値：7424

300世代：
最高値：7865
平均値：7567

400世代：
最高値：8035
平均値：7732

500世代：
最高値：8159
平均値：7837

1000世代：
最高値：8380
平均値：8036

2000世代：
最高値：8421
平均値：8081

3000世代：
最高値：8581
平均値：8216

4000世代：
最高値：8663
平均値：8296

5000世代：
最高値：8663
平均値：8286

10000世代：
最高値：8788
平均値：8406

```

#コード

```Individual.cpp
#include <random>
using namespace std;

class Individual {
public:
	
	// 各遺伝子
	int gene[100];

	// 初期化
	Individual() {
		for (int i = 0; i < 100; i++) {
			gene[i] = rand() % 100;
		}
	}

	void Crossover(Individual* indivi) {
		int start = rand() % 90;
		int end = start + rand() % 10;
		for (int i = start; i < end - start; i++) {
			int tmp = indivi->gene[i];
			indivi->gene[i] = gene[i];
			gene[i] = tmp;
		}
	}

	// 適応度を取得
	int GetScore() {
		int score = 0;
		for (int i = 0; i < 100; i++) {
			score += gene[i];
		}
		return score;
	}

	// 突然変異
	void Mutation() {
		for (int i = 0; i < 10; i++) {
			gene[rand() % 100] = rand() % 100;
		}
	}

private:


};

```

```main.cpp

#include <stdio.h>
#include "Individual.h"
#include <vector>

vector<Individual> individuals;
int generationCount = 0;

int GetAvarage() {
	int sum = 0;
	for (int i = 0; i < 100; i++) {
		sum += individuals[i].GetScore();
	}
	return sum / 100;
}

void StepGeneration() {
	for (int i = 0; i < 30; i++) {
		individuals[rand() % 100].Crossover(&individuals[rand() % 100]);
	}
	for (int i = 0; i < 10; i++) {
		individuals[rand() % 100].Mutation();
	}

	vector<Individual> ranking;
	for (int i = 0; i < 100; i++) {
		ranking.emplace_back(individuals[i]);
	}
	
	for (int i = 0; i < 100; i++) {
		for (int j = 99; j > 0; j--) {
			if (ranking[j - 1].GetScore() < ranking[j].GetScore()) {
				Individual tmp = ranking[j];
				ranking[j] = ranking[j - 1];
				ranking[j - 1] = tmp;
			}
		}
	}
	
	individuals.clear();
	for (int j = 0; j < 3; j++) {
		for (int i = 0; i < 30; i++) {
			individuals.emplace_back(ranking[i]);
		}
	}
	for (int i = 0; i < 10; i++) {
		individuals.emplace_back(Individual());
	}

	// 世代結果表示
	if (generationCount % 10 == 0) {
		printf("%d世代：", generationCount);
		printf("\n最高値：%d", ranking[0].GetScore());
		printf("\n平均値：%d\n\n", GetAvarage());
	}
	generationCount++;
}

int main() {
	
	for (int i = 0; i < 100; i++) {
		individuals.emplace_back(Individual());
	}
	vector<Individual> ranking;
	for (int i = 0; i < 100; i++) {
		ranking.emplace_back(individuals[i]);
	}

	for (int i = 0; i < 100; i++) {
		for (int j = 99; j > 0; j--) {
			if (ranking[j - 1].GetScore() < ranking[j].GetScore()) {
				Individual tmp = ranking[j];
				ranking[j] = ranking[j - 1];
				ranking[j - 1] = tmp;
			}
		}
	}
	printf("%d世代：", generationCount);
	printf("\n最高値：%d", ranking[0].GetScore());
	printf("\n平均値：%d\n\n", GetAvarage());
	generationCount++;
	
	for (int i = 0; i < 10000; i++) {
		StepGeneration();
	}
	return 0;
}
```

#編集可能パラメーター

##突然変異時の変異遺伝子数
10部分

```cpp
void Mutation() {
    for (int i = 0; i < 10; i++) {
        gene[rand() % 100] = rand() % 100;
    }
}
```

##交叉の範囲

```cpp
void Crossover(Individual* indivi) {
        int start = rand() % 90;
        int end = start + rand() % 10;
}
```

startの数字(ここでは90)、endの数字(10)で交叉の範囲を指定。これの合計値は100(パラメーター数)にする必要がある。
広いとランダム化、狭いと収束する

##一世代につきの交叉数
30部分、多くても大丈夫だった

```cpp
for (int i = 0; i < 30; i++) {
		individuals[rand() % 100].Crossover(&individuals[rand() % 100]);
	}
```

##一世代につきの突然変異数
StepGeneration()内、10部分

```cpp
for (int i = 0; i < 10; i++) {
    individuals[rand() % 100].Mutation();
}
```
多いと逆に下がってしまうことがあった

##世代交代
上位30個体を3倍にし、完全新規の10個体を追加して100個体にしている。

```cpp

for (int j = 0; j < 3; j++) {
        for (int i = 0; i < 30; i++) {
            individuals.emplace_back(ranking[i]);
        }
    }
    for (int i = 0; i < 10; i++) {
        individuals.emplace_back(Individual());
    }
```