Search

The work presented herein focuses on the design of distributed autonomous controllers for collective behaviour of Micro-unmanned Aerial Vehicles (MAVs). Two alternative approaches to this topic are introduced: one based upon the Evolutionary Robotics (ER) paradigm, the other one upon flocking principles. Three computer simulators have been developed in order to carry out the required experiments, all of them having their focus on the modelling of fixed-wing aircraft flight dynamics. The employment of fixed-wing aircraft rather than the omni-directional robots typically employed in collective robotics significantly increases the complexity of the challenges that an autonomous controller has to face. This is mostly due to the strict motion constraints associated with fixed-wing platforms, that require a high degree of accuracy by the controller. Concerning the ER approach, the experimental setups elaborated have resulted in controllers that have been evolved in simulation with the following capabilities: (1) navigation across unknown environments, (2) obstacle avoidance, (3) tracking of a moving target, and (4) execution of cooperative and coordinated behaviours based on implicit communication strategies. The design methodology based upon flocking principles has involved tests on computer simulations and subsequent experimentation on real-world robotic platforms. A customised implementation of Reynolds’ flocking algorithm has been developed and successfully validated through flight tests performed with the swinglet MAV. It has been notably demonstrated how the Evolutionary Robotics approach could be successfully extended to the domain of fixed-wing aerial robotics, which has never received a great deal of attention in the past. The investigations performed have also shown that complex and real physics-based computer simulators are not a compulsory requirement when approaching the domain of aerial robotics, as long as proper autopilot systems (taking care of the ”reality gap” issue) are used on the real robots.

Fuzzy association rule mining discovers patterns in transactions, such as shopping baskets in a supermarket, or Web page accesses by a visitor to a Web site. Temporal patterns can be present in fuzzy association rules because the underlying process generating the data can be dynamic. However, existing solutions may not discover all interesting patterns because of a previously unrecognised problem that is revealed in this thesis. The contextual meaning of fuzzy association rules changes because of the dynamic feature of data. The static fuzzy representation and traditional search method are inadequate. The Genetic Iterative Temporal Fuzzy Association Rule Mining (GITFARM) framework solves the problem by utilising flexible fuzzy representations from a fuzzy rule-based system (FRBS). The combination of temporal, fuzzy and itemset space was simultaneously searched with a genetic algorithm (GA) to overcome the problem. The framework transforms the dataset to a graph for efficiently searching the dataset. A choice of model in fuzzy representation provides a trade-off in usage between an approximate and descriptive model. A method for verifying the solution to the hypothesised problem was presented. The proposed GA-based solution was compared with a traditional approach that uses an exhaustive search method. It was shown how the GA-based solution discovered rules that the traditional approach did not. This shows that simultaneously searching for rules and membership functions with a GA is a suitable solution for mining temporal fuzzy association rules. So, in practice, more knowledge can be discovered for making well-informed decisions that would otherwise be lost with a traditional approach.

The renewal of derelict inner-city urban districts suffering from high levels of socio-economic deprivation and sustainability problems is one of the key research areas in urban planning and regeneration. Subject to a wide range of social, economical and environmental factors, decision support for an optimal allocation of residential and service lots within such districts is regarded as a complex task. Pre-assessment of various neighbourhood factors before the commencement of actual location allocation of various public services is considered paramount to the sutainable outcome of regeneration projects. Spatial assessment in such derelict built-up areas requires planning of lot assignment for residential buildings in a way to maximize accessibility to public services while minimizing the deprivation of built neighbourhood areas. However, the prediction of socio-economic deprivation impact on the regeneration districts in order to optimize the location-allocation of public service infrastructure is a complex task. This is generally due to the highly conflicting nature of various service structures with various socio-economic and environmental factors. In regards to the problem given above, this thesis presents the development of an evolutionary AI-based decision support systemto assist planners with the assessment and optimization of regeneration districts. The work develops an Adaptive Network Based Fuzzy Inference System (ANFIS) based module to assess neighbourhood districts for various deprivation factors. Additionally an evolutionary genetic algorithms based solution is implemented to optimize various urban regeneration layouts based upon the prior deprivation assessment model. The two-tiered framework initially assesses socio-cultural deprivation levels of employment, health, crime and transport accessibility in neighbourhood areas and produces a deprivation impact matrix overthe regeneration layout lots based upon a trained, network-based fuzzy inference system. Based upon this impact matrix a genetic algorithm is developed to optimize the placement of various public services (shopping malls, primary schools, GPs and post offices) in a way that maximize the accessibility of all services to regenerated residential units as well as contribute to minimize the measure of deprivation of surrounding neighbourhood areas. The outcome of this research is evaluated over two real-world case studies presenting highly coherent results. The work ultimately produces a smart urban regeneration toolkit which provides designer and planner decision support in the form of a simulation toolkit.

