No description available.

No description available.

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.

Chi Wai Ho, Raymond. / Thesis submitted in: December 1999. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2000. / Includes bibliographical references (leaves 93-97). / Abstracts in English and Chinese. / Chapter Chapter 1 --- Introduction --- p.7 / Chapter 1.1 --- Thesis Outline --- p.10 / Chapter 1.2 --- Contribution at a Glance --- p.11 / Chapter Chapter 2 --- Background Concept and Related Work --- p.14 / Chapter 2.1 --- Genetic Algorithms (GAs) --- p.14 / Chapter 2.2 --- The Nature of GAs --- p.16 / Chapter 2.3 --- The Role of Mutation --- p.17 / Chapter 2.4 --- The Role of Crossover --- p.18 / Chapter 2.5 --- The Roles of the Mutation and Crossover Rates --- p.19 / Chapter 2.6 --- Adaptation of the Mutation and Crossover Rates --- p.19 / Chapter 2.7 --- Diversity Control --- p.21 / Chapter 2.8 --- Coarse-grain Parallel Genetic Algorithms --- p.25 / Chapter 2.9 --- Adaptation of Migration Period --- p.26 / Chapter 2.10 --- Serial and Parallel GAs --- p.27 / Chapter 2.11 --- Distributed Java Machine (DJM) --- p.28 / Chapter 2.12 --- Clustering --- p.30 / Chapter Chapter 3 --- Adaptation of the Mutation and Crossover Rates --- p.35 / Chapter 3.1 --- The Probabilistic Rule-based Adaptive Model (PRAM) --- p.35 / Chapter 3.2 --- Time Complexity --- p.37 / Chapter 3.3 --- Storage Complexity --- p.38 / Chapter Chapter 4 --- Diversity Control --- p.39 / Chapter 4.1 --- Repelling --- p.39 / Chapter 4.2 --- Implementation --- p.42 / Chapter 4.3 --- Lazy Repelling --- p.43 / Chapter 4.4 --- Repelling and Lazy Repelling with Deterministic Crowding --- p.43 / Chapter 4.5 --- Comparison of Repelling and Lazy Repelling with Recent Diversity Maintenance Models in Time Complexity --- p.44 / Chapter Chapter 5 --- An Adaptive Parallel Genetic Algorithm --- p.46 / Chapter 5.1 --- A Steady-State Genetic Algorithm --- p.46 / Chapter 5.2 --- An Adaptive Parallel Genetic Algorithm (aPGA) --- p.47 / Chapter 5.3 --- An Adaptive Parallel Genetic Algorithm for Clustering --- p.48 / Chapter 5.4 --- Implementation --- p.48 / Chapter 5.5 --- Time Complexity --- p.51 / Chapter Chapter 6 --- Performance Evaluation of PRAM --- p.52 / Chapter 6.1 --- Solution Quality --- p.58 / Chapter 6.2 --- Efficiency --- p.60 / Chapter 6.3 --- Discussion --- p.62 / Chapter Chapter 7 --- Performance Evaluation of Repelling --- p.66 / Chapter 7.1 --- Performance Comparison of Repelling and Lazy Repelling with Deterministic Crowding --- p.70 / Chapter 7.2 --- Performance Comparison with Recent Diversity Maintenance Models --- p.73 / Chapter 7.3 --- Performance Comparison with Serial and Parallel Gas --- p.75 / Chapter Chapter 8 --- Performance Evaluation of aPGA --- p.78 / Chapter 8.1 --- Scalability of Different Dimensionalities --- p.78 / Chapter 8.2 --- Speedup of Schwefel's function --- p.83 / Chapter 8.3 --- Solution Quality of Clustering Problems --- p.87 / Chapter 8.4 --- Speedup of The Clustering Problem --- p.89 / Chapter Chapter 9 --- Conclusion --- p.91

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.