No description available.

This thesis is divided into two parts. The first part considers and develops some of the statistics used in genetic programming (GP) while the second uses those statistics to study and develop a form of incremental evolution and an early termination heuristic for GP. The first part looks in detail at success proportion, Koza's minimum computational effort, and a measure we rename "success effort". We describe and develop methods to produce confidence intervals for these measures as well as confidence intervals for the difference and ratio of these measures. The second part studies Jackson's fitness-based incremental evolution. If the number of fitness evaluations are considered (rather than the number of generations) then we find some potential benefit through reduction in the effort required to find a solution. We then automate the incremental evolution method and show a statistically significant improvement compared to GP with automatically defined functions (ADFs). The success effort measure is shown to have the critical advantage over Koza's measure as it has the ability to include a decreasing cost of failure. We capitalise on this advantage by demonstrating an early termination heuristic that again offers a statistically significant advantage.

This thesis principally addresses some problems in genetic programming (GP) and grammar-guided genetic programming (GGGP) arising from the lack of operators able to make small and bounded changes on both genotype and phenotype space. It proposes a new and flexible representation for genetic programming, using a state-of-the-art formalism from natural language processing, Tree Adjoining Grammars (TAGs). It demonstrates that the new TAG-based representation possesses two important properties: non-fixed arity and locality. The former facilitates the design of new operators, including some which are bio-inspired, and others able to make small and bounded changes. The latter ensures that bounded changes in genotype space are reflected in bounded changes in phenotype space. With these two properties, the thesis shows how some well-known difficulties in standard GP and GGGP tree-based representations can be solved in the new representation. These difficulties have been previously attributed to the treebased nature of the representations; since TAG representation is also tree-based, it has enabled a more precise delineation of the causes of the difficulties. Building on the new representation, a new grammar guided GP system known as TAG3P has been developed, and shown to be competitive with other GP and GGGP systems. A new schema theorem, explaining the behaviour of TAG3P on syntactically constrained domains, is derived. Finally, the thesis proposes a new method for understanding performance differences between GP representations requiring different ways to bound the search space, eliminating the effects of the bounds through multi-objective approaches.

Evolvable Hardware is a technique derived from evolutionary computation applied to a hardware design. The term evolutionary computation involves similar steps as involved in the human evolution. It has been given names in accordance with the electronic technology like, Genetic Algorithm (GA), Evolutionary Strategy (ES) and Genetic Programming (GP). In evolutionary computing, a configured bit is considered as a human chromosome for a genetic algorithm, which has to be downloaded into hardware. Early evolvable hardware experiments were conducted in simulation and the only elite chromosome was downloaded to the hardware, which was labelled as Extrinsic Hardware. With the invent of Field Programmable Gate Arrays (FPGAs) and Reconfigurable Processing Units (RPUs), it is now possible for the implementation solutions to be fast enough to evaluate a real hardware circuit within an evolutionary computation framework; this is called an Intrinsic Evolvable Hardware. This research has been taken in continuation with project 'Evolvable Hardware' done at Manukau Institute of Technology (MIT). The project was able to manually evolve two simple electronic circuits of NAND and NOR gates in simulation. In relation to the project done at MIT this research focuses on the following: To automate the simulation by using In Circuit Debugging Emulators (IDEs), and to develop a strategy of configuring hardware like an FPGA without the use of their company supplied in circuit debugging emulators, so that the evolution of an intrinsic evolvable hardware could be controlled, and is hardware independent. As mentioned, the research conducted here was able to develop an evolvable hardware friendly Generic Structure which could be used for the development of evolvable hardware. The structure developed was hardware independent and was able to run on various FPGA hardware’s for the purpose of intrinsic evolution. The structure developed used few configuration bits as compared to current evolvable hardware designs.

No description available.

When performing predictive data mining, the use of ensembles is claimed to virtually guarantee increased accuracy compared to the use of single models. Unfortunately, the problem of how to maximize ensemble accuracy is far from solved. In particular, the relationship between ensemble diversity and accuracy is not completely understood, making it hard to efficiently utilize diversity for ensemble creation. Furthermore, most high-accuracy predictive models are opaque, i.e. it is not possible for a human to follow and understand the logic behind a prediction. For some domains, this is unacceptable, since models need to be comprehensible. To obtain comprehensibility, accuracy is often sacrificed by using simpler but transparent models; a trade-off termed the accuracy vs. comprehensibility trade-off. With this trade-off in mind, several researchers have suggested rule extraction algorithms, where opaque models are transformed into comprehensible models, keeping an acceptable accuracy. In this thesis, two novel algorithms based on Genetic Programming are suggested. The first algorithm (GEMS) is used for ensemble creation, and the second (G-REX) is used for rule extraction from opaque models. The main property of GEMS is the ability to combine smaller ensembles and individual models in an almost arbitrary way. Moreover, GEMS can use base models of any kind and the optimization function is very flexible, easily permitting inclusion of, for instance, diversity measures. In the experimentation, GEMS obtained accuracies higher than both straightforward design choices and published results for Random Forests and AdaBoost. The key quality of G-REX is the inherent ability to explicitly control the accuracy vs. comprehensibility trade-off. Compared to the standard tree inducers C5.0 and CART, and some well-known rule extraction algorithms, rules extracted by G-REX are significantly more accurate and compact. Most importantly, G-REX is thoroughly evaluated and found to meet all relevant evaluation criteria for rule extraction algorithms, thus establishing G-REX as the algorithm to benchmark against.

