JP6663873B2 - プログラム自動生成システム及びプログラム自動生成方法 - Google Patents

Description

本発明は、プログラム自動生成システム及びプログラム自動生成方法に関する。

コンピュータプログラム作成は、高度な専門スキルが必要な作業の一つである。特に、大規模かつ複雑なプログラムを作成する場合や、記述すべき処理内容が難しい問題に対しては、その作成コストは非常に高くなる。このような設計を自動的に行う試みとして、例えば、遺伝的プログラミングがある。遺伝的プログラミングは、プログラムを構文木とみなして構造的に進化計算を行う手法である。

遺伝的プログラミングによる進化計算に関連する技術として、例えば、特許文献１がある。特許文献１は、入力データ及び目標データを問題として与え、この入力データ及び目標データに基づいてプログラムの処理フローを修正する処理フロー生成装置を開示している。この処理フロー生成装置では、処理の組み合わせ構造とパラメータを同時に進化計算する。

特開２０１５−２３０７０２号公報

しかしながら、特許文献１では、処理構造の基本単位である基本ノードや設定するパラメータの項目については、事前にユーザが設計しておかなければならない。

遺伝的プログラミングの交配処理及び突然変異処理は、ランダム性のある変換である。このため、対象が複雑な問題の場合には、適切に基本ノードやパラメータを設定しないと、処理の組み合わせ数が膨大となり解が収束しない。

特許文献１では、基本ノードやパラメータの設定を事前にユーザが設計しているので、複雑な問題に対して、適切に基本ノードやパラメータの設定が行われない可能性がある。この結果、処理の組み合せの爆発を起こしてしまう恐れがある。

本発明の目的は、処理の組み合せの爆発を抑制してプログラムを自動的に生成することにある。

本発明の一態様に係るプログラム自動生成システムは、生成すべき第１のプログラムに対する入力データ、目標データ及び設計要件の入力を受け付ける入力部と、複数の既存の第２のプログラムを記憶するプログラム記憶部と、前記第１のプログラムを生成するプログラム生成装置と、前記プログラム生成装置が生成した前記第１のプログラムを出力する出力部、を備え、前記プログラム生成装置は、前記プログラム記憶部に記憶された前記複数の第２のプログラムを分析してプログラムモデルを生成するプログラム分析部と、前記プログラム分析部が生成した前記プログラムモデルと前記入力部から入力された前記設計要件に基づいて、進化計算のための基本ノードと制約条件を生成する基本ノード／制約条件生成部と、前記基本ノード／制約条件生成部が生成した前記基本ノード及び前記制約条件と、前記入力部から入力された前記入力データ及び前記目標データに基づいて、前記進化計算により前記第１のプログラムを生成する最適化部と、を有することを特徴とする。

本発明の一態様に係るプログラム自動生成方法は、生成すべき第１のプログラムに対する入力データ、目標データ及び設計要件の入力を受け付け、複数の既存の第２のプログラムを記憶し、前記複数の第２のプログラムを分析してプログラムモデルを生成し、前記生成した前記プログラムモデルと前記入力された前記設計要件に基づいて、進化計算のための基本ノードと制約条件を生成し、前記生成した基本ノード及び前記制約条件と、前記入力された前記入力データ及び前記目標データに基づいて、前記進化計算により前記第１のプログラムを生成し、前記生成した前記第１のプログラムを出力することを特徴とする。

本発明によれば、組み合せの爆発を抑制してプログラムを自動的に生成することができる。

実施例1のプログラム自動生成システムの構成例を示すブロック図である。 実施例１のプログラム自動生成システムが適用されるシステム構成の一例を示すブロック図である。 実施例１のプログラム自動生成システムが実行する処理の概要を説明するフローチャートである。 実施例１のプログラム自動生成システムがプログラム分析処理で抽出する構文構造の１例である。 実施例１のプログラム自動生成システムがプログラム分析処理で抽出する構文構造が持つノード情報の１例である。 実施例１のプログラム自動生成システムが実行するプログラム分析処理の概要を説明するフローチャートである。 実施例１のプログラム自動生成システムが実行するプログラム分析処理の概要を説明するフローチャートであり、生成するプログラムモデルがベクトルデータである場合の１例である。 実施例１のプログラム自動生成システムが実行するプログラム分析処理の概要を説明するフローチャートであり、生成するプログラムモデルがテンプレートデータである場合の１例である。 実施例１のプログラム自動生成システムが実行するプログラム分析処理の概要を説明するフローチャートであり、生成するプログラムモデルが確率遷移グラフである場合の１例である。 実施例１のプログラム自動生成システムが実行するプログラム分析処理において、生成されるベクトルデータの１例である。 実施例１のプログラム自動生成システムが実行するプログラム分析処理において、生成されるベクトルデータの１例である。 実施例１のプログラム自動生成システムが実行するプログラム分析処理において、生成されるベクトルデータの学習過程の１例である。 実施例１のプログラム自動生成システムが実行するプログラム分析処理において、生成されるベクトルデータの学習過程の１例である。 実施例１のプログラム自動生成システムが実行するプログラム分析処理において、生成されるテンプレートデータの１例である。 実施例１のプログラム自動生成システムが実行するプログラム分析処理において、生成される確率遷移グラフの１例である。 実施例１のプログラム自動生成システムが実行する基本ノード・制約条件生成処理の概要を説明するフローチャートである。 実施例１のプログラム自動生成システムが実行する最適化処理の概要を説明するフローチャートである。 実施例２のプログラム自動生成システムが実行するプログラム分析装置の構成例を示すブロック図である。 実施例２のプログラム自動生成システムが実行するプログラム分析処理の概要を説明するフローチャートである。 実施例２のプログラム自動生成システムが実行するプログラム分析処理において生成される依存関係グラフの１例である。 実施例２のプログラム自動生成システムが実行するプログラム分析処理において生成される依存関係グラフ上に付加された重み情報の１例である。 実施例２のプログラム自動生成システムが実行するプログラム分析処理において、生成されるベクトルデータの学習過程の１例である。

