Advancing Genetic Programming via Information Theory

Genetic Programming (GP) is a powerful tool often used to solve optimization problems where analytical methods are unusable. While the general technique is well understood, there exist deficiencies in the multitude of implementations currently widely available. The primary areas of improvement are computation time, search space reduction, and accuracy. Despite significant advances in GP systems, a key deficiency remains in the structural randomization of symbolic GP trees. Our initial assumptions regarding the formation of expression trees in symbolic GP trees is at best highly limited and normally simply non-existent. In this paper, we introduce a new GP methodology that incorporates both current cutting- edge GP system solutions as well as an information-theoretic approach to expression tree initialization. Through a more informed initial tree construction, this approach reduces the search space and model complexity. We introduce in this work the methodology as well as the accompanying theoretical component and comparison benchmarks from tests. A key advantage of the algorithm proposed is its high parallelization potential which is highlighted in further discussion. The method consists of two parts. The first is a variable-interaction system termed Entropy Shaving that is used for both variable selection and initial expression structure generation. The second is a GP system that utilizes the variable-interaction system as input to determine a final solution.