SEARCH · Search NASA

Results for “evolutionary algorithm”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 235 records · Page 13

All sources NASA NTRS DOE OSTI

NASA NTRS2000

JavaGenes: Evolving Graphs with Crossover

Genetic algorithms usually use string or tree representations. We have developed a novel crossover operator for a directed and undirected graph representation, and used this operator to evolve molecules and circuits. Unlike strings or trees, a single point in the representation cannot divide every possible graph into two parts, because graphs may contain cycles. Thus, the crossover operator is non-trivial. A steady-state, tournament selection genetic algorithm code (JavaGenes) was written to implement and test the graph crossover operator. All runs were executed by cycle-scavagging on networked workstations using the Condor batch processing system. The JavaGenes code has evolved pharmaceutical drug molecules and simple digital circuits. Results to date suggest that JavaGenes can evolve moderate sized drug molecules and very small circuits in reasonable time. The algorithm has greater difficulty with somewhat larger circuits, suggesting that directed graphs (circuits) are more difficult to evolve than undirected graphs (molecules), although necessary differences in the crossover operator may also explain the results. In principle, JavaGenes should be able to evolve other graph-representable systems, such as transportation networks, metabolic pathways, and computer networks. However, large graphs evolve significantly slower than smaller graphs, presumably because the space-of-all-graphs explodes combinatorially with graph size. Since the representation strongly affects genetic algorithm performance, adding graphs to the evolutionary programmer's bag-of-tricks should be beneficial. Also, since graph evolution operates directly on the phenotype, the genotype-phenotype translation step, common in genetic algorithm work, is eliminated.

Globus, Al↗

NASA NTRS1985

Analysis of adaptive algorithms for an integrated communication network

Techniques were examined that trade communication bandwidth for decreased transmission delays. When the network is lightly used, these schemes attempt to use additional network resources to decrease communication delays. As the network utilization rises, the schemes degrade gracefully, still providing service but with minimal use of the network. Because the schemes use a combination of circuit and packet switching, they should respond to variations in the types and amounts of network traffic. Also, a combination of circuit and packet switching to support the widely varying traffic demands imposed on an integrated network was investigated. The packet switched component is best suited to bursty traffic where some delays in delivery are acceptable. The circuit switched component is reserved for traffic that must meet real time constraints. Selected packet routing algorithms that might be used in an integrated network were simulated. An integrated traffic places widely varying workload demands on a network. Adaptive algorithms were identified, ones that respond to both the transient and evolutionary changes that arise in integrated networks. A new algorithm was developed, hybrid weighted routing, that adapts to workload changes.

Reed, Daniel A.↗

NASA NTRS1995

Tracking magnetogram proper motions by multiscale regularization

Long uninterrupted sequences of solar magnetograms from the global oscillations network group (GONG) network and from the solar and heliospheric observatory (SOHO) satellite will provide the opportunity to study the proper motions of magnetic features. The possible use of multiscale regularization, a scale-recursive estimation technique which begins with a prior model of how state variables and their statistical properties propagate over scale. Short magnetogram sequences are analyzed with the multiscale regularization algorithm as applied to optical flow. This algorithm is found to be efficient, provides results for all the spatial scales spanned by the data and provides error estimates for the solutions. It is found that the algorithm is less sensitive to evolutionary changes than correlation tracking.

Jones, Harrison P.↗

NASA NTRS1997

An Evolutionary Optimization System for Spacecraft Design

Spacecraft design optimization is a domian that can benefit from the application of optimization algorithms such as genetic algorithms. In this paper, we describe DEVO, an evolutionary optimization system that addresses these issues and provides a tool that can be applied to a number of real-world spacecraft design applications. We describe two current applications of DEVO: physical design if a Mars Microprobe Soil Penetrator, and system configuration optimization for a Neptune Orbiter.

Orbiter optimization algorithms↗

NASA NTRS2011

Fast Image Texture Classification Using Decision Trees

