Search NASA⌕ Search

SEARCH · Search NASA

Results for “heuristic algorithms”

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.

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

At least 523 records · Page 29

Using a multifrontal sparse solver in a high performance, finite element code

We consider the performance of the finite element method on a vector supercomputer. The computationally intensive parts of the finite element method are typically the individual element forms and the solution of the global stiffness matrix both of which are vectorized in high performance codes. To further increase throughput, new algorithms are needed. We compare a multifrontal sparse solver to a traditional skyline solver in a finite element code on a vector supercomputer. The multifrontal solver uses the Multiple-Minimum Degree reordering heuristic to reduce the number of operations required to factor a sparse matrix and full matrix computational kernels (e.g., BLAS3) to enhance vector performance. The net result in an order-of-magnitude reduction in run time for a finite element application on one processor of a Cray X-MP.

King, Scott D.↗

Heuristic Area Cost Estimation for Observational Coverage Schedulers

This paper presents a comparison of heuris- tics used to estimate the amount of time it would take for a spacecraft to image an area using Boustrophedon decomposition (Choset and Pignon 1998). Machine learning tech- niques are used to characterize algorithmic performance of coverage algorithms. It is shown that an ordinary least-squares linear model is among the most accurate in a set of constant and linear order regression models both in terms of memory consumption and schedule duration. These are demonstrated using the ASPEN planning system (Fukunaga et al. 1997) on the Eagle Eye domain.

Knight, Russell↗

External calibration of polarimetric radar images using distributed targets

A new technique is presented for calibrating polarimetric synthetic aperture radar (SAR) images using only the responses from natural distributed targets. The model for polarimetric radars is assumed to be X = cRST where X is the measured scattering matrix corresponding to the target scattering matrix S distorted by the system matrices T and R (in general T does not equal R(sup t)). To allow for the polarimetric calibration using only distributed targets and corner reflectors, van Zyl assumed a reciprocal polarimetric radar model with T = R(sup t); when applied for JPL SAR data, a heuristic symmetrization procedure is used by POLCAL to compensate the phase difference between the measured HV and VH responses and then take the average of both. This heuristic approach causes some non-removable cross-polarization responses for corner reflectors, which can be avoided by a rigorous symmetrization method based on reciprocity. After the radar is made reciprocal, a new algorithm based on the responses from distributed targets with reflection symmetry is developed to estimate the cross-talk parameters. The new algorithm never experiences problems in convergence and is also found to converge faster than the existing routines implemented for POLCAL. When the new technique is implemented for the JPL polarimetric data, symmetrization and cross-talk removal are performed on a line-by-line (azimuth) basis. After the cross-talks are removed from the entire image, phase and amplitude calibrations are carried out by selecting distributed targets either with azimuthal symmetry along the looking direction or with some well-known volume and surface scattering mechanisms to estimate the relative phases and amplitude responses of the horizontal and vertical channels.

Yueh, Simon H.↗

Dynamic optimization and economic evaluation of flexible heat integration in a hybrid concentrated solar power plant

Hybridization of concentrated solar power (CSP) plants provides flexibility in operation that can drastically improve the solar-to-electric (STE) efficiency and levelized cost of electricity (LCOE) relative to standalone CSP plants. Flexible heat integration (FHI) is a novel concept where the collection and integration of CSP within a power plant is modified relative to the amount of solar energy available. FHI improves the thermal efficiency of a hybrid solar tower steam Rankine cycle power plant but leads to increased pumping needs due to continuously elevated molten salt flow rates through the collection system, which can negatively impact STE efficiency. The present work is carried out to maximize the STE efficiency of a hybrid CSP plant utilizing FHI by employing a dynamic optimization framework where a genetic algorithm optimizes the operation of the plant over a given solar irradiance profile. The study concerns a plant hypothetically located in Salt Lake City, Utah. Here, the optimization results confirm the accuracy of a predictive heuristic where the preferred operation of the plant can be estimated relative to local peaks in the incident power generated by the heliostat collection field. The optimized FHI operation demonstrates a yearly STE efficiency of 13.8%, whereas the equivalent base-level hybrid and solar-only plants exhibit solar efficiencies of 13.4% and 11.2%, respectively. Economic analysis shows that FHI reduces yearly natural gas costs, leading to a $\$0.5$/MWh reduction in LCOE relative to the base-level hybrid configuration. Overall, the results show that hybrid FHI schemes exhibit economic benefits along with observed thermodynamic improvements.

