Dissertations / Theses on the topic 'Genetic Programming'

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
PROGRAMA DE EXCELENCIA ACADEMICA
Sistemas Fuzzy-Genéticos compreendem uma área que une Sistemas de Inferência Fuzzy e Meta-Heurísticas prevalentes nos conceitos de seleção natural e recombinação genética. Esta é de grande interesse para a comunidade científica, pois propicia a descoberta de conhecimento em áreas onde a compreensão do fenômeno em estudo é exíguo, além de servir de apoio à decisão para gestores público-privados. O objetivo desta dissertação é desenvolver um novo Sistema Fuzzy-Genético Genérico, denominado Genetic Programming Fuzzy Inference System (GPFIS). O principal aspecto do modelo GPFIS são as componentes do seu processo de Inferência Fuzzy. Esta estrutura é composta em sua base pela Programação Genética Multigênica e pretende: (i ) possibilitar o uso de operadores de agregação, negação e modificadores linguísticos de forma simplificada; (ii ) empregar heurísticas de definição do consequente mais apropriado para uma parte antecedente; e (iii ) usar um procedimento de defuzzificação, que induzido pela forma de fuzzificação e sobre determinadas condições, pode proporcionar uma estimativa mais acurada. Todas estas são contribuições que podem ser estendidas a outros Sistemas Fuzzy-Genéticos. Para demonstrar o aspecto genérico, o desempenho e a importância de cada componente para o modelo proposto, são formuladas uma série de investigações empíricas. Cada investigação compreende um tipo de problema: Classificação, Previsão, Regressão e Controle. Para cada problema, a melhor configuração obtida durante as investigações é usada no modelo GPFIS e os resultados são comparados com os de outros Sistemas Fuzzy-Genéticos e modelos presentes na literatura. Por fim, para cada problema é apresentada uma aplicação detalhada do modelo GPFIS em um caso real.
Genetic Fuzzy Systems constitute an area that brings together Fuzzy Inference Systems and Meta-Heuristics that are often related to natural selection and genetic recombination. This area attracts great interest from the scientific community, due to the knowledge discovery capability in situations where the comprehension of the phenomenon under analysis is lacking. It can also provides support to decision makers. This dissertation aims at developing a new Generic Genetic Fuzzy System, called Genetic Programming Fuzzy Inference System (GPFIS). The main aspects of GPFIS model are the components which are part of its Fuzzy Inference procedure. This structure is basically composed of Multi-Gene Genetic Programming and intends to: (i ) apply aggregation operators, negation and linguistic hedges in a simple manner; (ii ) make use of heuristics to define the consequent term most appropriate to the antecedent part; (iii ) employ a defuzzification procedure that, driven by the fuzzification step and under some assumptions, can provide a most accurate estimate. All these features are contributions that can be extended to other Genetic Fuzzy Systems. In order to demonstrate the general aspect of GPFIS, its performance and the relevance of each of its components, several investigations have been performed. They deal with Classification, Forecasting, Regression and Control problems. By using the best configuration obtained for each of the four problems, results are compared to other Genetic Fuzzy Systems and models in the literature. Finally, applications of GPFIS actual cases in each category is reported.

GP has traditionally been implemented in LISP but there is a slow migration towards faster languages like C++. Any implementation language is dictated not only by the speed of the platform but also by the desirability of such an implementation. With a large number of scientists migrating to scientifically-biased programming languages like Mathematica, such provides an ideal testbed for GP.In this study it was attempted to implement GP on a Mathematica platform, exploiting the advantages of Mathematica's unique capabilities. Wherever possible, optimizations have been applied to drive the GP algorithm towards realistic goals. At an early stage it was noted that the standard GP algorithm could be significantly speeded up by parallelisation and the distribution of processing. This was incorporated into the algorithm, using known techniques and Mathematica-specific knowledge.

Stack-based genetic programming uses variable length, linear programs executing on a virtual stack machine. This concept was proposed and evaluated by Timothy Perkis. The Java programming language uses a stack-based virtual machine to perform operations. This paper examined the possibility of performing stack-based genetic programming directly using the stack on the Java virtual machine. The problems of combining stack based genetic programming with the Java virtual machine stack were explored. Excessive runtime delay on bytecode verification of the chromosome carrying classes undergoing fitness evaluation was identified. Another problem is that the Java virtual machine stack must be tightly controlled and cannot have illegal operands. Direct comparison of stack-based genetic programming on the Java virtual machine to common tree-based genetic programming was not performed due to discovered flaws in the architecture. A practical model to implement stack-based genetic programming on the Java virtual machine using a class bytecode assembler was proposed. This model combines the GPsys genetic programming system with the JAS bytecode assembler resulting in an architecture called GPsys-JAS. A further recommendation to compare stack-based genetic programming on the Java virtual machine against stack-based genetic programming using the Java Stack class was suggested.

Thesis (M.S. in Information Technology Management) Naval Postgraduate School, December 1993.
Thesis advisor(s): B. Ramesh ; William R. Gates. "December 1993." Includes bibliographical references. Also available online.

This master’s thesis is an investigation into automatically created functions when applying Genetic Programming to a problem. The thesis begins with a description of Genetic Programming and the different parts that is required to apply Genetic Programming to a problem. This is followed by descriptions of different methods for automatically creating functions when using Genetic Programming as a problem solving method. A new method for automatically creating functions is proposed with the name Structural Module Creation. Structural Module Creation creates new functions based on the most frequent subtrees in the population of individuals. Experiments are conducted on the even-k-parity problem to compare Structural Module Creation to Module Acquisition (another modularization method) and Genetic Programming without a modularization method. The result of the different experiments showed no improvement when using Structural Module Creation compared to Module Acquisition and Genetic Programming without a modularization method. The conclusion that can be drawn is that Structural Module Creation is not applicable to the even-k-parity problem. Appendix A contains graphs depicting the different experiments. Appendix B contains a description of the implementation of the system.

Dramatic growth in database technology has outpaced the ability to analyze the information stored in databases for new knowledge and has created an increasing potential for the loss of undiscovered knowledge. This potential gains for such knowledge discovery are particularly large in the Department of Defense where millions of transactions, from maintenance to medical information, are recorded yearly. Due to the limitations of traditional knowledge discovery methods in analyzing this data, there is a growing need to utilize new knowledge discovery methods to glean knowledge from vast databases. This research compares a new knowledge discovery approach using a genetic program (GP) developed at the Naval Postgraduate School that produces data associations expressed as IF X THEN Y rules. In determining validity of this GP approach, the program is compared to traditional statistical and inductive methods of knowledge discovery. Results of this comparison indicate the viability of using a GP approach in knowledge discovery by three findings. First, the GP discovered interesting patterns from the data set. Second, the GP discovered new relationships not uncovered by the traditional methods. Third, the GP demonstrated a greater ability to focus the knowledge discovery search towards particular relationships, such as producing exact or general rules

COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
A superioridade de desempenho dos algoritmos quânticos, em alguns problemas específicos, reside no uso direto de fenômenos da mecânica quântica para realizar operações com dados em computadores quânticos. Esta característica fez surgir uma nova abordagem, denominada Computação com Inspiração Quântica, cujo objetivo é criar algoritmos clássicos (executados em computadores clássicos) que tirem proveito de princípios da mecânica quântica para melhorar seu desempenho. Neste sentido, alguns algoritmos evolutivos com inspiração quântica tem sido propostos e aplicados com sucesso em problemas de otimização combinatória e numérica, apresentando desempenho superior àquele dos algoritmos evolutivos convencionais, quanto à melhoria da qualidade das soluções e à redução do número de avaliações necessárias para alcançá-las. Até o presente momento, no entanto, este novo paradigma de inspiração quântica ainda não havia sido aplicado à Programação Genética (PG), uma classe de algoritmos evolutivos que visa à síntese automática de programas de computador. Esta tese propõe, desenvolve e testa um novo modelo de algoritmo evolutivo com inspiração quântica, denominado Programação Genética Linear com Inspiração Quântica (PGLIQ), para a evolução de programas em código de máquina. A Programação Genética Linear é assim denominada porque cada um dos seus indivíduos é representado por uma lista de instruções (estruturas lineares), as quais são executadas sequencialmente. As contribuições deste trabalho são o estudo e a formulação inédita do uso do paradigma da inspiração quântica na síntese evolutiva de programas de computador. Uma das motivações para a opção pela evolução de programas em código de máquina é que esta é a abordagem de PG que, por oferecer a maior velocidade de execução, viabiliza experimentos em larga escala. O modelo proposto é inspirado em sistemas quânticos multiníveis e utiliza o qudit como unidade básica de informação quântica, o qual representa a superposição dos estados de um sistema deste tipo. O funcionamento do modelo se baseia em indivíduos quânticos, que representam a superposição de todos os programas do espaço de busca, cuja observação gera indivíduos clássicos e os programas (soluções). Nos testes são utilizados problemas de regressão simbólica e de classificação binária para se avaliar o desempenho da PGLIQ e compará-lo com o do modelo AIMGP (Automatic Induction of Machine Code by Genetic Programming), considerado atualmente o modelo de PG mais eficiente na evolução de código de máquina, conforme citado em inúmeras referências bibliográficas na área. Os resultados mostram que a Programação Genética Linear com Inspiração Quântica (PGLIQ) apresenta desempenho geral superior nestas classes de problemas, ao encontrar melhores soluções (menores erros) a partir de um número menor de avaliações, com a vantagem adicional de utilizar um número menor de parâmetros e operadores que o modelo de referência. Nos testes comparativos, o modelo mostra desempenho médio superior ao do modelo de referência para todos os estudos de caso, obtendo erros de 3 a 31% menores nos problemas de regressão simbólica, e de 36 a 39% nos problemas de classificação binária. Esta pesquisa conclui que o paradigma da inspiração quântica pode ser uma abordagem competitiva para se evoluir programas eficientemente, encorajando o aprimoramento e a extensão do modelo aqui apresentado, assim como a criação de outros modelos de programação genética com inspiração quântica.
The superior performance of quantum algorithms in some specific problems lies in the direct use of quantum mechanics phenomena to perform operations with data on quantum computers. This feature has originated a new approach, named Quantum-Inspired Computing, whose goal is to create classic algorithms (running on classical computers) that take advantage of quantum mechanics principles to improve their performance. In this sense, some quantum-inspired evolutionary algorithms have been proposed and successfully applied in combinatorial and numerical optimization problems, presenting a superior performance to that of conventional evolutionary algorithms, by improving the quality of solutions and reducing the number of evaluations needed to achieve them. To date, however, this new paradigm of quantum inspiration had not yet been applied to Genetic Programming (GP), a class of evolutionary algorithms that aims the automatic synthesis of computer programs. This thesis proposes, develops and tests a novel model of quantum-inspired evolutionary algorithm named Quantum-Inspired Linear Genetic Programming (QILGP) for the evolution of machine code programs. Linear Genetic Programming is so named because each of its individuals is represented by a list of instructions (linear structures), which are sequentially executed. The contributions of this work are the study and formulation of the novel use of quantum inspiration paradigm on evolutionary synthesis of computer programs. One of the motivations for choosing by the evolution of machine code programs is because this is the GP approach that, by offering the highest speed of execution, makes feasible large-scale experiments. The proposed model is inspired on multi-level quantum systems and uses the qudit as the basic unit of quantum information, which represents the superposition of states of such a system. The model’s operation is based on quantum individuals, which represent a superposition of all programs of the search space, whose observation leads to classical individuals and programs (solutions). The tests use symbolic regression and binary classification problems to evaluate the performance of QILGP and compare it with the AIMGP model (Automatic Induction of Machine Code by Genetic Programming), which is currently considered the most efficient GP model to evolve machine code, as cited in numerous references in this field. The results show that Quantum-Inspired Linear Genetic Programming (QILGP) presents superior overall performance in these classes of problems, by achieving better solutions (smallest error) from a smaller number of evaluations, with the additional advantage of using a smaller number of parameters and operators that the reference model. In comparative tests, the model shows average performance higher than that of the reference model for all case studies, achieving errors 3-31% lower in the problems of symbolic regression, and 36-39% in the binary classification problems. This research concludes that the quantum inspiration paradigm can be a competitive approach to efficiently evolve programs, encouraging the improvement and extension of the model presented here, as well as the creation of other models of quantum-inspired genetic programming.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017.
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (page 55).
In this work I introduce genetic programming [5] as a general technique to produce programs with arbitrary behavior. I discuss genetic programming and its application the task of symbolic regression. I introduce behavioral genetic programming [6] as an extension to genetic programming and explore various extensions to it. The codebase that I build is made sufficiently flexible to easily accommodate future adaptions to the behavioral genetic programming methodology. I test the performance of the implementation of behavioral genetic programming along with several extensions.
by Steven B. Fine.
M. Eng.

In the last decades, an increasing attention has been directed to the application of Genetic Programming. This approach has been adopted to a wide number of fields, reporting successful results also in finance domain as automated computational programming tool. Starting from the theoretical research in Genetic Programming, the aim of this work is to focus on the actual implementation of this methodology to the financial field, especially on the prediction of derivative securities behavior. The attention will be centered on the option pricing and empirical tests will be carried out on market data. Proceeding from the analysis of already developed and qualified studies in the existing literature, this work examines developed models and the reached conclusions. Further, the research will be amplified including the examination of the effect of different variables on the option price behavior, particularly after the variation of different parameters.

The domain of medical imaging analysis has burgeoned in recent years due to the availability and affordability of digital radiographic imaging equipment and associated algorithms and, as such, there has been significant activity in the automation of the medical diagnostic process. One such process, cephalometric analysis, is manually intensive and it can take an experienced orthodontist thirty minutes to analyse one radiology image. This thesis describes an approach, based on genetic programming, neural networks and machine learning, to automate this process. A cephalometric analysis involves locating a number of points in an X-ray and determining the linear and angular relationships between them. If the points can be located accurately enough, the rest of the analysis is straightforward. The investigative steps undertaken were as follows: Firstly, a previously published method, which was claimed to be domain independent, was implemented and tested on a selection of landmarks, ranging from easy to very difficult. These included the menton, upper lip, incisal upper incisor, nose tip and sella landmarks. The method used pixel values, and pixel statistics (mean and standard deviation) of pre-determined regions as inputs to a genetic programming detector. This approach proved unsatisfactory and the second part of the investigation focused on alternative handcrafted features sets and fitness measures. This proved to be much more successful and the third part of the investigation involved using pulse coupled neural networks to replace the handcrafted features with learned ones. The fourth and final stage involved an analysis of the evolved programs to determine whether reasonable algorithms had been evolved and not just random artefacts learnt from the training images. A significant finding from the investigative steps was that the new domain independent approach, using pulse coupled neural networks and genetic programming to evolve programs, was as good as or even better than one using the handcrafted features. The advantage of this finding is that little domain knowledge is required, thus obviating the requirement to manually generate handcrafted features. The investigation revealed that some of the easy landmarks could be found with 100\% accuracy while the accuracy of finding the most difficult ones was around 78\%. An extensive analysis of evolved programs revealed underlying regularities that were captured during the evolutionary process. Even though the evolutionary process took different routes and a diverse range of programs was evolved, many of the programs with an acceptable detection rate implemented algorithms with similar characteristics. The major outcome of this work is that the method described in this thesis could be used as the basis of an automated system. The orthodontist would be required to manually correct a few errors before completing the analysis.

