- author = "Stefano Ruberto",
- title = "Genetic Programming with Semantic Equivalence Classes",
- school = "GSSI Gran Sasso Science Institute",
- year = "2017",
- address = "Viale Francesco Crispi 7, 67100 L'Aquila, Italy",
- month = jun # " 8",
- keywords = "genetic algorithms, genetic programming, ESAGP, GPPLUS, GPMUL",
-
URL = "
http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/Ruberto_thesis.pdf",
- size = "110 pages",
-
abstract = "This dissertation has been carried out in the context
of Evolutionary Algorithms and specifically in the
application of Genetic Programming (GP) techniques to
symbolic regression problems. In this class of
problems, given an input vector of independent
numerical variables, algorithms are able to find models
that approximate a desired scalar output. Among the
machine learning techniques, GP has the important
advantage of synthesising as output a full intelligible
model. Recently, interesting new approaches measure the
computational behaviour of such models, their
semantics, considering the output vector on all the
test cases in the training set. By characterizing the
behaviour of the model at hand, it is possible to
improve the efficiency during exploration of the
solution space, while avoiding duplicate behaviours and
directing the evolution towards the desired directions.
In this context, geometric approaches play a very
important role, mainly due to their performance in
terms of models accuracy and ability to generalize.
However, they also suffer from a number of drawbacks,
i.e., the exponential growth of the models structure
(bloat) and a slow convergence rate.
In this dissertation we propose a radically different approach, which is based on a new semantic framework that performs effectively against bloat, thus preserving models clarity, and reaching comparable accuracy and generalization performances starting from a common background. More specifically, we introduce the concept of semantics-based equivalence classes. The approach is implemented by means of two different novel genetic programming systems, in which two different definitions of equivalence are used. In both these systems, whenever a solution in an equivalence class is found, it is possible to analytically generate any other solution in that equivalence class. As such, these two systems allow us to shift the objective of genetic programming: instead of finding a globally optimal solution, the objective is to find any solution that belongs to the same equivalence class as a global optimum. Equivalence classes generalize the use of pseudo-distances, as opposed to the traditional use of proper metrics in semantic analysis. Furthermore, we propose improvements to these genetic programming systems in which, once a solution belonging to a particular equivalence class is generated, no other solutions in that class are accepted anymore in the population during the evolution. We call filtered systems these improved versions with respect to efficiency and speed in the solution space exploration phase.
We validated the proposed approach via a experimental results obtained on seven complex real-life test problems. Experimental results show that using equivalence classes is a promising direction and that filters are generally helpful to improve the performance of the systems. Experimental results also show that filters are useful to improve the performance of a state-of-the-art GP method. Indeed, we did an extensive experimentation on the well-known linear scaling technique; this contribution is rather general and can work in synergy with the aforementioned semantic/geometric techniques and with other machine learning frameworks.",
- notes = "Supervisor: Leonardo Vanneschi. Ivano Malavolta",
