Titulo Estágio
Artificial Genetic Representation Database
Áreas de especialidade
Sistemas Inteligentes
Engenharia de Software
Local do Estágio
ECOS - CISUC
Enquadramento
Genetic representations and operators are widely recognised as key aspects of evolutionary algorithms. Concerning representations, the issues of redundancy and neutrality continue to draw attention. Redundant representations are those where several different genotypes decode to the same phenotype. If, in addition, such genotypes are connected by single-point mutations, the representation is said to exhibit neutrality. Many genotype-phenotype mappings in Nature are known to be neutral, a fact that has profound implications on the roles of natural selection and genetic drift in natural evolution.
The study of neutrality in artificial genetic representations is relevant for two main reasons. On the one hand, establishing a parallel with natural representations should allow some hypothesis about how given representation properties influence the evolutionary process to be put to the test. On the other hand, since neutrality has emerged in natural representations, there may be a reason to believe that it is somehow advantageous, and exploiting it in artificial evolution may lead to faster evolutionary algorithms.
One approach to the study of neutrality has been the development of families of artificial neutral genetic representations based on the formalism of error-control codes. Such families are extremely rich in terms of the combinations of representation properties that can be achieved, but are also extremely large. Therefore, there is great interest in efficiently enumerating and characterising such representations.
Objetivo
The main objective of this work is the development of a database of representations for Evolutionary Algorithms and associated interface(s) providing access to their properties and associated information, in the spirit of public repositories such as the ChemSpider chemical structure database (try out http://www.chemspider.com/Search.aspx?q=c6h6 for an example query) or the Stanford RNA Mapping Database (https://rmdb.stanford.edu/). Of particular interest are existing families of redundant neutral binary representations which possess a rich mathematical structure, and are good candidates for research on how representation properties relate to evolutionary search performance. In addition to the characterisation of individual representations in terms of relevant numerical properties, visualisation of the associated neutral-network structures and phenotype-density maps should be provided, as well as representation search facilities.
Plano de Trabalhos - Semestre 1
1. Familiarisation with the study of neutral representations in Evolutionary Computation.
2. Familiarisation with the neutral representations to be considered, their theoretical properties, and strategies for their enumeration.
3. Characterisation of the representations in an existing database containing over 1700 million records, each representing up to 20160 different representations in a compressed form. The initial focus will be on the computation of some numerical properties that are shared by all representations in each record and on graphical depictions of the corresponding neutral-network structures.
4. Development of a web interface to support peruse of the database.
5. Intermediate report writing.
Plano de Trabalhos - Semestre 2
1. Development of embarrassingly parallel algorithms for the enumeration of very large families of neutral representations to populate the database.
2. Development of mechanisms to search the database for individual representations within (compressed) records.
3. Database deployment and evaluation.
4. Dissertation writing.
Condições
Good background in algorithms, data structures and evolutionary computation. 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, and the database will be deployed on the DEI cloud infrastructure.
Orientador
Carlos M. Fonseca
cmfonsec@dei.uc.pt 📩