The evolution of explicitly represented topologies such as graphs involves devising methods for mutating, comparing and combining structures in meaningful ways and identifying and maintaining the necessary topological diversity. Research has been conducted in the area of the evolution of trees in genetic programming and of neural networks and some of these problems have been addressed independently by the different research communities. In the domain of neural networks, NEAT (Neuroevolution of Augmenting Topologies) has shown to be a successful method for evolving increasingly complex networks. This system's success is based on three interrelated elements: speciation, marking of historical information in topologies, and initializing search in a small structures search space. This provides the dynamics necessary for the exploration of diverse solution spaces at once and a way to discriminate between different structures. Although different representations have emerged in the area of genetic programming, the study of the tree representation has remained of interest in great part because of its mapping to programming languages and also because of the observed phenomenon of unnecessary code growth or bloat which hinders performance. The structural similarity between trees and neural networks poses an interesting question: Is it possible to apply the techniques from NEAT to the evolution of trees and if so, how does it affect performance and the dynamics of code growth? In this work we address these questions and present analogous techniques to those in NEAT for genetic programming.
M.S.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Engineering MSCpE

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO
PROGRAMA DE EXCELENCIA ACADEMICA
A Programação Genética permite que computadores resolvam problemas automaticamente, sem que eles tenham sido programados para tal. Utilizando a inspiração no princípio da seleção natural de Darwin, uma população de programas, ou indivíduos, é mantida, modificada baseada em variação genética, e avaliada de acordo com uma função de aptidão (fitness). A programação genética tem sido usada com sucesso por uma série de aplicações como projeto automático, reconhecimento de padrões, controle robótico, mineração de dados e análise de imagens. Porém, a avaliação da gigantesca quantidade de indivíduos gerados requer excessiva quantidade de computação, levando a um tempo de execução inviável para problemas grandes. Este trabalho explora o alto poder computacional de unidades de processamento gráfico, ou GPUs, para acelerar a programação genética e permitir a geração automática de programas para grandes problemas. Propomos duas novas metodologias para se explorar a GPU em programação genética: compilação em linguagem intermediária e a criação de indivíduos em código de máquina. Estas metodologias apresentam vantagens em relação às metodologias tradicionais usadas na literatura. A utilização de linguagem intermediária reduz etapas de compilação e trabalha com instruções que estão bem documentadas. A criação de indivíduos em código de máquina não possui nenhuma etapa de compilação, mas requer engenharia reversa das instruções que não estão documentadas neste nível. Nossas metodologias são baseadas em programação genética linear e inspiradas em computação quântica. O uso de computação quântica permite uma convergência rápida, capacidade de busca global e inclusão da história passada dos indivíduos. As metodologias propostas foram comparadas com as metodologias existentes e apresentaram ganhos consideráveis de desempenho. Foi observado um desempenho máximo de até 2,74 trilhões de GPops (operações de programação genética por segundo) para o benchmark Multiplexador de 20 bits e foi possível estender a programação genética para problemas que apresentam bases de dados de até 7 milhões de amostras.
Genetic Programming enables computers to solve problems automatically, without being programmed to it. Using the inspiration in the Darwin s Principle of natural selection, a population of programs or individuals is maintained, modified based on genetic variation, and evaluated according to a fitness function. Genetic programming has been successfully applied to many different applications such as automatic design, pattern recognition, robotic control, data mining and image analysis. However, the evaluation of the huge amount of individuals requires excessive computational demands, leading to extremely long computational times for large size problems. This work exploits the high computational power of graphics processing units, or GPUs, to accelerate genetic programming and to enable the automatic generation of programs for large problems. We propose two new methodologies to exploit the power of the GPU in genetic programming: intermediate language compilation and individuals creation in machine language. These methodologies have advantages over traditional methods used in the literature. The use of an intermediate language reduces the compilation steps, and works with instructions that are well-documented. The individuals creation in machine language has no compilation step, but requires reverse engineering of the instructions that are not documented at this level. Our methodologies are based on linear genetic programming and are inspired by quantum computing. The use of quantum computing allows rapid convergence, global search capability and inclusion of individuals past history. The proposed methodologies were compared against existing methodologies and they showed considerable performance gains. It was observed a maximum performance of 2,74 trillion GPops (genetic programming operations per second) for the 20-bit Multiplexer benchmark, and it was possible to extend genetic programming for problems that have databases with up to 7 million samples.

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
PROGRAMA DE EXCELENCIA ACADEMICA
Uma das tarefas mais importantes na indústria de exploração e produção de petróleo é a discriminação litológica. Uma das principais fontes de informação para subsidiar a discriminação e caracterização litológica é a perfilagem que é corrida no poço. Porém, na grande maioria dos trabalhos os perfis utilizados na discriminação litológica são apenas aqueles disponíveis no domínio dos poços. Para que modelos de discriminação litológica possam ser extrapolados para além do domínio dos poços, faz-se necessário a utilização de características que estejam presentes tanto nos poços como fora deles. As características mais utilizadas para realizar esta integração rocha-perfil-sísmica são os atributos elásticos. Dentre os atributos elásticos o que mais se destaca é a impedância. O objetivo desta dissertação foi a utilização da programação genética como modelo classificador de atributos elásticos para a discriminação litológica. A proposta se justifica pela característica da programação genética de seleção e construção automática dos atributos ou características utilizadas. Além disso, a programação genética permite a interpretação do classificador, uma vez que é possível customizar o formalismo de representação. Esta classificação foi empregada como parte integrante do fluxo de trabalho estatístico e de física de rochas, metodologia híbrida que integra os conceitos da física de rochas com técnicas de classificação. Os resultados alcançados demonstram que a programação genética atingiu taxas de acertos comparáveis e em alguns casos superiores a outros métodos tradicionais de classificação. Estes resultados foram melhorados com a utilização da técnica de substituição de fluídos de Gassmann da física de rochas.
One of the most important tasks in the oil exploration and production industry is the lithological discrimination. A major source of information to support discrimination and lithological characterization is the logging raced into the well. However, in most studies the logs used in the lithological discrimination are only those available in the wells. For extrapolating the lithology discrimination models beyond the wells, it is necessary to use features that are present both inside and outside wells. One of the features used to conduct this rock-log-seismic integration are the elastic attributes. The impedance is the elastic attribute that most stands out. The objective of this work was the utilization of genetic programming as a classifier model of elastic attributes for lithological discrimination. The proposal is justified by the characteristic of genetic programming for automatic selection and construction of features. Furthermore, genetic programming allows the interpretation of the classifier once it is possible to customize the representation formalism. This classification was used as part of the statistical rock physics workflow, a hybrid methodology that integrates rock physics concepts with classification techniques. The results achieved demonstrate that genetic programming reached comparable hit rate and in some cases superior to other traditional methods of classification. These results have been improved with the use of Gassmann fluid substitution technique from rock physics.

Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.
Includes bibliographical references (leaves 74-75).
Function inlining is a compiler optimization where the function call is replaced by the code from the function itself. Using a form of machine learning called genetic programming, this thesis examines which factors are important in determining which function calls to inline to maximize performance. A number of different heuristics are generated for inlining decisions in the Trimaran compiler, which improve on performance from the current default inlining heuristic. Also, trends in function inlining are examined over the thousands of compilation runs that are completed.
by Chris Yu.
M.Eng.

Avhandling för teknologie doktorsexamen i datavetenskap, som kommer att försvaras offentligt tisdagen den 11 mars 2014 kl. 13.15, M404, Högskolan i Borås. Opponent: docent Niklas Lavesson, Blekinge Tekniska Högskola, Karlskrona.

Genetic Programming is a form of Evolutionary Computation in which computer programs are evolved by methods based on simulating the natural evolution of biological species. A new generation of a species acquires the characteristics of previous generations through the inheritance of genes by sexual reproduction and through random changes in alleles by random mutation. The new generation may enhance its ability to survive by the acquisition of cultural knowledge through learning processes. This thesis combines the transfer of knowledge by genetic means with the transfer of knowledge by cultural means. In particular, it introduces a new evolutionary operator, memory operator. In conventional genetic programming systems, a new generation is formed from a mating pool whose members are selected from the fittest members of previous generation. The new generation is produced by the exchange of genes between members of the mating pool and the random replacement of genes in the offspring. The new generation may or may not be able to survive better than its predecessor in a given environment. The memory operator augments the evolutionary process by inserting into new chromosomes genetic material known to often result in fitness improvements. This material is acquired through a learning process in which the system is required to evolve generations that survive in a less demanding environment. The cultural knowledge acquired in this learning process is applied as an intelligent form of mutation to aid survival in a more demanding environment.

