Mimicking natural evolution to solve hard optimization problems has played an important role in the artificial intelligence arena. Such techniques are broadly classified as Evolutionary Algorithms (EAs) and have been investigated for around four decades during which important contributions and advances have been made. One main evolutionary technique which has been widely investigated is the Genetic Algorithm (GA). GAs are stochastic search techniques that follow the Darwinian principle of evolution. Their application in the solution of hard optimization problems has been very successful. Indeed multi-dimensional problems presenting difficult search spaces with characteristics such as multi-modality, epistasis, non regularity, deceptiveness, etc., have all been effectively tackled by GAs. In this research, a competitive form of GAs known as fine or cellular GAs (cGAs) are investigated, because of their suitability for System on Chip (SoC) implementation when tackling real-time problems. Cellular GAs have also attracted the attention of researchers due to their high performance, ease of implementation and massive parallelism. In addition, cGAs inherently possess a number of structural configuration parameters which make them capable of sustaining diversity during evolution and therefore of promoting an adequate balance between exploitative and explorative stages of the search. The fast technological development of Integrated Circuits (ICs) has allowed a considerable increase in compactness and therefore in density. As a result, it is nowadays possible to have millions of gates and transistor based circuits in very small silicon areas. Operational complexity has also significantly increased and consequently other setbacks have emerged, such as the presence of faults that commonly appear in the form of single or multiple bit flips. Tough environmental or time dependent operating conditions can trigger faults in registers and memory allocations due to induced radiation, electron migration and dielectric breakdown. These kinds of faults are known as Single Event Effects (SEEs). Research has shown that an effective way of dealing with SEEs consists of a combination of hardware and software mitigation techniques to overcome faulty scenarios. Permanent faults known as Single Hard Errors (SHEs) and temporary faults known as Single Event Upsets (SEUs) are common SEEs. This thesis aims to investigate the inherent abilities of cellular GAs to deal with SHEs and SEUs at algorithmic level. A hard real-time application is targeted: calculating the attitude parameters for navigation in vehicles using Global Positioning System (GPS) technology. Faulty critical data, which can cause a system’s functionality to fail, are evaluated. The proposed mitigation techniques show cGAs ability to deal with up to 40% stuck at zero and 30% stuck at one faults in chromosomes bits and fitness score cells. Due to the non-deterministic nature of GAs, dynamic on-the-fly algorithmic and parametric configuration has also attracted the attention of researchers. In this respect, the structural properties of cellular GAs provide a valuable attribute to influence their selection pressure. This helps to maintain an adequate exploitation-exploration tradeoff, either from a pure topological perspective or through genetic operations that also make use of structural characteristics in cGAs. These properties, unique to cGAs, are further investigated in this thesis through a set of middle to high difficulty benchmark problems. Experimental results show that the proposed dynamic techniques enhance the overall performance of cGAs in most benchmark problems. Finally, being structurally attached, the dimensionality of cellular GAs is another line of investigation. 1D and 2D structures have normally been used to test cGAs at algorithm and implementation levels. Although 3D-cGAs are an immediate extension, not enough attention has been paid to them, and so a comparative study on the dimensionality of cGAs is carried out. Having shorter radii, 3D-cGAs present a faster dissemination of solutions and have denser neighbourhoods. Empirical results reported in this thesis show that 3D-cGAs achieve better efficiency when solving multi-modal and epistatic problems. In future, the performance improvements of 3D-cGAs will merge with the latest benefits that 3D integration technology has demonstrated, such as reductions in routing length, in interconnection delays and in power consumption.

No description available.

In this thesis we used genetic algorithms as a core gameplay mechanic for games. We created a flexible genetic algorithms framework that allowed us to iterate quickly through various designs and prototypes of games. We developed two iterations of fighting robots game and a racing game that used our framework to implement genetic algorithms. Playtesting showed that such a sophisticated game mechanic like this one can be fun and appealing to players.

In this thesis we used genetic algorithms as a core gameplay mechanic for games. We created a flexible genetic algorithms framework that allowed us to iterate quickly through various designs and prototypes of games. We developed two iterations of fighting robots game and a racing game that used our framework to implement genetic algorithms. Playtesting showed that such a sophisticated game mechanic like this one can be fun and appealing to players.

