Titulo Estágio
Local Search Approaches to Genetic Programming
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
DEI
Enquadramento
Genetic Programming (GP) can be understood as the application of evolutionary algorithms to the generation of computer programs capable of solving a given task, such as symbolic regression (discovering the structure of functions that fit given data), classification, electrical circuit design, and the optimisation of game-playing agents. However, GP is often considered to transcend evolutionary algorithms as such because a GP solution is supposed to encode a way of solving many instances of the same problem. For example, a game-playing agent should be able to perform well against all (or, at least, most) opponents, rather than simply be able to beat a designated opponent.
Despite the above, most problems solved by GP can still be understood as combinatorial or, possibly, mixed (partly discrete and partly continuous) optimisation problems that are characterised by a well-defined search space and an objective function to be minimised or maximised. Therefore, it should also be possible to design GP algorithms like any other local-search algorithm, whether evolutionary or not, by focusing on the characteristics of the problem to be solved and defining an appropriate search neighbourhood and the corresponding search operators.
This Master’s thesis will explore the development of genetic programming algorithms based on abstract syntax tree (AST) representations, for which suitable notions of distance can be defined.
Objetivo
The main objective of this work is the development of novel search operators and population initialisation strategies for ASTs in GP. In particular, a clear definition of the combinatorial search space and suitable notions of edit distance between ASTs will allow the problem to be solved by GP to be posed in much the same way as any other combinatorial optimisation problem. Geometric mutation and recombination operators will be derived from the chosen definition of distance, and implemented so as to allow different search strategies to be applied in a transparent way. The uniform sampling of the search space for the purpose of population initialisation will be considered in the same scope.
Plano de Trabalhos - Semestre 1
1. Literature review on genetic programming.
2. Study of geometric search operators in evolutionary algorithms and related concepts.
3. Formalisation and implementation of geometric mutation operators for ASTs.
4. Development of algorithms for the uniform sampling of the search space.
5. Proof-of-concept implementation of a simple GP algorithm based on the initialisation and mutation operators developed.
6. Intermediate report writing.
Plano de Trabalhos - Semestre 2
1. Development and implementation of geometric recombination operators for ASTs.
2. Full-fledged implementation of GP algorithm(s) based on the operators developed.
3. Experimental evaluation and of the algorithms proposed and discussion of the results achieved.
4. Dissertation writing.
Condições
Good background in algorithms, data structures, evolutionary computation, and statistics. The work will be carried out in the laboratories of the CISUC Adaptive Computing Group. A multiprocessor server is available to support the development and evaluation of the algorithms developed.
A full-time research scholarship (Bolsa de Investigação para Licenciado) to support this line of work is planned for the second semester.
Orientador
Carlos Manuel Mira da Fonseca
cmfonsec@dei.uc.pt 📩