This thesis presents Genetic Algorithm for Deriving Software (Gads), a new technique for genetic programming. Gads combines a conventional genetic algorithm with a context-sensitive grammar. The key to Gads is the onto genic mapping, which converts a genome from an array of integers to a correctly typed program in the phenotype language defined by the grammar. A new type of grammar, the reflective attribute grammar (rag), is introduced. The rag is an extension of the conventional attribute grammar, which is designed to produce valid sentences, not to recognize or parse them. Together, Gads and rags provide a scalable solution for evolving type-correct software in independently-chosen context-sensitive languages. The statistics of performance comparison is investigated. A method for representing a set of genetic programming systems or problems on a cladogram is presented. A method for comparing genetic programming systems or problems on a single rational scale is proposed.

Embedded systems dominate the computing landscape. This dominance is increasing with the advent of ubiquitous computing whereby lightweight, low-resource systems are being deployed on a vast scale. These systems present new engineering challenges: high-volume production places a stronger emphasis on absolute cost, resources available to executing software are highly constrained, and physical manufacturing capabilities approach hard limits. Add to this the sensitive nature of many of these systems, such as smartcards used for financial transactions, and the development of these systems becomes a formidable engineering challenge. For the software engineer, the incentive to produce efficient and resource-aware software for these platforms is great, yet existing tools do not support them well in this task. It is difficult to assess the impact of decisions made at the source code level in terms of how they change a system's resource consumption. Existing toolchains, together with the very complex interactions of software and their host processors, can produce unforeseen implications at run-time of even small changes. We could describe such a situation as an instance of programming the unprogrammable, and Genetic Programming is one solution method used for such problems. Genetic Programming, inspired by nature's ability to solve problems involving complex interactions and strong pressures on resource consumption, is a clear candidate for attacking the challenges presented in these systems. Genetic Programming facilitates the creation and manipulation of source code in a way that grants us fine control over its measurable characteristics. In this thesis, I investigate the potential of Genetic Programming as a tool in controlling the non-functional properties of software, as a new method of designing code for low-resource systems. I demonstrate the feasibility of this approach, and investigate some of the ways Genetic Programming could be utilised by a practitioner. In doing so, I also identify key components that any application of Genetic Programming to such a domain will require. I review current low-resource system optimisation, Genetic Programming and methods for simultaneously handling multiple requirements. I present a series of empirical investigations designed to provide evidence for and against a set of hypotheses regarding the success of Genetic Programming in solving problems within the low-resource systems domain. These experiments include the creation of new software, the improvement of existing software and the fine-grained control of resource usage in general. Thus I will address a range of non-functional requirements related to the resource-consumption of a program, and demonstrate how we can apply techniques inspired by natural evolution in combination with conventional optimisation methods to address some of the problems that the plethora of low-resource systems present. To conclude, I review the progress made, reassess my hypotheses, and outline how these new methods can be carried forward to a wide range of applications.

2012/2013
Machine learning is a suite of techniques that allow developing algorithms for performing tasks by generalizing from examples. Machine learning systems, thus, may automatically synthesize programs from data. This approach is often feasible and cost-effective where manual programming or manual algorithm design is not. In the last decade techniques based on machine learning have spread in a broad range of application domains. In this thesis, we will present several novel applications of a specific machine Learning technique, called Genetic Programming, to a wide set of engineering applications grounded in real world problems. The problems treated in this work range from the automatic synthesis of regular expressions, to the generation of electricity price forecast, to the synthesis of a model for the tracheal pressure in mechanical ventilation. The results demonstrate that Genetic Programming is indeed a suitable tool for solving complex problems of practical interest. Furthermore, several results constitute a significant improvement over the existing state-of-the-art. The main contribution of this thesis is the design and implementation of a framework for the automatic inference of regular expressions from examples based on Genetic Programming. First, we will show the ability of such a framework to cope with the generation of regular expressions for solving text-extraction tasks from examples. We will experimentally assess our proposal comparing our results with previous proposals on a collection of real-world datasets. The results demonstrate a clear superiority of our approach. We have implemented the approach in a web application that has gained considerable interest and has reached peaks of more 10000 daily accesses. Then, we will apply the framework to a popular "regex golf" challenge, a competition for human players that are required to generate the shortest regular expression solving a given set of problems. Our results rank in the top 10 list of human players worldwide and outperform those generated by the only existing algorithm specialized to this purpose. Hence, we will perform an extensive experimental evaluation in order to compare our proposal to the state-of-the-art proposal in a very close and long-established research field: the generation of a Deterministic Finite Automata (DFA) from a labelled set of examples. Our results demonstrate that the existing state-of-the-art in DFA learning is not suitable for text extraction tasks. We will also show a variant of our framework designed for solving text processing tasks of the search-and-replace form. A common way to automate search-and-replace is to describe the region to be modified and the desired changes through a regular expression and a replacement expression. We will propose a solution to automatically produce both those expressions based only on examples provided by user. We will experimentally assess our proposal on real-word search-and-replace tasks. The results indicate that our proposal is indeed feasible. Finally, we will study the applicability of our framework to the generation of schema based on a sample of the eXtensible Markup Language documents. The eXtensible Markup Language documents are largely used in machine-to-machine interactions and such interactions often require that some constraints are applied to the contents of the documents. These constraints are usually specified in a separate document which is often unavailable or missing. In order to generate a missing schema, we will apply and will evaluate experimentally our framework to solve this problem. In the final part of this thesis we will describe two significant applications from different domains. We will describe a forecasting system for producing estimates of the next day electricity price. The system is based on a combination of a predictor based on Genetic Programming and a classifier based on Neural Networks. Key feature of this system is the ability of handling outliers-i.e., values rarely seen during the learning phase. We will compare our results with a challenging baseline representative of the state-of-the-art. We will show that our proposal exhibits smaller prediction error than the baseline. Finally, we will move to a biomedical problem: estimating tracheal pressure in a patient treated with high-frequency percussive ventilation. High-frequency percussive ventilation is a new and promising non-conventional mechanical ventilatory strategy. In order to avoid barotrauma and volutrauma in patience, the pressure of air insufflated must be monitored carefully. Since measuring the tracheal pressure is difficult, a model for accurately estimating the tracheal pressure is required. We will propose a synthesis of such model by means of Genetic Programming and we will compare our results with the state-of-the-art.
XXVI Ciclo
1984