以下、添付図面を参照して実施例について説明する。まず、実施例の概要について説明する。

遺伝的プログラミングによる進化計算では、最適化問題として進化計算を実行する際に、基本ノードやパラメータなどの制約条件の設計が非常に重要となる。このため、実施例のプログラム自動生成システム（図１参照）は、主に、以下の２つの処理機能を実行する。

（１）プログラムモデル学習機能１０１
既存のプログラム郡から知識を抽出して、プログラムの自動生成に利用する。このため、複数のプログラムが記憶されたプログラム記憶部２００からプログラムモデルを作成する。プログラム記憶部２００は、例えば、プログラムファイルが保持されたデータベースやオープンソースソフトウェア（ＯＳＳ）のソフトウェアリポジトリである。ソフトウェアリポジトリとしては、ＣＶＳ、Ｓｕｂｖｅｒｓｉｏｎ、Ｇｉｔなどのソフトウェア構成管理システムが含まれる。プログラムモデル学習機能１０１では、事前にプログラム記憶部２００からプログラム郡（ソフトウェア郡）を読み出して分析し、その分析結果をプログラムモデルとして、プログラムモデル記憶部１０５に格納しておく。これにより、事前にユーザが基本ノードやパラメータの設計を行う必要はない。

プログラムモデルとしては、例えば、プログラムの全体の意味をコード化したベクトルデータや、複数プログラム間から頻出構造をテンプレートとして抽出した構造データがある。プログラムモデル記憶部１０５はベクトルデータと構造データを系統的に格納するデータベースである。例えば、ＳＱＬなどのリレーショナルデータベースや、特に構造データを扱う場合には、ＸＭＬデータベースが利用できる。

（２）プログラムモデル活用機能１０２
事前に生成されたプログラムモデルと、ユーザが入力する設計要件を用いて、進化計算のための基本ノードと制約条件を生成する。そして、生成された基本ノードと制約条件と、入力データ及び目標データを用いて進化計算を実行してプログラムを生成する。進化計算は、例えば、遺伝的プログラミングである。生成される基本ノードは、進化計算の組み合わせ要素となるノードである。

制約条件は、プログラムモデルの種類と活用方法によって多岐のものがある。狭義には、制約条件は、進化計算のパラメータであり、個体数、世代数、交叉確率、突然変異確率などが含まれる。また、広義には、ノードの分類情報による選択重み、ノードの選択確率などが含まれる。ユーザが入力する設計要件は、例えば、活用プログラムの種別、ライブラリの種別、様式などが含まれる。また、プログラムを修正して改良したプログラムを生成する場合において、修正前のプログラムを設計要件に含めることもできる。進化計算においてプログラムは木構造で表現され、進化計算によって最適化された木構造は、対応するプログラムコードに変換されて出力される。

以上のような２つの機能（プログラムモデル学習機能１０１、プログラムモデル活用機能１０２）を持つ処理を実行することにより、データベースやソフトウェアリポジトリの中に含まれる既存のプログラムの中から知識を取り出してプログラムモデルを作成する。さらに、生成されたプログラムモデルを、例えば、遺伝的プログラミングの進化計算に活用することができる。よって、複雑な問題に対しても、処理の組み合わせの爆発を起こすことなくプログラムの自動生成が可能となる。

以下、図１、図２を参照して、実施例1のプログラム自動生成システムについて説明する。

図２に示すシステムは、プログラム生成装置１００、基地局２２０、ユーザ端末２１０、及びプログラム記憶部２００を有する。プログラム生成装置１００、基地局２００及びプログラム記憶部２００は、ネットワーク２４０を介して互いに接続される。ネットワーク２４０は、例えば、ＷＡＮ、ＬＡＮ等が考えられるが、ネットワーク２４０の種別に限定されない。ユーザ端末２１０は、基地局２２０を介して無線通信を介して、プログラム生成装置１００と接続される。なお、ユーザ端末２１０と基地局２２０との間は有線通信を介して接続されてよいし、ユーザ端末２１０が直接ネットワーク２４０と接続されてもよい。

ユーザ端末２１０は、例えば、パーソナルコンピュータ又はタブレット端末等の装置である。ユーザ端末２１０は、プロセッサ（図示省略）、メモリ（図示省略）、ネットワークインタフェース（図示省略）及び入出力装置（図示省略）を有する。入出力装置には、ディスプレイ、キーボード、マウス、及びタッチパネル等が含まれる。

ユーザ端末２１０は、プログラム生成装置１００を操作するためのユーザインタフェース（ユーザＩ／Ｆ）２１１を提供する。ユーザインタフェース２１１は、プログラム生成装置１００に設計要件や、入力データ及び目標データを入力し、また、プログラム生成装置１００から出力されたプログラムを受け付ける。

プログラム生成装置１００は、例えば、ハードウェア構成としてプロセッサ（図示省略）、メモリ（図示省略）、ネットワークインタフェース（図示省略）及びストレージ装置（図示省略）を備えた計算機である。

プログラム生成装置１００は、ユーザ端末２１０の指示に従って、プログラム生成処理を実行する。プログラム記憶部２００からプログラムデータを取得し、取得されたプログラムデータを分析する。プログラム記憶部２００から検索され、読み込まれた分析対象となるプログラムデータは、内部のストレージ装置又はメモリに格納される。プログラム生成処理のための実行プログラム及び当該プログラムの実行時に用いられる情報は、メモリに格納される。プロセッサが、当該プログラムを実行することで、プログラム生成装置１００が有する各種機能を実現できる。以下の説明において、機能部を主体に処理の説明をするときには、当該機能部を実現するプログラムがプロセッサによって実行されていることを示す。

