Cross-Representation Genetic Programming: A Case Study on Tree-Based and Linear Representations

Area of Science:

• Artificial Intelligence
• Computer Science
• Evolutionary Computation

Background:

• Genetic programming (GP) methods often rely on specific representations (e.g., tree-based, linear), each with domain-dependent advantages and disadvantages.
• The relationship between GP representations and fitness landscapes is complex, making it difficult to select the optimal representation for a given problem.
• Simultaneously evolving programs with multiple representations allows exploration of diverse search spaces and potential synergistic benefits.

Purpose of the Study:

• To address the gap in research on the simultaneous evolution of multiple GP representations.
• To propose a novel cross-representation GP algorithm leveraging both tree-based and linear representations.
• To investigate the effectiveness of inter-representation knowledge transfer in improving GP performance.

Main Methods:

• Development of a cross-representation genetic programming (GP) algorithm.
• Integration of both tree-based and linear representations within the GP framework.
• Introduction of a novel cross-representation crossover operator designed to exploit the interplay between different representations.

Main Results:

• Empirical evidence demonstrates that the proposed cross-representation GP approach enhances performance compared to single-representation GP.
• Navigating learned knowledge between tree-based and linear representations improves effectiveness in symbolic regression tasks.
• The algorithm shows improved effectiveness for dynamic job shop scheduling problems.

Conclusions:

• Simultaneous evolution of multiple GP representations, specifically tree-based and linear, can lead to superior search capabilities.
• The developed cross-representation crossover operator effectively harnesses the synergies between different representations.
• This approach offers a promising direction for advancing GP effectiveness across various problem domains.