14 SOLAR ENERGY↗

Fuzzy Logic Trajectory Design and Guidance for Terminal Area Energy Management

The second generation reusable launch vehicle will leverage many new technologies to make flight to low earth orbit safer and more cost effective. One important capability will be completely autonomous flight during reentry and landing, thus making it unnecessary to man the vehicle for cargo missions with stringent weight constraints. Implementation of sophisticated new guidance and control methods will enable the vehicle to return to earth under less than favorable conditions. The return to earth consists of three phases--Entry, Terminal Area Energy Management (TAEM), and Approach and Landing. The Space Shuttle is programmed to fly all three phases of flight automatically, and under normal circumstances the astronaut-pilot takes manual control only during the Approach and Landing phase. The automatic control algorithms used in the Shuttle for TAEM and Approach and Landing have been developed over the past 30 years. They are computationally efficient, and based on careful study of the spacecraft's flight dynamics, and heuristic reasoning. The gliding return trajectory is planned prior to the mission, and only minor adjustments are made during flight for perturbations in the vehicle energy state. With the advent of the X-33 and X-34 technology demonstration vehicles, several authors investigated implementing advanced control methods to provide autonomous real-time design of gliding return trajectories thus enhancing the ability of the vehicle to adjust to unusual energy states. The bulk of work published to date deals primarily with the approach and landing phase of flight where changes in heading angle are small, and range to the runway is monotonically decreasing. These benign flight conditions allow for model simplification and fairly straightforward optimization. This project focuses on the TAEM phase of flight where mathematically precise methods have produced limited results. Fuzzy Logic methods are used to make onboard autonomous gliding return trajectory design robust to a wider energy envelope, and the possibility of control surface failures, thus increasing the flexibility of unmanned gliding recovery and landing.

Burchett, Bradley↗

Exploring Network-Related Optimization Problems Using Quantum Heuristics

Network-related connectivity optimization problems are underlying a wide range of applications and are also of high computational complexity. We consider studying network optimization problems using two types of quantum heuristics.One is quantum annealing, and the other Quantum Alternating Operator Ansatz, an extension of the Quantum Approximate Optimization Algorithms for gate-model quantum computation, in which a cost-function based unitary and a non-commuting mixing unitary are applied alternately. We present problem mappings for problems of finding the spanning-tree or spanning-graph of a graph that optimizes certain costs, and a variant that further requires the spanning-tree be degree-bounded. With quantum annealing, all constraints are cast into penalty terms in the cost Hamiltonian, and the solution is encoded as the ground state of the Hamiltonian. We provide three mappings to the quadratic unconstrained binary optimization (QUBO) form, compare the resource requirements, and analyze the tradeoffs. For QAOA, we give special focus on the design of mixers based on the constraints presented in the problem, such that the system evolution remains in a subspace of the full Hilbert space where all constraints are satisfied. In the spanning-tree problem, one such hard constraint is that a mixer applied to a spanning-tree needs also be a spanning tree. This involves checking the connectivity of a subgraph, which is a global condition common for most network-related problems. We show how this feature can be efficiently represented in the mixer in a quantum coherent way, based on manipulation of a descendant-matrix and an adjacent matrix. We further develop a mixer for the spanning-graphs based on the spanning-tree mixer.

Wang, Zhihui↗

Automated problem scheduling and reduction of synchronization delay effects

