Fitness Landscape Compression for Genetic Programming

Abstract

Searching for programs by genetic programming has been successfully applied to many areas. However, the vast and rugged fitness landscape of searching programs often limits the further improvement of genetic programming. It takes a significant amount of time for genetic programming to traverse the huge search space and escape from local optima. To improve the learning effectiveness and efficiency of genetic programming, this paper explicitly compresses fitness landscapes. Specifically, we prioritize the primitives of genetic programming by a fitness landscape optimization method and maintain a dynamic and limited set of useful primitives that form the compressed landscape. We implement the new method with linear genetic programming. We verify the new genetic programming method on two types of problems, including symbolic regression and dynamic combinatorial optimization problems. Our results show that the proposed method has a very competitive learning performance with state-of-the-art methods, with a very promising training efficiency for both supervised and learn-to-optimize tasks. We further analyze and visualize example compressed landscapes, verifying the effectiveness of the proposed landscape compression method.