社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

自動プログラム生成におけるプログラム依存を考慮した交叉法の提案と評価
渡辺

大登†

柗本

真佑†

肥後 芳樹†

楠本 真二†

倉林 利行††

切貫

弘之††

治門††

丹野

† 大阪大学大学院情報科学研究科†† 日本電信電話株式会社
E-mail: †{h-watanb,shinsuke,kusumoto}@ist.osaka-u.ac.jp
あらまし 自動でプログラムを生成する技術の実現手法として，遺伝的アルゴリズム（GA）を用いた生成と検証に基づく手法が提案されている．この手法では，テストケースを入力として受け取り，プログラムの改変と評価を繰り返して全テストケースに通過するプログラムの生成を試みる．GA におけるプログラム改変の方法は変異と交叉に大別される．このうち，交叉は過去の改変履歴の一部を再利用する操作であり，一点交叉や一様交叉などの生物を模した方法がある．しかし，これら既存の交叉はプログラム内の依存関係を破壊し，構文的意味的に誤ったプログラムを生成する問題がある．そこで本研究ではプログラムの依存関係を予め解析し，依存関係を破壊しない新たな交叉手法を提案する．評価実験として，プログラミングコンテストの問題を題材に提案手法の効果を確かめた．その結果，コンパ
イル成功個体数は従来手法が優れていたものの，提案手法は従来手法では生成できないプログラムの生成に成功した．
キーワード 自動プログラム生成，自動プログラム修正，交叉，プログラムスライス

1. は じ め に

新たな塩基を 1 つ生成し親個体へ追加する操作である．この改変法には，プログラム文の挿入や削除，置換がある．交叉は過プログラムを開発者の介在なく完全自動で生成することを去に生成された 2 個体を両親として，両親の持つ塩基を組み替目指した研究の 1 つに，自動プログラム修正 [1]（Automatedえることで複数の個体を生成する．具体的な交叉法としては，Program Repair，APR）と呼ばれる技術を転用した方法が存在す

塩基列内のある場所を乱択によって決定し，その場所より後方る [2]．APR とは，バグを含むプログラムから自動的にバグをの全塩基を入れ替える一点交叉や，塩基列の対応する場所ごと取り除く技術である．この APR の分野にブレイクスルーをもに乱択によって塩基を入れ替える一様交叉がある．

たらしたツールとして GenProg [3] がある．GenProg は入力とGenProg にはバグ修正に多くの時間を要するという課題があして，バグを含むプログラムとテストケースを受け取り，遺伝る [5]．この理由は，GenProg のアルゴリズムにおいて乱択を的アルゴリズム [4]（Genetic Algorithm，GA）に基づき，入力用いる箇所が多いことにある．この課題に着目したツールとしされたバグを含むプログラムに対して改変（個体の生成）と優ては，予め用意した修正パターンを適用する PAR [6] や Reliﬁx

秀な個体の選別（個体の選択）を繰り返し探索的にソースコー[7]，多目的遺伝的アルゴリズムを利用する ARJA [8] や ARJAe

ドを全テストケースを通過する，バグのない状態に近づけてい[9] などが存在するが，いずれも個体選択や変異に着目したツー

く．APR を転用した自動プログラム生成（Automated Program

ルであり，交叉の改善には取り組んでいない．

Generation，APG）は，GA に基づく APR に対してバグを含む

本研究では APR を転用した APG における探索速度の向上をプログラムの代わりに最低限のコンパイルのみ可能な空プログ目的とした交叉の改善について考える．GenProg が用いる一点ラムを入力することで実現される．空プログラムは複数のテス

交叉や一様交叉の課題として，プログラムの制約条件を破壊しトが失敗する状態であり，これを複数のバグを含む状態とみなてしまうことが挙げられれる．プログラムは構文的制約や意味すことで，APR はテストケースを 1 つずつ通過するようにプロ的制約に代表される様々な制約条件を持つ．例えば，i = a +グラムを進化させていく．