プログラム記憶部２００は、例えば、プログラムファイルが保持されたデータベースやオープンソースソフトウェア（ＯＳＳ）のソフトウェアリポジトリである。ソフトウェアリポジトリには、ＣＶＳ、Ｓｕｂｖｅｒｓｉｏｎ、Ｇｉｔなどのソフトウェア構成管理システムが含まれる。

図１を参照して、メモリに格納されるプログラム生成処理のための実行プログラム及び情報について説明する。

プログラム生成装置１００は、プログラムモデル学習機能１０１とプログラムモデル活用機能１０２の２つの機能を有し、複数のプログラムモジュールから構成される。具体的には、プログラム生成装置１００は、プログラム検索部１０３、プログラム分析部１０４、プログラムモデル記憶部１０５、基本ノード／制約条件生成部１０６、最適化部１０７、基本ノード記憶部１０８を含む。

プログラム検索部１０３は、ユーザインタフェース２１１から検索項目やキーワードを受け取り、プログラム記憶部２００にアクセスしてプログラムを取得する。取得したプログラムは、内部ストレージ装置又はメモリに格納する。

プログラム分析部１０４は、取得したプログラムを分析し、プログラムモデルを生成する。生成したプログラムモデルは、プログラムモデル記憶部１０５に格納する。

プログラムモデル記憶部１０５は、生成されたプログラムモデルを格納する。内部ストレージ装置またはメモリ、もしくは、外部ネットワーク２４０を介して接続されるサーバまたはデータベースであってもよい。

基本ノード／制約条件生成部１０６は、ユーザインタフェース２１１から設計要件を受け取り、設計要件を満たすプログラムモデルをプログラムモデル記憶部１０５から抽出し、基本ノードと制約条件を生成する。生成した基本ノードは、基本ノード記憶部１０８に格納する。

最適化部１０７は、基本ノードと制約条件を受け取り、進化計算を実行してプログラムを生成する。生成したプログラムはユーザインタフェース２１１を介して、ユーザ端末２１０に出力される。

基本ノード記憶部１０８は、生成された基本ノードを格納する。内部ストレージ装置またはメモリ、もしくは、外部ネットワーク２４０を介して接続されるサーバまたはデータベースであってもよい。

次に、図３を参照して、プログラム生成装置１００が実行する処理について説明する。

プログラム生成装置１００は、ユーザ端末２１０から処理の開始を受信した場合に、以下の処理を実行する。

＜プログラムモデル学習機能１０１＞
プログラム生成装置１００は、ユーザウインタフェース２１１からキーワード、対象となるデータベース又はソフトウェアリポジトリの指定、期間指定などの検索項目を受け付け、それらの情報を元に、外部ネットワーク２４０を介して、プログラム記憶部２００から該当するプログラム群を検索する（ステップＳ３０1）。具体的には、プログラム検索部１０３が、プログラム群を検索する。検索されて抽出されたプログラム群は、プログラム生成装置１００の内部ストレージに格納される。

プログラム生成装置１００は、抽出されたプログラム群に対して、プログラム分析処理を実行する（ステップＳ３０２）。具体的には、プログラム分析部１０４がプログラム分析処理を実行する。プログラム分析処理では、プログラムは、図４に示すような抽象構文木（ＡＳＴ：Abstract Syntax Tree）などの木構造へ変換され、それらをベースに処理される。

プログラム分析処理と生成されるプログラムモデルには、多様な実施形態がある。例えば、生成されるプログラムモデルとしては、木の個体やノード毎に計算されるベクトルデータ、複数の木構造間の類似構造を抽出したテンプレートデータ、複数の木構造間の重ね合わせによって生成する確率遷移グラフデータなどが含まれる。プログラム分析部１０４が実行するプログラム分析処理については、図６、図６Ａ、図６Ｂ、図６Ｃを用いて後述する。

プログラム生成装置１００は、生成されたプログラムモデルをプログラムモデル記憶部１０５に格納する（ステップＳ３０２）。具体的には、プログラム分析部１０４がプログラム記憶部１０５への格納を実行する。プログラム分析処理によって作成されたプログラムモデルは、分析内容とプログラムモデルのデータ構造を考慮し、プログラムモデル記憶部１０５に系統的に格納される。

ステップＳ３０１〜Ｓ３０３までの処理がプログラムモデル学習機能１０１に該当する。これらのステップにおいて、プログラム記憶部２００に格納された既存のプログラム群の知識がプログラム分析部１０４によって学習され、プログラムモデルとして、プログラムモデル記憶部１０５に蓄えられる。

＜プログラムモデル活用機能１０２＞
プログラム分析装置１００は、進化計算に必要な基本ノードと制約条件を、プログラムモデル学習機能１０１で生成されたプログラムモデルと、ユーザが入力する設計要件を用いて生成する（ステップＳ３０４）。具体的には、基本ノード／制約条件生成部１０６が、基本ノード・制約条件生成処理を実行する。ユーザが入力する設計要件は、例えば、活用プログラムの種別、ライブラリの種別、様式などがある。これらは、プログラムモデル記憶部１０５に対するプログラムモデルの参照に使われる。

基本ノードは、木構造の各ノードを構成する基本要素である。例えば、図４に示す木構造のｎ０〜ｎ８が基本要素を表し、内容としては、例えば、図５のテーブルに記載のノードがある。図５に記載のノードは、意味の粒度が細かいが、プログラムモデルを用いて基本となる粒度が大きなノードを作成して進化計算の収束性を高める。