Texture analysis would permit improved autonomous, onboard science data interpretation for adaptive navigation, sampling, and downlink decisions. These analyses would assist with terrain analysis and instrument placement in both macroscopic and microscopic image data products. Unfortunately, most state-of-the-art texture analysis demands computationally expensive convolutions of filters involving many floating-point operations. This makes them infeasible for radiation- hardened computers and spaceflight hardware. A new method approximates traditional texture classification of each image pixel with a fast decision-tree classifier. The classifier uses image features derived from simple filtering operations involving integer arithmetic. The texture analysis method is therefore amenable to implementation on FPGA (field-programmable gate array) hardware. Image features based on the "integral image" transform produce descriptive and efficient texture descriptors. Training the decision tree on a set of training data yields a classification scheme that produces reasonable approximations of optimal "texton" analysis at a fraction of the computational cost. A decision-tree learning algorithm employing the traditional k-means criterion of inter-cluster variance is used to learn tree structure from training data. The result is an efficient and accurate summary of surface morphology in images. This work is an evolutionary advance that unites several previous algorithms (k-means clustering, integral images, decision trees) and applies them to a new problem domain (morphology analysis for autonomous science during remote exploration). Advantages include order-of-magnitude improvements in runtime, feasibility for FPGA hardware, and significant improvements in texture classification accuracy.

Thompson, David R.↗

DOE OSTI2019

Island model for parallel evolutionary optimization of spiking neuromorphic computing

Parallel genetic algorithms (PGAs) can be used to accelerate optimization by exploiting large-scale computational resources. In this work, we describe a PGA framework for evolving spiking neural networks (SNNs) for neuromorphic hardware implementation. The PGA framework is based on an islands model with migration. We show that using this framework, better SNNs for neuromorphic systems can be evolved faster.

Schuman, Catherine↗

NASA NTRS1990

Evolutionary tree reconstruction

It is described how Minimum Description Length (MDL) can be applied to the problem of DNA and protein evolutionary tree reconstruction. If there is a set of mutations that transform a common ancestor into a set of the known sequences, and this description is shorter than the information to encode the known sequences directly, then strong evidence for an evolutionary relationship has been found. A heuristic algorithm is described that searches for the simplest tree (smallest MDL) that finds close to optimal trees on the test data. Various ways of extending the MDL theory to more complex evolutionary relationships are discussed.

Cheeseman, Peter↗

DOE OSTI2023

Determining best practices for using genetic algorithms in molecular discovery

Genetic algorithms (GAs) are a powerful tool to search large chemical spaces for inverse molecular design. However, GAs have multiple hyperparameters that have not been thoroughly investigated for chemical space searches. In this tutorial, we examine the general effects of a number of hyperparameters, such as population size, elitism rate, selection method, mutation rate, and convergence criteria, on key GA performance metrics. Here, we show that using a self-termination method with a minimum Spearman’s rank correlation coefficient of 0.8 between generations maintained for 50 consecutive generations along with a population size of 32, a 50% elitism rate, three-way tournament selection, and a 40% mutation rate provides the best balance of finding the overall champion, maintaining good coverage of elite targets, and improving relative speedup for general use in molecular design GAs.

36 MATERIALS SCIENCE↗

NASA NTRS2008

Development of X-TOOLSS: Preliminary Design of Space Systems Using Evolutionary Computation

Evolutionary computational (EC) techniques such as genetic algorithms (GA) have been identified as promising methods to explore the design space of mechanical and electrical systems at the earliest stages of design. In this paper the authors summarize their research in the use of evolutionary computation to develop preliminary designs for various space systems. An evolutionary computational solver developed over the course of the research, X-TOOLSS (Exploration Toolset for the Optimization of Launch and Space Systems) is discussed. With the success of early, low-fidelity example problems, an outline of work involving more computationally complex models is discussed.

Schnell, Andrew R.↗

NASA NTRS2004

Evolutionary computing for the design search and optimization of space vehicle power subsystems

Evolutionary computing has proven to be a straightforward and robust approach for optimizing a wide range of difficult analysis and design problems. This paper discusses the application of these techniques to an existing space vehicle power subsystem resource and performance analysis simulation in a parallel processing environment.

evolutionary computing genetic algorithms optimiza↗

NASA NTRS2000

Automated Design of Quantum Circuits

In order to design a quantum circuit that performs a desired quantum computation, it is necessary to find a decomposition of the unitary matrix that represents that computation in terms of a sequence of quantum gate operations. To date, such designs have either been found by hand or by exhaustive enumeration of all possible circuit topologies. In this paper we propose an automated approach to quantum circuit design using search heuristics based on principles abstracted from evolutionary genetics, i.e. using a genetic programming algorithm adapted specially for this problem. We demonstrate the method on the task of discovering quantum circuit designs for quantum teleportation. We show that to find a given known circuit design (one which was hand-crafted by a human), the method considers roughly an order of magnitude fewer designs than naive enumeration. In addition, the method finds novel circuit designs superior to those previously known.

Williams, Colin P.↗