1; という文をプログラムに挿入するためには，挿入箇所より前

GA によるプログラム改変（個体生成）の方法は変異と交叉で a を定義する必要がある．しかし，既存の交叉ではこれらのに大別される．変異によって巨大な探索空間からテスト通過に制約条件を加味せず乱択によって新しい個体を生成するため，寄与する改変法（塩基）を選び出し，選び出された塩基間の組

この条件を充足しない個体が生成されうる．

合せを交叉によって探索する．変異は 1 つの個体を親として，

本稿では，プログラムが持つ制約条件を活用したプログラム—1—

親A： B1

B2

B3

B4

親B： b1b2

b3

b4

ランダム交叉

B2

b1

B3

b3

B4

b2

B1

b4

空プログラム

テストケース(a) ランダム交叉

親A： B1

B2

B3

B4

親B： b1

b2

b3

b4

一点交叉

B1

b2

b3

b4

b1

B2

B3

B4

親B： b1

B2

b2

B3

b3

B4

一様交叉

b4

個体を
生成

個体を
選択

図 2: 遺伝的アルゴリズムを用いた自動プログラム生成の流れ

一点交叉(b) 一点交叉

親A： B1

全テストを通過する
プログラム

b1

B2

B3

b4

両親の遺伝子上の場所を乱択によって 1 つ選び，その場所より後ろを入れ替える手法（図 1b）

B1

b2

b3

B4

(c) 一様交叉

図 1: 交叉の例

一様交叉
各遺伝子ごとに，独立に 1/2 の確率で入れ替えるかを決定する手法（図 1c）
次に，APG に対する GA の適用について説明する．GA はメタヒューリスティクスであり，その適用においては個体の遺伝生成に特化した交叉を提案する．プログラムの制約を考慮した子設計と選択に用いる個体評価の方法を定義する必要がある．

交叉によって，APR の巨大な探索空間から解が含まれない空間

GenProg では，前者をプログラムへの編集，後者を入力されたのみを削減し探索の高速化を目指す．評価実験ではプログラム

テストケースの通過数としている．図 2 に GenProg を用いたコンテストの問題を題材として，提案する交叉と既存の交叉がAPG の流れをに示す．入力は最低限のコンパイルのみ可能な

生成した解候補のコンパイル成功率と両親に対して上位の解で空プログラムとテストケースの集合であり，出力は入力されたあるかを比較した．その結果，コンパイル成功個体数は従来手

全テストケースに通過するプログラムである．変異や交叉に法である一点交叉が優れていたものの，提案手法は従来手法でよってプログラムに僅かな改変を加えることで新たな個体を生は生成できない両親の上位となる個体の生成に成功した．

成し，個体のテスト通過数によって優秀な個体を選択する．図

2. 準

備

では，4 つのテストケースが入力され，3 つの個体が生成された状態を示している．生成された 3 個体の通過テスト数は上か

2. 1 遺伝的アルゴリズムを用いた自動プログラム生成

ら 0，1，2 である．この通過テスト数に基づき，選択と淘汰さ

遺伝的アルゴリズム（GA）とは，生物の進化過程を模したメれる個体が決定される．図では，最上部に位置する通過テスト

タヒューリスティクスアルゴリズムである．ループ（世代）を

数 0 の個体が淘汰され，それ以外の 2 個体が選択された．GA

重ねるごとに個体を求める解へと少しずつ近づけていく．各世

ではこのような処理のループによって，最終的に全テストを通代においては，一定数の解候補（個体）に対して変形を加え，過するプログラムを生成する．

変形された個体がどの程度解へ近づいたかを評価し，次世代へ

2. 2 既存手法の課題

用いる個体を選択する．GA の主要部分となる変形は個体の持本節では，プログラミングコンテスト AtCoder1 で過去に開催

つ遺伝子に対して行われ，その方法には変異と交叉の 2 種類がされた AtCoder Beginner Contest（ABC）102 の A 問題 2 を題材存在する．