制約条件は、プログラムモデルの種類と活用方法によって多岐のものがある。狭義には、制約条件は、進化計算のパラメータであり、個体数、世代数、交叉確率、突然変異確率などが含まれる。また、広義には、ノードの分類情報による選択重み、ノードの選択確率などが含まれる。制約条件は、ユーザの設計要件で直接指定することもできる。基本ノード／制約条件生成部１０６が実行する基本ノード／制約条件生成処理については後述する。

プログラム分析装置１００は、生成された基本ノードを基本ノード記憶部１０８に格納する（ステップＳ３０５）。具体的には、基本ノード／制約条件生成部１０６が基本ノード記憶部１０８への格納を実行する。ここで、基本ノード記憶部１０８は、内部ストレージ又はメモリ内のモジュールである。

プログラム分析装置１００は、生成された基本ノードと制約条件を元に、進化計算を実行してプログラムを生成する（ステップＳ３０６）。具体的には、最適化部１０７が、遺伝的プログラミングによる進化計算を実行する。最適化部１０７は、ユーザインタフェース２１１を介して、入力データ及び目標データを入力として受け付ける。入力データに対する出力データと目標データの比較から適応度を決定する。

進化計算において、木構造で表現されたプログラム群は、突然変異、交差などの遺伝的プログラミングの演算を繰り返し行って適応度を評価され、既定となる世代に到達するもしくは解が収束した時点で処理は終了する。最適化部１０７は、終了時における収束した木構造をプログラムコードに変換する。最適化部１０７が実行する最適化処理については後述する。

プログラム分析装置１００は、生成したプログラムコードを、ユーザインタフェース２１１を介して、ユーザ端末２１０へ出力する（ステップＳ３０７）。このとき、プログラムコードをユーザ端末２１０にある画面上に表示するようにしてもよい。また、プログラムコードの作成完了だけを通知し、ユーザがプログラム分析装置１００に問い合わせてダウンロードするようにしてもよい。

ステップＳ３０４〜Ｓ３０７までの処理がプログラムモデル活用機能１０２に該当する。これらのステップＳ３０４〜Ｓ３０７において、プログラム記憶部２００に格納された既存のプログラム群の知識が、最適化処理によって活用されてプログラムが生成される。

＜各処理の説明＞
図６を参照して、実施例１のプログラム分析部１０４が実行する処理の概要について説明する。ここで、図６Ａは、実施例１のプログラム分析部１０４が実行する処理の１形態の概要を説明するためのフローチャートである。図６Ｂは、実施例１のプログラム分析部１０４が実行する処理の１形態の概要を説明するためのフローチャートである。図６Ｃは、実施例１のプログラム分析部１０４が実行する処理の１形態の概要を説明するためのフローチャートである。

図７Ａ、図７Ｂは、図６Ａの実施において、作成されるノード辞書の１例を示す説明図である。図８Ａ、図８Ｂは、図６Ａの実施において、ノードベクトルの学習を示した１例を示す説明図である。図９は、図６Ｂの実施において、抽出されたモデルの１例を示す説明図である。図１０は、図６Ｃの実施において、作成されたモデルの１例を示す説明図である。

プログラム分析部１０４は、プログラム群を入力として、それらからプログラムモデルを学習して生成する。プログラム分析部１０４は、まず、入力されたプログラム毎（ステップＳ６０1）にプログラムを木構造へと変換する（ステップＳ６０２）。プログラムに対する木構造は、例えば、抽象構文木である。図４に示すような構造で表現され、各ノードは、例えば、図５に示すような意味を持つ。プログラム分析処理と生成されるプログラムモデルには、多様な実施形態がある。例えば、生成されるプログラムモデルとしては、プログラムやノード毎に計算されるベクトルデータ、複数の木構造間の類似構造を抽出したテンプレートデータ、複数の木構造間の重ね合わせによって生成する確率遷移グラフデータなどが含まれる。

以下、図６Ａ、図６Ｂ、図６Ｃを参照して、プログラムモデルの実施形態について説明する。

図６Ａは、プログラムや木構造のノード毎に計算されるベクトルデータをプログラムモデルとした場合の実施形態である。

まず、プログラム分析部１０４は、入力されるプログラム群からノード辞書を作成する（ステップＳ６１１）。ノード辞書は、入力される全てのプログラムにおいて出現するノードの種別を列挙したリストである。図７Ａは、図４に対応するノード辞書の例であり、プログラムＸ４００とプログラムＹ４０１に出現するノードの種別が列挙されている。

プログラム分析部１０４は、ノード辞書の項目毎（ステップＳ６１２）に、ノードベクトルを学習する（ステップＳ６１３）。ノードベクトルは、ノードの種別毎に設定される多次元ベクトルであり、初期値は、例えば、ランダムな値である。ノードベクトルは、構文木の全ての親ノードと子ノードの関係を抽出し、それらをサンプルに、機械学習などの手法によって繰り返し学習することで導出される。機械学習の手法には、ニューラルネットワークの手法などを用いることができる。ノードベクトルの学習（ステップＳ６１３）が終了すると、図７Ｂのように各ノードの項目に対してベクトル情報が与えられる。

図８Ａは、ノードベクトルの学習終了時に、図４のプログラムＸ４００に対して、ノードベクトルが付加された様子を説明したものである。図７Ｂのテーブルからわかるように、図８Ａのノードのn0,n1,n2…などのラベルが同じ場所には、同じノードベクトルが付加されている。なお、ノードベクトルの次元数はパラメータであり、事前に設定しておいてもよいし、分析の都度、ユーザインタフェース２１１を介して、分析条件設定により指定してもよい。

