Multimodal Adaptive Graph Evolution for Program Synthesis

Program synthesis constitutes a category of problems where the objective is to automatically produce computer programs that meet specified criteria. Among Genetic Programming algorithms, Cartesian Genetic Programming has been successfully used for a variety of function synthesis problems, such as circuit design, pattern analysis, and game playing. These problems are designed to work only on a single data type, for example, boolean values or entire images. Cartesian Genetic Programming cannot directly be applied to problems with multiple data types, which poses a great limitation, as more realistic programs should be able to deal with different data types. Mixed-Type Cartesian Genetic Programming is the only current extension of Cartesian Genetic Programming which allows for processing different data types. In this work, we present and study Multimodal Adaptive Graph Evolution, a multi-chromosome generalization of Cartesian Genetic Programming that groups functions by return type and constrains graph mutation based on node’s type coherence. We compare Multimodal Adaptive Graph Evolution to Mixed-Type Cartesian Genetic Programming on the Program Synthesis Benchmark Suite, showing that the representation and mutation constraints of Multimodal Adaptive Graph Evolution aid in the search of multimodal functions. Using Search Trajectory Networks, we find that Multimodal Adaptive Graph Evolution converges faster to a local or global minimum compared to Mixed-Type Cartesian Genetic Programming and explores the solution space more effectively by creating candidate solutions with lower semantic redundancy.