Although traditionally Wireless Sensor Network (WSNs) have been regarded as static sensor arrays used mainly for environmental monitoring, recently, its applications have undergone a paradigm shift from static to more dynamic environments, where nodes are attached to moving objects, people or animals. Applications that use WSNs in motion are broad, ranging from transport and logistics to animal monitoring, health care and military. These application domains have a number of characteristics that challenge the algorithmic design of WSNs. Firstly, mobility has a negative effect on the quality of the wireless communication and the performance of networking protocols. Nevertheless, it has been shown that mobility can enhance the functionality of the network by exploiting the movement patterns of mobile objects. Secondly, the heterogeneity of devices in a WSN has to be taken into account for increasing the network performance and lifetime. Thirdly, the WSN services should ideally assist the user in an unobtrusive and transparent way. Fourthly, energy-efficiency and scalability are of primary importance to prevent the network performance degradation. This thesis contributes toward the design of a new hybrid optimization algorithm; ENAMS (Energy optimizatioN Algorithm for Mobile Sensor networks) which is based on the Evolutionary Computation and Swarm Intelligence to increase the life time of mobile wireless sensor networks. The presented algorithm is suitable for large scale mobile sensor networks and provides a robust and energy- efficient communication mechanism by dividing the sensor-nodes into clusters, where the number of clusters is not predefined and the sensors within each cluster are not necessary to be distributed in the same density. The presented algorithm enables the sensor nodes to move as swarms within the search space while keeping optimum distances between the sensors. To verify the objectives of the proposed algorithm, the LEGO-NXT MIND-STORMS robots are used to act as particles in a moving swarm keeping the optimum distances while tracking each other within the permitted distance range in the search space.

This thesis describes the investigations undertaken to produce a novel hybrid optimisation technique that combines both global and local searching to produce good solutions quickly. Many evolutionary computation and experimental design methods are considered before genetic algorithms and evolutionary operation are combined to produce novel optimisation algorithms. A novel piece of software is created to run two and three factor evolutionary operation experiments. A range of new hybrid small population genetic algorithms are created that contain evolutionary operation in all generations (static hybrids) or contain evolutionary operation in a controlled number of generations (dynamic hybrids). A large number of empirical tests are carried out to determine the influence of operators and the performance of the hybrids over a range of standard test functions. For very small populations, twenty or less individuals, stochastic universal sampling is demonstrated to be the most suitable method of selection. The performance of very small population evolutionary operation hybrid genetic algorithms is shown to improve with larger generation gaps on simple functions and on more complex functions increasing the generation gap does not deteriorate performance. As a result of the testing carried out for this study a generation gap of 0.7 is recommended as a starting point for empirical searches using small population genetic algorithms and their hybrids. Due to the changing presence of evolutionary operation, the generation gap has less influence on dynamic hybrids compared to the static hybrids. The evolutionary operation, local search element is shown to positively influence the performance of the small population genetic algorithm search. The evolutionary operation element in the hybrid genetic algorithm gives the greatest improvement in performance when present in the middle generations or with a progressively greater presence. A recommendation for the information required to be reported for benchmarking genetic algorithm performance is also presented. This includes processor, platform, software information as well as genetic algorithm parameters such as population size, number of generations, crossover method and selection operators and results of testing on a set of standard test functions.