プログラム分析部１０４は、プログラム毎（ステップＳ６１５）に、木の末端、すなわち、葉の部分からノードベクトルの追学習を実施する（ステップＳ６１６）。ステップＳ６１６では、ステップＳ６１３で学習されたノードベクトルを初期値として、より根に近いノードが下層のノードの情報を含むことができるようにベクトル情報を統合する。図８Ｂは、ノードベクトルの追学習を示したものであり、下層のノードから再帰的に上層のノードで、ベクトル情報を統合していく。ベクトル情報の統合には、線形結合を用いてもよいし、部分構造をニューラルネットワークの構造として学習して求めてもよい。

以上の処理を実行することにより、プログラム分析部１０４は、上層のノードベクトルほど、抽象度の高い表現を持つベクトル情報が得られる。最上位のノードに着目すれば、プログラムの意味をベクトルで表現することができる。図６Ａの実施形態では、プログラムの構造データと、それぞれのノードが持つベクトルデータをプログラムモデルとして出力する。

図６Ｂは、複数の木構造間の類似構造を抽出したテンプレートデータをプログラムモデルとした場合の実施形態である。

プログラム分析部１０４は、複数の既存のプログラムから共通構造を抽出するために、全てのプログラムの構文木の中から部分構造を抽出し（ステップＳ６２３）、その出現数を元に共通構造を抽出していく（ステップＳ６２５）。 初期の部分構造を２ノードの構造とし、ステップＳ６２１の繰り返しにおいて、共通する部分構造を拡張しながら、共通構造を抽出する。図９は、図４に対応して共通構造を抽出した木構造である。なお、この実施形態では完全一致する共通構造を抽出しているが、それに限らず類似の構造であればよい。出現数はパラメータであり、事前に設定しておいてもよいし、分析の都度、ユーザインタフェース２１１を介して、分析条件設定により指定してもよい。

以上の処理を実行することにより、プログラム分析部１０４は、類似の構造を持つ部分木のモデルを抽出することができる。図６Ｂの実施形態では、この類似の構造を持つ部分木のモデルをプログラムモデルとして出力する。

図６Ｃは、複数の木構造間の重ね合わせによって生成する確率遷移グラフデータをプログラムモデルとした場合の実施形態である。

まず、プログラム分析部１０４は、プログラムリストを作成する（ステップＳ６３１）。そして、プログラムリストの１番目のプログラムをベースプログラムとして設定する（ステップＳ６３２）。プログラムリストの項目毎に、ベースプログラムの木構造に対して、対象となるプログラムの木構造を重ね合わせていく（ステップＳ６３４）。このとき、構造の重ね合わせによって、重なり合う部分のエッジ（辺）またはノードは、重みが増え、重ね合わせされた木構造は確率遷移グラフとなる。図１０は、対象となるプログラムを、図４のプログラムＸ４００とプログラムＹ４０１とした場合の、確率遷移グラフの１例である。太いラインで示されたエッジとノードは重なる部分であり、他のエッジやノードと比較して、高い尤度（確率）が設定されている。

以上の処理を実行することにより、プログラム分析部１０４は、プログラム構造に対して確率を持つ確率遷移グラフを作成することができる。図６Ｃの実施形態では、この確率遷移グラフをプログラムモデルとして出力する。

次に、図１１を参照して、基本ノード／制約条件生成部１０６が実行する処理の概要について説明する。

基本ノード／制約条件生成部１０６は、ユーザインタフェース２１１を介して入力されるユーザの設計要件と、プログラムモデルとを用いて、進化計算のための基本ノードと制約条件を生成する。

基本ノード／制約条件生成部１０６は、ユーザインタフェース２１１を介して入力されるユーザの設計要件を読み込む（ステップＳ１１０１）。ここで、設計要件は、例えば、活用プログラムの種別、ライブラリの種別、様式などが含まれる。プログラムを修正して改良したプログラムを生成する場合において、修正前のプログラムを設計要件に含めることもできる。

基本ノード／制約条件生成部１０６は、設計要件に従って、プログラムモデルを選択して読み込む。設計要件として、活用プログラムの種別が選択されていた場合、類似のプログラムに起因するプログラムモデルを選択する。また、前述したベクトルデータ、テンプレートデータ、確率遷移グラフのいずれのモデルを使う、もしくは組み合わせて使うかも選択することができる。

基本ノード／制約条件生成部１０６は、プログラムモデルと設計要件に従って、制約条件を生成する（ステップＳ１１０３）。ここで、制約条件は、プログラムモデルの種類と活用方法によって多岐のものがある。例えば、狭義には、制約条件は、進化計算のパラメータであり、個体数、世代数、交叉確率、突然変異確率などが含まれる。また、広義には、ノードの分類情報による選択重み、ノードの選択確率および変異確率などが含まれる。

基本ノード／制約条件生成部１０６は、狭義の制約条件である進化計算に必要なパラメータを、事前に設定しておいたものを利用してもよいし、もしくは、設計要件でユーザが指定したものを用いてもよい。基本ノード／制約条件生成部１０６は、広義の制約条件を、主にプログラムモデルの分析によって生成する。

例えば、ベクトルデータによるプログラミングモデルでは、各ノード間の類似度をベクトルデータから容易に計算することができる。そのため、予めプログラムモデル記憶部１０５に格納されているベクトルデータを複数のカテゴリに分類（分類１、分類２、分類３等）することで、プログラムらしさを表現することができる。これらのノードの分類と、交差や突然変異対象のノードを比較することで、プログラムらしくない部分を優先して排除することが可能となる。よって、制約条件は、ノード分類情報による選択重みとして与えられる。

例えば、ベクトルデータによるプログラミングモデルでは、後述する進化計算における初期集団の生成において、プログラムらしさを表現可能な分類情報により、ランダムではなく、よりプログラムらしい構造を持つ個体を生成し、優先的に集団に含めることができる。