として既存手法の課題を説明する．図 3 に APG の入力と生成

変

異個体の具体的な例を示す．図では 3 つのテストケースと最低限

生物の進化における突然変異を模した方法である．現存するのコンパイルのみ可能なプログラムを APG に入力している．

個体から親となる 1 個体を選び出し，その個体に対して僅かなGA で生成される個体は図中の V1 から V4 の 4 つの個体が示変形を加え新たな個体を生成する．

すように，塩基の列からなる遺伝子を持つ．塩基や遺伝子の設

交叉

計は様々なものが考えられるが，ここでは塩基はプログラムへ

生物の進化における交配を模した方法である．現存する個体の操作とその位置から構成される．図中の個体 V1 は B1 のみ

から両親となる 2 個体を選び出し，両親に過去に加えられた変からなる遺伝子を持ち，その塩基 B1 は 2 行目を return n に形（塩基）を組み合わせて新たな個体を生成する．

置換するプログラムへの編集を意味している．個体 V1 はこの交叉の具体的な手法として以下の 3 手法を挙げる．

遺伝子の適用の結果，2 つ目のテストを通過するように進化しランダム交叉

ている．

両親の全ての遺伝子をランダムに並び替え，半分を取り出す

ここで，GA の処理中に個体 V1 と V2 が生成されたとする．

手法（図 1a）（注 1）：https://atcoder.jp（注 2）：https://atcoder.jp/contests/abc102/tasks/abc102_a—2—

ABC102A 問題文

位置：2行目
操作：return nで置換3つのテストケース

塩基 B2

APG

位置：2行目
操作：int k=n*2を挿入

f(int n) {return 0
}

B1

B2

B3

B4

位置：3行目
操作：return kを挿入

個体 V2

f(int n) {

B1

B2

B3

B4

}

来の交叉はプログラムの構文や意味を利用せず，乱択によってのみ個体を生成している．このような交叉は効率的とはいえなを利用して，コンパイル成功やテスト通過観点から両親の上位を生成することを目的とした新たな交叉を考える必要がある．

2. 3 プログラムスライス
プログラムスライス [11] とは，プログラム内の各文の依存関

f(int n) {int k=n*2
if(n%2!=0) return kreturn 0}

return nの塩基が入れ替えられ生成された．V3 はコンパイル失敗，V4

い．プログラムの構文や意味，テストの実行時に得られる情報

塩基 B4

交叉対象となる2つの生成個体（両親）の下方に一点交叉による子の例として V3 と V4 を示す．V3 とはコンパイルには成功するものの全テストに失敗している．従塩基 B3

初期プログラム

両親とする交叉による新たな個体（子）の生成を考える．図 3

V4 は一点交叉によって両親となった V1，V2 が持つ 2 つ目以降

位置：2行目
操作：if(n%2!=0)を挿入

assert(f(3)).is(6)assert(f(10)).is(10)assert(f(9999)).is(19998)

個体 V1することで APG の効率が向上する [10]．よって，V1 と V2 を

塩基 B1

正整数 n に対して，2 と n の両方で割り切れる最小の正整数を求めよ．

係を明らかにする技術である．スライスには大きくスタティッ
クスライス [12] とダイナミックスライス [13] が存在するが，本稿では前者に着目する．スタティックスライスはプログラム内のある文の実行に影響を与える可能性のある全ての文を抽出する技術である．スライス起点を通過テストの通過する return

一点交叉により生成された個体（子）文としてスライス技術を使えば，通過テストの実行に必要な文
個体 V3

B1

B2

f(int n) {int k=n*2
return k
return n
}

B3

B4

個体 V4

B1

B2

B3

B4

のみを抽出できる．

f(int n) {if(n%2!=0) {}return 0}

3. 提 案 手 法
本研究では，プログラムスライスを用いた遺伝子の依存を保持する交叉を提案する．プログラムスライスの利用によって，

