A purely-evolutionary memetic algorithm as a first step towards symbiotic coevolution

In this paper we propose a memetic algorithm in which a local search step, also based on evolutionary principles, is added to a conventional evolutionary algorithm. In particular, we have considered a basic experimental setup in which a genetic algorithm (GA) is used to optimize the numeric terminals of programs evolved using genetic programming (GP). We present results obtained in testing our approach on symbolic regression problems and compare them to results obtained on the same problems by similar approaches which incorporated non-evolutionary local search optimization. The paper presents a set of results obtained with a basic scheme in which GP and GA steps alternate with prefixed frequency. We also present some preliminary results obtained with a more complex, general and potentially more performing scheme in which the same idea has been translated into a coevolutionary environment. In this coevolutionary scheme, the fitness of GA individuals, which encode numerical values, is proportional to the fitness that is globally achieved by GP individuals which use them as terminals. We envision this as the simplest possible implementation of a general coevolutionary scheme in which heterogeneous populations evolve, driven by a fitness function that reflects their capability to either solve the main problem or to contribute to other individuals that are tackling it.