Semantic crossover operators based on the first and second partial derivatives of the fitness function for genetic programming

Abstract

Semantic genetic operators in evolutionary algorithms, particularly in GP, have been proved to be a better heuristic than traditional syntactic operators by improving the performance of GP over certain problems. A semantic operator, crossover or mutation, is guided by the behavior (semantics) of the individual, rather than its syntax, in order to create new and fitter individuals. In this work, we propose to use the information provided by the first and second partial derivatives of the error function (fitness function) w.r.t. the crossing point, to develop novel semantic crossover operators for GP that outperform the traditional crossover. A semantic crossover operator based on partial derivatives will guide the crossover operation by the minimization of the error contribution of the subtree rooted at the crossing point. In order to develop these new operators, a new methodology is proposed to compute the first and second partial derivatives of the fitness function with respect to the crossing point, this methodology is inspired in the backpropagation algorithm used to train ANNs. The information provided by the partial derivatives will guide a search in the second parent in order to find more suitable values for the subtree rooted at the crossing point. The semantic operators presented in this work are tested in three different kind of problems commonly solved with GP: Regression, Classification and Feature Selection. Besides comparing the semantic crossover operators against the traditional syntactical crossover other semantic methods are also included in the comparison, for Regression problems. For Classification and Feature Selection the comparison is with other traditional techniques used for such tasks. The obtained results show a major improvement from traditional crossover for GP in the problems tested and are competitive against other semantic operators and traditional techniques.

Los operadores genéticos semánticos en los algoritmos evolutivos, especialmente en PG, han demostrado ser una heurística con mejores resultados que los operadores genéticos sintácticos tradicionales debido a que aumentan el desempeño de PG. Un operador semántico utiliza la información proporcionada por el comportamiento (semántica) del individuo, de tal forma que su descendencia esté mejor adaptada que el individuo original. Este trabajo propone utilizar la información proporcionada por la primera y segunda derivada parcial de la función de error con respecto al punto de cruza seleccionado, con la finalidad de desarrollar diferentes operadores semánticos para PG. Un operador semántico de cruza basado en las derivadas parciales guiara el proceso de cruza de manera que minimice el error que proporciona el punto de cruza. Para poder desarrollar estos nuevos operadores semánticos de cruza, se ha propuesto una nueva metodología para poder calcular las derivadas parciales de la función de error con respecto al punto de cruza, dicha metodología está inspirada en el algoritmo de propagación hacia atrás que es usado para entrenar Redes Neuronales. La información que proporcionan las derivadas parciales es usada para realizar una búsqueda en el segundo padre para encontrar valores más apropiados para el subárbol cuya raíz es el punto de cruza. Los operadores semánticos presentados en este trabajo fueron probados en tres diferentes clases de problemas: Regresión, Clasificación y Selección de características. Además de comparar los operadores semánticos de cruza contra la cruza sintáctica tradicional también otros operadores semánticos se han incluido en la comparativa en los problemas de Regresión. Para Clasificación y Selección de características la comparación fue hecha contra técnicas tradicionales usadas para este tipo de problemas. Los resultados obtenidos muestran una mejora considerable respecto a la cruza tradicional de PG en los problemas usados mientras que son competitivos contra otras técnicas semánticas y técnicas tradicionales.