Adaptation of a Success Story in GAs: Estimation-of-Distribution Algorithms for Tree-based Optimization Problems

Fundamental research into Genetic Algorithms (GA) has led to one of the biggest successes in the design of stochastic optimization algorithms: Estimation-of-Distribution Algorithms (EDAs). These principled algorithms identify and exploit structural features of a problem's structure during optimization. EDA design has so far been limited to classical solution representations such as binary strings or vectors of real values. In this chapter we adapt the EDA approach for use in optimizing problems with tree representations and thereby attempt to expand the boundaries of successfull evolutionary algorithms. To do so, we propose a probability distribution for the space of trees, based on a grammar. To introduce dependencies into the distribution, grammar transformations are performed that facilitate the description of specific subfunctions. The results of performing experiments on two benchmark problems demonstrate the feasibility of the approach.