図 3: 生成個体の具体例と既存交叉の課題

依存の保持だけでなく，コンパイルやテスト通過に不要な塩基の除外という副次的な効果も期待できる．提案手法は既存の交叉手法と同様に，両親となる 2 個体を入力として受け取り，それらから生成された複数の子を出力する．ただし，両親が相補的な個体であることを前提としている．両親が相補的な個体でV2ない場合，子は生成されない．提案手法のアルゴリズムをアル
ゴリズム 1 に示す．提案手法は以下の 4 つのステップから構成
される．

•

Step-1：片方の親のみが通過するテストの抽出•

Step-2：プログラムスライス起点の決定•

Step-3：スライスによる依存塩基の抽出•

Step-4：抽出された塩基の結合

Step-1：片方の親のみが通過するテストの抽出
両親の通過テストを比較し，片方の親のみが通過するテストを抽出する．生成する子はこのステップで抽出されたテストに

V1
V4

図 4: テスト数 3 のときの全個体の関係

通過することが期待される．

Step-2：プログラムスライス起点の決定
親となる各個体について，Step-1 で抽出された各テストごとにプログラムスライスの起点となる文を決定する．スライス起個体 V1 は前述のとおり，塩基 B1 を持ち 2 つ目のテストに通過している．また，V2 は V1 の失敗する 1 つ目と 3 つ目のテストに通過している．V1 と V2 はテスト通過の観点から互いの失敗
テストを補い合う相補的な個体と理解できる．テスト数 3 のときの全個体の関係を図 4 に示す．図より V1 と V2 は上下関係にないことが分かる．このような相補的な個体を優先的に交叉点は通過テストの実行に影響のある最小限の文の集合が得られる箇所が望ましい．よって，通過テストの実行経路に含まれる，

return 文もしくは throw 文をプログラムスライスの起点とす
る．return 文が存在しない場合は，通過テストの実行経路に含まれる最後に実行された文をスライス起点とする．このようにして，Step-1 で抽出したテストと 1 対 1 に対応するプログラ
ムスライスの起点を決定する．

—3—

Step-3：利用する塩基の抽出催された AtCoder Beginner Contest（ABC）のうち ABC101 から

Step-2 で得られた各スライス起点からプログラムスライスをABC180 までの 100 点問題 80 問を用いた．この 80 問に対し得る．プログラムスライスによって得られた文に対応する塩基て，kGenProg を実行し GA 中に生成された個体のうち，相補的を交叉に利用する塩基として抽出する．また，抽出した塩基はな関係にある個体対を全て収集した．kGenProg の実行に必要

抽出前の順に並び替える．例えば，塩基の列 (𝑎, 𝑏, 𝑐, 𝑑, 𝑒) からな入力を表 1 に示す．実験題材の生成のために，kGenProg に(𝑎, 𝑏, 𝑑) を抽出する場合，その順番は (𝑎, 𝑏, 𝑑) の 1 通りとなる．

必要なその他のパラメータは既定値 4 を用いた．

Step-4：抽出された塩基の結合

上記 160 試行から 1,486 対の相補的な個体対が得られた．こ

各親個体から抽出された塩基を 1 つに結合し遺伝子を作成すの 1,486 個体対を両親として，従来の交叉 3 種と提案手法を用る．結合時に重複する塩基は取り除く．重複排除の目的は，変いて子の生成を行う．

数定義などの重複によるコンパイルの失敗を防ぐことにある．

4. 2 評 価 指 標

結合した塩基から出力となる子を生成できる．

本実験では大きく 2 種類の評価指標を用いる．交叉によって生成された子自体の評価と親子の比較による評価である．前者

アルゴリズム 1 Linkage Crossoverには，コンパイル可能な子の個数と生成プログラムの行数を用

Input:いる．コンパイル可能な子を多く生成できるほど，よい交叉手

Parent genes 𝐺 𝐴 and 𝐺 𝐵

