Theory and Algorithms Commons^™

Growing Reservoir Networks Using The Genetic Algorithm Deep Hyperneat, Nancy L. Mackenzie

Student Research Symposium

Typical Artificial Neural Networks (ANNs) have static architectures. The number of nodes and their organization must be chosen and tuned for each task. Choosing these values, or hyperparameters, is a bit of a guessing game, and optimizing must be repeated for each task. If the model is larger than necessary, this leads to more training time and computational cost. The goal of this project is to evolve networks that grow according to the task at hand. By gradually increasing the size and complexity of the network to the extent that the task requires, we will build networks that are more …

Algebraic Neural Architecture Representation, Evolutionary Neural Architecture Search, And Novelty Search In Deep Reinforcement Learning, Ethan C. Jackson

Electronic Thesis and Dissertation Repository

Evolutionary algorithms have recently re-emerged as powerful tools for machine learning and artificial intelligence, especially when combined with advances in deep learning developed over the last decade. In contrast to the use of fixed architectures and rigid learning algorithms, we leveraged the open-endedness of evolutionary algorithms to make both theoretical and methodological contributions to deep reinforcement learning. This thesis explores and develops two major areas at the intersection of evolutionary algorithms and deep reinforcement learning: generative network architectures and behaviour-based optimization. Over three distinct contributions, both theoretical and experimental methods were applied to deliver a novel mathematical framework and experimental …

Investigating Genetic Algorithm Optimization Techniques In Video Games, Nathan Ambuehl

Undergraduate Honors Theses

Immersion is essential for player experience in video games. Artificial Intelligence serves as an agent that can generate human-like responses and intelligence to reinforce a player’s immersion into their environment. The most common strategy involved in video game AI is using decision trees to guide chosen actions. However, decision trees result in repetitive and robotic actions that reflect an unrealistic interaction. This experiment applies a genetic algorithm that explores selection, crossover, and mutation functions for genetic algorithm implementation in an isolated Super Mario Bros. pathfinding environment. An optimized pathfinding AI can be created by combining an elitist selection strategy with …

An Algorithm For Quantum Circuit Optimization, Raymond Garwei Wong

Computer Science and Software Engineering

In the past 20 years, many researchers shifted their focus to developing computers based on quantum mechanical phenomenon as current computers started to plateau in performance. Some problems such as integer factorization have been shown to perform much more efficiently on a quantum computer than on its classical counterpart. However, quantum computers will continue to remain the object of theoretical research unless it can be physically manifested, and quantum circuit optimization hopes to be a useful aid in turning the theory into a reality. My project looks at a possible approach to solving the issue of circuit optimization by incorporating …

Fusion Of Visual And Thermal Images Using Genetic Algorithms, Sertan Erkanli

Electrical & Computer Engineering Theses & Dissertations

Demands for reliable person identification systems have increased significantly due to highly security risks in our daily life. Recently, person identification systems are built upon the biometrics techniques such as face recognition. Although face recognition systems have reached a certain level of maturity, their accomplishments in practical applications are restricted by some challenges, such as illumination variations. Current visual face recognition systems perform relatively well under controlled illumination conditions while thermal face recognition systems are more advantageous for detecting disguised faces or when there is no illumination control. A hybrid system utilizing both visual and thermal images for face recognition …

A Review Of Procedures To Evolve Quantum Algorithms, Adrian Gepp, Phil Stocks

Adrian Gepp

There exist quantum algorithms that are more efficient than their classical counterparts; such algorithms were invented by Shor in 1994 and then Grover in 1996. A lack of invention since Grover’s algorithm has been commonly attributed to the non-intuitive nature of quantum algorithms to the classically trained person. Thus, the idea of using computers to automatically generate quantum algorithms based on an evolutionary model emerged. A limitation of this approach is that quantum computers do not yet exist and quantum simulation on a classical machine has an exponential order overhead. Nevertheless, early research into evolving quantum algorithms has shown promise. …