It is anticipated that in order to make effective use of many future high performance architectures, programs will have to exhibit at least a medium grained parallelism. A framework is presented for partitioning very sparse triangular systems of linear equations that is designed to produce favorable preformance results in a wide variety of parallel architectures. Efficient methods for solving these systems are of interest because: (1) they provide a useful model problem for use in exploring heuristics for the aggregation, mapping and scheduling of relatively fine grained computations whose data dependencies are specified by directed acrylic graphs, and (2) because such efficient methods can find direct application in the development of parallel algorithms for scientific computation. Simple expressions are derived that describe how to schedule computational work with varying degrees of granularity. The Encore Multimax was used as a hardware simulator to investigate the performance effects of using the partitioning techniques presented in shared memory architectures with varying relative synchronization costs.

Saltz, Joel H.↗

Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation

Whittle index policy is a heuristic to the intractable restless multi-armed bandits (RMAB) problem. Although it is provably asymptotically optimal, finding Whittle indices remains difficult. In this paper, we present Neural-Q-Whittle, a Whittle index based Q-learning algorithm for RMAB with neural network function approximation, which is an example of nonlinear two-timescale stochastic approximation with Q-function values updated on a faster timescale and Whittle indices on a slower timescale. Despite the empirical success of deep Q-learning, the non-asymptotic convergence rate of Neural-Q-Whittle, which couples neural networks with two-timescale Q-learning largely remains unclear. This paper provides a finite-time analysis of Neural-Q-Whittle, where data are generated from a Markov chain, and Q-function is approximated by a ReLU neural network. Our analysis leverages a Lyapunov drift approach to capture the evolution of two coupled parameters, and the nonlinearity in value function approximation further requires us to characterize the approximation error. Combing these provide Neural-Q-Whittle with convergence rate, where is the number of iterations.

reinforcement learning, structured learning, conve↗

Syntgen: a system to generate temporal networks with user-specified topology

Abstract In the last few years, the study of temporal networks has progressed markedly. The evolution of clusters of nodes (or communities) is one of the major focus of these studies. However, the time dimension increases complexity, introducing new constructs and requiring novel and enhanced algorithms. In spite of recent improvements, the relative scarcity of timestamped representations of empiric networks, with known ground truth, hinders algorithm validation. A few approaches have been proposed to generate synthetic temporal networks that conform to static topological specifications while in general adopting an ad hoc approach to temporal evolution. We believe there is still a need for a principled synthetic network generator that conforms to problem domain topological specifications from a static as well as temporal perspective. Here, we present such a system. The unique attributes of our system include accepting arbitrary node degree and cluster size distributions and temporal evolution under user control, while supporting tunable joint distribution and temporal correlation of node degrees. Theoretical contributions include the analysis of conditions for graphic sequences of inter- and intracluster node degrees and cluster sizes and the development of a heuristic to search for the cluster membership of nodes that minimizes the shared information distance between clusterings. Our work shows that this system is capable of generating networks under user controlled topology with up to thousands of nodes and hundreds of clusters with strong topology adherence. Much larger networks are possible with relaxed requirements. The generated networks support algorithm validation as well as problem domain analysis.

Pereira, Luis Ramada↗

OPTIMIZATION OF FAST FISSION GAS RELEASE MODEL PARAMETERS USING MACHINE LEARNING ACCELERATED EVOLUTIONARY ALGORITHMS

Fission gas release models used in FRAPCON and FAST are based on equations that describe the physical transport phenomena that control release from the fuel pellet to the rod void volume of fission gas produced during irradiation. Although these models are physically based, many of the parameters that control the release such as the impact of burnup on diffusion and bubble formation and saturation are critical to the accurate prediction of fission gas release, but cannot be measured in any quantitative way. To overcome this problem, these parameters have been empirically derived to provide a best fit to the available data that includes rod puncture data and electron probe microanalysis (EMPA) and X-ray fluorescence (XRF) data of radial location of residual gas within the pellet. In general, a heuristic approach for deriving these parameters via practical implementation of expert analyses on just a few dependent variables has been shown to perform quite well in most situations. In this paper, we present an approach for applying machine learning to expedite model development. This approach is based on developing a deep artificial neural network which describes FRAPCON’s fission gas release models, and optimizes parameters by a differential evaluation algorithm. This approach allows us to quickly and accurately tune physical models based on expert judgment, and works as a human-in-the-loop approach, to assist the modeler in identifying and addressing regions of high uncertainty in a multi-parameter space. Results of the updated fission gas release model will be shown for all the FAST assessment data.