Nature has created complex biological structures that exhibit intelligent behaviour through an evolutionary process. Thus, intelligence and evolution are intimately connected. This has inspired evolutionary computation (EC) that simulates the evolutionary process to develop powerful techniques such as genetic algorithms (GAs), genetic programming (GP), evolutionary strategies (ES) and evolutionary programming (EP) to solve real-world problems in learning, control, optimization and classification. GP discovers the relationship among data and expresses it as a LISP-S expression i.e., a computer program. Thus the goal of program discovery as a solution for a problem is addressed by GP in the framework of evolutionary computation. In this thesis, we address for the first time the problem of applying GP to mu1ticategory pattern classification. In supervised pattern classification, an input vector of m dimensions is mapped onto one of the n classes. It has a number of application areas such as remote sensing, medical diagnosis etc., A supervised classifier is developed by using a training set that contains representative samples of various classes present in the application. Supervised classification has been done earlier with maximum likelihood classifier: neural networks and fuzzy logic. The major considerations in applying GP to pattern classification are listed below: (i) GP-based techniques are data distribution-free i.e., no a priori knowledge is needed abut the statistical distribution of the data or no assumption such as normal distribution for data needs to be made as in MLC. (ii) GP can directly operate on the data in its original form. (iii) GP can detect the underlying but unknown relationship that mists among data and express it as a mathematical LISP S-expression. The generated LISP S-expressions can be directly used in the application environment. (iv) GP can either discover the most important discriminating features of a class during evolution or it requires minor post-processing of the LISP-S expression to discover the discriminant features. In a neural network, the knowledge learned by the neural network about the data distributions is embedded in the interconnection weights and it requires considerable amount of post-processing of the weights to understand the decision of the neural network. In 2-category pattern classification, a single GP expression is evolved as a discriminant function. The output of the GP expression can be +l for samples of one class and -1 for samples of the other class. When the GP paradigm is applied to an n-class problem, the following questions arise: Ql. As a typical GP expression returns a value (+l or -1) for a 2-class problem, how does one apply GP for the n-class pattern classification problem? Q2. What should be the fitness function during evolution of the GP expressions? Q3. How does the choice of a function set affect the performance of GP-based classification? Q4. How should training sets be created for evaluating fitness during the evolution of GP classifier expressions? Q5. How does one improve learning of the underlying data distributions in a GP framework? Q6. How should conflict resolution be handled before assigning a class to the input feature vector? Q7. How does GP compare with other classifiers for an n-class pattern classification problem? The research described here seeks to answer these questions. We show that GP can be applied to an n-category pattern classification problem by considering it as n 2-class problems. The suitability of this approach is demonstrated by considering a real-world problem based on remotely sensed satellite images and Fisher's Iris data set. In a 2-class problem, simple thresholding is sufficient for a discriminant function to divide the feature space into two regions. This means that one genetic programming classifier expression (GPCE) is sufficient to say whether or not the given input feature vector belongs to that class; i.e., the GP expression returns a value (+1 or -1). As the n-class problem is formulated as n 2-class problems, n GPCEs are evolved. Hence, n GPCE specific training sets are needed to evolve these n GPCEs. For the sake of illustration, consider a 5-class pat tern classification problem. Let n, be the number of samples that belong to class j, and N, be the number of samples that do not belong to class j, (j = 1,..., 5). Thus, N1=n2+n3+n4+n5 N2=n1+n3+n4+n5 N3=n1+n2+n4+n5 N4=n1+n2+n3+n5 N5=n1+n2+n3+n4 Thus, When the five class problem is formulated as five 2-class problems. we need five GPCEs as discriminant functions to resolve between n1 and N1, n2 and N2, n3 and N3, n4 and N4 and lastly n5 and N5. Each of these five 2-class problems is handled as a separate 2-class problem with simple thresholding. Thus, GPCE# l resolves between samples of class# l and the remaining n - 1 classes. A training set is needed to evaluate the fitness of GPCE during its evolution. If we directly create the training set, it leads to skewness (as n1 < N1). To overcome the skewness, an interleaved data format is proposed for the training set of a GPCE. For example, in the training set of GPCE# l, samples of class# l are placed alternately between samples of the remaining n - 1 classes. Thus, the interleaved data format is an artifact to create a balanced training set. Conventionally, all the samples of a training set are fed to evaluate the fitness of every member of the population in each generation. We call this "global" learning 3s GP tries to learn the entire training set at every stage of the evolution. We have introduced incremental learning to simplify the task of learning for the GP paradigm. A subset of the training set is fed and the size of the subset is gradually increased over time to cover the entire training data. The basic motivation for incremental learning is to improve learning during evolution as it is easier to learn a smaller task and then to progress from a smaller task to a bigger task. Experimental results are presented to show that the interleaved data format and incremental learning improve the performance of the GP classifier. We also show that the GPCEs evolved with an arithmetic function set are able to track variation in the input better than GPCEs evolved with function sets containing logical and nonlinear elements. Hence, we have used arithmetic function set, incremental learning, and interleaved data format to evolve GPCEs in our simulations. AS each GPCE is trained to recognize samples belonging to its own class and reject samples belonging to other classes a strength of association measure is associated with each GPCE to indicate the degree to which it can recognize samples belonging to its own class. The strength of association measures are used for assigning a class to an input feature vector. To reduce misclassification of samples, we also show how heuristic rules can be generated in the GP framework unlike in either MLC or the neural network classifier. We have also studied the scalability and generalizing ability of the GP classifier by varying the number of classes. We also analyse the performance of the GP classifier by considering the well-known Iris data set. We compare the performance of classification rules generated from the GP classifier with those generated from neural network classifier, (24.5 method and fuzzy classifier for the Iris data set. We show that the performance of GP is comparable to other classifiers for the Iris data set. We notice that the classification rules can be generated with very little post-processing and they are very similar to the rules generated from the neural network and C4.5 for the Iris data set. Incremental learning influences the number of generations available for GP to learn the data distribution of classes whose d is -1 in the interleaved data format. This is because the samples belonging to the true class (desired output d is +1) are alternately placed between samples belonging to other classes i.e., they are repeated to balance the training set in the interleaved data format. For example, in the evolution of GPCE for class# l, the fitness function can be fed initially with samples of class#:! and subsequently with the samples of class#3, class#4 and class#. So in the evaluation of the fitness function, the samples of class#kt5 will not be present when the samples of class#2 are present in the initial stages. However, in the later stages of evolution, when samples of class#5 are fed, the fitness function will utilize the samples of both class#2 and class#5. As learning in evolutionary computation is guided by the evaluation of the fitness function, GPCE# l gets lesser number of generations to learn how to reject data of class#5 as compared to the data of class#2. This is because the termination criterion (i.e., the maximum number of generations) is defined a priori. It is clear that there are (n-l)! Ways of ordering the samples of classes whose d is -1 in the interleaved data format. Hence a heuristic is presented to determine a possible order to feed data of different classes for the GPCEs evolved with incremental learning and interleaved data format. The heuristic computes an overlap index for each class based on its spatial spread and distribution of data in the region of overlap with respect to other classes in each feature. The heuristic determines the order in which classes whose desired output d is –1 should be placed in each GPCE-specific training set for the interleaved data format. This ensures that GP gets more number of generations to learn about the data distribution of a class with higher overlap index than a class with lower overlap index. The ability of the GP classifier to learn the data distributions depends upon the number of classes and the spatial spread of data. As the number of classes increases, the GP classifier finds it difficult to resolve between classes. So there is a need to partition the feature space and identify subspaces with reduced number of classes. The basic objective is to divide the feature space into subspaces and hence the data set that contains representative samples of n classes into subdata sets corresponding to the subspaces of the feature space, so that some of the subdata sets/spaces can have data belonging to only p classes (p < n). The GP classifier is then evolved independently for the subdata sets/spaces of the feature space. This results in localized learning as the GP classifier has to learn the data distribution in only a subspace of the feature space rather than in the entire feature space. By integrating the GP classifier with feature space partitioning (FSP), we improve classification accuracy due to localized learning. Although serial computers have increased steadily in their performance, the quest for parallel implementation of a given task has continued to be of interest in any computationally intensive task since parallel implementation leads to a faster execution than a serial implementation As fitness evaluation, selection strategy and population structures are used to evolve a solution in GP, there is scope for a parallel implementation of GP classifier. We have studied distributed GP and massively parallel GP for our approach to GP-based multicategory pattern classification. We present experimental results for distributed GP with Message Passing Interface on IBM SP2 to highlight the speedup that can be achieved over the serial implementation of GP. We also show how data parallelism can be used to further speed up fitness evaluation and hence the execution of the GP paradigm for multicategory pat tern classification. We conclude that GP can be applied to n-category pattern classification and its potential lies in its simplicity and scope for parallel implementation. The GP classifier developed in this thesis can be looked upon as an addition to the earlier statistical, neural and fuzzy approaches to multicategory pattern classification.