例えば、テンプレートデータまたは確率遷移グラフによるプログラミングモデルでは、プログラムのよりメタな構造を進化計算の更新処理に利用することができる。特に、確率遷移グラフでは、ノード間の確率遷移が定義されており、ノード間の接続の自然さを確率として表現することができる。この情報を用いることで、接続の不自然な箇所を優先的に排除してより自然なプログラムを生成できるように、通常の進化計算におけるランダムな変化に方向付けを行うことができる。よって、制約条件は、ノードの選択確率および変異確率として与えられる。

基本ノード／制約条件生成部１０６は、プログラムモデルと設計要件に従って、進化計算のための基本ノードを生成する（ステップＳ１１０４）。基本ノードは、進化計算における木構造の各ノードを構成する基本要素となる。前述のように、プログラムモデルを用いて、基本となる粒度が大きなノードを作成し、進化計算の収束性を高める。

基本ノード／制約条件生成部１０６は、設計要件に、ライブラリ情報など、既に構造の情報を持った要素が指定された場合には、それを直接基本ノードに含めることができる。

基本ノード・制約条件生成部１０６は、基本ノードを主にプログラミングモデルの分析によって生成する。例えば、ベクトルデータによるプログラミングモデルの場合、プログラムらしさを表現した分類情報のから、代表的なベクトルを抽出し、そのベクトルに対応するノードを構成する部分構造を、基本ノードに加えることができる。

例えば、テンプレートデータによるプログラミングモデルの場合、テンプレートとして与えられる構造を、そのまま基本ノードに加えてもよい。

以上の処理を実行することにより、基本ノード／制約条件生成部１０６は、プログラミングモデルを活用し、種々の基本ノード、制約条件を生成することができる。

次に、図１２を参照して、最適化部１０７が実行する処理の概要について説明する。

最適化部１０７は、生成された基本ノードと制約条件を元に、遺伝的プログラミングによる進化計算を実行する。

最適化部１０７は、制約条件を元に、初期世代の集団を生成する（ステップＳ１２０１）。個体数、世代数、交叉確率、突然変異確率が制約条件として設定される。プログラムモデルにより生成された分類によって、個体の生成に確率が付与されている場合には、その情報を用いて個体を生成し、それを繰り返すことで集団を生成する。付帯情報がない場合には、ランダムに初期個体が生成される。個体生成のための基本ノードとしては、基本ノード／制約条件生成部１０６が生成した基本ノードを用いる。

最適化部１０７は、世代毎（ステップＳ１２０２）に、進化計算を実行する。まず、入力された入力データ及び目標データを用いて、適合度を計算する。ここで、適合度は、入力データに対する個体の出力データと、目標データの距離を表したものである。個体が所望の進化段階になったか否かは、この適合度によって判定される。

最適化部１０７は、適合度と制約条件を元に、集団から個体を選択する（ステップＳ１２０４）。適合度に比例する確率分布を用いて、変異させる数個体を選択する。このとき、個体の選択に、プログラムモデルによる生成された分類データがある場合には、その確率も考慮する。

最適化部１０７は、集団から選択された個体に対して、交差処理または突然変異処理を実行する（ステップＳ１２０５）。交差処理または突然変異処理は、交差確率及び突然変異確率によって決定される。交差または突然変異するノードを決定する場合、プログラムモデルから生成された選択確率が存在すれば、それを考慮する。存在しない場合は、ランダムに決定する。

最適化部１０７は、修正した個体を集団に戻す（ステップＳ１２０６）。最適化部１０７は、ステップＳ１２０２〜ステップＳ１２０７までの処理を世代数が既定数に達成するまで繰り返す。もしくは、収束した個体（出力データと目標データが一致した個体）が一定数出現するまで繰り返す。

最適化部１０７は、収束した個体の中から代表個体を選出する（ステップＳ１２０８）。ここで、例えば、複雑な構造ではなく単純な構造で記述するため、木構造のサイズが小さな個体を優先して選択する。

最適化部１０７は、代表個体をプログラムコードへ変換する（ステップＳ１２０９）。

以上の処理を実行することで、最適化部１０７は、プログラムモデルから生成した基本ノードと制約条件を活用し、解の収束性を高めることが可能となる。

実施例１によれば、プログラム生成装置１００は、データベースやソフトウェアリポジトリの中に含まれる既存のプログラムの中から知識を取り出して、ベクトルデータ、テンプレートデータ、確率遷移グラフなどのプログラムモデルを作成する。そして、生成されたプログラムモデルから基本ノードと制約条件を生成して遺伝的プログラミングの進化計算に活用する。これらを用いれば、複雑な問題に対しても、組み合わせ爆発を起こすことなくプログラムの自動生成が可能となる。

以下、図１３、図１４を参照して、実施例２のプログラム自動生成システムについて説明する。まず、実施例２の概要について説明する。

プログラム開発の現場において、大規模なソフトウェアリポジトリの活用が進んでいる。ソフトウェアリポジトリとは、プログラムやドキュメント、バグレポートなどの成果物を蓄積するデータベースのことである。ソフトウェア資源の管理や共有、再利用が可能となるメリットがある一方で、大規模化が進むことで、再利用のための検索や信頼性の確認といった活用の手間も増えている。これに対し、プログラムの普遍的な意味づけを与えようという動きがある。プログラムの意味づけに関する方法としては、人工知能分野ではディープラーニングなど機械学習が注目されており、特に、自然言語分野では、単語や文章の意味づけに目覚ましい進展がある。ベクトル化によって単語の概念を扱えるように学習させるアプローチである。プログラムを抽象構文木（ＡＳＴ）として扱うことで構成的な学習を可能とし、抽象構文木（ＡＳＴ）のノードレベルのベクトル化とツリーベースのニューラルネットワークによってプログラム全体の意味表現を獲得する。

