Theory and Algorithms Commons^™

Harnessing The Power Of Gradient-Based Simulations For Multi-Objective Optimization In Particle Accelerators, Kishansingh Rajput, Malachi Schram, Auralee Edelen, Jonathan Colen, Armen Kasparian, Ryan Roussel, Adam Carpenter, He Zhang, Jay Benesch

Data Science Faculty Publications

Particle accelerator operation requires simultaneous optimization of multiple objectives. Multi-objective optimization (MOO) is particularly challenging due to trade-offs between the objectives. Evolutionary algorithms, such as genetic algorithms (GAs), have been leveraged for many optimization problems, however, they do not apply to complex control problems by design. This paper demonstrates the power of differentiability for solving MOO problems in particle accelerators using a deep differentiable reinforcement learning (DDRL) algorithm. We compare the DDRL algorithm with model-free reinforcement learning (MFRL), GA, and Bayesian optimization (BO) for simultaneous optimization of heat load and trip rates in the continuous electron beam accelerator facility. The …

A Framework For Task Offloading In Heterogeneous Computing Applications Within The Fog Ran Architecture, Samira Taheri, Neda Moghim, Naser Movahhedinia, Sachin Shetty

VMASC Publications

Fog Radio Access Network (Fog RAN) has recently emerged as a promising architecture for supporting low-latency applications by bringing fog nodes and cloud resources closer to end users. However, existing research on computational offloading in Fog RAN lacks a comprehensive framework that addresses three key aspects: where to offload tasks, which processing nodes to utilize, and how to allocate resources for tasks with varying latency requirements. To address this gap, we propose TOFRA (Task Offloading for Fog RAN), a novel latency-aware task offloading framework. TOFRA is a centralized system that determines the optimal offloading strategy, whether to execute tasks locally, …

Comparison Of Evolutionary Algorithms: A Case Study On The Multi-Objective Carbon-Aware Mine Planning, Nurul Asyikeen Binte Azhar, Aldy Gunawan, Shih-Fen Cheng, Erwin Leonardi

Research Collection School Of Computing and Information Systems

The NP-hard precedence-constrained production scheduling problem (PCPSP) for mine planning chooses the ordered removal of materials from the mine pit and the next processing steps based on resource, geological, and geometrical constraints. Traditionally, it prioritizes the net present value (NPV) of profits across the lifespan of the mine. Yet, the growing shift in environmental concerns also requires shifts to more carbon-aware practices. In this paper, we use the enhanced multi-objective version of the generic PCPSP formulation by adding the NPV of carbon costs as another objective. We then compare how the Non-dominated Sorting Genetic Algorithm II (NSGA-II) and the Pareto …

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 …

Marine Quay Crane Scheduling Using A Combined Modified Genetic Algorithm And Priority Rules Approach, V. H. Nguyen, D. T. Nguyen

Civil & Environmental Engineering Faculty Publications

Quay crane scheduling problem (QCSP) is the problem of the allocation of quay cranes to handle the unloading and loading of containers at seaport container terminals and defining the service sequence of vessel bays of each quay crane. The treatment of crane interference constraints and the increased in vessel size make the problem difficult to solve. Due to the growing interest in applied research for this problem, many researchers have used different algorithms and methods to obtain some solutions. This paper will propose a modified genetic algorithm combined with priority rules to deal with it. The advantage of the proposed …

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 Genetic Algorithm Approach For Optimized Routing, Pavithra Gudur

Electrical & Computer Engineering Theses & Dissertations

Genetic Algorithms find several applications in a variety of fields, such as engineering, management, finance, chemistry, scheduling, data mining and so on, where optimization plays a key role. This technique represents a numerical optimization technique that is modeled after the natural process of selection based on the Darwinian principle of evolution. The Genetic Algorithm (GA) is one among several optimization techniques and attempts to obtain the desired solution by generating a set of possible candidate solutions or populations. These populations are then compared and the best solutions from the set are retained. Subsequently, new candidate solutions are produced, and the …

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 …

The Development Of Genetic Algorithm For The Prediction Of Ship Motion From Wave Radar Data, Sumanth Tirumala Vangipuram

Electrical & Computer Engineering Theses & Dissertations

Genetic Algorithms represent a model of natural process based on the Darwinian principle of evolution. Genetic algorithms are used to solve optimization problems by generating a set of possible solutions and determining which of these solutions most closely match the desired result. The Genetic Algorithm (GA) initially generates a random set of possible solutions, or populations, determines which members of the population are most desirable, and calculates better solutions by implementing genetic operations such as reproduction, cloning, and mutation. Problems where the evaluation of a solution is computationally simple enable the GA to search a vast search space. One of …

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 …

Intelligent System Applications Based On Genetic Algorithms, Yasin Volkan Pehlivanoglu

Mechanical & Aerospace Engineering Theses & Dissertations

As a stochastic search method, evolutionary algorithm (EA) is an emergent optimization algorithm mimicking the natural evolution, where a "biological population" evolves over generations to adapt to an environment by selection, recombination, and mutation. When EA is applied to optimization problems, fitness, individual, and genes usually correspond to an objective function value, a design candidate, and design variables, respectively.

One of the key features of EA is that they search from multiple points in design space, instead of moving from a single point as in gradient-based methods. Furthermore, EA works on function evaluations alone and does not require derivatives or …

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 …

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

Generalization And Parallelization Of Messy Genetic Algorithms And Communication In Parallel Genetic Algorithms, Laurence D. Merkle

Theses and Dissertations

Genetic algorithms (GA) are highly parallelizable, robust semi- optimization algorithms of polynomial complexity. The most commonly implemented GAs are 'simple' GAs (SGAs). Reproduction, crossover, and mutation operate on solution populations. Deceptive and GA-hard problems are provably difficult for simple GAs. Messy GAs (MGA) are designed to overcome these limitations. The MGA is generalized to solve permutation type optimization problems. Its performance is compared to another MGA's, an SGA's, and a permutation SGA's. Against a fully deceptive problem the generalized MGA (GMGA) consistently performs better than the simple GA. Against an NP-complete permutation problem, the GMGA performs better than the other …