NASA NTRS2010

Particle Swarm Optimization Toolbox

The Particle Swarm Optimization Toolbox is a library of evolutionary optimization tools developed in the MATLAB environment. The algorithms contained in the library include a genetic algorithm (GA), a single-objective particle swarm optimizer (SOPSO), and a multi-objective particle swarm optimizer (MOPSO). Development focused on both the SOPSO and MOPSO. A GA was included mainly for comparison purposes, and the particle swarm optimizers appeared to perform better for a wide variety of optimization problems. All algorithms are capable of performing unconstrained and constrained optimization. The particle swarm optimizers are capable of performing single and multi-objective optimization. The SOPSO and MOPSO algorithms are based on swarming theory and bird-flocking patterns to search the trade space for the optimal solution or optimal trade in competing objectives. The MOPSO generates Pareto fronts for objectives that are in competition. A GA, based on Darwin evolutionary theory, is also included in the library. The GA consists of individuals that form a population in the design space. The population mates to form offspring at new locations in the design space. These offspring contain traits from both of the parents. The algorithm is based on this combination of traits from parents to hopefully provide an improved solution than either of the original parents. As the algorithm progresses, individuals that hold these optimal traits will emerge as the optimal solutions. Due to the generic design of all optimization algorithms, each algorithm interfaces with a user-supplied objective function. This function serves as a "black-box" to the optimizers in which the only purpose of this function is to evaluate solutions provided by the optimizers. Hence, the user-supplied function can be numerical simulations, analytical functions, etc., since the specific detail of this function is of no concern to the optimizer. These algorithms were originally developed to support entry trajectory and guidance design for the Mars Science Laboratory mission but may be applied to any optimization problem.

Grant, Michael J.↗

DOE OSTI2024

Neural architecture search via similarity adaptive guidance

Evolutionary neural network architecture search (ENAS) has attracted the attention of many experts due to its global optimization capabilities to automatically search for convolutional neural network architectures based on the target task. The current search space for ENAS is not to design a fully structured network, but to search for smaller cell architectures to reduce search costs. However, blind search strategies do not effectively utilize the potential experience of the population. In order to utilize the potential experience learned by the current population to guide the evolutionary search of the population, we propose a similarity guided neural network architecture search algorithm based on cell architecture, which utilizes the similarity between pairwise architectures in the population as empirical knowledge learned by the population. Our proposed algorithm provides a novel method for calculating architecture similarity, which calculates architecture similarity separately from the cell and macro-structure. Then we decouple the connections and operations in the cell and calculate connection and operation similarity separately. In addition, we propose adaptive similarity selection and binary tournament selection strategies to enhance the algorithm’s global and local search capabilities and effectively explore the search space. Finally, we design an improved single-point crossover operator to enhance the local search ability of the evolutionary operator. The experimental results show that SAGNAS is a competitive algorithm that achieves 97.44% and 81.60% in CIFAR10 and CIFAR100 with only 1.9 GPU-days spent.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2018

Numerical parameter optimizations of the Ignition and Growth model for a HMX plastic bonded explosive

We present here a novel method for optimizing parameters of the Ignition and Growth (I&G) reactive flow model for high explosives. The I&G model predicts the shock initiation response of explosives subjected to dynamic loading. However, calibrating the model is a time-consuming process because it has several parameters, typically requires multiple data sets, and there are no direct correlations between parameters and data. In this study, we couple a scalable optimization algorithm to simulations of shock initiation experiments in the multi-physics code ALE3D. We develop four I&G model parameter sets for the HMX (1,3,5,7-tetranitro-1,3,5,7-tetrazocane)-based explosive LX-07 [90 wt. % HMX, 10 wt. % Viton A] based on minimizing the difference between calculations and measurements at the embedded pressure gauges in 1D gun shock experiments. Our study shows that a cost function based on both shock time of arrival and pressure pulse shape demonstrates the best agreement with experimental data.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

NASA NTRS2000

A Parallel Genetic Algorithm for Automated Electronic Circuit Design

We describe a parallel genetic algorithm (GA) that automatically generates circuit designs using evolutionary search. A circuit-construction programming language is introduced and we show how evolution can generate practical analog circuit designs. Our system allows circuit size (number of devices), circuit topology, and device values to be evolved. We present experimental results as applied to analog filter and amplifier design tasks.

Lohn, Jason D.↗

DOE OSTI2019

Visualization System for Evolutionary Neural Networks for Deep Learning

