Markov Chain Analysis of Depth Growth in GP-ES Algorithm
摘要
This paper presents an analysis of the Genetic Programming with Evolution Strategy (GP+ES) algorithm using a Markov chain model focusing on tree depth dynamics during evolution. Several simplifying assumptions are made, most notably that all program trees are full binary trees and that ES always finds optimal constants, allowing representation of each individual solely by its depth. Based on the resulting model, methods for estimating the first hitting depth, expected depth changes, and growth tendencies are presented, including approaches via survival probability, geometric approximation, or absorbing state analysis. The results show that the model can be used to set initial tree depth optimally, thus improving solution efficiency while controlling bloat.