Coevolving deep hierarchies of programs to solve complex tasks

Abstract

Scaling genetic programming to organize large complex combinations of programs remains an under investigated topic in general. This work revisits the issue by first demonstrating the respective contributions of coevolution and diversity maintenance. Competitive coevolution is employed to organize a task in such a way that the most informative training cases are retained. Cooperative coevolution helps discover modularity in the solutions discovered and, in this work, is fundamental to constructing complex structures of programs that still execute efficiently (the policy tree). The role of coevolution and diversity maintenance is first independently established under the task of discovering reinforcement learning policies for solving Rubik's Cubes scrambled with 5-twists. With this established, a combined approach is then adopted for building large organizations of code for representing policies that solve 5 to 8-twist combinations of the Cube. The resulting 'deep' policy tree organizes hundreds of programs to provide optimal solutions to tens of millions of test cube configurations.