Improving Genetic Programming with Novel Exploration - Exploitation Control.

Low population diversity is recognized as a factor in premature convergence of evolutionary algorithms. We investigate program synthesis performance via grammatical evolution. We focus on novelty search – substituting the conventional search objective – based on synthesis quality, with a novelty objective. This prompts us to introduce a new selection method named knobelty. It parametrically balances exploration and exploitation by creating a mixed population of parents. One subset is chosen based on performance quality and the other subset is chosen based on diversity. Three versions of this method, two that adaptively tune balance during evolution solve program synthesis problems more accurately, faster and with less duplication than grammatical evolution with lexicase selection.