【UE4】遺伝的アルゴリズムを実装してみた

はじめに

UE4で遺伝的アルゴリズムを実装してみました。
内容は非常に単純なものでユーザーが指定した文字列に適合する遺伝子を持つオブジェクトが現れるまで適性評価と交叉、突然変異を繰り返すというものです。

参考にした書籍は
ゲーム開発者のAI入門
です。ゲームAIを学ぶ際の取っ掛かりとして非常に優れています。

遺伝的アルゴリズムとは？

かなり単純に説明すると
生物が持つ遺伝による進化をコンピュータ上で再現しちゃおうぜ
というアルゴリズムです。
生物は新しい世代（子世代）が誕生する度に親世代の遺伝子を交叉（混ぜあわせ）させ新たな世代を生み出します。新たに生まれた世代の中にはある確率で親の持つ遺伝子を無視して突然変異するものも現れます。
親の遺伝子をしっかりと引き継いだ個体と突然変異した個体を同一の環境に置くことで、その環境に適した個体を残し、適さない個体を淘汰させます。
交叉と突然変異、淘汰を繰り返し環境に適した個体を生み出す。この進化のプロセスをプログラムに落とし込んだものが遺伝的アルゴリズムです。
プログラムに落とし込んだことにより進化のプロセスは生物だけではなく様々なものに転用できるようになりました。
中でも面白い例は「新幹線の先頭部を遺伝的アルゴリズムを用いてデザインした」事例でしょうか。ネットに詳しく書かれているサイトもありますので調べていただければと思います。

プロジェクトをアップしています

BasicGAExample.zip
OneDriveにプロジェクトをアップしているので、プロジェクトと併せてこちらを読んでもらえるとより理解しやすいかと思います。

プロジェクトの内容

プロジェクトは３つのアセットしか入っていません。
ExampleMap - 遺伝的アルゴリズムを実行するシーン
DNAObject - 遺伝子情報と遺伝子が行なう仕事をまとめたObject型を親としたクラス
GA - 遺伝的アルゴリズムをまとめたクラス。遺伝子を作成、比較し優れた最も適した遺伝子を次の世代へと託す

このプロジェクトで行っていることは「はじめに」の方でも書きましたが、ユーザーが指定した文字列を環境とみなし、各遺伝子を環境に適応させる。つまり指定した文字列と同様の遺伝子を生み出すということをしています。
アルゴリズムそのものを見る前に遺伝子を表すDNAObjectから解説していきます。

DNAObject

遺伝的アルゴリズムの処理を見る前に中身の単純なDNAObjectから見ていきます。
DNAObjectには５つの変数と４つのカスタムイベントから構成されています。

【変数】
Genes - 遺伝子そのものを表す最も重要な変数
Fitness - 用意された環境に対してどれほど適応しているかを表す変数。適応度とも言える。
Mutation - 突然変異する確率。0.01%から1%くらいが好ましい値。
RefStrings - 初期に生成される遺伝子や突然変異で参考にする文字列。A～Zと空白文字を含めた27文字で構成される。
Score - 一時変数。適応度を算出するために用いる。

【カスタムイベント】
Create From Random - 最初の世代を生み出す際に用いる。変数RefStringsからランダムに文字を取得し遺伝子として組み込む。

Create From Parent - 第二世代から用いられる。２つの親を受け取り各親からランダムに遺伝子を取得し、遺伝子として組み込む。一様交叉という手法を用いる。

Set Fitness - どれほど環境に適応しているかを算出する

Mutate - 変数Mutationの確率で突然変異を起こす。

DNAObjectの中身は結構単純だと思います。
変数GenesはString型の配列となっていて、各要素に１文字ずつ格納されます。
イベントCreateFromRandomでターゲットとなる文字列の文字数を取得し、変数RefStringsからランダムに参照しGenesへ格納することでGenesはターゲット文字列の文字数と同様のサイズとなります。

イベントCreateFromParentではForeachLoopを用いてGenesの各要素に対し一定の確率でどちらかの親の要素を取得し自身の遺伝子としています。
この各親の要素を取得し自身の遺伝子とすることを交叉（こうさ）といいます。
交叉には一点交叉、二点交叉、多点交叉、一様交叉と幾つかの種類があります。ここで使用している交叉方法は一様交叉です。一様交叉は各要素を必ず入れ替えるのでは無く確率で入れ替えを判断する交叉方法です。

イベントSetFitnessも素直にターゲットの文字列と遺伝子を１つずつ比較し適応度を求めています。比較した文字が同じであればスコアを加算し、最終的なスコアをターゲットの文字数で割れば比が求められます。

