Titulo Estágio
Improving Grammars for Grammatical Evolution
Área Tecnológica
Sistemas Evol. e Comp.
Local do Estágio
CISUC-ECOS
Enquadramento
The Evolutionary Computation area appeared in the 1960s, as an Artificial Intelligence branch that draws its inspiration in the principles of natural selection and genetics. Historically, there are several Evolutionary Algorithm (EA) models, such as Genetic Algorithms, Evolutionary Strategies, Evolutionary Programming, or Genetic Programming.
To tackle a certain problem, a set of potential solutions is created and evaluated. Then, variation operators are iteratively applied to the best solutions leading to the appearance of new promising ways to solve the problem at hand. The process stops when a predetermined termination criterion is met.
Genetic Programming (GP) is a EA branch where solutions codify an algorithmic strategy, i.e., a computer program. Algorithms can be encoded using different types of representations, such as parse-trees or grammars. The latter has gained some relevance in recent years, mainly due to Grammatical Evolution (GE).
In GE, variation operators are applied to solutions encoded as straightforward binary strings. A mapping process is then required to decode this information into an executable algorithmic strategy.
A Context-Free-Grammar (CFG), using the Backus–Naur Form (BNF) notation, is usually adopted to define the mapping rules.
BNF-based GE has some limitations. For instance, when one has to write a production with a range of values, the alternative is to write manually all the values in the range. Or when one has to repeat a certain non-terminal for a predetermined number of times, the BNF notation lacks the tools to do so.
Objetivo
Building on the work that is currently being developed in our lab, the goal is to develop and test a framework to overcome the limitations imposed by the BNF notation. More precisely, the aim is to build a framework based on an extended grammar notation. This notation should contain a set of tools to overcome some of the limitations imposed by the BNF.
Plano de Trabalhos - Semestre 1
- State-of-the-art review
- Analysis of the existing GE framework
- Proposal of the extended grammar notation
- Documentation
Plano de Trabalhos - Semestre 2
- Development of the extended GE framework
- Experimental analysis of the extended GE framework
- Documentation
Condições
The ECOS Laboratory and its computing resources are available for performing experiments. The research group has a computer cluster available for the experimental analysis.
Observações
The student will work within a research group with high national and international visibility. During the work the student will acquire a set of skills that are important for who wants to pursuit an academic/researching career.
The candidate curriculum is required.
Students with strong skills in programming (Python) are highly preferred.
Orientador
Nuno Lourenço / Francisco B. Pereira / Ernesto Costa
naml@dei.uc.pt 📩