Johns, Jesse M.↗

NEW DIRECTIONS IN RADIOISOTOPE SPECTRUM IDENTIFICATION

Recent studies have found the performance of commercial handheld detectors with automatic RIID software to be less than acceptable. Previously, we have explored approaches rooted in speech processing such as cepstral features and information-theoretic measures. Scientific advances are often made when researchers identify mathematical or physical commonalities between different fields and are able to apply mature techniques or algorithms developed in one field to another field which shares some of the same challenges. The authors of this paper have identified similarities between the unsolved problems faced in gamma-spectroscopy for automated radioisotope identification and the challenges of the much larger body of research in speech processing. Our research has led to a probabilistic framework for describing and solving radioisotope identification problems. Many heuristic approaches to classification in current use, including for radioisotope classification, make implicit probabilistic assumptions which are not clear to the users and, if stated explicitly, might not be considered desirable. Our framework leads to a classification approach with demonstrable improvements using standard feature sets on proof-of-concept simulated and field-collected data.

38 RADIATION CHEMISTRY, RADIOCHEMISTRY, AND NUCLEA↗

Robust pupil center detection using a curvature algorithm

Determining the pupil center is fundamental for calculating eye orientation in video-based systems. Existing techniques are error prone and not robust because eyelids, eyelashes, corneal reflections or shadows in many instances occlude the pupil. We have developed a new algorithm which utilizes curvature characteristics of the pupil boundary to eliminate these artifacts. Pupil center is computed based solely on points related to the pupil boundary. For each boundary point, a curvature value is computed. Occlusion of the boundary induces characteristic peaks in the curvature function. Curvature values for normal pupil sizes were determined and a threshold was found which together with heuristics discriminated normal from abnormal curvature. Remaining boundary points were fit with an ellipse using a least squares error criterion. The center of the ellipse is an estimate of the pupil center. This technique is robust and accurately estimates pupil center with less than 40% of the pupil boundary points visible.

Non-NASA Center↗

Energy-efficient mapping of large-scale workflows under deadline constraints in big data computing systems

Large-scale workflows for big data analytics have become a main consumer of energy in data centers where moldable parallel computing models such as MapReduce are widely applied to meet high computational demands with time-varying computing resources. The granularity of task partitioning in each moldable job of such big data workflows has a significant impact on energy efficiency, which remains largely unexplored. In this paper, we analyze the properties of moldable jobs and formulate a workflow mapping problem to minimize the dynamic energy consumption of a given workflow request under a deadline constraint in big data systems. Since this problem is strongly NP-hard, we design a fully polynomial-time approximation scheme (FPTAS) for a special case with a pipeline-structured workflow on a homogeneous cluster and a heuristic for the generalized problem with an arbitrary workflow on a heterogeneous cluster. The performance superiority of the proposed solution in terms of dynamic energy saving and deadline missing rate is illustrated by extensive simulation results in comparison with existing algorithms, and further validated by real-life workflow implementation and experimental results in Hadoop/YARN systems.

97 MATHEMATICS AND COMPUTING↗

Functional expansion representations of artificial neural networks

In the past few years, significant interest has developed in using artificial neural networks to model and control nonlinear dynamical systems. While there exists many proposed schemes for accomplishing this and a wealth of supporting empirical results, most approaches to date tend to be ad hoc in nature and rely mainly on heuristic justifications. The purpose of this project was to further develop some analytical tools for representing nonlinear discrete-time input-output systems, which when applied to neural networks would give insight on architecture selection, pruning strategies, and learning algorithms. A long term goal is to determine in what sense, if any, a neural network can be used as a universal approximator for nonliner input-output maps with memory (i.e., realized by a dynamical system). This property is well known for the case of static or memoryless input-output maps. The general architecture under consideration in this project was a single-input, single-output recurrent feedforward network.

