- author = "Ning Tao and Anthony Ventresque and Takfarinas Saber",
- title = "Multi-objective Grammar-guided Genetic Programming with Code Similarity Measurement for Program Synthesis",
- booktitle = "2022 IEEE Congress on Evolutionary Computation (CEC)",
- year = "2022",
- editor = "Carlos A. Coello Coello and Sanaz Mostaghim",
- address = "Padua, Italy",
- month = "18-23 " # jul,
- keywords = "genetic algorithms, genetic programming, Grammar-Guided Genetic Programming, G3P, Codes, Error analysis, Measurement uncertainty, Evolutionary computation, Benchmark testing, Software, Program Synthesis, Grammar-Guided Genetic Programming, Levenshtein Distance, Cosine, FuzzyWuzzy, TokenSortRatio, CCFinder, suffix-tree matching, SIM, Code Similarity, Multi-Objective Optimization, MOGP",
- isbn13 = "978-1-6654-6708-7",
-
DOI = "
doi:10.1109/CEC55065.2022.9870312",
- abstract = "Grammar-Guided Genetic Programming (G3P) is widely recognised as one of the most successful approaches for program synthesis, i.e., the task of automatically discovering an executable piece of code given user intent. G3P has been shown capable of successfully evolving programs in arbitrary languages that solve several program synthesis problems based only on a set of input/output examples. Despite its success, the restriction on the evolutionary system to only leverage input/output error rate during its assessment of the programs it derives limits its scalability to larger and more complex program synthesis problems. With the growing number and size of open software repositories and generative artificial intelligence approaches, there is a sizable and growing number of approaches for retrieving/generating source code (potentially several partial snippets) based on textual problem descriptions. Therefore, it is now, more than ever, time to introduce G3P to other means of user intent (particularly textual problem descriptions). In this paper, we would like to assess the potential for G3P to evolve programs based on their similarity to particular target codes of interest (obtained using some code retrieval/generative approach). Through our experimental evaluation on a well known program synthesis benchmark, we have shown that G3P successfully manages to evolve some of the desired programs with all four considered similarity measures. However, in its default configuration, G3P is not as successful with similarity measures as it is with the classical input/output error rate when solving program synthesis problems. Therefore, we propose a novel multi-objective G3P approach that combines the similarity to the target program and the traditional input/output error rate. Our experiments show that compared to the error-based G3P, the multiobjective G3P approach could improve the success rate of specific problems and has great potential to improve on the traditional G3P system.",
-
notes = "Also known as \cite{9870312}
'no similarity measure that improves G3P success rate on all problems' 'Several small grammars are defined [one] each for a data type' 'two objectives (i.e., input/output error rate and the degree of similarity against a target code).' Number IO, Smallest, Median, String Lengths Backwards, Negative To Zero.
'similarity-based G3P system is not able to achieve a similar result as the error-based G3P system.'",