イベントMutateは遺伝子の各要素ごとに0～1のランダムに生成された数値と突然変異の確率を表すMutationと比較し、条件に合えばRefStringsからランダムに１文字取得して格納します。

GA

遺伝子を表すDNAObjectを一通り確認した所で遺伝的アルゴリズムそのものを実装しているオブジェクトGAを見ていきます。変数と処理の量は多いですが一つ一つは単純なものとなっています。

【変数】
TargetString - 各遺伝子が目指す文字列
PopulationSize - １世代ごとの個体数。10を指定すれば10個の個体が生成される。
MutationRate - 遺伝子の突然変異率。0.01%から1%の値が好ましい。
Population - 遺伝子を格納する配列
Highest_Fitness, Highest_Index - 現世代で最も良い適応率とその適応率を持つ遺伝子を示す配列のインデックス。
PopulationPool - 新たな世代を生み出すものに適した遺伝子を格納するための配列
N、X、Y - 一時変数

【カスタムイベント】
Create DNAObjects - DNAObjectのインスタンスを生成しCreate From Randomを呼び出す。生成されたインスタンスは配列Populationに格納する。

Calculate Highest DNA - 現世代で最も適応率の高い遺伝子を求める。

Create Mating Pool - ある程度環境に適応したと判断される遺伝子を交配用の遺伝子とし、交配用遺伝子配列に格納する。適応率が高い個体程多く格納される。

Create Next Gen DNA - 新しい世代を生み出すための準備と生成

Choice Random Parent Index - ランダムに次世代の親となる配列のインデックスを選択する。ルーレット方式による選択を行っている。

Create DNA from Parent - イベントChoice Random Parent Indexで選ばれたインデックスから遺伝子オブジェクトを取得し親として遺伝子を生成する。

【デフォルトイベント】
Begin Play - 指定された一世代ごとの個体数分DNAObjectを作成する。

Event Tick - メインループ。適応率を求め最も優れた個体を求め、次の世代を生成する。表示用の制御も行う。

このブループリントで注目して欲しいところは次世代を生成する過程の部分です。
交配用の遺伝子を格納するCreate Mating Poolでは各遺伝子が持つ適応率を100倍して整数値にしています。
第一世代を例にすると第一世代では0%から100%までの適応率を持つ遺伝子が生成されているはずです。100%の適応率を持つ遺伝子が現れた場合はそのまま処理を終了しますが、そうでは無い場合、適応率を100倍した数だけ交配用プールに格納します。
これにより適応率が高ければ高いほど多くの遺伝子を交配用プールに格納できます。つまり優れた遺伝子ほど次世代へ遺伝子を託すチャンスが増えるということになります。
そして世代が進むごとに適応率は上昇するはずなので、少なくとも前世代よりも結果が悪くなるということは起きなくなります。
この適応率が高い個体を選ぶ事を選択といい適応率が低いものを排除することを淘汰といいます。

交叉が幾つか種類があったように選択にも幾つか種類があります。
ルーレット方式 - 適応度に基づきルーレット盤を作成し、選択する方式
ランキング方式 - 適応度が最も高いものを50%の確率で選び、次に高いものを25%の確率で選ぶという順位ごとに確率が定められた選択方式
トーナメント方式 - 適応度に関わらずランダムに個体を選び、トーナメント式に適応度を比較する。トーナメントに選ばれた個体の中で最も適応度の高いものを選択する方式。

このプロジェクトではルーレット方式で親を選択しています。

詳しくはWikipediaで！

交叉や選択にいくつか種類がありました、ここでは簡易に説明しましたが詳しく知りたい方はWikipedia GAのページを読んでみてください。
中々面白いですよ。

おわりに

UE4での遺伝的アルゴリズムの実装に加えて遺伝的アルゴリズムそのものについても簡単に説明してみました。
遺伝的アルゴリズムは進化を通じて環境に適応していきますが、これに似たアルゴリズムとして「機械学習」があります。機械学習は遺伝的アルゴリズムに比べると考えが複雑ですが、過去の行動から問題に対する適切な行動をAI自身が学習するアルゴリズムです。
少し前に話題になった「Deep Learning」は機械学習に属する技術です。
現在ネットや書籍を漁りながらどうにか実装できないかと試行錯誤していますが、いつできるかわかりません。
興味を持った方は機械学習を是非実装してみてください。そして実装できたら自分に教えてください。よろしくお願いします。