教室ブログ

2019.02.28

アルゴリズム

六十谷校

こんにちは、Wam六十谷校の川口です。

以前、AIによる遺伝的アルゴリズムを使ったゲームの映像を見たときに、おもしろそうだと思っていましたが最近色々なものに使われていると感じるようになりました。
遺伝的アルゴリズムは生物進化における遺伝と適者生存による自然淘汰の仕組みをソフトウェアで模すことで複雑な問題の最適解を探索する手法です。ある命題に対する解の候補を遺伝子とその集合体の染色体で表現した個体を複数用意し、適応度の高い個体を優先して交叉、突然変異などの操作を繰り返しながら最適解の探索を行います。必要とされる条件は評価関数の全順序性と探索空間が位相を持っていることです。
各要素は符号化し、表現型から遺伝子型などへ変換し、N個のランダムな個体の集団を「現世代」とし、それらをを格納可能な集団を「次世代」とします。評価関数を用いて、現世代の各個体の適応度を計算し、ある確率で交叉を行い、突然変異を適用します。個体数がN個になるまで繰り返し、次世代を現世代に移行し、命題が収束するまで繰り返します。最終世代の中で最も適応度の高い個体を解として出力します。ある閾値より適応度、増加率が大きくなった場合などを最終的な収束として判断しています。
符号化（エンコーディング）にはバイナリ、順列、実数値、木構造などがあり、合うものを選択します。バイナリエンコーディングは遺伝子をビットで表し、順列エンコーディングは遺伝子を順序を表す数字で表し、巡回セールスマン問題などに用いられます。実数値エンコーディングはバイナリで難しい場合に各遺伝子を数値や文字で表します。木構造エンコーディングは染色体を配列でなく木構造で表現し、遺伝伝的プログラミングなどの表現に用いられます。
符号化したものは選択して交叉させます。適応度に基づいて対象を選び出す操作で生物自然淘汰をモデルにしています。交叉は２つの個体の遺伝子の一部を入れ替えるもので、期待値選択、ランク方式、トーナメント方式、多点交叉法、一様交叉法、部分一致交叉法、サブツアー交叉法、摂動・転座・挿入欠失・大変異などがあり、世代間の変化を齎します。

現世代集合全体が次世代集合に置き換えられる離散世代モデルは、世代間における個体のオーバーラップが存在せず、単純GAモデルはルーレット選択と交叉・突然変異を用いて親世代と同数の子固体のみを次世代として残し、初期収束による局所解の発生や進化的停滞が起こりやすくなります。　連続世代モデルは現世代のうち一定の割合だけ入れ替えるので、初期収束が起こりにくく、多様性も維持できます。
問題点として、最初の方の世代で偶然に適応度の高い個体が生じた場合、その個体が爆発的に増えることがあり、探索が早い段階で収束してしまう初期収束があります。対策として、集団数を増やし、選択確率の変更、突然変異率を増やす（変異確率は通常0.1～1％に設定）などがあります。また、大変異という特定の世代において突然変異率を急激に高める方法（自然界の氷河期による大量絶滅などに相当）があります。また、最適解と一致しない遺伝子が混入することで最適解の生成を妨げるヒッチハイキングという問題があります。これは二点交叉の場合遺伝子長が増加するにつれて、加速度的に確率が低下しますが、一様交叉であれば遺伝子長に依存しません。
遺伝アルゴリズムは対象となる問題に関する数学的な知識がない場合でも適用が可能です。問題の性質に適したエンコーディングと交叉方法を選ぶことで、組み合わせが多く指数関数的に複雑さが増加する問題でも線形的な時間増加で探索することができます。新型新幹線の空力設計のデザインや人工衛星のアンテナの形状などにも使われており、NP困難に相当するナップサック問題や巡回セールスマン問題や創作としても利用できます。例えば音階の違いは周波数ですが、ある関数は周波数とその整数倍の波のみで構成されるなら周期関数であるといえます。倍音をまとめてコントロールするために遺伝的アルゴリズムで周波数変調をパラメータ操作することでFM音源を作成する手法もあります。GPU力は必要ですが、勘では難しい調整も地道な努力で成し遂げられる様は人間を模して作られたアルゴリズムだと感じます。