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

DOI 情報処理学会

書誌事項

タイトル別名
  • Program Slice-based Crossoverfor Automated Program Genration

この論文をさがす

抄録

自動でプログラムを生成する技術の実現手法として，遺伝的アルゴリズム（GA）を用いた生成と検証に基づく手法が提案されている．この手法では，テストケースを入力として受け取り，プログラムの改変と評価を繰り返して全テストケースに通過するプログラムの生成を試みる．GAにおけるプログラム改変の方法は変異と交叉に大別される．このうち，交叉は過去の改変履歴の一部を再利用する操作であり，一点交叉や一様交叉などの生物を模した方法がある．しかし，これら既存の交叉はプログラム内の依存関係を破壊し，構文的意味的に誤ったプログラムを生成するという問題がある．そこで本研究ではプログラムの依存関係をあらかじめ解析し，依存関係を破壊しない新たな交叉手法を提案する．評価実験として，プログラミングコンテストの問題80問を対象とした適用実験を行った結果，既存の交叉と比べた生成効率の向上を確認した．

As a method for realizing the technology of automatic program generation, there is an approach based on the generation and verification using genetic algorithm (GA). In this method, it receives test cases as inputs and attempts to generate a program that passes all test cases by repeating modification and evaluation of the program. In GA, there are two types of program modifications: mutation and crossover. Crossover reuses part of the past modification history, and there are methods modeled after organisms such as single-point crossover and uniform crossover. However, these existing crossovers have the problem of generating syntactically and semantically incorrect programs by breaking the dependencies within the program. Therefore, in this research, we propose a new crossover method that pre-analyzes the dependencies of the program and does not break the dependencies. As an evaluation experiment, we conducted an application experiment targeting 80 programming contest problems and confirmed an improvement in generation efficiency compared to existing crossovers.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