法といえる．生成プログラムの行数を比較する目的は，提案手

Passed tests 𝑃𝑎𝑠𝑠𝑒𝑑 𝐴 and 𝑃𝑎𝑠𝑠𝑒𝑑𝐵法による不要な塩基の除外効果を確認することにある．

Output:次に，後者について説明する． まず，テスト通過の比較によChild Genes 𝐺
1: function Make-Gene(𝐺 𝐴 , 𝐺 𝐵 , 𝑃𝑎𝑠𝑠𝑒𝑑 𝐴 , 𝑃𝑎𝑠𝑠𝑒𝑑 𝐵 )2:

𝑃𝑎𝑠𝑠𝑒𝑑𝑂𝑛𝑙𝑦𝐴 ← 𝑃𝑎𝑠𝑠𝑒𝑑 𝐴 \ 𝑃𝑎𝑠𝑠𝑒𝑑𝐵

3:

𝑃𝑎𝑠𝑠𝑒𝑑𝑂𝑛𝑙𝑦𝐵 ← 𝑃𝑎𝑠𝑠𝑒𝑑𝐵 \ 𝑃𝑎𝑠𝑠𝑒𝑑 𝐴

4:

𝑆𝑒𝑙𝑒𝑐𝑡𝑒𝑑 𝐴 ← Select-Genes(𝐺 𝐴 , 𝑃𝑎𝑠𝑠𝑒𝑑𝑂𝑛𝑙𝑦𝐴)

5:

𝑆𝑒𝑙𝑒𝑐𝑡𝑒𝑑𝐵 ← Select-Genes(𝐺 𝐵 , 𝑃𝑎𝑠𝑠𝑒𝑑𝑂𝑛𝑙𝑦𝐵)6:

𝐺 ← marge-Genes(𝑆𝑒𝑙𝑒𝑐𝑡𝑒𝑑 𝐴, 𝑆𝑒𝑙𝑒𝑐𝑡𝑒𝑑𝐵)7:

return 𝐺

る 2 つの個体間での関係を定義する．

•

下位：相手の通過テストに 1 つ以上失敗し，相手の全失敗テストに失敗•

同値：通過テストと失敗テストが等しい•

上位：相手の全通過テストに通過し，相手の失敗テスト

を 1 つ以上通過•

相補：相手の通過テストに 1 つ以上通過し，相手の失敗

テストに 1 つ以上通過

8: function Select-Genes(𝐺, 𝑇)
9:

𝐶𝑜𝑣𝑒𝑟 𝑒𝑑𝑅𝑒𝑡𝑢𝑟 𝑛𝑆𝑡 𝑚𝑡 ← Coverage-Analysis(𝐺, 𝑇)

10:

𝐷𝑒 𝑝𝑒𝑛𝑑𝑒𝑛𝑡𝐺𝑒𝑛𝑒𝑠 ← 𝑆𝑙𝑖𝑐𝑒 (𝐺, 𝐶𝑜𝑣𝑒𝑟 𝑒𝑑𝑅𝑒𝑡𝑢𝑟 𝑛𝑆𝑡 𝑚𝑡 )11:

return 𝐷𝑒 𝑝𝑒𝑛𝑑𝑒𝑛𝑡𝐺𝑒𝑛𝑒𝑠

この関係から，交叉により生成された子個体と親個体の取りうる関係は表 2 に示した 4 H2 = 10 通りへ分類できる．ただし，
本実験では親個体を相補的な個体と限定しているため，表中の-で示した 4 種の関係となる子個体は生成されない．

4. 実

親子の比較による評価では，各交叉手法により生成された子

験を表 2 の 6 種の関係へ分類し，その個体数を比較する．以下

提案手法の評価のため，提案手法を GenProg の Java 実装であで，各関係の解釈を順に述べる．

る kGenProg [14] に実装し実験を行った．比較対象として，2. 1

上位&上位