Nature has created complex biological structures that exhibit intelligent behaviour through an evolutionary process. Thus, intelligence and evolution are intimately connected. This has inspired evolutionary computation (EC) that simulates the evolutionary process to develop powerful techniques such as genetic algorithms (GAs), genetic programming (GP), evolutionary strategies (ES) and evolutionary programming (EP) to solve real-world problems in learning, control, optimization and classification. GP discovers the relationship among data and expresses it as a LISP-S expression i.e., a computer program. Thus the goal of program discovery as a solution for a problem is addressed by GP in the framework of evolutionary computation. In this thesis, we address for the first time the problem of applying GP to mu1ticategory pattern classification. In supervised pattern classification, an input vector of m dimensions is mapped onto one of the n classes. It has a number of application areas such as remote sensing, medical diagnosis etc., A supervised classifier is developed by using a training set that contains representative samples of various classes present in the application. Supervised classification has been done earlier with maximum likelihood classifier: neural networks and fuzzy logic. The major considerations in applying GP to pattern classification are listed below: (i) GP-based techniques are data distribution-free i.e., no a priori knowledge is needed abut the statistical distribution of the data or no assumption such as normal distribution for data needs to be made as in MLC. (ii) GP can directly operate on the data in its original form. (iii) GP can detect the underlying but unknown relationship that mists among data and express it as a mathematical LISP S-expression. The generated LISP S-expressions can be directly used in the application environment. (iv) GP can either discover the most important discriminating features of a class during evolution or it requires minor post-processing of the LISP-S expression to discover the discriminant features. In a neural network, the knowledge learned by the neural network about the data distributions is embedded in the interconnection weights and it requires considerable amount of post-processing of the weights to understand the decision of the neural network. In 2-category pattern classification, a single GP expression is evolved as a discriminant function. The output of the GP expression can be +l for samples of one class and -1 for samples of the other class. When the GP paradigm is applied to an n-class problem, the following questions arise: Ql. As a typical GP expression returns a value (+l or -1) for a 2-class problem, how does one apply GP for the n-class pattern classification problem? Q2. What should be the fitness function during evolution of the GP expressions? Q3. How does the choice of a function set affect the performance of GP-based classification? Q4. How should training sets be created for evaluating fitness during the evolution of GP classifier expressions? Q5. How does one improve learning of the underlying data distributions in a GP framework? Q6. How should conflict resolution be handled before assigning a class to the input feature vector? Q7. How does GP compare with other classifiers for an n-class pattern classification problem? The research described here seeks to answer these questions. We show that GP can be applied to an n-category pattern classification problem by considering it as n 2-class problems. The suitability of this approach is demonstrated by considering a real-world problem based on remotely sensed satellite images and Fisher's Iris data set. In a 2-class problem, simple thresholding is sufficient for a discriminant function to divide the feature space into two regions. This means that one genetic programming classifier expression (GPCE) is sufficient to say whether or not the given input feature vector belongs to that class; i.e., the GP expression returns a value (+1 or -1). As the n-class problem is formulated as n 2-class problems, n GPCEs are evolved. Hence, n GPCE specific training sets are needed to evolve these n GPCEs. For the sake of illustration, consider a 5-class pat tern classification problem. Let n, be the number of samples that belong to class j, and N, be the number of samples that do not belong to class j, (j = 1,..., 5). Thus, N1=n2+n3+n4+n5 N2=n1+n3+n4+n5 N3=n1+n2+n4+n5 N4=n1+n2+n3+n5 N5=n1+n2+n3+n4 Thus, When the five class problem is formulated as five 2-class problems. we need five GPCEs as discriminant functions to resolve between n1 and N1, n2 and N2, n3 and N3, n4 and N4 and lastly n5 and N5. Each of these five 2-class problems is handled as a separate 2-class problem with simple thresholding. Thus, GPCE# l resolves between samples of class# l and the remaining n - 1 classes. A training set is needed to evaluate the fitness of GPCE during its evolution. If we directly create the training set, it leads to skewness (as n1 < N1). To overcome the skewness, an interleaved data format is proposed for the training set of a GPCE. For example, in the training set of GPCE# l, samples of class# l are placed alternately between samples of the remaining n - 1 classes. Thus, the interleaved data format is an artifact to create a balanced training set. Conventionally, all the samples of a training set are fed to evaluate the fitness of every member of the population in each generation. We call this "global" learning 3s GP tries to learn the entire training set at every stage of the evolution. We have introduced incremental learning to simplify the task of learning for the GP paradigm. A subset of the training set is fed and the size of the subset is gradually increased over time to cover the entire training data. The basic motivation for incremental learning is to improve learning during evolution as it is easier to learn a smaller task and then to progress from a smaller task to a bigger task. Experimental results are presented to show that the interleaved data format and incremental learning improve the performance of the GP classifier. We also show that the GPCEs evolved with an arithmetic function set are able to track variation in the input better than GPCEs evolved with function sets containing logical and nonlinear elements. Hence, we have used arithmetic function set, incremental learning, and interleaved data format to evolve GPCEs in our simulations. AS each GPCE is trained to recognize samples belonging to its own class and reject samples belonging to other classes a strength of association measure is associated with each GPCE to indicate the degree to which it can recognize samples belonging to its own class. The strength of association measures are used for assigning a class to an input feature vector. To reduce misclassification of samples, we also show how heuristic rules can be generated in the GP framework unlike in either MLC or the neural network classifier. We have also studied the scalability and generalizing ability of the GP classifier by varying the number of classes. We also analyse the performance of the GP classifier by considering the well-known Iris data set. We compare the performance of classification rules generated from the GP classifier with those generated from neural network classifier, (24.5 method and fuzzy classifier for the Iris data set. We show that the performance of GP is comparable to other classifiers for the Iris data set. We notice that the classification rules can be generated with very little post-processing and they are very similar to the rules generated from the neural network and C4.5 for the Iris data set. Incremental learning influences the number of generations available for GP to learn the data distribution of classes whose d is -1 in the interleaved data format. This is because the samples belonging to the true class (desired output d is +1) are alternately placed between samples belonging to other classes i.e., they are repeated to balance the training set in the interleaved data format. For example, in the evolution of GPCE for class# l, the fitness function can be fed initially with samples of class#:! and subsequently with the samples of class#3, class#4 and class#. So in the evaluation of the fitness function, the samples of class#kt5 will not be present when the samples of class#2 are present in the initial stages. However, in the later stages of evolution, when samples of class#5 are fed, the fitness function will utilize the samples of both class#2 and class#5. As learning in evolutionary computation is guided by the evaluation of the fitness function, GPCE# l gets lesser number of generations to learn how to reject data of class#5 as compared to the data of class#2. This is because the termination criterion (i.e., the maximum number of generations) is defined a priori. It is clear that there are (n-l)! Ways of ordering the samples of classes whose d is -1 in the interleaved data format. Hence a heuristic is presented to determine a possible order to feed data of different classes for the GPCEs evolved with incremental learning and interleaved data format. The heuristic computes an overlap index for each class based on its spatial spread and distribution of data in the region of overlap with respect to other classes in each feature. The heuristic determines the order in which classes whose desired output d is –1 should be placed in each GPCE-specific training set for the interleaved data format. This ensures that GP gets more number of generations to learn about the data distribution of a class with higher overlap index than a class with lower overlap index. The ability of the GP classifier to learn the data distributions depends upon the number of classes and the spatial spread of data. As the number of classes increases, the GP classifier finds it difficult to resolve between classes. So there is a need to partition the feature space and identify subspaces with reduced number of classes. The basic objective is to divide the feature space into subspaces and hence the data set that contains representative samples of n classes into subdata sets corresponding to the subspaces of the feature space, so that some of the subdata sets/spaces can have data belonging to only p classes (p < n). The GP classifier is then evolved independently for the subdata sets/spaces of the feature space. This results in localized learning as the GP classifier has to learn the data distribution in only a subspace of the feature space rather than in the entire feature space. By integrating the GP classifier with feature space partitioning (FSP), we improve classification accuracy due to localized learning. Although serial computers have increased steadily in their performance, the quest for parallel implementation of a given task has continued to be of interest in any computationally intensive task since parallel implementation leads to a faster execution than a serial implementation As fitness evaluation, selection strategy and population structures are used to evolve a solution in GP, there is scope for a parallel implementation of GP classifier. We have studied distributed GP and massively parallel GP for our approach to GP-based multicategory pattern classification. We present experimental results for distributed GP with Message Passing Interface on IBM SP2 to highlight the speedup that can be achieved over the serial implementation of GP. We also show how data parallelism can be used to further speed up fitness evaluation and hence the execution of the GP paradigm for multicategory pat tern classification. We conclude that GP can be applied to n-category pattern classification and its potential lies in its simplicity and scope for parallel implementation. The GP classifier developed in this thesis can be looked upon as an addition to the earlier statistical, neural and fuzzy approaches to multicategory pattern classification.