既存のプログラムを活用するためには、既存プログラムから学習された分類モデルが必要であり、普遍性をもったプログラムの意味づけや表現方法が必要となる。そこで、プログラムの表現方法として、構文構造だけでなく、プログラム処理の依存関係を考慮した上でベクトル表現が作成できる仕組みを与え、構文的な情報、意味的な情報の双方を利用する。これにより、プログラムの意味的な表現方法として、構文構造情報に加え、処理の依存関係も含めたプログラムのベクトル表現が可能となる。これにより、プログラムの分類問題などにおいて、高い精度を実現することができる。

実施例２では、プログラム分析部１０４の処理の、特に、ベクトルデータによるプログラムモデルにおいて、抽象構文木の構造だけでなく、状態や関数などのプログラム処理の依存関係も含めてベクトルデータを生成する。このように、実施例２では、構文的な情報と意味的な情報の双方を利用する。

実施例２では、実施例１との差異を中心に実施例２について説明する。なお、実施例１と同一の構成には同一の符号を付し、詳細な説明は省略する。

図１３を参照すると、実施例２のプログラム分析部１０４の構成例を示すブロック図である。実施例２のプログラム分析部１０４は、構文情報取得部１３０１、ノードベクトル学習部１３０２、依存関係情報取得部１３０３、重み生成部１３０４及びノードベクトル結合部１３０５を有する。

構文情報取得部１３０１は、入力されたプログラムを木構造へと変換する。ノードベクトル学習部１３０２は、変換された全てのプログラムの木構造を用いて、ノード辞書の項目毎のノードベクトルを学習する。

依存関係情報取得部１３０３は、入力されたプログラムから、プログラム内部に記述されている依存関係を抽出する。依存関係情報は、例えば、関数の参照関係などがある。ソース、クラス、データなど別の粒度の依存関係をベースにしてもよい。依存関係情報は、例えば、依存関係グラフとしてグラフ構造で記述される。重み生成部１３０４は、生成された依存関係情報を入力として、ノード毎に重要度を示す重みを生成する。ノードベクトル結合部１３０５は、生成されたノードベクトル情報と重み情報と用いて、ベクトルを結合し、対応するプログラムのベクトルデータを得る。

図１４を参照して、実施例２のプログラム分析部１０４が実行する処理について説明する。プログラム分析部１０４は、まず、入力されたプログラム毎（ステップＳ６０1）に、プログラムを木構造へと変換する（ステップＳ６０２）。この処理は、実施例１と同様である。続いて、図６Ａと同様に、ノードベクトルの学習を実施する（ステップＳ６１１〜Ｓ６１４）。

次に、ノードベクトルの学習に並行して、プログラム毎に、依存関係の抽出処理を行う（ステップＳ１４０４）。依存関係情報は、例えば、関数の参照関係などである。ソース、クラス、データなど別の粒度の依存関係をベースとしてもよい。依存関係情報は、例えば、依存関係グラフとしてグラフ構造で記述される。

図１５Ａは、依存関係を関数の参照関係とした際の依存関係グラフの例を示す。依存関係を求める要素をノード、関係性をエッジとして接続してグラフを生成する。図１５Ａでは、関数をノードとし、例えば、関数Ｂが関数Ａを参照した場合、関数Ａから関数Ｂへの接続を有効エッジとして記載している。また、関数Ｃは関数Ｄと関数Ｅを参照しているので、関数Ｄから関数Ｃへの接続を有効エッジとして、関数Ｅから関数Ｃへの接続を他の有効エッジとして記載している。計算機プログラム上で、依存関係グラフは、例えば隣接リストで与えることができる。

プログラム分析部１０４は、生成した依存関係情報を元に、構文木の各ノードに付加する重み情報を生成する。例えば、図１５Ａの依存関係グラフ上で、中心性計算を実施することで、図１５Ｂのようなグラフ上の各ノードの重要度を算出することができる。

依存関係グラフ上で実施される中心性計算には、例えば、多くのノード間の媒介となるものに高いスコアを与える媒介中心性などが利用できる。例えば、関数Ｅは関数Ｉ、関数Ｊ及び関数Ｋを参照しているので、関数Ｅのノードに付加する重み情報として高いスコア（０．７）が与えられる。一方、関数Ａのノードは、どのノードも参照していないので、関数Ａのノードに付加する重み情報として低いスコア（０．２）が与えられる。

このノード毎に計算された重要度を構文木上の各ノードに対応づけることで、該当するノードベクトルの結合に重みを与える。図１６は、構文木４００において、n0が図１５Ａの関数Ｃ、n1が関数Ｅ、n3が関数Ｄ、n4が関数Ｂとした場合の例である。依存関係グラフから導出された重み情報は、n1（関数Ｅ）、n3（関数Ｄ）、n4（関数Ｂ）を結合して、n0（関数Ｃ）を結合する時に使われる。

プログラム分析部１０４は、ノードベクトルの結合処理を実行する（ステップＳ１４０９）。結合の接続関係は、構文構造情報から得る。ベクトルを結合する際の重みは、重み情報から得る。重み情報を考慮すること以外は、図６Ａと同様の手続きである。

実施例２によれば、ベクトルデータの学習に、構造情報に加え、依存関係情報を用いることで、状態や接続関係を表現可能なベクトルデータを生成することが可能となる。より高い表現能力を持つ結合方法によって、処理中に実施されるプログラムの分類などのタスクにおいて、高い精度を実現することが可能となる。

Claims (15)

