Improving Grammatical Evolution in Santa Fe Trail using Novelty Search

摘要

Grammatical Evolution is an evolutionary algorithm that can evolve complete programs using a Backus Naur form gram-mar as a plug-in component to describe the output language. An important issue of Grammatical Evolution, and evolution-ary computation in general, is the difficulty in dealing with deceptive problems and avoid premature convergence to lo-cal optima. Novelty search is a recent technique, which does not use the standard fitness function of evolutionary algo-rithms but follows the gradient of behavioral diversity. It has been successfully used for solving deceptive problems mainly in neuro-evolutionary robotics where it was origi-nated. This work presents the first application of Novelty Search in Grammatical Evolution (as the search component of the later) and benchmarks this novel approach in a well-known deceptive problem, the Santa Fe Trail. For the ex-periments, two grammars are used: one that defines a search space semantically equivalent to the original Santa Fe Trail problem as defined by Koza and a second one which were widely used in the Grammatical Evolution literature, but which defines a biased search space. The application of nov-elty search requires to characterize behavior, using behavior descriptors and compare descriptions using behavior similar-ity metrics. The conducted experiments compare the per-formance of standard Grammatical Evolution and its Nov-elty Search variation using four intuitive behavior descriptors. The experimental results demonstrate that Grammatical Evo-lution with Novelty Search outperforms the traditional fitness based Grammatical Evolution algorithm in the Santa Fe Trail problem demonstrating a higher success rates and better so-lutions in terms of the required steps.