11β-hydroxysteroid dehydrogenase type 2 (11β-HSD2) rapidly inactivates GCs within the placenta and other fetal tissues, hence serving as a ‘barrier’ to limit exposure of the fetus to maternal GCs, ensuring an appropriate fetal milieu for normal development. The synthetic GC, dexamethasone (Dex) is thought to bypass the 11β-HSD2 ‘barrier’ due to poor substrate specificity. Prenatal administration in rats has been shown to programme low birth weight and anxiety, associated with hypothalamic pituitary adrenal (HPA) axis hyperactivity and the decreased hippocampal gene expression of corticosteroid receptors, an effect thought to underlie the observed behavioural phenotype. Studies described here extend previous findings and show that prenatal Dex programmes enhanced fear-potentiation reflecting heightened state anxiety. These effects were associated with enhanced c-fos mRNA expression following mild stress exposure within the frontal and cingulated cortex, indicating increased cellular activation. We have used a second model of GC programming which involves crossing mice heterozygous for 11β-HSD2-null allele, generating offspring of three genotypes in the same litter (11β-HSD2+/+, +/- and -/-), allowing direct study of excessive fetal exposure to GCs, independent of altered maternal physiology and/or behaviour, thus providing a unique programming model. In our studies, 11β-HSD2-null mutants displayed reduced birthweight, increased anxiety-related behaviour and mild cognitive deficits, despite normal circulating corticosterone and limbic expression of HPA axis-associated genes. However, dysregulated expression of these candidate genes during the early postnatal period was evident, indicative of an altered developmental trajectory. In addition to programmed effects on the brain and behaviour, 11β-HSD2 null mice exhibit reduced fat deposition, acute weight maintenance deficits and spontaneous hypoactivity despite evidence of normal glucose homeostasis. These metabolic findings emphasize the crucial interactions of early-life programming effects of GCs with the adult GC environment.

In this thesis, we develop a new language for genetic programming, specifically designed for high-level controller scripting on mobile robots. We then test this language against previous conventions on the Robots Everywhere Antbot platform. We develop a genetic programming framework using Python and the new language, to create corridor-following programs in a simple simulation. Using this framework, we conduct a variety of experiments to find good parameters and techniques that apply to this new language, which can evolve the best controllers. Our results suggest that hierarchical GP using a measure of elitism is likely the best solution, and that the new language is very capable of evolving solutions with a high degree of robustness and generality.

Genetic programming is an approach that utilises the power of evolution to allow computers to evolve programs. While loops are natural components of most programming languages and appear in every reasonably-sized application, they are rarely used in genetic programming. The work is to investigate a number of restricted looping constructs to determine whether any significant benefits can be obtained in genetic programming. Possible benefits include: Solving problems which cannot be solved without loops, evolving smaller sized solutions which can be more easily understood by human programmers and solving existing problems quicker by using fewer evaluations. In this thesis, a number of explicit restricted loop formats were formulated and tested on the Santa Fe ant problem, a modified ant problem, a sorting problem, a visit-every-square problem and a difficult object classification problem. The experimental results showed that these explicit loops can be success fully used in genetic programming. The evolutionary process can decide when, where and how to use them. Runs with these loops tended to generate smaller sized solutions in fewer evaluations. Solutions with loops were found to some problems that could not be solved without loops. The results and analysis of this thesis have established that there are significant benefits in using loops in genetic programming. Restricted loops can avoid the difficulties of evolving consistent programs and the infinite iterations problem. Researchers and other users of genetic programming should not be afraid of loops.

Learning Classifier Systems (LCS) traditionally use a ternary encoding to generalise over the environmental inputs and to associate appropriate actions. However, a number of schemes have been presented beyond this, ranging from integers to artificial neural networks. This thesis investigates the use of Dynamical Genetic Programming (DGP) as a knowledge representation within LCS. DGP is a temporally dynamic, graph-based, symbolic representation. Temporal dynamism has been identified as an important aspect in biological systems, artificial life, and cognition in general. Furthermore, discrete dynamical systems have been found to exhibit inherent content-addressable memory. In this thesis, the collective emergent behaviour of ensembles of such dynamical function networks are herein shown to be exploitable toward solving various computational tasks. Significantly, it is shown possible to exploit the variable-length, adaptive memory existing inherently within the networks under an asynchronous scheme, and where all new parameters introduced are self-adaptive. It is shown possible to exploit the collective mechanics to solve both discrete and continuous-valued reinforcement learning problems, and to perform symbolic regression. In particular, the representation is shown to provide improved performance beyond a traditional Genetic Programming benchmark on a number of a composite polynomial regression tasks. Superior performance to previously published techniques is also shown in a continuous-input-output reinforcement learning problem. Finally, it is shown possible to perform multi-step-ahead predictions of a financial time-series by repeatedly sampling the network states at succeeding temporal intervals.

