遺伝的アルゴリズムの代わりにランダムサーチを用いた APR ツール RSRepair の論文．

近年 APR が流行っており，そのきっかけとなったのが GenProg と PAR である． どちらのツールもそれなりの個数の実際のバグを，実用的な時間で修復できている． しかし，そのアルゴリズムが本当に有効に働いているかの確認はされておらず， 特に GenProg は遺伝的アルゴリズムを用いているが，ミューテーション（プログラム改変）がうまく行っているだけで，実はセレクションやフィットネスは必要ではないのではないかという懸念がある． それを明らかにするために，GenProg の遺伝的アルゴリズムをランダムサーチに変更した RSRepair を実装，実験し，APR における遺伝的アルゴリズムの妥当性を確かめた．

ランダムサーチとは，その名の通り探索空間から適当な値を持ってきて確認し，あっていれば終了，合っていなければ繰り返す手法である． 乱暴に言うと遺伝的アルゴリズムの1世代目である． そのため，セレクションやフィットネスを計算する必要がない． また，GenProg では間違ったミューテーションをある世代で採用してしまうと，それ以降で解を見つけることが不可能になってしまうかもしれないという問題点があるが，それを考える必要もなくなる（と思う）．

筆者らは GenProg を改造して RSRepair を実装した． 実験結果から，GenProg に比べて短い試行回数，時間で解を発見できることを確認している．

所感としては，単純なバグだったらランダムサーチの方が確かに楽に直りそうだなと感じた． 修正に複数の文が必要な場合には弱そう． あと，実行時間の評価を行っているが，RSRepair はテストケースの絞り込むを行っている一方， GenProg は回帰テストを行っているため，そこを合わせないとランダムサーチの時間における有効性の証明にならないと思う． GenProg の方が夢（将来性）がある気がする．