遺伝的アルゴリズムで水の呼吸を会得する

# きっかけ

鬼滅の刃面白い。
刀から水のエフェクト出たり、妹が竹くわえてたり百眼っぽくなったりで、楽しい。
そんな時にGo Conference 2019 Summer in Fukuokaに行って、``Goでつくる進化計算パッケージ``と言う発表をみた。
これを使えば俺でも水の呼吸(*1)が習得できるんじゃなかろうか。

![kimetsunoyaiba.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/42445/d4832c6c-2a80-61d3-84f7-87057b0fce56.png)

<font color="dark_pink">利権に配慮して自分で書いた。</font>


*1: 刀から水のエフェクトを出す呼吸法。本来は山を駆け回ったり石を切ったりして習得する。

# 結論

水の呼吸は下記の通りとなりました。

| index | 秒数[sec] | 動作 | 脈拍[puls/min] | 体内残存酸素量[㎤] | 合計取得酸素量[㎤] |
| -----: | -----: | :-----: | -----: | -----: | ------: |
| 1 | 5 | 吸う | 75 | 624 | 624 |
| 2 | 5 | 吐く | 75 | 258 | 624 |
| 3 | 5 | 吸う | 75 | 797 | 1163 |
| 4 | 5 | 吐く | 75 | 532 | 1163 |
| 5 | 5 | 吸う | 75 | 890 | 1521 |
| 6 | 5 | 吐く | 75 | 334 | 1521 |
| 7 | 5 | 吸う | 75 | 889 | 2076 |
| 8 | 3 | 吐く | 75 | 618 | 2076 |
| 9 | 1 | 止める | 77 | - | - |
| 10 | 1 | 吐く | 79 | 490 | 2076 |
| 11 | 5 | 吸う | 79 | 783 | 2369 |
| 12 | 5 | 吐く | 79 | 462 | 2369 |
| 13 | 5 | 吸う | 79 | 1176 | 3083 |
| 14 | 5 | 吐く | 79 | 825 | 3083 |
| 15 | 5 | 吸う | 79 | 1308 | 3566 |
| 16 | 5 | 吐く | 79 | 719 | 3566 |
| 17 | 5 | 吸う | 79 | 2223 | 5070 |
| 18 | 5 | 吐く | 79 | 1166 | 5070 |
| 19 | 5 | 吸う | 79 | 2455 | 6359 |
| 20 | 5 | 吐く | 79 | 1559 | 6359 |
| 21 | 5 | 吸う | 79 | 2383 | 7183 |
| 22 | 5 | 吐く | 79 | 1701 | 7183 |
| 23 | 5 | 吸う | 79 | 2613 | 8095 |
| 24 | 5 | 吐く | 79 | 1163 | 8095 |
| 25 | 5 | 吸う | 79 | 2558 | 9490 |
| 26 | 5 | 吐く | 79 | 1221 | 9490 |
| 27 | 5 | 吸う | 79 | 2481 | 10750 |
| 28 | 5 | 吐く | 79 | 1296 | 10750 |
| 29 | 5 | 吸う | 79 | 2153 | 11607 |
| 30 | 5 | 吐く | 79 | 664 | 11607 |
| 31 | 5 | 吸う | 79 | 1967 | 12910 |
| 32 | 5 | 吐く | 79 | 1307 | 12910 |
| 33 | 5 | 吸う | 79 | 1988 | 13591 |
| 34 | 5 | 吐く | 79 | 1073 | 13591 |
| 35 | 5 | 吸う | 79 | 2174 | 14692 |
| 36 | 5 | 吐く | 79 | 1362 | 14692 |
| 37 | 5 | 吸う | 79 | 1950 | 15280 |
| 38 | 5 | 吐く | 79 | 1304 | 15280 |


<font color="dark_pink">み　ん　な　も　や　っ　て　み　よ　う　！</font>

# やること

``水の呼吸をすると刀から水が出るようになる。``のであれば、取り込める酸素量にも関連しているハズ。
もっとはっきり言えば、``酸素こそ水``。
と言うわけで下記条件に決めた。

 + 進化の到達点: 刀から水が出る最大の酸素量。要は酸素量。
 + パラメタ: 一定時間(3[min])内の呼吸パターン
   + 吸気深度(どれだけの時間でどれだけの量を吸うか)
   + 排気深度(どれだけの時間でどれだけの量を吐くか)