by Hoi Wing, Yung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 56-60). / Abstracts in English and Chinese. / List of Figures --- p.v / List of Tables --- p.vi / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview --- p.1 / Chapter 1.2 --- Literature Review --- p.3 / Chapter 1.2.1 --- On the Fixed Multiprocessor Job Scheduling Problems --- p.6 / Chapter 1.2.2 --- On the Nonfixed Multiprocessor Job Scheduling Problems --- p.8 / Chapter 1.3 --- Problem Formulation --- p.12 / Chapter 1.4 --- Organization of the Thesis --- p.13 / Chapter 2 --- Genetic Algorithms --- p.15 / Chapter 2.1 --- Basic Concepts --- p.15 / Chapter 2.2 --- Main components --- p.17 / Chapter 3 --- A New Genetic Algorithm --- p.24 / Chapter 3.1 --- Coding --- p.25 / Chapter 3.1.1 --- Simple Example --- p.28 / Chapter 3.2 --- Similarity of Chromosomes --- p.30 / Chapter 3.3 --- Fitness Evaluation --- p.33 / Chapter 3.4 --- Configurations --- p.35 / Chapter 3.4.1 --- Parent Selection --- p.35 / Chapter 3.4.2 --- Multipoint Crossover --- p.36 / Chapter 3.4.3 --- Multipoint Mutation --- p.38 / Chapter 3.4.4 --- Replacement Step --- p.38 / Chapter 3.4.5 --- Termination Criterion --- p.39 / Chapter 4 --- Experimental Results --- p.41 / Chapter 4.1 --- Total Weighted Completion Time --- p.41 / Chapter 4.1.1 --- Lee and Cai's Algorithm --- p.42 / Chapter 4.1.2 --- Computational Results --- p.44 / Chapter 4.1.3 --- On the Problem of Minimizing the Total Completion Time --- p.46 / Chapter 4.2 --- Makespan --- p.48 / Chapter 4.2.1 --- Mahesh's Algorithms and Linn & Chen's Algorithm --- p.48 / Chapter 4.2.2 --- Computational Results --- p.52 / Chapter 5 --- Conclusion --- p.54 / Bibliography --- p.56

In this thesis we used genetic algorithms as a core gameplay mechanic for games. We created a flexible genetic algorithms framework that allowed us to iterate quickly through various designs and prototypes of games. We developed two iterations of fighting robots game and a racing game that used our framework to implement genetic algorithms. Playtesting showed that such a sophisticated game mechanic like this one can be fun and appealing to players.

This paper describes the development of OM-Darwin, a generalized system for composing with genetic algorithms (GA), realized as a library for OpenMusic. It provides a simple GA engine, along with sophisticated devices for genotype encoding, phenotype mapping and modular fitness function design, while offering a collection of objects that represent common musical forms and rules. A comparison with other optimization methods reveals some advantages in the GA approach, in particular the capability of defining frequency-based rules and producing partial solutions to difficult musical problems. Reference is made to the author's Future Perfect (2010) for 13 instruments, composed entirely using OM-Darwin.

