An investigation of local patterns for estimation of distribution genetic programming
Erik Hemberg, Kalyan K. Veeramachaneni, James A. McDermott, Constantin Berzan, Una-May O’Reilly · 2012
We present an improved estimation of distribution (EDA) genetic programming (GP) algorithm which does not rely upon a prototype tree. Instead of using a prototype tree, Operator-Free Genetic Programming learns the distribution of ancestor node chains, "n-grams", in a fit fraction of each generation's population. It then uses this information, via sampling, to create trees for the next generation. Ancestral n-grams are used because an analysis of a GP run conducted by learning depth first graphical models for each generation indicated their emergence as substructures of conditional dependence. We are able to show that our algorithm, without an operator and a prototype tree, achieves, on average, performance close to conventional tree based crossover GP on the problem we study. Our approach sets a direction for pattern-based EDA GP which off ers better tractability and improvements over GP with operators or EDAs using prototype trees.