The idea of automatic programming using the genetic programming paradigm is a concept that has been explored in the work of Koza and several works since. Most problems attempted using genetic programming are finite in size, meaning that the problem involved evolving a function that operates over a finite domain, or evolving a routine that will only run for a finite amount of time. For problems with a finite domain, the internal representation of each individual is typically a finite automaton that is unable to store an unbounded amount of data. This thesis will address the problem of applying genetic programming to problems that have a ``discrete unbounded domain", meaning the problem involves evolving a function that operates over an unbounded domain with discrete quantities. For problems with an discrete unbounded domain, the range of possible behaviors achievable by the evolved functions increases with more versatile internal memory schemes for each of the individuals. The specific problem that I will address in this thesis is the problem of evolving a real-time deciding program for a fixed language of strings. I will discuss two paradigms that I will use to attempt this problem. Each of the paradigms will allow each individual to store an unbounded amount of data, using an internal memory scheme with at least the capabilities of a Turing tape. As each character of an input string is being processed in real time, the individual will be able to imitate a single step of a Turing machine. While the real-time restriction will certainly limit the languages for which a decider may be evolved, the fact that the evolved deciding programs run in real-time yields possible applications for these paradigms in the discovery of new algorithms. The first paradigm that I will explore will take a naive approach that will ultimately prove to be unsuccessful. The second paradigm that I will explore will take a more careful approach that will have a much greater success, and will provide insight into the design of genetic programming paradigms for problems over a discrete unbounded domain.

Large-scale mining practices have disturbed many natural watersheds in northern Alberta, Canada. To restore disturbed landscapes and ecosystems functions, reconstruction strategies have been adopted with the aim of establishing sustainable reclaimed lands. The success of the reconstruction process depends on the design of reconstruction strategies, which can be optimized by improving the understanding of the controlling hydrological processes in the reconstructed watersheds. Evapotranspiration is one of the important components of the hydrological cycle; its estimation and analysis are crucial for better assessment of the reconstructed landscape hydrology, and for more efficient design. The complexity of the evapotranspiration process and its variability in time and space has imposed some limitations on previously developed evapotranspiration estimation models. The vast majority of the available models estimate the rate of potential evapotranspiration, which occurs under unlimited water supply condition. However, the rate of actual evapotranspiration (AET) depends on the available soil moisture, which makes its physical modeling more complicated than the potential evapotranspiration. The main objective of this study is to estimate and analyze the AET process in a reconstructed landscape.<p> Data driven techniques can model the process without having a complete understanding of its physics. In this study, three data driven models; genetic programming (GP), artificial neural networks (ANNs), and multilinear regression (MLR), were developed and compared for estimating the hourly eddy covariance (EC)-measured AET using meteorological variables. The AET was modeled as a function of five meteorological variables: net radiation (Rn), ground temperature (Tg), air temperature (Ta), relative humidity (RH), and wind speed (Ws) in a reconstructed landscape located in northern Alberta, Canada. Several ANN models were evaluated using two training algorithms of Levenberg-Marquardt and Bayesian regularization. The GP technique was employed to generate mathematical equations correlating AET to the five meteorological variables. Furthermore, the available data were statistically analyzed to obtain MLR models and to identify the meteorological variables that have significant effect on the evapotranspiration process. The utility of the investigated data driven models was also compared with that of HYDRUS-1D model, which is a physically based model that makes use of conventional Penman-Monteith (PM) method for the prediction of AET. HYDRUS-1D model was examined for estimating AET using meteorological variables, leaf area index, and soil moisture information. Furthermore, Wavelet analysis (WA), as a multiresolution signal processing tool, was examined to improve the understanding of the available time series temporal variations, through identifying the significant cyclic features, and to explore the possible correlation between AET and the meteorological signals. WA was used with the purpose of input determination of AET models, a priori.<p> The results of this study indicated that all three proposed data driven models were able to approximate the AET reasonably well; however, GP and MLR models had better generalization ability than the ANN model. GP models demonstrated that the complex process of hourly AET can be efficiently modeled as simple semi-linear functions of few meteorological variables. The results of HYDRUS-1D model exhibited that a physically based model, such as HYDRUS-1D, might perform on par or even inferior to the data driven models in terms of the overall prediction accuracy. The developed equation-based models; GP and MLR, revealed the larger contribution of net radiation and ground temperature, compared to other variables, to the estimation of AET. It was also found that the interaction effects of meteorological variables are important for the AET modeling. The results of wavelet analysis demonstrated the presence of both small-scale (2 to 8 hours) and larger-scale (e.g. diurnal) cyclic features in most of the investigated time series. Larger-scale cyclic features were found to be the dominant source of temporal variations in the AET and most of the meteorological variables. The results of cross wavelet analysis indicated that the cause and effect relationship between AET and the meteorological variables might vary based on the time-scale of variation under consideration. At small time-scales, significant linear correlations were observed between AET and Rn, RH, and Ws time series, while at larger time-scales significant linear correlations were observed between AET and Rn, RH, Tg, and Ta time series.

No description available.

No description available.