Schema theory for genetic programming with one-point crossover and point mutation

Area of Science:

• Computer Science
• Artificial Intelligence
• Evolutionary Computation

Background:

• The theory of schemata is crucial in genetic programming (GP) for understanding evolutionary processes.
• Existing schema definitions in GP have limitations regarding their strengths and weaknesses.
• The original schema concept in genetic algorithms (GAs) provides a foundational understanding.

Purpose of the Study:

• To propose a simplified and more intuitive definition of schemata for GP.
• To develop an improved schema theorem for GP that accurately models schema propagation.
• To establish a theoretical link between schema evolution in GP and GAs.

Main Methods:

• Reviewing existing results in GP schema theory.
• Introducing a new, simpler schema definition for GP.
• Implementing one-point crossover and point mutation operators.
• Deriving a new schema theorem for GP based on the revised schema definition.

Main Results:

• A novel, simpler schema definition for GP is presented, closely resembling the GA concept.
• An improved schema theorem for GP is derived, detailing schema propagation across generations.
• The new GP schema theorem is shown to be a natural counterpart to the GA schema theorem.
• Asymptotic convergence of the GP schema theorem to the GA schema theorem is demonstrated.

Conclusions:

• The proposed simpler schema definition facilitates a more effective analysis of GP.
• The improved schema theorem offers a clearer understanding of evolutionary dynamics in GP.
• This work bridges theoretical understanding between GP and GAs, advancing evolutionary computation.
• The findings pave the way for more efficient and predictable GP systems.