ただし、人間なのでずっと吸い続けたり吐き続けたりは無理。なので、下記制約を付ける。

 + (吸気量 - 排気量)は0～4000[㎤]で推移
 + 吸排気の各時間範囲: 1～10[sec]
 + 基準脈拍: 75[回/分]
 + 吸排気の基準時間: 3～8[sec]
   + 連続吸気秒数or連続排気秒数が2[sec]以下の場合、脈拍が上がる
     + 増加: 3[sec] - 連続吸排気秒数
   + 連続吸気秒数or連続排気秒数が9[sec]以上の場合、脈拍が下がる
     + 減少: 連続吸排気秒数 - 基準時間
 + 個体の死亡条件
   + 11秒以上吸気し続けた。
   + 11秒以上排気し続けた。
   + 1分以上息を止めた。
   + 吸排気パターン上で体内酸素量が0～4000[㎤]の範囲外になった。
   + 脈拍が59～91[回/分]を超えた。

脈拍を取り入れたのは、誰がどう考えたって``1秒で4000吸って1秒で4000吐けばいいじゃん``って気づくから。
あと面倒なのでこの世には酸素しかない事にする。窒素とかない。吸ったら全部酸素。

# 手順

``Goで作る進化計算パッケージ``のスライドが素晴らしかったので自分も合わせて書く。

## Encoding - 一定時間内の呼吸を定義する

一定時間(3[min])を1[sec]単位で区切り、180[sec]=180次元のベクトルとする。

ex) 3[sec]間200[㎤]吸って、2[sec]間息を止めて、5[sec]間100[㎤]吐く

| sec index | 吸排気量[㎤] | 体内酸素量[㎤] |
| ----: | ----: |  ----: |
| 1 | 200 | 200 |
| 2 | 200 | 400 |
| 3 | 200 |  600 |
| 4 | 0 |  600 |
| 6 | 0 | 600 |
| 7 | -100 | 500 |
|8 | -100 | 400 |
| 9 | -100 | 300 |
| 10 | -100 | 200 |
| 11 | -100 | 100 |

ゲノムとしてTanjiroを作る。

```go
type Tanjiro struct {
	Kokyu []int
}

func (t Tanjiro) Initialization() eago.Genome {
	kokyu := make([]int, 180)
	for i := range kokyu {
		if (i % 10) <= 4 {
			kokyu[i] = rand.Intn(400)
		} else {
			kokyu[i] = rand.Intn(400) * -1
		}
	}
	return Tanjiro{Kokyu: kokyu}
}
```

## Fitness - 酸素量

先に述べた通り、生きて呼吸をするものの内、酸素量が一番多い個体を水の呼吸に適応したとみなす。
どれぐらい適応したかの値は、``吸入した酸素量 / 最大吸入可能酸素量``の逆数で出す。
最大吸入可能酸素量は16秒周期(吸排気各8[sec])の深呼吸(4000[㎤])の倍とする。
``90000[㎤] = 180[sec] / 16[sec] * 4000[㎤] * 2``とする。
やってみると分かるが、わりと吸う。全吸入。

```go
func (t Tanjiro) Fitness() float64 {
	displacementContinuaryDie := func(direction int, sec int) bool {
		die := false
		displacementContinuary := 0
		for _, kokyu := range t.Kokyu {
			if t.sign(kokyu) != direction {
				displacementContinuary = 0
				continue
			}
			displacementContinuary++
			if displacementContinuary >= sec {
				die = true
				break
			}
		}
		return die
	}
	if displacementContinuaryDie(0, 60) {
		return 1.0
	}
	if displacementContinuaryDie(-1, 11) {
		return 1.0
	}
	if displacementContinuaryDie(1, 11) {
		return 1.0
	}
	minHeartPuls, maxHeartPuls := t.getSummaryHeartPuls()
	if minHeartPuls < HeartPulsLower {
		return 1.0
	}
	if maxHeartPuls > HeartPulsUpper {
		return 1.0
	}
	minDisplacement, maxDisplacement := t.getDisplacementSummary()
	if minDisplacement < 0 {
		return 1.0
	}
	if maxDisplacement > 4000 {
		return 1.0
	}
	totalOx := t.getDisplacementTotal()
	if totalOx >= MaxTotalOxgen {
		return 0.0
	}
	return (1.0 - (float64(totalOx) / float64(MaxTotalOxgen)))
}
```