1. 生成すべき第１のプログラムに対する入力データ、目標データ及び設計要件の入力を受け付ける入力部と、
   複数の既存の第２のプログラムを記憶するプログラム記憶部と、
   前記第１のプログラムを生成するプログラム生成装置と、
   前記プログラム生成装置が生成した前記第１のプログラムを出力する出力部、を備え、
   前記プログラム生成装置は、
   前記プログラム記憶部に記憶された前記複数の第２のプログラムを分析してプログラムモデルを生成するプログラム分析部と、
   前記プログラム分析部が生成した前記プログラムモデルと前記入力部から入力された前記設計要件に基づいて、進化計算のための基本ノードと制約条件を生成する基本ノード／制約条件生成部と、
   前記基本ノード／制約条件生成部が生成した前記基本ノード及び前記制約条件と、前記入力部から入力された前記入力データ及び前記目標データに基づいて、前記進化計算により前記第１のプログラムを生成する最適化部と、
   を有することを特徴とするプログラム自動生成システム。
2. 前記プログラムモデルは、前記第２のプログラムの意味をコード化したベクトルデータであり、
   前記プログラム分析部は、前記ベクトルデータを導出するために、前記複数の第２のプログラムから構文構造情報を抽出し、前記構文構造情報からノードの項目を列挙してノードベクトル情報を学習することを特徴とする請求項１に記載のプログラム自動生成システム。
3. 前記プログラムモデルは、テンプレートデータであり、
   前記プログラム分析部は、前記テンプレートデータを導出するために、前記複数の第２のプログラムから構文構造情報を抽出し、前記構文構造情報から部分構造を抽出して前記複数の第２のプログラム間の類似構造を抽出することを特徴とする請求項１に記載のプログラム自動生成システム。
4. 前記プログラムモデルは、確率遷移グラフであり、
   前記プログラム分析部は、前記確率遷移グラフを導出するために、前記複数の第２のプログラムからプログラムリストを作成し、前記作成したプログラムリストに従って前記複数の第２のプログラムの構文構造情報を重ね合わせることを特徴とする請求項１に記載のプログラム自動生成システム。
5. 前記プログラムモデルは、前記第２のプログラムの意味をコード化したベクトルデータであり、
   前記プログラム分析部は、前記ベクトルデータを導出するために、前記複数の第２のプログラムから構文構造情報を抽出し、前記複数の第２のプログラムから依存関係情報を抽出し、前記構文構造情報からノードの項目を列挙してノードベクトル情報を学習し、前記依存関係情報から重み情報を生成し、前記ノードベクトル情報と前記重み情報に基づいて前記ノードベクトルを追学習することを特徴とする請求項１に記載のプログラム自動生成システム。
6. 前記入力部は、前記設計要件として、活用プログラムの種別、ライブラリの種別又は様式を入力することを特徴とする請求項１に記載のプログラム自動生成システム。
7. 前記入力部は、前記設計要件として、修正前の前記第１のプログラムを入力することを特徴とする請求項１に記載のプログラム自動生成システム。
8. 前記基本ノード／制約条件生成部は、前記制約条件として、個体数、世代数、交差確率、突然変異確率、ノードの分類情報による選択重み、ノードの選択確率又はノードの変異確率を生成することを特徴とする請求項１に記載のプログラム自動生成システム。
9. 前記プログラムモデルは、前記第２のプログラムの意味をコード化したベクトルデータであり、
   前記基本ノード／制約条件生成部は、前記ベクトルデータを用いて、前記複数の第２のプログラム中のノードを分類し、前記ノードの分類情報を基に前記制約条件を生成することを特徴とする請求項１に記載のプログラム自動生成システム。
10. 前記プログラムモデルは、テンプレートデータ又は確率遷移グラフであり、
    前記基本ノード／制約条件生成部は、前記テンプレートデータ又は前記確率遷移グラフを用いて、前記複数の第２のプログラム中のノード間の接続関係を分析し、前記ノードの接続関係を基に前記制約条件を生成することを特徴とする請求項１に記載のプログラム自動生成システム。
11. 前記基本ノード／制約条件生成部は、前記基本ノードとして、前記進化計算のために処理される木構造の各ノードを構成する基本となるノードを生成することを特徴とする請求項１に記載のプログラム自動生成システム。
12. 前記プログラムモデルは、前記第２のプログラムの意味をコード化したベクトルデータであり、
    前記基本ノード／制約条件生成部は、前記ベクトルデータを用いて、前記複数の第２のプログラム中のノードを分類し、前記ノードの分類情報を基に前記進化計算のための基本ノードを生成することを特徴とする請求項１に記載のプログラム自動生成システム。
13. 前記プログラムモデルは、テンプレートデータであり、
    前記基本ノード／制約条件生成部は、前記テンプレートデータを前記基本ノードとして用いることを特徴とする請求項１に記載のプログラム自動生成システム。
14. 前記進化計算は、遺伝的プログラミングであり、
    前記最適化部は、
    前記制約条件を基に初期集団を生成し、前記入力データ及び前記目標データを用いて、前記入力データに対する個体の出力データと前記目標データの距離を表す適応度を計算し、
    前記適合度と前記制約条件を基に前記初期集団から前記個体を選択し、前記初期集団から選択された前記個体に対して、前記制約条件を用いて交差又は突然変異処理を実行して修正した個体を前記初期集団に戻し、
    前記遺伝的プログラミングによる前記進化計算によって、世代を繰り返し更新して、前記適応度を収束させて前記第１のプログラムを生成することを特徴とする請求項１に記載のプログラム自動生成システム。
15. 生成すべき第１のプログラムに対する入力データ、目標データ及び設計要件の入力を受け付け、
    複数の既存の第２のプログラムを記憶し、
    前記複数の第２のプログラムを分析してプログラムモデルを生成し、
    前記生成した前記プログラムモデルと前記入力された前記設計要件に基づいて、進化計算のための基本ノードと制約条件を生成し、
    前記生成した基本ノード及び前記制約条件と、前記入力された前記入力データ及び前記目標データに基づいて、前記進化計算により前記第１のプログラムを生成し、
    前記生成した前記第１のプログラムを出力することを特徴とするプログラム自動生成方法。

Images