Genetic Algorithms For The Extended Gcd Problem, Jonathan P. Sorenson

Jonathan P. Sorenson

We present several genetic algorithms for solving the extended greatest common divisor problem. After defining the problem and discussing previous work, we will state our results.

Segmentation Of Thermographic Images Of Hands Using A Genetic Algorithm, Payel Ghosh, Judith Gold, Melanie Mitchell

Computer Science Faculty Publications and Presentations

This paper presents a new technique for segmenting thermographic images using a genetic algorithm (GA). The individuals of the GA also known as chromosomes consist of a sequence of parameters of a level set function. Each chromosome represents a unique segmenting contour. An initial population of segmenting contours is generated based on the learned variation of the level set parameters from training images. Each segmenting contour (an individual) is evaluated for its fitness based on the texture of the region it encloses. The fittest individuals are allowed to propagate to future generations of the GA run using selection, crossover and …

Basic Online Scheduling System Optimizer: A Study In Genetic Alogrithms [Sic], Norman Lee Langhorne

Theses Digitization Project

The purpose of this project is to provide the School of Computer Science and Engineering at California State University, San Bernardino with an optimizing schedule module to enhance the latest version of the Basic Online Scheduling System.

Bit-Error-Rate-Minimizing Channel Shortening Using Post-Feq Diversity Combining And A Genetic Algorithm, Gokhan Altin

Theses and Dissertations

In advanced wireline or wireless communication systems, i.e., DSL, IEEE 802.11a/g, HIPERLAN/2, etc., a cyclic prefix which is proportional to the channel impulse response is needed to append a multicarrier modulation (MCM) frame for operating the MCM accurately. This prefix is used to combat inter symbol interference (ISI). In some cases, the channel impulse response can be longer than the cyclic prefix (CP). One of the most useful techniques to mitigate this problem is reuse of a Channel Shortening Equalizer (CSE) as a linear preprocessor before the MCM receiver in order to shorten the effective channel length. Channel shortening filter …

Application Of Optimization Techniques To Spectrally Modulated, Spectrally Encoded Waveform Design, Todd W. Beard

Theses and Dissertations

A design process is demonstrated for a coexistent scenario containing Spectrally Modulated, Spectrally Encoded (SMSE) and Direct Sequence Spread Spectrum (DSSS) signals. Coexistent SMSE-DSSS designs are addressed under both perfect and imperfect DSSS code tracking conditions using a non-coherent delay-lock loop (DLL). Under both conditions, the number of SMSE subcarriers and subcarrier spacing are the optimization variables of interest. For perfect DLL code tracking conditions, the GA and RSM optimization processes are considered independently with the objective function being end-to-end DSSS bit error rate. A hybrid GA-RSM optimization process is used under more realistic imperfect DLL code tracking conditions. In …

Prostate Segmentation On Pelvic Ct Images Using A Genetic Algorithm, Payel Ghosh, Melanie Mitchell

Computer Science Faculty Publications and Presentations

A genetic algorithm (GA) for automating the segmentation of the prostate on pelvic computed tomography (CT) images is presented here. The images consist of slices from three-dimensional CT scans. Segmentation is typically performed manually on these images for treatment planning by an expert physician, who uses the “learned” knowledge of organ shapes, textures and locations to draw a contour around the prostate. Using a GA brings the flexibility to incorporate new “learned” information into the segmentation process without modifying the fitness function that is used to train the GA. Currently the GA uses prior knowledge in the form of texture …

A Genetic Algorithm For Cellular Manufacturing Design And Layout, Xiaodan Wu, Chao-Hsien Chu, Yunfeng Wang, Weili Yan

Research Collection School Of Computing and Information Systems

