Titulo Estágio
Genetic Programming as Local Search
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
ECOS - CISUC
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 the prefix or postfix representation of abstract syntax trees (ASTs), for which suitable notions of distance can be defined based on string edit distance [1]. The associated computational problems are related to finding longest common subsequences, and can typically be approached using dynamic programming.
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 [2] 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.
Evaluation of the algorithms developed will be performed experimentally on symbolic regression and/or classification problems commonly arising in Machine Learning.
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 based on a suitable intermediate representation such as prefix or postfix notation.
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. Fully-fledged implementation of GP algorithm(s) based on the operators developed.
3. Computational study.
4. Evaluation and discussion of the algorithms proposed and of the results achieved.
5. Dissertation writing.
Condições
Good background in algorithms, data structures, evolutionary computation, and statistics. The work will be carried out in the CISUC ECOS laboratories. A computer cluster is available to support the development and evaluation of the algorithms developed.
Observações
References
[1] J. Macedo, C. M. Fonseca, and E. Costa, “Geometric crossover in syntactic space,” in Genetic Programming, 21st European Conference, EuroGP 2018, Proceedings (M. Castelli, L. Sekanina, M. Zhang, S. Cagnoni, and P. García-Sánchez, eds.), vol. 10781 of Lecture Notes in Computer Science, pp. 237–252, Switzerland: Springer International Publishing, 2018.
[2] A. Moraglio, Towards a Geometric Unification of Evolutionary Algorithms. PhD thesis, Department of Computer Science, University of Essex, UK, 2007.
Orientador
Carlos M. Fonseca
cmfonsec@dei.uc.pt 📩