As the complexity of neural network models has grown, it has become increasingly important to optimize their design automatically through metalearning. Methods for discovering hyperparameters, topologies, and learning rate schedules have lead to significant increases in performance. This dissertation tackles a new type of metalearning: loss-function optimization. Loss functions define a model's core training objective and thus present a clear opportunity. Two techniques, GLO and TaylorGLO, were developed to tackle this metalearning problem using genetic programming and evolutionary strategies. Experiments show that neural networks trained with metalearned loss functions are more accurate, have higher data utilization, train faster, and are more robust against adversarial attacks. A theoretical framework was developed to analyze how and why different loss functions bias training towards different regions of the parameter space. Using this framework, their performance gains are found to result from a regularizing effect that is tailored to each domain. Overall, this dissertation demonstrates that new, metalearned loss functions can result in better trained models, and provides the next stepping stone towards fully automated machine learning.

In this dissertation we ask, formulate an apparatus for answering, and answer the following three questions: Where do Genetic Algorithms fit in the greater scheme of pattern recognition? Given primitive mechanics, can Genetic Algorithms match or exceed the performance of theoretically-based methods? Can we build a generic universal Genetic Algorithm for classification? To answer these questions, we develop a genetic algorithm which optimizes MATLAB classifiers and a variable length genetic algorithm which does classification based entirely on boolean logic. We test these algorithms on disparate datasets rooted in cellular biology, music theory, and medicine. We then get results from these and compare their confusion matrices. For those unfamiliar with Genetic Algorithms, we include a primer on the subject in chapter 1, and include a literature review and our motivations. In Chapter 2, we discuss the development of the algorithms necessary as well as explore other features necessitated by their existence. In Chapter 3, we share and discuss our results and conclusions. Finally, in Chapter 4, we discuss future directions for the corpus we have developed.

Many approaches to applying Genetic Algorithms (GAs) to Nondeterministic Polynomial time Complete (NPC) problems involve population members encoded directly from the problem solution space. While this technique enables trivial mapping of the population members to solutions, it can cause complex problems for GA operators as they attempt to direct the evolution of the population toward more promising areas of the solution space. These operators, using inspiration from genetics and evolution in the biological world, combine and manipulate the current population to produce a new population that, it is hoped, will eventually converge toward better solutions to the original problem. However, many problems, especially graph-space problems, cannot be so easily manipulated when GA members consist of direct encodings. In such cases, GA operators must perform awkward transformations to convert the progeny into viable solutions. Here is where heuristic encoding comes into play, in that any combination of genes will produce a viable solution. However, this additional level of abstraction does cause other problems and tends to weaken the guiding effects of traditional GA operators. Thus, I have designed custom GA operators that mitigate these problems by using the solutions produced by the heuristic encoded members to better guide the manipulation when producing the next generation. This dissertation shows that heuristic encoding is an effective technique for the representation of solutions to graph-space problems. It also shows that, when using heuristic encoding, GAs with traditional operators perform well compared to more direct encoding techniques. Finally it shows the combination of heuristic encoding and GA operators designed to work with them increases GA performance and can be competitive with other techniques. I believe that these techniques will also work well for other types of problems for which GAs are commonly applied.

An agent may interact with its environment and learn complex tasks based on evaluative feedback through a process known as reinforcement learning. Reinforcement learning requires exploration of unfamiliar situations, which necessarily involves unknown and potentially dangerous or costly outcomes. Supervising agents in these situations can be seen as a type of nurturing and requires an investment of time usually by humans. Nurturing, one individual investing in the development of another individual with which it has an ongoing relationship, is widely seen in the biological world, often with parents nurturing their o spring. There are many types of nurturing, including helping an individual to carry out a task by doing part of the task for it. In arti cial intelligence, nurturing can be seen as an opportunity to develop both better machine learning algorithms and robots that assist or supervise other robots. Although the area of nurturing robotics is at a very early stage, the hope is that this approach can result in more sophisticated learning systems. This dissertation demonstrates the e ectiveness of nurturing through experiments involving the evolution of the parameters of a reinforcement learning algorithm that is capable of nding good policies in a changing environment in which the agent must learn an episodic task in which there is discrete input with perceptual aliasing, continuous output, and delayed reward. The results show that nurturing is capable of promoting the evolution of learning in such environments.

