Thesis (Ph.D.) - Carleton University, 2007. / Includes bibliographical references (p. 261-266). Also available in electronic format on the Internet.

Thesis (M.S.)--Worcester Polytechnic Institute. / Title from title screen. Keywords: genetic programming; approximations; machine learning; artificial intelligence. Includes bibliographical references (p. 92-94).

Automatic text classification using current approaches is known to perform poorly when documents are noisy or when limited amounts of textual content is available. Yet, many users need access to such documents, which are found in large numbers in digital libraries and in the WWW. If documents are not classified, they are difficult to find when browsing. Further, searching precision suffers when categories cannot be checked, since many documents may be retrieved that would fail to meet category constraints. In this work, we study how different types of evidence from multiple sources can be intelligently fused to improve classification of text documents into predefined categories. We present a classification framework based on an inductive learning method -- Genetic Programming (GP) -- to fuse evidence from multiple sources. We show that good classification is possible with documents which are noisy or which have small amounts of text (e.g., short metadata records) -- if multiple sources of evidence are fused in an intelligent way. The framework is validated through experiments performed on documents in two testbeds. One is the ACM Digital Library (using a subset available in connection with CITIDEL, part of NSF's National Science Digital Library). The other is Web data, in particular that portion associated with the Cadê Web directory. Our studies have shown that improvement can be achieved relative to other machine learning approaches if genetic programming methods are combined with classifiers such as kNN. Extensive analysis was performed to study the results generated through the GP-based fusion approach and to understand key factors that promote good classification. / Ph. D.

Process Algebras are a Formal Modelling methodology which are an effective tool for defining models of complex systems, particularly those involving multiple interacting processes. However, describing such a model using Process Algebras requires expertise from both the modeller and the domain expert. Finding the correct model to describe a system can be difficult. Further more, even with the correct model, parameter tuning to allow model outputs to match experimental data can also be both difficult and time consuming. Evolutionary Algorithms provide effective methods for finding solutions to optimisation problems with large and noisy search spaces. Evolutionary Algorithms have been proven to be well suited to investigating parameter fitting problems in order to match known data or desired behaviour. It is proposed that Process Algebras and Evolutionary Algorithms have complementary strengths for developing models of complex systems. Evolutionary Algorithms require a precise and accurate fitness function to score and rank solutions. Process Algebras can be incorporated into the fitness function to provide this mathematical score. Presented in this work is the Evolving Process Algebra (EPA) framework, designed for the application of Evolutionary Algorithms (specifically Genetic Algorithms and Genetic Programming optimisation techniques) to models described in Process Algebra (specifically PEPA and Bio-PEPA) with the aim of evolving fitter models. The EPA framework is demonstrated using multiple complex systems. For PEPA this includes the dining philosophers resource allocation problem, the repressilator genetic circuit, the G-protein cellular signal regulators and two epidemiological problems: HIV and the measles virus. For Bio-PEPA the problems include a biochemical reactant-product system, a generic genetic network, a variant of the G-protein system and three epidemiological problems derived from the measles virus. Also presented is the EPA Utility Assistant program; a lightweight graphical user interface. This is designed to open the full functionality and parallelisation of the EPA framework to beginner or naive users. In addition, the assistant program aids in collating and graphing after experiments are completed.

Dans le cadre de cette thèse, nous nous intéresseons à l'amélioration des techniques de programmation génétique (PG), en particulier nous avons essayer d'améliorer la performance de la PG en cas d'utilisation de grammaire riche, où l'ensemble de terminaux contient plus que nécessaire pour représenter des solutions optimales. Pour cela, nous avons présenté le problème de la sélection d'attributs en rappelant les principales approches, et nous avons utilisé la technique de mesure de poids des terminaux pour affiner la sélection d'attributs. En second lieu, nous présentons des travaux sur un autre algorithme qui s'inspire de la boucle évolutionnaire : l'évolution différentielle (ED), et nous étudions la performance de cette technique sur la branche de la programmation génétique linéaire. Nous présentons et comparons les performances de cette dernière technique sur un ensemble de "benchmarks" classique de la PG. / This thesis mainly deals with genetic programming. In this work, we are interested in improving the overall performance of genetic programming (GP) when dealing with rich grammar when the terminal set is very large. We introduce the problem of attributes selection and in our work we introduce a scheme based on the weight (based on the frequency) to refine the attribute selection. In the second part of this work, we try to improve the evolution engine with the help of the differential evolution (DE) algorithm. This new engine is applied to linear genetic programming. We then present some experiments and make some comparisons on a set of classical benchmarks.

This thesis describes the use of genetic programming to automate the discovery of numerical approximation formulae. Results are presented involving rediscovery of known approximations for Harmonic numbers and discovery of rational polynomial approximations for functions of one or more variables, the latter of which are compared to Padé approximations obtained through a symbolic mathematics package. For functions of a single variable, it is shown that evolved solutions can be considered superior to Padé approximations, which represent a powerful technique from numerical analysis, given certain tradeoffs between approximation cost and accuracy, while for functions of more than one variable, we are able to evolve rational polynomial approximations where no Padé approximation can be computed. Furthermore, it is shown that evolved approximations can be iteratively improved through the evolution of approximations to their error function. Based on these results, we consider genetic programming to be a powerful and effective technique for the automated discovery of numerical approximation formulae.

During the last years cartesian genetic programming proved to be a very perspective area of the evolutionary computing. However it has its limitations, which make its use in area of large and generic problems impossible. These limitations can be eliminated using the recent method allowing self-modification of programs in cartesian genetic programming. The purpose of this thesis is to review the development in this area done so far. Next objective is to design own solutions for solving various problems that are hardly solvable using the ordinary cartesian genetic programming. One of the problems to be considered is generating the terms of various Taylor series. Due to the fact that the solution to this problem requires generalisation, the goal is to prove that the self-modifying cartesian genetic programming scores better than classic one for this problem. Another discussed problem is using the self-modifying genetic programming for developing arbitrarily large sorting networks. In this case, the objective is to prove that self-modification brings new features to the cartesian genetic programming allowing the development of arbitrarily sized designs.

The school timetabling problem is a common optimization problem faced by many primary and secondary schools. Each school has its own set of requirements and constraints that are dependent on various factors such as the number of resources available and rules specified by the department of education for that country. There are two objectives in this study. In previous studies, genetic algorithms have only been used to solve a single type of school timetabling problem. The first objective of this study is to test the effectiveness of a genetic algorithm approach in solving more than one type of school timetabling problem. The second objective is to evaluate a genetic algorithm that uses an indirect representation (IGA) when solving the school timetabling problem. This IGA approach is then compared to the performance of a genetic algorithm that uses a direct representation (DGA). This approach has been covered in other domains such as job shop scheduling but has not been covered for the school timetabling problem. Both the DGA and IGA were tested on five school timetabling problems. Both the algorithms were initially developed based on findings in the literature. They were then improved iteratively based on their performance when tested on the problems. The processes of the genetic algorithms that were improved were the method of initial population creation, the selection methods and the genetic operators used. Both the DGA and the IGA were found to produce timetables that were competitive and in some cases superior to that of other methods such as simulated annealing and tabu search. It was found that different processes (i.e. the method of initial population creation, selection methods and genetic operators) were needed for each problem in order to produce the best results. When comparing the performance of the two approaches, the IGA outperformed the DGA for all of the tested school timetabling problems. / Thesis (M.Sc.)-University of KwaZulu-Natal, Pietermaritzburg, 2013.

No description available.

Many complex systems in nature are governed by simple local interactions, although a number are also described by global interactions. For example, within the field of hydraulics the Navier-Stokes equations describe free-surface water flow, through means of the global preservation of water volume, momentum and energy. However, solving such partial differential equations (PDEs) is computationally expensive when applied to large 2D flow problems. An alternative which reduces the computational complexity, is to use a local derivative to approximate the PDEs, such as finite difference methods, or Cellular Automata (CA). The high speed processing of such simulations is important to modern scientific investigation especially within urban flood modelling, as urban expansion continues to increase the number of impervious areas that need to be modelled. Large numbers of model runs or large spatial or temporal resolution simulations are required in order to investigate, for example, climate change, early warning systems, and sewer design optimisation. The recent introduction of the Graphics Processor Unit (GPU) as a general purpose computing device (General Purpose Graphical Processor Unit, GPGPU) allows this hardware to be used for the accelerated processing of such locally driven simulations. A novel CA transformation for use with GPUs is proposed here to make maximum use of the GPU hardware. CA models are defined by the local state transition rules, which are used in every cell in parallel, and provide an excellent platform for a comparative study of possible alternative state transition rules. Writing local state transition rules for CA systems is a difficult task for humans due to the number and complexity of possible interactions, and is known as the ‘inverse problem’ for CA. Therefore, the use of Genetic Programming (GP) algorithms for the automatic development of state transition rules from example data is also investigated in this thesis. GP is investigated as it is capable of searching the intractably large areas of possible state transition rules, and producing near optimal solutions. However, such population-based optimisation algorithms are limited by the cost of many repeated evaluations of the fitness function, which in this case requires the comparison of a CA simulation to given target data. Therefore, the use of GPGPU hardware for the accelerated learning of local rules is also developed. Speed-up factors of up to 50 times over serial Central Processing Unit (CPU) processing are achieved on simple CA, up to 5-10 times speedup over the fully parallel CPU for the learning of urban flood modelling rules. Furthermore, it is shown GP can generate rules which perform competitively when compared with human formulated rules. This is achieved with generalisation to unseen terrains using similar input conditions and different spatial/temporal resolutions in this important application domain.