## Crossover - 交叉

水の呼吸適応個体同士の遺伝を次世代に残す。
2人のTanjiroから良い感じのTanjiroを生み出す。
ただし、100回交叉して生きる望みがない場合は先祖返りする。

```go
func (t Tanjiro) Crossover(X eago.Genome) eago.Genome {
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < 100; i++ {
		mid := rand.Intn(len(t.Kokyu))
		kokyu := append(t.Kokyu[:mid], (X.(Tanjiro)).Kokyu[mid:]...)
		if t.Fitness() < 1.0 {
			return Tanjiro{Kokyu: kokyu}
		}
	}
	return t.Initialization()
}

```

## Mutation - 変異

初期状態からの変化を促すために、水の呼吸適応個体に変異を与える。
ただし、一定数変化しても生きる望みがないならば先祖返り。

```go
func (t Tanjiro) Mutation() {
	mutationRate := 0.0005
	rand.Seed(time.Now().UnixNano())
	succeed := false
	for i := 0; i < 100; i++ {
		for i := 0; i < len(t.Kokyu); i++ {
			if rand.Float64() < mutationRate {
				t.Kokyu[i] = (rand.Intn(1000) - 500)
			}
		}
		if t.Fitness() < 1.0 {
			succeed = true
			break
		}
	}
	if !succeed {
		for i := range t.Kokyu {
			if (i % 10) <= 4 {
				t.Kokyu[i] = rand.Intn(200)
			} else {
				t.Kokyu[i] = rand.Intn(200) * -1
			}
		}
	}
}
```

# 進化を見る

<details><summary>コード全体</summary><div>