The primary goal of artificial intelligence research is to develop a machine capable of learning to solve disparate real-world tasks autonomously, without relying on specialized problem-specific inputs. This dissertation suggests that such machines are realistic: If No Free Lunch theorems were to apply to all real-world problems, then the world would be utterly unpredictable. In response, the dissertation proposes the information-maximization principle, which claims that the optimal optimization methods make the best use of the information available to them. This principle results in a new algorithm, evolutionary annealing, which is shown to perform well especially in challenging problems with irregular structure.

The one-dimensional bin-packing problem (BPP) is a well known problem in the realm of operations research. In the BPP, objects with pre-defined "weights" are packed into bins, each having a maximum weight capacity. The goal is to minimize the number of bins needed to hold objects. In a Genetic Algorithm for this problem, an individual candidate solution consists of a permutation of object~ representing their order of placement. A heuristic is then used to place objects in bins according to their specified order. The heuristic chosen is generally First Fit, Best Fit, or Worst Fit. The number of bins needed to store the objects is a solution's fitness. In Genetic Algorithms, the fitness value of a solution represents its likelihood to pass on its genetic material to new generations. In the case of the BPP, the less the number of bins needed, the greater a solution's fitness. To create new generations, solutions are "crossed-over" to combine features of their particular solutions and create a new organism. New generations are then created in a cycle until a predetermined limit has been reached and the best organism found becomes the solution to the problem. Many situations arise where two solutions may have the exact same fitness value according to the number of bins. However, these two solutions may not be equivalent in terms of solving the BPP. Solutions which pack objects more tightly in bins are more desirable because they have more potential to be improved in future generations. To distinguish these solutions, we propose a second fitness criterion: the free space in the final bin of a solution. By adding this secondary fitness criterion, the performance of the standard GA algorithm for the BPP can be improved by a significant margin. This has implications for any implementation of bin-packing GAs, as the modification is relatively minor and produces better results; therefore being a cost-effective improvement.

Artificial neural networks (ANNs) are an abstraction of the low-level architecture of biological brains that are often applied in general problem solving and function approximation. Neuroevolution (NE), i.e. the evolution of ANNs, has proven effective at solving problems in a variety of domains. Information from the domain is input to the ANN, which outputs its desired actions. This dissertation presents a new NE algorithm called Hypercube-based NeuroEvolution of Augmenting Topologies (HyperNEAT), based on a novel indirect encoding of ANNs. The key insight in HyperNEAT is to make the algorithm aware of the geometry in which the ANNs are embedded and thereby exploit such domain geometry to evolve ANNs more effectively. The dissertation focuses on applying HyperNEAT to tactical and strategic decision domains. These domains involve simultaneously considering short-term tactics while also balancing long-term strategies. Board games such as checkers and Go are canonical examples of such domains; however, they also include real-time strategy games and military scenarios. The dissertation details three proposed extensions to HyperNEAT designed to work in tactical and strategic decision domains. The first is an action selector ANN architecture that allows the ANN to indicate its judgements on every possible action all at once. The second technique is called substrate extrapolation. It allows learning basic concepts at a low resolution, and then increasing the resolution to learn more advanced concepts. The iii final extension is geometric game-tree pruning, whereby HyperNEAT can endow the ANN the ability to focus on specific areas of a domain (such as a checkers board) that deserve more inspection. The culminating contribution is to demonstrate the ability of HyperNEAT with these extensions to play Go, a most challenging game for artificial intelligence, by combining HyperNEAT with UCT

