Titulo Estágio
Simultaneous Search of Syntactic and Semantic Spaces in Genetic Programming
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
DEI-FCTUC
Enquadramento
Genetic Programming (GP) is a powerful technique from evolutionary computation that evolves computer programs to solve complex problems. One of the main advantages of GP is its ability to automatically generate symbolic expressions or models that are often human-readable and potentially easy to interpret. In today’s world, where many machine learning methods act as "black boxes", being able to produce models that are transparent and understandable is especially valuable, particularly in areas, such as legal and healthcare, where explainability is just as important as accuracy.
Despite its strengths, GP often struggles with premature convergence and stagnation in local optima. These challenges are deeply tied to the representation of individuals and the variation operators applied, which together define the fitness landscape and the search neighbourhoods.
Traditionally, GP works in the syntactic space, focusing on the structure of program trees. However, there are also semantic approaches that focus on program behaviour. This dissertation aims to explore the combination of both types of approaches, with the goal of evolving solutions that are not only effective but also easy to understand.
Objetivo
The main objective of this dissertation is to design, implement, and evaluate a hybrid Genetic Programming algorithm that simultaneously searches both the syntactic and semantic solution spaces. To achieve this, we aim to combine two geometric GP approaches: Geometric Syntactic Genetic Programming (GSynGP) [1], which operates on the structure (syntax) of programs, and Geometric Semantic Genetic Programming (GSGP) [2], which focuses on their behaviour (semantics).
GSynGP is a recent approach that introduces geometric crossover operators in the syntactic space of tree-based GP. These operators allow for smoother and more controlled changes between individuals, while also implicitly controlling the growth in program size (bloat). On the other hand, GSGP works in the semantic space, directly altering the outputs of programs using geometric operators. This leads to a simpler search process by creating an error surface with only one peak (unimodal). However, GSGP has a major drawback: it tends to produce much larger programs, which makes the results harder to interpret and limits scalability.
This project proposes a new hybrid approach that takes advantage of both methods by exploring the syntactic and semantic spaces simultaneously. The goal is to combine the efficiency and compactness of GSynGP with the strong performance of GSGP, aiming to produce solutions that are both accurate and interpretable.
The approach devised shall be tested on popular synthetic benchmark problems from the literature as well as real-world datasets, comparing its performance to those of existing methods.
1 - Macedo, João, Carlos M. Fonseca, and Ernesto Costa. "Geometric crossover in syntactic space." European Conference on Genetic Programming. Cham: Springer International Publishing, 2018.
2 - Vanneschi, Leonardo. "An introduction to geometric semantic genetic programming." NEO 2015: Results of the Numerical and Evolutionary Optimization Workshop NEO 2015 held at September 23-25 2015 in Tijuana, Mexico. Cham: Springer International Publishing, 2016.
Plano de Trabalhos - Semestre 1
1 - Literature review.
2 - Design and implementation of the first version of the hybrid algorithm.
3 - Preliminary testing and validation in benchmark problems.
4 - Writing of the intermediate report.
Plano de Trabalhos - Semestre 2
5 - Exploration of different hibridisations and refinement of the algorithm.
7 - Validation.
8 - Writing of a scientific article with the main results.
9 - Writing of the thesis.
Condições
The work will be conducted in the bio-inspired Artificial Intelligence (bAI) group from CISUC.
There is a possibility of the student being awarded a scholarship (Bolsa de Investigação para Licenciado) for at least 6 months, renewable for an equal period by agreement between the advisor and the intern. The scholarship will follow the Fundação para a Ciência e Tecnologia (FCT) monthly stipend guidelines.
Orientador
João Macedo / Nuno Lourenço
jmacedo@dei.uc.pt 📩