```go:main.go
package main

import (
	"fmt"
	"log"
	"math"
	"math/rand"
	"time"

	"github.com/tsurubee/eago"
)

const (
	BaseDisplacementContinuaryLowerSec int = 3
	BaseDisplacementContinuaryUpperSec int = 8
	BaseHeartPuls                      int = 75
	HeartPulsUpper                     int = 91
	HeartPulsLower                     int = 59
	MaxTotalOxgen                      int = 90000
)

type Tanjiro struct {
	Kokyu []int
}

func (t Tanjiro) Initialization() eago.Genome {
	kokyu := make([]int, 360)
	for i := range kokyu {
		if (i % 10) <= 4 {
			kokyu[i] = rand.Intn(400)
		} else {
			kokyu[i] = rand.Intn(400) * -1
		}
	}
	return Tanjiro{Kokyu: kokyu}
}

func (t Tanjiro) getSummaryHeartPuls() (int, int) {
	heartPuls := BaseHeartPuls
	minHeatPuls := math.MaxInt32
	maxHeatPuls := math.MinInt32
	displacementContinuary := 0
	direction := t.sign(t.Kokyu[0])
	for _, kokyu := range t.Kokyu {
		if t.sign(kokyu) != direction {
			if BaseDisplacementContinuaryLowerSec > displacementContinuary {
				heartPuls += (BaseDisplacementContinuaryLowerSec - displacementContinuary)
			}
			if BaseDisplacementContinuaryUpperSec < displacementContinuary {
				heartPuls -= (displacementContinuary - BaseDisplacementContinuaryUpperSec)
			}
			if heartPuls > maxHeatPuls {
				maxHeatPuls = heartPuls
			}
			if heartPuls < minHeatPuls {
				minHeatPuls = heartPuls
			}
			displacementContinuary = 0
			direction = t.sign(kokyu)
		}
		displacementContinuary++
	}
	if BaseDisplacementContinuaryLowerSec > displacementContinuary {
		heartPuls += (BaseDisplacementContinuaryLowerSec - displacementContinuary)
	}
	if BaseDisplacementContinuaryUpperSec < displacementContinuary {
		heartPuls -= (displacementContinuary - BaseDisplacementContinuaryUpperSec)
	}
	if heartPuls > maxHeatPuls {
		maxHeatPuls = heartPuls
	}
	if heartPuls < minHeatPuls {
		minHeatPuls = heartPuls
	}
	return minHeatPuls, maxHeatPuls
}

func (t Tanjiro) getDisplacementSummary() (int, int) {
	displacement := 0
	minDisplacement := 0
	maxDisplacement := 0
	for _, kokyu := range t.Kokyu {
		displacement += kokyu
		if minDisplacement > displacement {
			minDisplacement = displacement
		}
		if maxDisplacement < displacement {
			maxDisplacement = displacement
		}
	}
	return minDisplacement, maxDisplacement
}

func (t Tanjiro) Fitness() float64 {
	displacementContinuaryDie := func(direction int, sec int) bool {
		die := false
		displacementContinuary := 0
		for _, kokyu := range t.Kokyu {
			if t.sign(kokyu) != direction {
				displacementContinuary = 0
				continue
			}
			displacementContinuary++
			if displacementContinuary >= sec {
				die = true
				break
			}
		}
		return die
	}
	if displacementContinuaryDie(0, 60) {
		return 1.0
	}
	if displacementContinuaryDie(-1, 11) {
		return 1.0
	}
	if displacementContinuaryDie(1, 11) {
		return 1.0
	}
	minHeartPuls, maxHeartPuls := t.getSummaryHeartPuls()
	if minHeartPuls < HeartPulsLower {
		return 1.0
	}
	if maxHeartPuls > HeartPulsUpper {
		return 1.0
	}
	minDisplacement, maxDisplacement := t.getDisplacementSummary()
	if minDisplacement < 0 {
		return 1.0
	}
	if maxDisplacement > 4000 {
		return 1.0
	}
	totalOx := t.getDisplacementTotal()
	if totalOx >= MaxTotalOxgen {
		return 0.0
	}
	return (1.0 - (float64(totalOx) / float64(MaxTotalOxgen)))
}

func (t Tanjiro) Mutation() {
	mutationRate := 0.0005
	rand.Seed(time.Now().UnixNano())
	succeed := false
	for i := 0; i < 100; i++ {
		for i := 0; i < len(t.Kokyu); i++ {
			if rand.Float64() < mutationRate {
				t.Kokyu[i] = (rand.Intn(1000) - 500)
			}
		}
		if t.Fitness() < 1.0 {
			succeed = true
			break
		}
	}
	if !succeed {
		for i := range t.Kokyu {
			if (i % 10) <= 4 {
				t.Kokyu[i] = rand.Intn(200)
			} else {
				t.Kokyu[i] = rand.Intn(200) * -1
			}
		}
	}
}

func (t Tanjiro) Crossover(X eago.Genome) eago.Genome {
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < 100; i++ {
		mid := rand.Intn(len(t.Kokyu))
		kokyu := append(t.Kokyu[:mid], (X.(Tanjiro)).Kokyu[mid:]...)
		if t.Fitness() < 1.0 {
			return Tanjiro{Kokyu: kokyu}
		}
	}
	return t.Initialization()
}

func (t Tanjiro) sign(kokyu int) int {
	if kokyu == 0 {
		return 0
	}
	if kokyu > 0 {
		return 1
	}
	return -1
}

func (t Tanjiro) getDisplacementTotal() int {
	displacementSummary := 0
	for _, kokyu := range t.Kokyu {
		if kokyu > 0 {
			displacementSummary += kokyu
		}
	}
	return displacementSummary
}

func (t Tanjiro) ShowKokyu() {
	minHeartPuls, maxHeartPuls := t.getSummaryHeartPuls()
	minDisplacement, maxDisplaccement := t.getDisplacementSummary()
	fmt.Printf("total oxgen: %d, displacement: (%d - %d), heart puls: (%d - %d) \n",
		t.getDisplacementTotal(),
		minDisplacement,
		maxDisplaccement,
		minHeartPuls,
		maxHeartPuls)
	displacementContinuary := 0
	displacementSummary := 0
	displacement := 0
	heartPuls := BaseHeartPuls
	displacementDirection := t.sign(t.Kokyu[0])

	directionText := func(direction int) string {
		if direction == 0 {
			return "stop"
		}
		if direction > 0 {
			return "suck"
		}
		return "exhale"
	}

	for _, kokyu := range t.Kokyu {
		if t.sign(kokyu) != displacementDirection {
			if BaseDisplacementContinuaryLowerSec > displacementContinuary {
				heartPuls += (BaseDisplacementContinuaryLowerSec - displacementContinuary)
			}
			if BaseDisplacementContinuaryUpperSec < displacementContinuary {
				heartPuls -= (displacementContinuary - BaseDisplacementContinuaryUpperSec)
			}

			if displacementDirection == 0 {
				fmt.Printf("%d[sec] %s - heart puls: %d\n", displacementContinuary, directionText(displacementDirection), heartPuls)
			} else {
				fmt.Printf("%d[sec] %s - heart puls: %d - (Ox: %d, Total Ox: %d)\n", displacementContinuary, directionText(displacementDirection), heartPuls, displacement, displacementSummary)
			}
			displacementDirection = t.sign(kokyu)
			displacementContinuary = 0
		}
		if kokyu > 0 {
			displacementSummary += kokyu
		}
		displacement += kokyu
		displacementContinuary++
	}
	if BaseDisplacementContinuaryLowerSec > displacementContinuary {
		heartPuls += (BaseDisplacementContinuaryLowerSec - displacementContinuary)
	}
	if BaseDisplacementContinuaryUpperSec < displacementContinuary {
		heartPuls -= (displacementContinuary - BaseDisplacementContinuaryUpperSec)
	}
	if displacementDirection == 0 {
		fmt.Printf("%d[sec] %s - heart puls: %d\n", displacementContinuary, directionText(displacementDirection), heartPuls)
	} else {
		fmt.Printf("%d[sec] %s - heart puls: %d - (Ox: %d, Total Ox: %d)\n", displacementContinuary, directionText(displacementDirection), heartPuls, displacement, displacementSummary)
	}
}

func main() {
	start := time.Now()
	tanjiro := Tanjiro{}
	rand.Seed(start.UnixNano())
	ga := eago.NewGA(eago.GAConfig{
		PopulationSize: 100,
		NGenerations:   2000000,
		CrossoverRate:  0.9,
		MutationRate:   0.9,
		ParallelEval:   true,
	})
	ga.Selector = eago.Tournament{
		NContestants: 40,
	}
	ga.PrintCallBack = func() {
		if ga.Generations%100 == 0 {
			sofar := time.Since(start)
			fmt.Printf("Generation %3d | Elapsed time: %s | Fitness=%.3f\n",
				ga.Generations,
				sofar,
				ga.BestIndividual.Chromosome.(Tanjiro).Fitness())
			ga.BestIndividual.Chromosome.(Tanjiro).ShowKokyu()
		}
	}
	if err := ga.Minimize(tanjiro); err != nil {
		log.Fatal(err)
	}
}
```
</div></details>