Lossy image compression algorithms sacrifice perfect imagereconstruction in favor of decreased storage requirements. Modernlossy compression schemes, such as JPEG2000, rely upon the discretewavelet transform (DWT) to achieve high levels of compression whileminimizing the loss of information for image reconstruction. Somecompression applications require higher levels of compression thanthose achieved through application of the DWT and entropy coding. Insuch lossy systems, quantization provides high compression rates atthe cost of increased distortion. Unfortunately, as the amount ofquantization increases, the performance of the DWT for accurateimage reconstruction deteriorates. Previous research demonstratesthat a genetic algorithm can improve image reconstruction in thepresence of quantization error by replacing the wavelet filtercoefficients with a set of evolved coefficients.This dissertation develops a methodology for the evolution ofdigital filters capable of outperforming the DWT for imagereconstruction at a given compression rate in the presence ofquantization error. This dissertation compares potential fitnessmeasures for evaluating reconstruction error. Experiments comparethe usefulness of local versus standard population initializationand mutation operators. In order to perform an efficient yetthorough traversal of the search space, several recombinationoperators developed specifically for real-valued evolution areevaluated. Additionally, this dissertation presents and develops anovel technique to emphasize the reconstruction of the high-spacialfrequency areas of an image through use of edge detection algorithmsand focused evolution. An analysis of the ease of traversal throughthe fitness landscapes defined by various image quality measuressupports the development of a framework for evolving robust imagetransform filters.Particular emphasis is placed upon the development of transformsthat provide consistently accurate reconstruction of quantizedsatellite and aerial reconnaissance images. The development oftransforms that preserve the intelligence that can be gained fromhighly compressed images transmitted over a limited bandwidth is ofdefense and security interest. This dissertation assembles a database ofpublicly available satellite images collected for a wide range ofsubjects, including aircraft and airfields, naval bases, army bases,cities, and factories. Experiments employing these images aregeared toward the development of filters appropriate for civilianand military aerial reconnaissance applications requiring limitedbandwidth for image transmission. Because the evolution employs theDWT algorithm, the resulting filters are easy to implement inhardware appropriate for digital signal processing applications.

This thesis shows how to incorporate Unified Modeling Language sequence diagrams into genetic algorithm-based automated test case generators to increase the code coverage of their resulting test cases. Automated generation of test data through evolutionary testing was proven feasible in prior research studies. In those previous investigations, the metrics used for determining the test generation method effectiveness were the percentages of testing statement and branch code coverage achieved. However, the code coverage realized in those preceding studies often converged at suboptimal percentages due to a lack of guidance in conditional statements. This study compares the coverage percentages of 16 different Java programs when test cases are automatically generated with and without incorporating associated UML sequence diagrams. It introduces a tool known as the Evolutionary Test Case Generator, or ETCG, an automatic test case generator based on genetic algorithms that provides the ability to incorporate sequence diagrams to direct the heuristic search process and facilitate evolutionary testing. When the generator uses sequence diagrams, the resulting test cases showed an average improvement of 21% in branch coverage and 8% in statement coverage over test cases produced without using sequence diagrams.

We are continuously challenged by ever increasing problem complexity and the need to develop algorithms that can solve complex problems and solve them within a reasonable amount of time. Modularity is thought to reduce problem complexity by decomposing large problems into smaller and less complex subproblems. In practice, introducing modularity into evolutionary algorithm representations appears to improve search performance; however, how and why modularity improves performance is not well understood. In this thesis, we seek to better understand the effects of modularity on search. In particular, what are the effects of module creation on the search space structure and how do these structural changes affect performance? We define a theoretical and empirical framework to study modularity in evolutionary algorithms. Using this framework, we provide evidence of the following. First, not all types of modularity have an effect on search. We can have highly modular spaces that in essence are equivalent to simpler non-modular spaces. This is the case, because these spaces achieve higher degree of modularity without changing the fundamental structure of the search space. Second, for the cases when modularity actually has an effect on the fundamental structure of the search space, if left without guidance, it would only crowd and complicate the space structure resulting in a harder space for most search algorithms. Finally, we have the case when modularity not only has an effect in the search space structure, but most importantly, module creation can be guided by problem domain knowledge. When this knowledge can be used to estimate the value of a module in terms of its contribution toward building the solution, then modularity is extremely effective. It is in this last case that creating high value modules or low value modules has a direct and decisive impact on performance. The results presented in this thesis help to better understand, in a principled way, the effects of modularity on search. Better understanding the effects of modularity on search is a step forward in the larger issue of evolutionary search applied to increasingly complex problems.

