学位論文
進化計算による自動プログラミングのための表現の研究

矢吹 太朗
東京大学大学院 新領域創成科学研究科 基盤情報学専攻

概要

遺伝的プログラミング (Genetic Programming, GP) のための新しい表現形式を提案する。 関数の回帰的なネットワーク (Recurrent Network consisting of Trees, RTN) である。 GPは進化計算 (evolutionary computing, EC) の一種で、プログラムの自動生成に用いられる。 ECは自動的な最適化やデザインのフレームワークである。

ECは次の要素で特徴付けることができる。

通常これらの特徴は独立に定義される。 このようなモデル自体を考え直すのも興味深いことではあるが、ここではGPのための表現形式のみを研究対象とする。

GPを利用する際に、われわれはRTNを用いてプログラムを表現する。 RTNは任意のアルゴリズムを表現できる、つまりチューリング完全な表現形式である。 そのため、RTNの利用者は問題の解がRTNで表現可能かどうかを心配する必要はない。 その一方で、最も普及している標準的なGPにおいては、プログラムは単一の構文木で表現され、その表現力は強く制限されたものになっている。 たとえば、構文木を構成する非終端記号が純関数で、構文木を評価した結果をプログラムの出力（または振舞い）と見なすならば、この表現のレパートリは有限オートマトンのものよりも小さくなる。

制限された表現力でも与えられた問題の解を記述するには十分だということを、進化計算に先立って知っているならば、このことは問題にはならない。 しかしながら、もしこの十分性を知らないで、しかも探索に失敗した場合、失敗の原因が進化計算にあるのか表現形式にあるのかを知ることはできない。 たとえば、 $ \{ww\vert w\in\{0,1\}*\}$ という言語を判定するプログラムを生成したいとしよう。 もしレパートリがプッシュダウン・オートマトンのそれと同じ表現を用いたならば、探索は決して成功しない。 プッシュダウン・オートマトンではこの言語を判定できないからである。

考えられる解決法として、理想的には無限の番地付きメモリとそれにアクセスするための非終端記号を導入するというものがある。 そのような非終端記号からなる構文木で解の候補を表現し、特定のメモリの値が停止条件を満たすまで構文木の評価を繰り返すならば、表現力はチューリング・マシンと同等つまりチューリング完全になることが示されている。

しかしながら、チューリング完全性以外にもGPのための表現形式が満たすべき条件はある。 それは次のようなものである。

これらの必要性は本文で詳しく議論する。

本論文ではこれらの条件を満たすような表現形式、RTNを提案する。 RTNは標準的なGPの自然な拡張である。 標準的なGPは解の表現として単一の構文木を用いる。 一方、RTNは回帰的なネットワークである。 ネットワークは複数のノードで構成されるが、個々のノードは値と構文木で表現される純関数を持つ。 構文木を構成するのに特別な非終端記号は必要ない。 終端記号は$ 4$つの変数と定数のいずれかである。 標準的なGPにおいては、プログラムへの入力は変数に代入されるが、RTNにおいてはノードの値に代入される。

RTNの例を示す。 $ 2$つのノードからなるRTNである。 各ノードが持つ関数は、

$\displaystyle \char93 1$ $\displaystyle : (c-P[c])/2,$    
$\displaystyle \char93 2$ $\displaystyle : P[a] d,$    

である。 ここで$ P$は$ 2$で割った余りを返すような手続きである。 関数は最大で$ 4$つの引数$ a$, $ b$, $ c$, $ d$を持つ。 これらの引数にはノードの値が代入される。 代入方法は、$ \char93 1$については $ \{*, *, 1, *\}$、$ \char93 2$については $ \{1, *, *, 2\}$のように表現される。 $ \char93 1$の$ 3$番目の要素と$ \char93 2$の$ 1$番目の要素はともに$ 1$であるから、$ \char93 1$の第$ 3$変数つまり$ c$と$ \char93 2$の第$ 1$変数つまり$ a$には$ \char93 1$の値が代入される。 $ \char93 2$の$ 4$番目の要素は$ 2$であるから、$ \char93 2$の$ 4$番目の変数つまり$ d$には$ \char93 2$の値が代入される。

プログラムは離散的なタイム・ステップに従って実行される。 ノード$ \char93 n$が持つ関数を$ f_n$、時刻$ t$での値を$ v[[n, t]]$とする。 関数$ f_n$が持つ引数の数を$ k_n$とし、$ i$番目の引数には#$ l_{n,i}$の値が代入されるものとする。 時刻$ t+1$における#$ n$の値は、

$\displaystyle v[[n, t+1]]=f_n[v[[l_{n,1},t]],\ \cdots\ ,v[[l_{n,k_{n}},t]]] $
となる。 プログラムへの入力は$ \char93 1$の値に代入され、$ \char93 2$の値は$ t=0$において$ 1$とする。 例として、プログラムへの入力が$ 2$進数$ 1011$だったとする。 RTNの遷移は次のようになる。
$ \char93 1$の値 $ 1011$ $ 101$ $ 10$ $ 1$ 0
$ \char93 2$の値 $ 1$ $ 1$ $ 1$ 0 0
$ \char93 1$の値が0になったとき、プログラムへの入力が0を含んでいた場合に限って$ \char93 2$の値が0になる。

RTNが任意のチューリング・マシンをシミュレートできること、つまりRTNが任意のアルゴリズムを表現できることは簡単に示すことができる。 証明は本文中で与える。

応用例として、RTNを用いたGPによる言語判定装置の自動生成を試みる。 これは従来のGPが失敗していた課題である。 RTNを用いたGPはこの課題に成功する。 比較実験として、番地付きメモリを用いたGPでもこの課題を試みるが、これは成功しない。 このことから、一般的な自動プログラミングにおけるRTNの有効性が期待される。

GPのための表現形式はほかにもさまざまなものが提案されている。 それらとRTNの違いについても議論する。 また、違いを議論する際に用いる基準についても考察する。 たとえば、No Free Lunch Theorem は重要ではないことがわかる。

TOP