節で説明したランダム交叉，一点交叉，一様交叉の 3 手法を用両方の親に対して優れている個体を表す．提案手法の生成目

いる．

標の個体である．

4. 1 実験題材の作成

上位&相補

提案手法や従来の交叉手法の動作のためには，入力となる 2

一方の親に対して上位であり，他方に対して相補的な個体を個体からなる両親が必要である．この実験題材となる両親の生表す．個体の多様性向上の観点から重要な個体であるが，提案成のために，プログラミングコンテスト AtCoder3 で過去に開手法の生成目標ではない．
相補&相補

表 1: kGenProg への入力
項目

値

両方の親に対して相補的な個体を表す．上位&相補と同じく，重要な個体ではあるが，生成目標ではない．
相補&同値

入力問題

ABC101∼ABC180 100 点問題

問題数

80

乱数シード

0∼1 （＝ 2 試行）表す．上位&相補や相補&相補と同じく重要な個体ではあるが，制限時間

1 試行あたり 1 時間生成目標ではない．

最大世代数

無制限

プログラムへの操作 挿入のみ
終了条件
（注 3）：https://atcoder.jp

正解個体の発見・時間切れ

一方の親に対して相補的であり，他方に対して同値な個体を相補&下位
一方の親に対して同値，他方に対して下位の個体を表す．交（注 4）：https://github.com/kusumotolab/kGenProg/tree/v1.8.0#options—4—叉による上位個体の生成に失敗したことを表す．しかし，生成

