はじめに
「何か面白いものないかな～」といった時に覗くYouTubeチャンネルに「The Coding Train」というチャンネルがあるのですが、最近覗いていたらこのような動画を見つけました。
Coding Challenge #29: Smart Rockets in p5.js
見たところ遺伝的アルゴリズムを用いてロケットを目標物に着弾させるための経路を探すシミュレーションのようでした。
過去にUE4で遺伝的アルゴリズムの実装記事（【UE4】遺伝的アルゴリズムを実装してみた）を書いたのですが内容は「指定した文字列を遺伝的アルゴリズムを用いて当てる」という、画面に動きがなく大変地味なものでした。
上記の動画であれば画面に動きが付き見ていてとても面白い内容になると感じたので「UE4で実装してみよう！」と思いたち実際に実装してみた次第ですが実装内容はほとんど動画と同じです。
遺伝的アルゴリズムとは
遺伝的アルゴリズムそのものの解説は過去に書いた
を参照して頂ければと思います。
プロジェクトはこちらから！
プロジェクトの解説
ダウンロードしたプロジェクトには２つのレベルがあります。（Content\Maps フォルダにあります）
下の動画はP_SmartRocketレベルのものです。
記事用 pic.twitter.com/almZ5BLgL3
— PavilionDV7 (@Dv7Pavilion) 2018年6月16日
実行すれば多くのロケットオブジェクトが生成され適当に動き回ります。
交叉、突然変異、淘汰を繰り返し世代が進むと適当に動き回っていたロケットは次第に画面上部にある白玉（これはターゲットです）に向かうようになります。
更に世代が進むと動きが洗練され無駄のない、最短に近い移動距離で白玉へと向かいます。
このような動作を実現するために、これから3つのオブジェクトがどのような実装になっているかを解説していきます。
BP_GeneticAlgorithm
このブループリントではロケットオブジェクトの生成と管理、ロケットから算出されるフィットネス値を基に遺伝子の交叉、突然変異を実行し遺伝子を進化させ再びロケットにセットします。
遺伝的アルゴリズムの実現に必要な関数やイベントの呼び出しは全て、このBP_GeneticAlgorithmから行われます。
使用する変数
| 変数名 | 用途 |
|---|---|
| RocketLifeSpan | 各ロケットの寿命。これはロケットが持つ遺伝子の要素数となる。 |
| PopulationSize | 生成するロケット数。個体数とも言う。 |
| Target | ロケットが向かうべき目標物。この目標物までの経路をアルゴリズムで最適化する。 |
| RocketMaxSpeed | ロケットの最大推進力。 |
| UpdateCount | 更新回数。現在何フレーム目を実行しているか？を知るためにある。 |
| Rockets | 生成したロケットを格納する配列。 |
| MatingPool | 交配用プール。交叉対象のロケットはここからランダムに取り出される。 |
更新処理
生成したロケットの更新処理はBP_RocketのTickイベントでは行わず、このBP_GeneticAlgorithmから更新処理を呼び出してロケットの座標を更新させています。
このような実装になったのは参考にした動画がこの手法だったというのもありますが、UE4らしくEvent Dispatchers等を使用してRocketLifespan回分のTickイベントを実行したロケットをディスパッチイベントで受け取り、生成したロケット全てが同様の通知を送ったことを確認した後、交叉＆再生成を行うといった処理を実装したりしましたが上記の図のようなシンプルな形にならなかったため動画の手法をそのまま採用しています。
全てのRocket配列の要素を更新し終えたらUpdateCountをインクリメントします。
配列要素のUpdateイベント呼び出し、UpdateCountのインクリメントをUpdateCountがRocketLifespanと同値になるまで繰り返します。
UpdateCountがRocketLifespanと同値になった時、生成したロケットは寿命を迎え次の世代を生成するために現世代の評価（Evaluate）とランダムにロケットを選択（Selection）し交叉させ次の世代を生成します。
適応度と交配プール
上の図はEvaluate関数の下段部分です。
Evaluate関数では各ロケットから算出されたフィットネス値の中で最も高いフィットネス値をLocalMaxFitness変数へと格納しています。そのLocalMaxFitness変数を使って各ロケットが持つフィットネス値をスケーリングします。
今回の遺伝的アルゴリズムでは過去に書いた記事と同様にルーレット選択を用いて次世代に残す遺伝子を選択しますが、ルーレット選択を用いる際の重要なテクニックとして**「適応度スケーリング」というものがあります。各ロケットが取りうるフィットネス値の差が極端に大きい場合（例えば1000～0とか）選択される遺伝子に大きく偏りが出てしまいます。もちろん優れた遺伝子が次世代に多く残るのは解きたい問題に対して有効に働きますが「初期収束」や「局所解」**に陥ってしまうという問題があります。
適応度スケーリングを行うことで選択される確率の偏りを解消し、各ロケットの多様性を保証し更に良い解を得られるようにします。
スケーリングしたフィットネス値（1.0～0.0に収まる）を100倍しパーセントへと変換します。
Truncateで小数点以下を切り捨てた値がMatingPool配列へと格納される個数になります。つまりフィットネス値がMaxFitnessに近いほどMatingPoolへ格納される個数が多くなり、次の世代へ遺伝子を残すチャンスが増えるということになります。
BP_DNA
このブループリントは遺伝子情報であるGenes配列を持ち、初期化や交叉、突然変異を行います。
各ロケットはBP_DNAをアクターコンポーネントとして備え、各フレームごとにGenes配列を加速度として参照し座標を更新します。そしてBP_GeneticAlgorithmによって交叉や突然変異を命令され実行し、ロケットは進化した新たな遺伝子を持ちます。
使用する変数
| 変数名 | 用途 |
|---|---|
| Genes | 要素には各フレームごとに適用する加速度が保持されており、要素数はロケットの寿命と同数になる。 |
初期化
Initializeイベントでは引数NewGenesによって異なる動作をします。
最初の世代（BP_GeneticAlgorithmによってSpawnActorされたロケット群）では引数には要素が１つのみのVector型配列が渡されます。続くBranchノードではTrueが実行され、RocketLifespan分の１の長さを持つランダムなベクトルをGenes配列へと追加していきます。
最初の世代のみ要素が１つだけの配列が渡される理由ですが、UE4では引数に配列がある場合空っぽの配列というのは渡すことが出来ずMake Arrayノードを使って最低でも１つの要素を持つ仮の配列を作って引数に渡す必要があるからです。
第２世代以降では引数NewGenesは常にRocketLifespanの要素数を持つ配列が渡されますので、BranchノードはFalseを通ります。その時引数NewGenesには交叉や突然変異によって生まれた次世代の遺伝子情報が格納されています。
交叉を行うCrossOver
CrossOver関数は引数に渡されたパートナーDNAのGenesと自身のGenesを交叉させます。ここでの交叉方法は**「一点交叉」**となっています。
一点交叉は上の図のような仕組みになっています。両者の遺伝子配列を入れ替える地点（Segment Point）を決め、左側もしくは右側をそれぞれ入れ替えます。
ブループリントではSegment PointをRandom Integerノードを使ってランダムに決定しています。ForLoopノードで各インデックスとSegment Pointを比較しSegment Point未満のインデックスにある要素をパートナーDNAと置き換えます。この動作は上で示した一点交叉の動作と全く同じです。
突然変異
CrossOver関数によって遺伝子が交叉された後は突然変異を行います。
突然変異の実装は単純です。Random Bool with Weightノードを使用してMutation Rate％の確率でTrueを返すようにします。Trueが返されたインデックスの要素をRandom Unit Vectorで１の長さを持つランダムなベクトルに置き換えます。
Mutation Rateの値はデフォルトで1%となっています。とても低いように感じますが突然変異の確率は1%～5%くらいまでの範囲が良いとされています。
突然変異は今までの親から受け継いだ遺伝子を無かったことにします。この仕組みは世代を大きく進化させるきっかけにもなりますが、同時に退化させるきっかけにもなります。ですので不用意にMutation Rateを大きくし頻繁に突然変異が起こるようになると、それぞれの世代で親の能力がリセットされてしまい進化の過程が見られなくなります。
ためしにMutation Rateを大きな値（0.5とか）にしてみると面白いものが見られると思います。
ある世代ではきれいに目標物へと向かい、ある世代では全く見当違いな方向へと飛んでいってしまったりと世代ごとで非常にバラバラな動きを見せるはずです。
BP_Rocket
BP_RocketはBP_DNAのGenes配列を参照し、実際に目標物へと飛んでいくアクターです。
フィットネス値はこのブループリントで計算され、BP_GeneticAlgorithmはそれを基に選択＆淘汰を行います。
使用する変数
| 変数名 | 用途 |
|---|---|
| Velocity | 各フレームごとに適用される推進力。 |
| Max Speed | ロケットに適用される最大推進力。Velocityはこのサイズにクランプされる。 |
| Completed Count | 目標物に衝突した際に記録されるフレーム数。数値が小さいほどフィットネス値にプラス評価される。 |
| Completed | 目標物に衝突したことを記録する。Trueであればフィットネス値にプラス評価。 |
| Crashed | 壁や障害物に衝突したことを記録する。Trueであればフィットネス値にマイナス評価。 |
衝突検知処理
目標物との衝突を記録するCompleted変数や障害物との衝突を記録するCrashed変数がありますが、２つのフラグはOn Component Begin Overlapイベントで操作されます。
衝突したアクターが目標物と同一だった場合はCompletedをTrueにし、衝突までのタイムを記録します。
衝突したアクタが目標物ではなかったとき、いきなり障害物にぶつかったと判定していますが、BP_RocketのSphere Collision コンポーネントにはオリジナルのコリジョンプリセットを設定しています。
オブジェクトタイプは**「Rocket」**としており「Rocket」同士の衝突はIgnore（無視）するように設定しています。これによりBP_Rocket同士が衝突することはありませんので、先程のような分岐処理が可能になります。
フィットネス値を求める
遺伝的アルゴリズムにおいてフィットネス値の計算は選択や突然変異と並んで重要で、「どのような進化を辿るのか」を表現します。
BP_Rocketでは評価する点が２つあります。１つ目は**「目標物までの距離」。２つ目は「目標物に衝突するまでの時間」です。今回のプロジェクトにおいて優れた種とは寿命を迎えた時点で「目標物までの距離が短く」「目標物に衝突するまでの時間が少ない」**種としています。
上の図では１つ目の評価点「目標物までの距離」をフィットネス値に変換しています。
ここで使用しているMath Expressionはp5.jsのmap関数をコピーしたものです。
引数Start1～Stop1に収まる変換したい値（引数Num）を引数Start2～Stop2までの範囲に変換します。
今回の例では目標物までの距離（大体0～1000までに収まる）を10～0の範囲に変換しています。つまり目標物までの距離が最大の1000だった場合、0を返します。目標物までの距離が0（つまり衝突した）の場合では10が返ってきます。
このMath Expressionが返す値はそのままフィットネス値に加算されます。
続いては２つ目の評価点「目標物に衝突するまでの時間」をフィットネス値に変換する処理です。
１つ目の評価点と同じMath Expressionを使っています。ここで変換する値は**「目標物に衝突した時点でのフレーム数」となっています。
Completed Count変数がRocket Lifespan変数と同値だった場合、Math Expressionは0を返し、Completed Countが0に近いほど（タイムが短いほど）、Math Expressionは高い数値を返します。
この評価点は参考にした動画では実装されていませんでした。そのため目標物へと衝突するまでの経路というのは全く考慮されておらず、どれだけ遠回りしたとしてもロケットの寿命までに目標物に衝突すればOKだったのです。
今回のプロジェクトでは世代が進むごとに「明後日の方向に飛び回るロケット」から「ふらふらしながらも目標物へと衝突するロケット」へと進化していきます。そこから更に世代を進めると「最短ルートに近い経路で目標物へと衝突するロケット」へと変化します。まさに「Smart Rocket」といった様相を見せるのですが、ロケットがそのような進化を辿る決定的な要因はこの「目標物に衝突するまでの時間」**をフィットネス値として取り扱ったからです。
２つの評価点によるフィットネス値が求まった後は**「目標物に衝突したか？」「壁や障害物に衝突したか？」によってペナルティを与えます。
目標物に衝突している場合、それは種として非常に優れていることを意味しますからフィットネス値を10倍し、後々の世代へと引き継がれやすくします。障害物にぶつかってしまった場合は残念ながら種として劣っているとみなされフィットネス値を１０分の１にします。これにより失敗してしまった種は早々に淘汰されていきます。
このように「うまくいったらプラス点」「失敗してしまったらマイナス点」**というようなペナルティーを与える方法は遺伝的アルゴリズムが最適解に向かって進化するスピードを早める事が出来る便利なテクニックです。
おわりに
過去に書いた【UE4】遺伝的アルゴリズムを実装してみたでは非常に地味な画面でしたが、今回のプロジェクトでは四方八方にロケットが飛び交いつつも、世代が進むごとに一直線に目標物へと向かう進化の様子を見ることが出来るようになりました。
やっぱり動きがある方がわかりやすいし面白いですね。
このような記事が書けたのもThe Coding Train様がこの話題を取り上げ動画にしてくださったおかげです。
ここまで読んでいただきありがとうございました。お疲れ様でした。
#追記
フィットネス値を求める際、Math Expressionを使ってある範囲までを取る値を別の範囲にマッピングするノードを作成しました。これはp5.jsのmap関数のコードをコピペしたものなのですが、UE4には全く同じ機能を持つノードが用意されていました。
Map Range Clamped / UnClampedというノードです。２つのノードの使い方や動作についてはTwitterにまとめたので、そちらを読んで頂ければと思います。
【便利なノード「Map Range Clamped/UnClamped」】#UE4 #UE4Study
— PavilionDV7 (@Dv7Pavilion) 2018年6月21日
In Range A～In Range Bまでの範囲内にあるValueをOut Range A～Out Range Bにマッピングするナイスなノード。
ClampedとUnClampedの違いについてはリプライから。 pic.twitter.com/t8csk3LAMc
【何がClampされるのか？】
— PavilionDV7 (@Dv7Pavilion) 2018年6月21日
Clampedでは入力されたValueがIn Range A～In Range Bの範囲にクランプされます。In Range A未満の値が渡されればIn Range Aに置き換え、In Range Bより大きい値であればIn Range Bに置き換えられる。
UnClampedではこれが行われない。（画像を参照） #UE4 #UE4Study pic.twitter.com/q7ENwstf8Z
以前Qiitaに投稿したSmart Rocketの記事ではMath Expressionを使ってMap Range UnClampedと同じ動作をする式を書いた。（この時はMap Range Clamped/UnClampedとかいう便利なノードがあるとは知らなかった。そしてこの式はp5.jsの該当する関数の中身をコピペしただけである。）#UE4 #UE4Study pic.twitter.com/ZHVxYrUIYS
— PavilionDV7 (@Dv7Pavilion) 2018年6月21日
【参考資料】https://t.co/szjcA5mHGQ
— PavilionDV7 (@Dv7Pavilion) 2018年6月21日