付録4 迷路のエンコーディング方法

迷路を進化させるためには、迷路の構造を進化演算子が適用可能な表現でコード化する必要があります。そこで少し複雑ですが、迷路のコード化の仕組みを見ていきましょう。

Genome（遺伝子）は、迷路の高さと幅（Height/Width)を決めるgene、入り口からゴールまでの経路を決めるPath Genes、迷路の壁を決めるWall Genesの2つがあります。そして、Wall Genesは、壁の位置を表す W（wall gene）と、通路の位置を表す P（passage gene)の2つから構成されています。 Genomeにコード化されているこれらの情報を使って、Trajectory（経路）が作られ、そして、迷路（Maze）が作られます。

たとえば、Height（高さ）とWidth（幅）が共に10、Path Genesの位置がLoc:(6, 4)、Wall Genesの壁の位置が0.2、通路の位置が0.8の遺伝子からはまず次のような図がまず作られます。

どのような手順で上図のような迷路ができるのか手順を追ってみてみましょう。まず、HeightとWidthの情報から迷路を離散的に10×10のマス目に区切り、枠組みを作ります。そして、Path Genesに従って迷路の入り口から出口までに経路を作成します。この図では、左下端が入り口、右上端が出口です。Path Genesの情報であるLoc:(6, 4)は、迷路の入り口からy軸方向に4つ進み、x軸方向に6だけ進むことを表しています。そして、到達した地点から、ゴールへ向かって、垂直に進み、行き止まりになった地点で、水平方向に進みます。

次に、経路以外の部分の空間を部分空間に分けます。左下の位置(1, 0)から、(2, 0)、(3, 0)・・・とx方向に経路にぶつかるまで進めていきます。このとき、部分空間の最大サイズ(x, y)まで、この作業を繰り返します。たとえば、最大サイズ(x,y)が(5, 5)に定められている場合は、最大の部分空間は5×5となります。x軸方向での最大値に達したら、次はy軸方向に空間を同様に広げていきます。y軸方向に進むと、経路にぶち当たるので、そこでストップです。すると、結果として、左下に5×3の空間ができます。

その後、x軸の次のマス(6, 0)から同じ操作を繰り返します。すると、右下に4×5サイズの部分空間ができあがります（オレンジ色）。次は、(0, 4)から同じ操作を行い、5×5の部分空間ができあがります（緑色）、(6, 5)から同様の操作で、4×4の部分空間、最後に、左上に1×5の部分空間が作られます。こうしてすべての部分空間を作成した後に、それぞれの部分空間に入るための入り口を作ってあげます。これは経路から最も近い壁にそれぞれ作られます。

次に、作成した部分空間に今度は壁（W）と通路（P）を作ります。W（0.2）、P（0.8）それぞれの値は、それぞれ壁と通路を作る相対的な位置を表しています。

左下の部分空間を例に壁と通路を作ります。初期状態の壁を置く方向は縦方向です。x軸方向で部分空間の端から0.2の位置に壁を置きます。このとき、壁を置く位置は離散化されたブロックの位置になることに注意してください。そして、通路を0.8の位置に作ります。

壁を境に作られた2つの空間にさらに、壁と通路を作っていきます。ここでも、0.2の位置に置いていきますが、離散化されている位置に修正して置きます。右の空間も同様です。この作業を一番最初の空間単位になるまで繰り返します。同じ作業を他の部分空間にも行うと、上の図のようにすべての部分空間に壁と通路ができあがり、Genomeから迷路（表現型）へのデコードは完成です。

そして、突然変異によってHeight/Width、Path Genes、Wall Genesへの追加、変更が行われます。たとえば、Wall Genesへの突然変異が加わり、W: 0.4, P: 0.8が追加された後は次のような迷路が作成されます。

追加する壁の向きは、その部分空間で1つ前に追加された壁とは垂直の方向に追加します。前回の向きは縦だったので、今度は横方向に壁を追加します。一番左下の空間から、y軸方向に0.4の位置に壁を横に配置し、x軸方向に0.8の位置に通路を配置します。同様に他の空間にも壁や通路を配置していくと上のような図になります。

Path Geneに突然変異が加わると経路の曲がり角が増えることになり、迷路全体のサイズに突然変異が加わると、迷路のサイズが大きくなります。たとえば、サイズが11×11になった場合は次のような迷路になります。

迷路の難易度、複雑さは、壁の数が多いほど複雑な迷路として扱われます。