Cellular manufacturing (CM) is an approach that can be used to enhance both flexibility and efficiency in today’s small-to-medium lot production environment. The design of a CM system (CMS) often involves three major decisions: cell formation, group layout, and group schedule. Ideally, these decisions should be addressed simultaneously in order to obtain the best results. However, due to the complexity and NP-complete nature of each decision and the limitations of traditional approaches, most researchers have only addressed these decisions sequentially or independently. In this study, a hierarchical genetic algorithm is developed to simultaneously form manufacturing cells and determine the group …

A Case For Exhaustive Optimization, Sanza Kazadi, Michele Lee, Lauren Lee

Sanza Kazadi

A Genetic Algorithm For Uav Routing Integrated With A Parallel Swarm Simulation, Matthew A. Russell

Theses and Dissertations

This research investigation addresses the problem of routing and simulating swarms of UAVs. Sorties are modeled as instantiations of the NP-Complete Vehicle Routing Problem, and this work uses genetic algorithms (GAs) to provide a fast and robust algorithm for a priori and dynamic routing applications. Swarms of UAVs are modeled based on extensions of Reynolds' swarm research and are simulated on a Beowulf cluster as a parallel computing application using the Synchronous Environment for Emulation and Discrete Event Simulation (SPEEDES). In a test suite, standard measures such as benchmark problems, best published results, and parallel metrics are used as performance …

Explicit Building-Block Multiobjective Genetic Algorithms: Theory, Analysis, And Developing, Jesse B. Zydallis

Theses and Dissertations

This dissertation research emphasizes explicit Building Block (BB) based MO EAs performance and detailed symbolic representation. An explicit BB-based MOEA for solving constrained and real-world MOPs is developed the Multiobjective Messy Genetic Algorithm II (MOMGA-II) which is designed to validate symbolic BB concepts. The MOMGA-II demonstrates that explicit BB-based MOEAs provide insight into solving difficult MOPs that is generally not realized through the use of implicit BB-based MOEA approaches. This insight is necessary to increase the effectiveness of all MOEA approaches. In order to increase MOEA computational efficiency parallelization of MOEAs is addressed. Communications between processors in a parallel MOEA …

Genetic Algorithms For Communications Network Design - An Empirical Study Of The Factors That Influence Performance, Hsinghua Chou, G. Premkumar, Chao-Hsien Chu

Research Collection School Of Computing and Information Systems

We explore the use of GAs for solving a network optimization problem, the degree-constrained minimum spanning tree problem. We also examine the impact of encoding, crossover, and mutation on the performance of the GA. A specialized repair heuristic is used to improve performance. An experimental design with 48 cells and ten data points in each cell is used to examine the impact of two encoding methods, three crossover methods, two mutation methods, and four networks of varying node sizes. Two performance measures, solution quality and computation time, are used to evaluate the performance. The results obtained indicate that encoding has …

Traveling Salesman Problem For Surveillance Mission Using Particle Swarm Optimization, Barry R. Secrest

Theses and Dissertations

The surveillance mission requires aircraft to fly from a starting point through defended terrain to targets and return to a safe destination (usually the starting point). The process of selecting such a flight path is known as the Mission Route Planning (MRP) Problem and is a three-dimensional, multi-criteria (fuel expenditure, time required, risk taken, priority targeting, goals met, etc.) path search. Planning aircraft routes involves an elaborate search through numerous possibilities, which can severely task the resources of the system being used to compute the routes. Operational systems can take up to a day to arrive at a solution due …

Investigation Of Image Feature Extraction By A Genetic Algorithm, Steven P. Brumby, James P. Theiler, Simon J. Perkins, Neal R. Harvey, John J. Szymanski, Jeffrey J. Bloch, Melanie Mitchell

Computer Science Faculty Publications and Presentations

