Go to Qiita Advent Calendar 2024 Top
LoginSignup
7
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@miyatama(NAOYUKI MIYATA)

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

Posted at

きっかけ

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

kimetsunoyaiba.png

利権に配慮して自分で書いた。

*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

み　ん　な　も　や　っ　て　み　よ　う　！

やること

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

  • 進化の到達点: 刀から水が出る最大の酸素量。要は酸素量。
  • パラメタ: 一定時間(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を作る。

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とする。
やってみると分かるが、わりと吸う。全吸入。

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回交叉して生きる望みがない場合は先祖返りする。

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 - 変異

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

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

進化を見る

コード全体
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)
	}
}

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

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

いざ実行

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で登壇者の方が
パラメタ調整に時間がかかるといっていた意味がよく分かった。

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

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

7
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
7
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?