Genetic Algorithm for Evolving an Objective Function of a Program Synthesizer

Bachelor thesis (2022)

Authors

N. EFTHYMIOU Electrical Engineering, Mathematics and Computer Science

Contributors

S. Dumančić Algorithmics - EEMCS (mentor)
G. Smaragdakis Cyber Security - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2022 NIKOLAOS EFTHYMIOU
More Info
expand_more

Published Date

23-06-2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

Program Synthesis is a challenging problem in Artificial Intelligence. An important element of a program synthesizer is the objective function that guides the combinatorial search for a program that satisfies a given user intent. Given multiple I/O example transformations that correspond to the intended behavior of the program, this function evaluates the performance of a generated program based on the distance of its output to the correct output. In this study, we consider the possibility of using a Genetic algorithm for the evolution of such a function as a means to partially automate the design process. In particular, we propose the GeneticObjective algorithm that evolves domain-specific objective functions by combining user-defined local distance functions in an algebraic expression. Using the Brute synthesizer, we conducted experiments in the Robot Planning and the String transformation domains, the results of which showed that such an approach evolves informative functions. The best evolved function reached the effectiveness of a manually-designed function in the Robot domain, while it outperformed the effectiveness of a hand-crafted function in the String domain.