We describe the implementation and performance of a genetic algorithm which generates image feature extraction algorithms for remote sensing applications. We describe our basis set of primitive image operators and present our chromosomal representation of a complete algorithm. Our initial application has been geospatial feature extraction using publicly available multi-spectral aerial-photography data sets. We present the preliminary results of our analysis of the efficiency of the classic genetic operations of crossover and mutation for our application, and discuss our choice of evolutionary control parameters. We exhibit some of our evolved algorithms, and discuss possible avenues for future progress.

An Adaptive Hierarchical Fuzzy Logic System For Modelling And Prediction Of Financial Systems, Mark Kingham

Theses: Doctorates and Masters

In this thesis, an intelligent fuzzy logic system using genetic algorithms for the prediction and modelling of interest rates is developed. The proposed system uses a Hierarchical Fuzzy Logic system in which a genetic algorithm is used as a training method for learning the fuzzy rules knowledge bases. A fuzzy logic system is developed to model and predict three month quarterly interest rate fluctuations. The system is further trained to model and predict interest rates for six month and one year periods. The proposed system is developed with first two, three, then four and finally five hierarchical knowledge bases to …

Statistical Dynamics Of The Royal Road Genetic Algorithm, Erik Van Nimwegen, James P. Crutchfield, Melanie Mitchell

Computer Science Faculty Publications and Presentations

Metastability is a common phenomenon. Many evolutionary processes, both natural and artificial, alternate between periods of stasis and brief periods of rapid change in their behavior. In this paper an analytical model for the dynamics of a mutation-only genetic algorithm (GA) is introduced that identifies a new and general mechanism causing metastability in evolutionary dynamics. The GA’s population dynamics is described in terms of flows in the space of fitness distributions. The trajectories through fitness distribution space are derived in closed form in the limit of infinite populations. We then show how finite populations induce metastability, even in regions where …

Conjugate Schema In Genetic Search, Sanza Kazadi

Sanza Kazadi

Genetic Algorithms For The Extended Gcd Problem, Jonathan P. Sorenson

Scholarship and Professional Work - LAS

We present several genetic algorithms for solving the extended greatest common divisor problem. After defining the problem and discussing previous work, we will state our results.

Refined Genetic Algorithms For Polypeptide Structure Prediction, Charles E. Kaiser Jr.

Theses and Dissertations

Accurate and reliable prediction of macromolecular structures has eluded researchers for nearly 40 years. Prediction via energy minimization assumes the native conformation has the globally minimal energy potential. An exhaustive search is impossible since for molecules of normal size, the size of the search space exceeds the size of the universe. Domain knowledge sources, such as the Brookhaven PDB can be mined for constraints to limit the search space. Genetic algorithms (GAs) are stochastic, population based, search algorithms of polynomial (P) time complexity that can produce semi-optimal solutions for problems of nondeterministic polynomial (NP) time complexity such as PSP. Three …

Analysis Of Linkage-Friendly Genetic Algorithms, Laurence D. Merkle

Theses and Dissertations

Evolutionary algorithms (EAs) are stochastic population-based algorithms inspired by the natural processes of selection, mutation, and recombination. EAs are often employed as optimum seeking techniques. A formal framework for EAs is proposed, in which evolutionary operators are viewed as mappings from parameter spaces to spaces of random functions. Formal definitions within this framework capture the distinguishing characteristics of the classes of recombination, mutation, and selection operators. EAs which use strictly invariant selection operators and order invariant representation schemes comprise the class of linkage-friendly genetic algorithms (lfGAs). Fast messy genetic algorithms (fmGAs) are lfGAs which use binary tournament selection (BTS) with …

Genetic Algorithms And Artificial Life, Melanie Mitchell, Stephanie Forrest

Computer Science Faculty Publications and Presentations

Genetic algorithms are computational models of evolution that play a central role in many artificial-life models. We review the history and current scope of research on genetic algorithms in artificial life, giving illustrative examples in which the genetic algorithm is used to study how learning and evolution interact, and to model ecosystems, immune system, cognitive systems, and social systems. We also outline a number of open questions and future directions for genetic algorithms in artificial-life research