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

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

・解候補の表現形式と解候補を改変するためのオペレータ・解候補の質を定義する適合度関数・解候補の集合の中から有望なものを選び出す選択方法　通常これらの特徴は独立に定義される。このようなモデル自体を考え直すのも興味深いことではあるが、ここではGPのための表現形式のみを研究対象とする。

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

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

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

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

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

プログラムは離散的なタイム・ステップに従って実行される。ノード#nが持つ関数をfn、時刻tでの値をv(n,t)とする。関数fnが持つ引数の数をknとし、i番目の引数には#ln,iの値が代入されるものとする。時刻t+1における#nの値は、〓となる。プログラムへの入力は#1の値に代入され、#2の値はt=0において1とする。例として、プログラムへの入力が2進数1011だったとする。RTNの遷移は次のようになる。〓#1の値が0になったとき、プログラムへの入力が0を含んでいた場合に限って#2の値が0になる。

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

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

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

本論文は8章からなり、第1章は序論、第2章は進化計算、第3章は新しい表現形式の必要性、第4章はさまざまな表現形式、第5章は関数の回帰的なネットワーク、第6章はほかの手法との比較、第7章は考察、第8章は結論である。

第1章は序論であり、本論文の主張が簡潔にまとめられている。

第2章においては、本論文の背景知識と主題が提示される。本論文は、生物の進化をモデル化した自動最適化および設計手法（進化計算）による計算機プログラムの自動生成（遺伝的プログラミング）の際に用いる表現形式を提案するものである。進化計算は設計や最適化においてはかなりの成功を納めているが、一般的な自動プログラミングに応用するのは野心的な試みである。

第3章においては、なぜ遺伝的プログラミングのための表現形式を研究しなければならないのかが議論される。表現形式について議論するための視点が3つ提示される。第1は表現能力の問題である。自動的にプログラムを生成する手法は、あらかじめ問題についての深い知識がない場合には、任意のアルゴリズムを表現可能な形式（チューリング完全）を用いなければならない。第2は進化計算で用いるのにふさわしいかどうかである。チューリング完全であっても、進化計算には向いていないということがどういうことかが、セル・オートマタを例に議論される。進化計算のためのよい表現形式である基準は、すべてのアルゴリズムを表現可能であること、入出力の仕方を仕様に含めることができること、知識を導入しやすいこと、機能が分離していること（モジュール化）、階層化していることである。

第4章においては、第3章で提示された基準に沿って、すでに提案されている既存の表現形式が、遺伝的プログラミングにふさわしいかどうかが議論される。具体的には、自動的関数定義とメモリ付き遺伝的プログラミングである。自動的関数定義は前述の基準のうち、モジュール化と階層化のために導入された手法であるが、ユーザが設定しなければならないことが多いことと、実行環境によっては停止問題というチューリング完全ゆえの弊害を回避するのが難しいという問題があることが指摘されている。メモリ付き遺伝的プログラミングはチューリング完全性のために提案された手法であるが、モジュール化という点で難があり、実際に進化計算で利用できるかどうかが問題になる（第6章ではこの手法が成功しないことが実験的に示される）。

第5章においては、新しい表現形式である「関数の回帰的なネットワーク」が提案される。標準的な遺伝的プログラミングにおいては、表現形式として単一の構文木が用いられるのに対して、ここで提案される表現形式は、ネットワーク上に複数の純関数を配置し、同時にそのノードが値を持つようにしたものである。先述の進化計算のための表現形式への要求のうち、階層化以外の要求は満たされている。この表現形式がチューリング完全であることはこの章で具体的に証明される。

第6章においては、実際に関数の回帰的なネットワークを用いてプログラムを自動生成し、他の表現形式を用いた場合との比較がなされている。扱われている問題は、Tomita languageの判定、入力中の0と1の数が等しいかどうかの判定、入力されたビット列の反転などを行うプログラムの生成である。Tomita languageの判定は、既存のほかのチューリング完全な表現を用いた比較実験も行われており、その結果からは本論文の手法の有意性が示されている。ビット列の反転に関しては、既存のほかの研究との比較がなされ、本論文の手法のほうがユーザにとって使いやすいという結論が得られている。

第7章においては、本論文で提案された手法と関連はあるが第6章では扱われなかったものについての考察がなされる。

第8章においては、本論文の結論が述べられ、それと平行して本論文に関連する未解決の問題が提示される。

なお、本論文の一部は共同研究によって行われたものであるが、論文提出者が主体となって提案及び実験・分析・検証を行ったもので、論文提出者の寄与が十分であると判断する。

以上これを要するに本論文は、生物の進化をモデル化した自動最適化および設計手法（進化計算）による計算機プログラムの自動生成（遺伝的プログラミング）の際に用いる表現形式を提案し、実験的に評価することによりその有効性を示したものであり、情報科学の発展に貢献するところ少なくない。

したがって、博士（科学）の学位を授与できると認める。