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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Markov Chain Analysis of Depth Growth in GP-ES Algorithm

  • Petr Michalíček,
  • Tomáš Brandejský

摘要

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.