Deep learning is actively used in a wide range of fields for scientific discovery. To effectively apply deep learning to a particular problem, it is important to select an appropriate network architecture and other hyper-parameters (at each layer). Evolving architectures and hyper-parameters using a genetic algorithm is one current approach to search the huge space of all possible configurations to find those more optimal for the problem. However, examining an evolutionary process and tuning the genetic algorithm are challenging, pushing most users to treat the process as a black box. To address this challenge, we propose a visualization system for evolutionary neural networks for deep learning. The key feature of our visualization system is to provide a visual analytics environment for evaluating a genetic algorithm in order to improve the underlying operations to reduce time to find good solutions. Our system is able to not only visualize how a genetic algorithm traverses its search space but also allows users to examine evolving networks in-depth to get insights to improve performance through interactive visualization components.

Chae, Junghoon↗

NASA NTRS2009

Evolutionary Computing Methods for Spectral Retrieval

A methodology for processing spectral images to retrieve information on underlying physical, chemical, and/or biological phenomena is based on evolutionary and related computational methods implemented in software. In a typical case, the solution (the information that one seeks to retrieve) consists of parameters of a mathematical model that represents one or more of the phenomena of interest. The methodology was developed for the initial purpose of retrieving the desired information from spectral image data acquired by remote-sensing instruments aimed at planets (including the Earth). Examples of information desired in such applications include trace gas concentrations, temperature profiles, surface types, day/night fractions, cloud/aerosol fractions, seasons, and viewing angles. The methodology is also potentially useful for retrieving information on chemical and/or biological hazards in terrestrial settings. In this methodology, one utilizes an iterative process that minimizes a fitness function indicative of the degree of dissimilarity between observed and synthetic spectral and angular data. The evolutionary computing methods that lie at the heart of this process yield a population of solutions (sets of the desired parameters) within an accuracy represented by a fitness-function value specified by the user. The evolutionary computing methods (ECM) used in this methodology are Genetic Algorithms and Simulated Annealing, both of which are well-established optimization techniques and have also been described in previous NASA Tech Briefs articles. These are embedded in a conceptual framework, represented in the architecture of the implementing software, that enables automatic retrieval of spectral and angular data and analysis of the retrieved solutions for uniqueness.

Terrile, Richard↗

NASA NTRS2007

Generative Representations for Automated Design of Robots

A method of automated design of complex, modular robots involves an evolutionary process in which generative representations of designs are used. The term generative representations as used here signifies, loosely, representations that consist of or include algorithms, computer programs, and the like, wherein encoded designs can reuse elements of their encoding and thereby evolve toward greater complexity. Automated design of robots through synthetic evolutionary processes has already been demonstrated, but it is not clear whether genetically inspired search algorithms can yield designs that are sufficiently complex for practical engineering. The ultimate success of such algorithms as tools for automation of design depends on the scaling properties of representations of designs. A nongenerative representation (one in which each element of the encoded design is used at most once in translating to the design) scales linearly with the number of elements. Search algorithms that use nongenerative representations quickly become intractable (search times vary approximately exponentially with numbers of design elements), and thus are not amenable to scaling to complex designs. Generative representations are compact representations and were devised as means to circumvent the above-mentioned fundamental restriction on scalability. In the present method, a robot is defined by a compact programmatic form (its generative representation) and the evolutionary variation takes place on this form. The evolutionary process is an iterative one, wherein each cycle consists of the following steps: 1. Generative representations are generated in an evolutionary subprocess. 2. Each generative representation is a program that, when compiled, produces an assembly procedure. 3. In a computational simulation, a constructor executes an assembly procedure to generate a robot. 4. A physical-simulation program tests the performance of a simulated constructed robot, evaluating the performance according to a fitness criterion to yield a figure of merit that is fed back into the evolutionary subprocess of the next iteration. In comparison with prior approaches to automated evolutionary design of robots, the use of generative representations offers two advantages: First, a generative representation enables the reuse of components in regular and hierarchical ways and thereby serves a systematic means of creating more complex modules out of simpler ones. Second, the evolved generative representation may capture intrinsic properties of the design problem, so that variations in the representations move through the design space more effectively than do equivalent variations in a nongenerative representation. This method has been demonstrated by using it to design some robots that move, variously, by walking, rolling, or sliding. Some of the robots were built (see figure). Although these robots are very simple, in comparison with robots designed by humans, their structures are more regular, modular, hierarchical, and complex than are those of evolved designs of comparable functionality synthesized by use of nongenerative representations.

Homby, Gregory S.↗