In this thesis a general mathematical framework to describe evolutionary algorithms is developed. The following two applications of the framework are presented in detail: (1) This framework allows us to use category theory to compare various evolutionary algorithms via their representation. In fact, we shall introduce a certain category, the morphisms of which are intuitively thought of as re-encoding functions. It turns out that these morphisms are related to the family of the so-called recombination-invariant subsets in a similar way as continuous maps are related to the family of open sets and measurable functions are related to the sigma-algebra of measurable sets. This allows us to classify all possible re-encodings of a given evolutionary search algorithm in terms of a classical genetic algorithm. (2) The classical theorem of Geiringer from theoretical biology can be generalized to a great extent in this new framework. Moreover, the proof of the generalized version depends on a classical fact about random walks associated to group actions and allows one to use the elegant techniques developed by Diaconis and his colleagues to estimate the rate of convergence towards the uniform stationary distribution for many evolutionary algorithms including various kinds of genetic programming techniques. The notion of a Geiringer algorithm (the type of algorithm to which the generalized Geiringer theorem applies) also has some ties to the representation (the topic of the first part).

As the complexity of our society and computational resources increases, so does the complexity of the problems that we approach using evolutionary search techniques. There are recent approaches to deal with the problem of scaling evolutionary methods to cope with highly complex difficult problems. Many of these approaches are biologically inspired and share an underlying principle: a problem representation based on basic representational building blocks that interact and self-organize into complex functions or designs. The observation from the central dogma of molecular biology that proteins are the basic building blocks of life and the recent advances in proteomics on analysis of structure, function and interaction of entire protein complements, lead us to propose a unifying framework of thought for these approaches: the proteomics approach. This thesis propose to investigate whether the self-organization of protein analogous structures at the representation level can increase the degree of complexity and ``novelty'' of solutions obtainable using evolutionary search techniques. In order to do so, we identify two fundamental aspects of this transition: (1) proteins interact in a three dimensional medium analogous to a multiset; and (2) proteins are functional structures. The first aspect is foundational for understanding of the second. This thesis analyzes the first aspect. It investigates the effects of using a genome to proteome mapping on evolutionary computation. This analysis is based on a genetic algorithm (GA) with a string to multiset mapping that we call the proportional genetic algorithm (PGA), and it focuses on the feasibility and effectiveness of this mapping. This mapping leads to a fundamental departure from typical EC methods: using a multiset of proteins as an intermediate mapping results in a \emph{completely location independent} problem representation where the location of the genes in a genome has no effect on the fitness of the solutions. Completely location independent representations, by definition, do not suffer from traditional EC hurdles associated with the location of the genes or positional effect in a genome. Such representations have the ability to self-organize into a genomic structure that appears to favor positive correlations between form and quality of represented solutions. Completely location independent representations also introduce new problems of their own such as the need for large alphabets of symbols and the theoretical need for larger representation spaces than traditional approaches. Overall, these representations perform as well or better than traditional representations and they appear to be particularly good for the class of problems involving proportions or multisets. This thesis concludes that the use of protein analogous structures as an intermediate representation in evolutionary computation is not only feasible but in some cases advantageous. In addition, it lays the groundwork for further research on proteins as functional self-organizing structures capable of building increasingly complex functionality, and as basic units of problem representation for evolutionary computation.