Gray, W. Steven↗

Optimal Experimental Design With Fast Neural Network Surrogate Models

Designing optimal experiments minimizes the uncertainty of results and maximizes the efficient use of resources. Herein, machine learning surrogate models and the approximate coordinate exchange (ACE) algorithm are used to determine optimum experimental designs over large or arbitrarily restrictive design spaces. Optimal experimental design is particularly salient in materials science where experiments are expensive and material properties must often be inferred indirectly. The proposed framework is demonstrated by finding optimal experiments with which the hidden constituent properties of composite materials can be most efficiently inferred from observable experimental outcomes. The optimum experimental design is given by an information-theoretic criteria, which maximizes the conditional mutual information between the hidden properties and the expected experimental outcomes. To perform tractable optimization a neural network is trained as a surrogate model to mimic a physics based simulation, which can calculate the expected experimental outcome based on a candidate experimental design and sampled constituent properties. The ACE algorithm is used to optimize over large design spaces with many tests and controlled parameters where an exhaustive search would be intractable even with the surrogate model. Using this approach, optimal experimental designs that are consistent with those produced by heuristic knowledge and established best practices are found; then optimal designs in larger design spaces where heuristic knowledge is unavailable are examined.

machine learning↗

Grouper: A Compact, Streamable Triangle Mesh Data Structure

Here, we present Grouper: an all-in-one compact file format, random-access data structure, and streamable representation for large triangle meshes. Similarly to the recently published SQuad representation, Grouper represents the geometry and connectivity of a mesh by grouping vertices and triangles into fixed-size records, most of which store two adjacent triangles and a shared vertex. Unlike SQuad, however, Grouper interleaves geometry with connectivity and uses a new connectivity representation to ensure that vertices and triangles can be stored in a coherent order that enables memory-efficient sequential stream processing. We also present a linear-time construction algorithm that allows streaming out Grouper meshes using a small memory footprint while preserving the initial ordering of vertices. In this construction, we show how the problem of assigning vertices and triangles to groups reduces to a well-known NP-hard optimization problem, and present a simple yet effective heuristic solution that performs well in practice. Our array-based Grouper representation also doubles as a triangle mesh data structure that allows direct access to vertices and triangles. Storing only about two integer references per triangle-i.e., less than the three vertex references stored with each triangle in a conventional indexed mesh format-Grouper answers both incidence and adjacency queries in amortized constant time. Our compact representation enables data-parallel processing on multicore computers, instant partitioning and fast transmission for distributed processing, as well as efficient out-of-core access. We demonstrate the versatility and performance benefits of Grouper using a suite of example meshes and processing kernels.

97 MATHEMATICS AND COMPUTING↗

Iterative pass optimization of sequence data

The problem of determining the minimum-cost hypothetical ancestral sequences for a given cladogram is known to be NP-complete. This "tree alignment" problem has motivated the considerable effort placed in multiple sequence alignment procedures. Wheeler in 1996 proposed a heuristic method, direct optimization, to calculate cladogram costs without the intervention of multiple sequence alignment. This method, though more efficient in time and more effective in cladogram length than many alignment-based procedures, greedily optimizes nodes based on descendent information only. In their proposal of an exact multiple alignment solution, Sankoff et al. in 1976 described a heuristic procedure--the iterative improvement method--to create alignments at internal nodes by solving a series of median problems. The combination of a three-sequence direct optimization with iterative improvement and a branch-length-based cladogram cost procedure, provides an algorithm that frequently results in superior (i.e., lower) cladogram costs. This iterative pass optimization is both computation and memory intensive, but economies can be made to reduce this burden. An example in arthropod systematics is discussed. c2003 The Willi Hennig Society. Published by Elsevier Science (USA). All rights reserved.

NASA Discipline Evolutionary Biology↗