遺伝的プログラミングを用いた項書換え系の自動合成に関する研究

点击翻译按钮获取中文摘要

本研究の目的は、GP手法により、停止性と合流性を満たす完備なTRSを自動合成することである。この目的を達成するために、平成13年度は、(1)適切な遺伝的操作の検討、(2)初期集団への制約の検討、(3)適合度(評価)関数の検討、について行い簡単な関数を表現するTRSの合成に成功した。特に、適合度関数の実現に際してTRSの停止性検証を行うことによって、これまでGPが不得意であった再帰的な関数の合成に成功している。しかし、実験を繰り返すことによって新たな問題点を発見した。実現したGPシステムでは関数記号や終端記号にデータ型による制限を行っていなかったため構文的には正しくとも、意味的に正しくないTRSを合成してしまう場合があった。平成14本年度は、この問題点を解決するため、データ型による項の構成と遺伝的操作を組合せ正しいTRSを合成するシステムを実現した、具体的には、予め、GPシステムに与える関数記号と終端記号にデータ型を付与し、このデータ型に違反する遺伝的操作を行わないように交差と突然変異オペレータを改良した。例えば、2つのリストの連結を行うappendをTRSで実現する場合、その第一、第2引数ともリスト型のデータ(項)を取る必要がある。平成13年度までのシステムでは、引数として任意のデータ型を取ってしまい、その結果、解へ結びつく個体数が減少し、期待する解を得るために、多くの世代を必要とした。平成14年度での改良の結果、構文的にも意味的にも正しいTRSの合成に成功した。ただし、現在は非常に簡単なTRSの合成のみが可能であり、今後の課題として、従来の帰納推論および完備化手続きとの連携により、より大規模なTRSの合成を行うシステムの実現があげられる。なお、これまでの成果をまとめた論文を執筆中である。