実行するためにはtsurubeeさんのeagoが必要。このライブラリめちゃくちゃいい。一礼してgo getする。

```bash
go get https://github.com/tsurubee/eago
```

いざ実行

```bash
go run main.go
```

待つこと約2時間半。水の呼吸がついに完成。
俺が深呼吸するとき、吸排気それぞれ8秒ぐらい。3分間にざっくり11回吸気するとして、44,000が平均酸素量とする。

200万世代を潜り抜けたTanjiroの呼吸は、

``15,280でした！``

もう一回いいます。

``15,280でした！``

詳しく書くと

 + 世代: 2,000,000 
 + 経過時間: 2h24m45.6057053s 
 + 適合度: Fitness=0.830
 + 取得酸素量合計: 15280
 + 体内酸素(最低, 最大): 0, 2613
 + 脈拍(最低, 最大): 75, 79 

もっと進むかと思ったけど全然だった！

ちなみに一番酸素量を取得したのは

 + 世代: 1,267,800 
 + 経過時間: 1h32m17.2806086s 
 + 適合度: 0.746 
 + 取得酸素量合計: 22,840
 + 体内酸素(最低, 最大): 0, 3549
 + 脈拍(最低, 最大): 75, 75

先祖返り怖い。

# ふりかえり

最初は初期状態の呼吸をランダムで生成していた為、ほぼ全員死んで、
死んだ者から次世代が生まれるというゾンビ遺伝が発生した。

遺伝的アルゴリズムで全員の適合度を安定化させるためには、それなりに条件を考える必要がある。
また、変異の条件なども調整を掛けないとうまく進まない。

調整をちょこちょこ加えてこの結果だ。

Go Conference 2019 Summer in Fukuokaで登壇者の方が
``パラメタ調整に時間がかかる``といっていた意味がよく分かった。

深いぜ遺伝的アルゴリズム。

あと、あんまり関係ないけど、
鬼滅の刃の最新話に獣の呼吸なるものが出てきてて、もうそれ呼吸じゃんって思った。