Genetic programming is a metaheuristic search method that uses a population of variable-length computer programs and a search strategy based on biological evolution. The idea of automatic programming has long been a goal of artificial intelligence, and genetic programming presents an intuitive method for automatically evolving programs. However, this method is not without some potential drawbacks. Search using procedural representations can be complex and inefficient. In addition, variable sized solutions can become unnecessarily large and difficult to interpret. The goal of this thesis is to understand the dynamics of genetic programming that encourages efficient and effective search. Toward this goal, the research focuses on an important property of genetic programming search: the population. The population is related to many key aspects of the genetic programming algorithm. In this programme of research, diversity is used to describe and analyse populations and their effect on search. A series of empirical investigations are carried out to better understand the genetic programming algorithm. The research begins by studying the relationship between diversity and search. The effect of increased population diversity and a metaphor of search are then examined. This is followed by an investigation into the phenomenon of increased solution size and problem difficulty. The research concludes by examining the role of diverse individuals, particularly the ability of diverse individuals to affect the search process and ways of improving the genetic programming algorithm. This thesis makes the following contributions: (1) An analysis shows the complexity of the issues of diversity and the relationship between diversity and fitness, (2) The genetic programming search process is characterised by using the concept of genetic lineages and the sampling of structures and behaviours, (3) A causal model of the varied rates of solution size increase is presented, (4) A new, tunable problem demonstrates the contribution of different population members during search, and (5) An island model is proposed to improve the search by speciating dissimilar individuals into better-suited environments. Currently, genetic programming is applied to a wide range of problems under many varied contexts. From artificial intelligence to operations research, the results presented in this thesis will benefit population-based search methods, methods based on the concepts of evolution and search methods using variable-length representations.

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO
PROGRAMA DE EXCELENCIA ACADEMICA
Na área de exploração e produção de petróleo são alocados grandes investimentos para conseguir diminuir os riscos associados à baixos níveis de produção, que podem ser minimizados mediante a acertada caracterização do reservatório de petróleo. Uma valiosa fonte de informação pode ser extraída de dados sísmicos 3D, obtidos do campo em estudo. O custo econômico de aquisição de esta base de dados para o reservatório completo é relativamente baixo, se comparado com uma amostragem direta por meio de perfurações de poços. Embora, a relação entre os dados sísmicos e as propriedades de reservatório seja considerada ambígua, esta deve ser integrada com informação confiável, como aquela obtida mediante perfilagem de poços. Fazendo uso dos abundantes dados sísmicos e das escassas, mas, precisas medições em perfurações existentes, foi desenvolvido neste trabalho um sistema baseado no algoritmo de Programação Genética (PG) para caracterizar geologicamente um reservatório de petróleo. PG é uma técnica de computação evolucionária capaz de estimar relações não lineares entre um conjunto de entrada e de saída, mediante uma expressão simbólica explícita. Para extrair informação adicional nos registros sísmicos são calculados atributos sísmicos, que facilitam a identificação de características estratigráficas ou estruturais do subsolo representadas indiretamente pela sísmica. Adicionalmente, é utilizado o método de inversão sísmica para o cálculo da impedância acústica, que é uma variável auxiliar derivada de sísmica calibrada com perfis de poço. Os atributos sísmicos junto com a impedância acústica servirão para a estimação de propriedades geológicas. Esta metodologia de trabalho foi testada em um reservatório real de grande complexidade geológica. Por meio de PG, foi representada satisfatoriamente a relação entre dados derivados da sísmica e a porosidade do campo, demostrando assim que PG é uma alternativa viável para a caracterização geológica de reservatórios. Posteriormente, foi realizada uma clusterização do campo baseada em características geofísicas que permitiram a construção de estimadores por PG especializados para cada zona.
In the field of oil exploration and production a great deal of investment is allocated in reducing the risks associated to low production levels that can be minimized through an accurate oil reservoir characterization. A valuable source of information can be extracted from 3D seismic data, obtained from the studied reservoir. The economic cost of the acquisition of this data base for the whole reservoir is relatively low, if compared to the direct sampling method of well drilling. Being that the relationship between seismic data and reservoir properties is considered ambiguous, it must be integrated with reliable information, such as that obtained by well logging. Making use of abundant seismic data and scarce, yet accurate, measurements from the existing drillings, it was developed in this study a system based in the algorithm of Genetic Programming (GP), to geologically characterize an oil reservoir. GP is an evolutionary computational technique capable of estimating the non-linear relationships between input and output parameter, through an explicit symbolic expression. In order to extract additional information from seismic records, seismic attributes are calculated, which facilitate tasks of identifying stratigraphic and structural characteristics of the subsurface, represented indirectly by seismic data. Moreover, a seismic inversion method is used to estimate the acoustic impedance, an auxiliary variable derived from seismic data calibrated by well logs. The seismic attributes along with the acoustic impedance will be used to estimate geological properties. This workflow was tested on a real reservoir, thus presenting geological complexity. Through GP, the relationship between seismic derived data and the field porosity was represented satisfactorily, demonstrating that GP is a viable alternative for geologic reservoir characterization. Afterwards, the reservoir was divided in clusters according to geophysical properties, this allowed the construction of GP based estimators for each zone.

Evolutionary algorithms are one category of optimization techniques that are inspired by processes of biological evolution. Evolutionary computation is applied to many domains and one of the most important is data mining. Data mining is a relatively broad field that deals with the automatic knowledge discovery from databases and it is one of the most developed fields in the area of artificial intelligence. Classification is a data mining method that assigns items in a collection to target classes with the goal to accurately predict the target class for each item in the data. Genetic programming (GP) is one of the effective evolutionary computation techniques to solve classification problems. GP solves classification problems as an optimization tasks, where it searches for the best solution with highest accuracy. However, GP suffers from some weaknesses such as long execution time, and the need to tune many parameters for each problem. Furthermore, GP can not obtain high accuracy for multiclass classification problems as opposed to binary problems. In this dissertation, we address these drawbacks and propose some approaches in order to overcome them. Adaptive GP variants are proposed in order to automatically adapt the parameter settings and shorten the execution time. Moreover, two approaches are proposed to improve the accuracy of GP when applied to multiclass classification problems. In addition, a Segment-based approach is proposed to accelerate the GP execution time for the data classification problem. Furthermore, a parallelization of the GP process using the MapReduce methodology was proposed which aims to shorten the GP execution time and to provide the ability to use large population sizes leading to a faster convergence. The proposed approaches are evaluated using different measures, such as accuracy, execution time, sensitivity, specificity, and statistical tests. Comparisons between the proposed approaches with the standard GP, and with other classification techniques were performed, and the results showed that these approaches overcome the drawbacks of standard GP by successfully improving the accuracy and execution time.

Genetic Programming (GP) is well known as a computationally intensive technique especially when considering regression or classification tasks with large datasets. Consequently, there has been considerable work conducted into improving the computational speed of GP. Recently, this has concentrated on exploiting highly parallel architectures in the form of Graphics Processing Units (GPUs). However, the reported speeds fall considerably short of the computational capabilities of these GPUs. This thesis investigates this issue, seeking to considerably improve the computational speed of GP. Indeed, this thesis will demonstrate that considerable improvements in the speed of GP can be achieved when fully exploiting a parallel Central Processing Unit (CPU) exceeding the performance of the latest GPU implementations. This is achieved by recognising that GP is as much a memory bound technique as a compute bound technique. By adopting a two dimensional stack approach, better exploitation of memory resources is achieved in addition to reducing interpreter overheads. This approach is applied to CPU and GPU implementations and compares favorably with compiled versions of GP. The second aspect of this thesis demonstrates that although considerable performance gains can be achieved using parallel hardware, the role of efficiency within GP should not be forgotten. Efficiency saving can boost the computational speed of parallel GP significantly. Two methods are considered, parsimony pressure measures and efficient tournament selection. The second efficiency technique enables a CPU implementation of GP to outperform a GPU implementation for classification type tasks even though the CPU has only a tenth of the computational power. Finally both CPU and GPU are combined for ultimate performance. Speedups of more than a thousand fold over a basic sequential version of GP are achieved and three fold over the best GPU implementation from the literature. Consequently, this speedup increases the usefulness of GP as a machine learning technique.

Genetic programming (GP) is a subset of evolutionary computation where candidate solutions are evaluated through execution or interpreted execution. The candidate solutions generated by GP are in the form of computer programs, which are evolved to achieve a stated objective. Darwinian evolutionary theory inspires the processes that make up GP which include crossover, mutation and selection. During a GP run, crossover, mutation and selection are performed iteratively until a program that satisfies the stated objectives is produced or a certain number of time steps have elapsed. The objectives of this thesis are to empirically analyse three different aspects of these evolved programs. These three aspects are diversity, efficient representation and the changing structure of programs during evolution. In addition to these analyses, novel algorithms are presented in order to test theories, improve the overall performance of GP and reduce program size. This thesis makes three contributions to the field of GP. Firstly, a detailed analysis is performed of the process of initialisation (generating random programs to start evolution) using four novel algorithms to empirically evaluate specific traits of starting populations of programs. It is shown how two factors simultaneously effect how strong the performance of starting population will be after a GP run. Secondly, semantically based operators are applied during evolution to encourage behavioural diversity and reduce the size of programs by removing inefficient segments of code during evolution. It is demonstrated how these specialist operators can be effective individually and when combined in a series of experiments. Finally, the role of the structure of programs is considered during evolution under different evolutionary parameters considering different problem domains. This analysis reveals some interesting effects of evolution on program structure as well as offering evidence to support the success of the specialist operators.

This thesis proposes several measures for a better understanding of the dynamic of the evolutionary process. In particular, measures to control bloat, overfitting and complexity of the solutions are defined. Moreover, several methods to improve the generalization ability of the solutions produced by the standard Genetic Programming (GP) algorithm are proposed. This thesis also focuses on the role of semantic in GP. In particular, a new GP algorithm that uses only semantic information is proposed. Finally, a study on the effect of multi objective optimization in GP is performed.