int error1 (int n){

された場合でも GA に悪影響を与えないと考えられる．片方のreturn n++;親に対して下位であるため，GA 中の選択処理によって淘汰さ

int k = 0; // compile error}

れ次世代で利用されないからである．
下位&下位

図 5: コンパイル失敗例：return 文の後に文が存在

両方の親に対して下位の個体を表す．相補&下位と同じく，交叉失敗と理解できる．

int error2 (int n){

4. 3 実 験 結 果

int k = 0;

4. 1 節で得られた 1,486 個体対を両親として，4 種の交叉法そ

if(n % 2 != 0){
int k = 3; // compile error

れぞれを用いて 1 組の両親に対し 10 個体の子を試みた．つま}り，1 つの交叉法あたりの生成個体数は 14,860 個体となる．
各交叉法と生成した子の内訳を表 3 に示す．表は個体数とreturn k;}

コンパイル可能数に占める割合を示している．コンパイル可能な個体は一点交叉を用いた場合に最も多く得られた．その一方

図 6: コンパイル失敗例：変数宣言の重複で，本研究の目的となる上位&上位や GA に良い影響を与える
上位&相補，相補&相補は提案手法での生成が最も多かった．
また，交叉失敗と理解できる相補&下位や下位&下位の個体も提案手法において最も多く生成された．

5. 2 提案手法のコンパイル失敗原因
提案手法のコンパイル失敗個体の原因について調査した．調査の結果，プログラムスライスから対応する塩基を抽出するの各交叉法ごとの個体の内訳を観察する．従来手法 3 種におい

みではコンパイル可能な個体の生成には不十分であると分かっては生成個体の傾向は似通っており，相補&同値が最も多くのた．これらを原因とするコンパイルエラーを防ぐためには，提割合を占めている．提案手法ではこの傾向は見られず，下位&

案手法における塩基の結合時により厳密な解析を行う必要があ

下位が最も多かった．

る．具体的なコンパイル失敗の原因とその例を以下で説明する．

コンパイル可能な個体におけるプログラム行数の平均を表 4に示す．平均行数が最も小さいのはランダム交叉であった．しかし，両親の上位互換となる上位&上位や上位&相補に着目す
ると提案手法の平均行数が最も短かった．

5. 考

return 文の後に文が存在Java では return 文の後に他の文が存在する場合，コンパイ
ルエラーとなる．この具体例を図 5 に示す．このような個体が生成された原因は提案手法の遺伝子結合の処理にある．このコンパイルエラーを回避するには，遺伝子結合時に return 文を察

ブロックの最下部に配置させるなどの工夫が必要である．

5. 1 提案手法の効果

変数宣言の重複提案手法は従来手法と比較して GA に良い影響を与えるといコンパイルエラーの原因として，変数宣言の重複が存在しえる．提案手法では僅かではあるが，従来手法では生成できなかった上位&上位となる個体を生成している．また，GA 中の個体の多様性を向上させる上位&相補や相補&相補となる個体も最も多く生成したことも理由である．交叉失敗と理解できる

た．この具体例を図 6 に示す．提案手法では，このコンパイル
エラーを回避するために，重複塩基の排除を行っていた. しかし，適用の位置のみが異なる塩基は排除していなかったため，
このコンパイルエラーが発生した．

相補&下位や下位&下位も提案手法での生成が最も多かったが，これらの個体は必ず淘汰されるため，GA に対して悪影響を与えることはない．
また，提案手法の副次的な作用である不要な塩基の排除も確認できた．表 4 より，提案手法により生成された個体のプログ
ラム行数が短いことから，この効果が分かる．

6. 妥当性の脅威
提案手法の実装には Java で実装された APR ツール kGenProgを用いた．Java 以外のプログラム言語，特にスクリプト言語を用いた場合，得られる実験結果が結果が異なる可能性がある．
また，GenProg など他のツールを用いた実験も妥当性確保に必要である．
実験では交叉対象となる両親を AtCoder の問題 80 問から生

表 2: 両親に対する子の関係成した．この問題以外から交叉の両親を作成した場合，同様の親 A に対して

親 B に対して
上位

相補

同値

下位

上位

上位&上位

上位&相補

-

-

相補

上位&相補

相補&相補

相補&同値

相補&下位

同値

-

相補&同値

-

-

下位

-

相補&下位

-

下位&下位

結果が得られるとは限らない．

7. お わ り に
本稿では，プログラムスライスを利用した両親の上位となる個体を生成する交叉を提案した．また，評価実験としてプログ
ラミングコンテスト AtCoder の問題 80 問から相補的な個体を—5—

表 3: コンパイル可能な個体数と両親との関係による分類
個体数

コンパイル可能

上位&上位

上位&相補

ランダム交叉

173

0(0.0%)

0

一点交叉

12,1680(0.0%)

6 (0.049%)

一様交叉

5,333

0

(0.0%) 23

提案手法

6,852

4 (0.058%) 54(0.0%)

相補&相補

相補&同値

7

118 (68%)(4.0%)

相補&下位

0(0.0%)

下位&下位

48

(28%)

96 (0.79%) 11,850 (97%)

108 (0.89%)

108 (0.89%)

725

(14%)

3,845 (72%)

366

374

(7.0%)(0.79%) 1,019(15%)

1,833 (27%) 1,322(19%) 2,620(38%)(0.43%)(6.9%)

表 4: コンパイル可能な個体におけるプログラム行数の平均
全体の平均

上位&上位

上位&相補

相補&相補

ランダム交叉

個体数

26.0

-

-

52.9

17.4

-

43.3

一点交叉

168

-

50.3

55.2

170

177

89.0

一様交叉

132

-

113.4

139

122

188

172

提案手法

36.5

21

28.4

38.3

19.1

37.9

47.6

生成し，提案手法の性質を確認した．コンパイル成功個体数は従来手法である一点交叉が優れていたものの，提案手法は従来
手法では生成できない両親の上位となる個体の生成に成功し[8]た．また，提案手法によって生成されるプログラムの行数を削
[9]

減できた．
今後の研究課題として，提案手法が APG の効率へどのような効果をもたらすのか確認することが挙げられる．生成できる[10]

プログラムの増減や生成時間を従来手法と比較することで，効果を確認する予定である．また，提案手法の副次的な作用である不要塩基の排除がテストケースへの過剰適合を招く可能性が考えられる．生成されたプログラムがテストケースへの過剰適

[11]
[12]

合 [15] を起こしていないか評価する必要がある．
手法の改善という観点では，5. 2 節で述べた提案手法でのコ[13]

ンパイル失敗原因への対応も重要な課題である．また，本稿で[14]はプログラムスライス技術のうち，スタティックスライスを用いたが，ダイナミックスライスの利用も検討している．
謝辞

本 研 究 は JSPS 科 研 費（JP20H04166，JP21K18302，

JP21K11820，JP21K11829，JP21H04877，JP22H03567，JP22K11985）の助成を得て行われた．
文[15]

相補&同値 相補&下位 下位&下位

regressions,” Proc. International Conference on Software Engineering,
pp.471–482, 2015.
Y. Yuan and W. Banzhaf, “ARJA: automated repair of java programs via
multi-objective genetic programming,” IEEE Transactions on Software
Engineering, vol.46, no.10, pp.1040–1067, 2020.
Y. Yuan and W. Banzhaf, “Toward better evolutionary program repair:
An integrated approach,” ACM Transactions on Software Engineeringand Methodology, vol.29, no.1, pp.1–53, 2020.
H. Watanabe, S. Matsumoto, Y. Higo, S. Kusumoto, T. Kurabayashi,
K. Hiroyuki, and H. Tanno, “Applying multi-objective genetic algorithm for eﬃcient selection on program generation,” Proc. Asia-Paciﬁc
Software Engineering Conference, pp.515–519, 2021.
M. Weiser, “Program slicing,” IEEE Transactions on Software Engineering, vol.SE-10, no.4, pp.352–357, 1984.
M. Weiser, “Programmers use slices when debugging,” Communications of the ACM, vol.25, no.7, pp.446–452, 1982.
B. Korel and J. Laski, “Dynamic slicing of computer programs,” Journal of Systems and Software, vol.13, no.3, pp.187–195, 1990.
柗本真佑，肥後芳樹，有馬諒，谷門照斗，内藤圭吾，松尾裕幸，
松本淳之介，富田裕也，華山魁生，楠本真二，“高処理効率性と高可搬性を備えた自動プログラム修正システムの開発と評価，”
情報処理学会論文誌，vol.61，no.4，pp.830–841，2020．
E.K. Smith, E.T. Barr, C.L. Goues, and Y. Brun, “Is the cure worse
than the disease? overﬁtting in automated program repair,” Proc. Joint
Meeting on Foundations of Software Engineering, pp.532–543, 2015.

献[1] L. Gazzola, D. Micucci, and L. Mariani, “Automatic software repair:
A survey,” IEEE Transactions on Software Engineering, vol.45, no.1,
pp.34–67, 2017.
[2] 富田裕也，松本淳之介，柗本真佑，肥後芳樹，楠本真二，倉林利行，切貫弘之，丹野治門，“遺伝的アルゴリズムを用いた自動プ
ログラム修正手法を応用したプログラミングコンテストの回答の自動生成に向けて，” 情報処理学会研究報告，第 2020-SE-204
巻，pp.1–8，March 2020．
[3] C.L. Goues, T. Nguyen, S. Forrest, and W. Weimer, “Genprog: A
generic method for automatic software repair,” IEEE Transactions on
Software Engineering, vol.38, no.1, pp.54–72, 2012.
[4] D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, 1st edition, Addison-Wesley Longman Publishing,
1989.
[5] F. Long and M. Rinard, “An analysis of the search spaces for generate
and validate patch generation systems,” Proc. International Conference
on Software Engineering, pp.702–713, 2016.
[6] D. Kim, J. Nam, J. Song, and S. Kim, “Automatic patch generation
learned from human-written patches,” Proc. International Conference
on Software Engineering, pp.802–811, 2013.
[7] S.H. Tan and A. Roychoudhury, “reliﬁx: Automated repair of software—6—