Programación Genética y Evolución Gramatical : un enfoque combinado usando Straight Line Programs

Abstract

RESUMEN: Uno de los principales inconvenientes en programación genética (GP) para resolver el problema de la regresión simbólica es diseñar una topología de la estructura de datos utilizada, esto es, determinar el número de operaciones adecuadas (no menos, ni demasiadas) que se requiere para solucionar el problema. En el presente trabajo se adopta un nuevo algoritmo basado en programación genética, straight line programs (SLPs) y evolución gramatical para diseñar la topología de los SLPs. Como resultado, produce SLPs más simples que tienen una mejor capacidad de generalización y son más fáciles de implementar. Además, debido al hecho de que la capacidad de generalización de los SLPs puede disminuir, el algoritmo utiliza un novedoso enfoque de penalización adaptativa para ajustar los SLPs generados a través del proceso de evolución. El método propuesto ha sido analizado con dos conjuntos de funciones objetivo previamente usadas en la literatura y los resultados han sido contrastados con otros algoritmos similares que usan SLPs como estructura de datos en GP. Los resultados experimentales sugieren que nuestro método presenta mejoras en la mayoría de los casos y que es un enfoque razonable a considerar para resolver regresión simbólica.

ABSTRACT: One of the main problems in genetic programming for solving symbolic regression problema is to design the topology of the data structure, that is, to determine the number of suitable operations (not less, not too many) required to solve the problem. In the present work a new algorithm based on genetic programming, straight line programs and grammatical evolution is adopted. As a result, it produces simpler Straight Line Programs (SLPs) that have a better generalization capacity and is easier to implement. Moreover, due to the fact that the generalization capacity of SLPs may decrease, the algorithm uses a novel adaptive penalti approach to adjust the structure generated through the process of evolution. The proposed method has been tested with two sets of target functions previosly used in the literature and the results are contrasted with other similar algorithms that use Straight Line Programs as data structure in genetic programming. The experimental results suggest that our method presents improvements in most cases and that it is a reasonable approach to consider for solving symbolic regression problem.