Lau Chun Ming. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1997. / Includes bibliographical references (leaves 122-125). / Chapter Chapter 1: --- Introduction --- p.1 / Chapter 1.1 --- Overview --- p.1 / Chapter 1.2 --- Static Plant Layout Problem --- p.1 / Chapter 1.3 --- Dynamic Plant Layout Problem --- p.3 / Chapter 1.4 --- Example Problem of SPLP --- p.4 / Chapter 1.5 --- Formulation of SPLP --- p.7 / Chapter 1.6 --- Example Problem of DPLP --- p.8 / Chapter 1.7 --- Mathematical Model of DPLP --- p.12 / Chapter 1.8 --- Characteristics of the DPLP --- p.13 / Chapter 1.9 --- Constrained Dynamic Plant Layout Problem (CDPLP) --- p.14 / Chapter 1.10 --- Mathematical Model of CDPLP --- p.14 / Chapter 1.11 --- Objective of the Research --- p.15 / Chapter 1.12 --- Conclusion --- p.16 / Chapter Chapter 2: --- Literature Review --- p.17 / Chapter 2.1 --- Overview --- p.17 / Chapter 2.2 --- Static Plant Layout Problem (SPLP) --- p.17 / Chapter 2.2.1 --- The optimal algorithms / Chapter 2.2.2 --- The sub-optimal algorithms / Chapter 2.2.3 --- Construction algorithms / Chapter 2.2.4 --- Improvement algorithms / Chapter 2.3 --- Dynamic Plant Layout Problem (DPLP) --- p.21 / Chapter 2.4 --- Conclusion: --- p.26 / Chapter Chapter 3: --- Genetic Algorithms in DPLP --- p.27 / Chapter 3.1 --- Introduction of Genetic Algorithms --- p.27 / Chapter 3.2 --- Genetic Algorithms in DPLP --- p.28 / Chapter 3.2.1 --- Encoding of a solution / Chapter 3.2.2 --- Fitness function / Chapter 3.2.3 --- Crossover operator / Chapter 3.2.4 --- Selection scheme / Chapter 3.2.5 --- Replacement and reproduction / Chapter 3.2.6 --- Mutation / Chapter 3.2.7 --- Initialization of parent pool / Chapter 3.2.8 --- Termination criterion / Chapter 3.3 --- Summary of the Proposed Method --- p.50 / Chapter Chapter 4: --- Computational Result of GA in DPLP --- p.51 / Chapter 4.1 --- Overview --- p.51 / Chapter 4.2 --- Characteristics of the Testing Problems --- p.51 / Chapter 4.3 --- Mathematical Model of DPLP for the Testing Problem --- p.52 / Chapter 4.4 --- The Design of Experiment --- p.53 / Chapter 4.4.1 --- The experiment / Chapter 4.4.2 --- Generating the initial layouts: / Chapter 4.5 --- Result: --- p.56 / Chapter 4.6 --- Analysis of Results --- p.60 / Chapter 4.6.1 --- 6department problems / Chapter 4.6.2 --- 15and 30 department problems / Chapter 4.7 --- Conclusion --- p.66 / Chapter Chapter 5: --- Constrained Dynamic Plant Layout Problem --- p.68 / Chapter 5.1 --- Overview --- p.68 / Chapter 5.2 --- The Mathematical Model of CDPLP --- p.69 / Chapter 5.3 --- Properties of CDPLP --- p.69 / Chapter 5.4 --- The Proposed GA on CDPLP --- p.71 / Chapter 5.4.1 --- Introduction / Chapter 5.4.2 --- Procedure / Chapter 5.4.3 --- Properties of dynamic programming under the dummy periods / Chapter 5.4.4 --- Properties of the proposed GA under the dummy periods / Chapter 5.4.5 --- The maximum number of iteration for the procedure / Chapter 5.5 --- Design of Experiment --- p.78 / Chapter 5.6 --- Result of Experiment on CDPLP --- p.81 / Chapter 5.7 --- Analysis of Results --- p.91 / Chapter 5.7.1 --- Type 1 budget (self): / Chapter 5.7.2 --- The average cost of the test / Chapter 5.8 --- Conclusion: --- p.93 / Chapter Chapter 6: --- Conclusion --- p.94 / Appendix A: The Improved Implementation for Conway and Venkataramanan's GA --- p.96 / Appendix B: Computational Result for CDPLP --- p.98 / Bibliography --- p.122

The basis of this thesis is the presumption that while neural networks are useful structures that can be used to model complex, highly non-linear systems, current methods of training the neural networks are inadequate in some problem domains. Genetic algorithms have been used to optimise both the weights and architectures of neural networks, but these approaches do not treat the neural network in a sensible manner. In this thesis, I define the basis of computation within a neural network as a single neuron and its associated input connections. Sets of these neurons, stored in a matrix representation, comprise the building blocks that are transferred during one or more epochs of a genetic algorithm. I develop the concept of a Neural Building Block and two new genetic algorithms are created that utilise this concept. The first genetic algorithm utilises the micro neural building block (micro-NBB); a unit consisting of one or more neurons and their input connections. The micro-NBB is a unit that is transmitted through the process of crossover and hence requires the introduction of a new crossover operator. However the micro NBB can not be stored as a reusable component and must exist only as the product of the crossover operator. The macro neural building block (macro-NBB) is utilised in the second genetic algorithm, and encapsulates the idea that fit neural networks contain fit sub-networks, that need to be preserved across multiple epochs. A macro-NBB is a micro-NBB that exists across multiple epochs. Macro-NBBs must exist across multiple epochs, and this necessitates the use of a genetic store, and a new operator to introduce macro-NBBs back into the population at random intervals. Once the theoretical presentation is completed the newly developed genetic algorithms are used to evolve weights for a variety of architectures of neural networks to demonstrate the feasibility of the approach. Comparison of the new genetic algorithm with other approaches is very favourable on two problems: a multiplexer problem and a robot control problem.

Thesis (M.S.)--University of Nevada, Reno, 2006. / "May, 2006." Includes bibliographical references (leaves 70-72). Online version available on the World Wide Web.