Search NASA⌕ Search

SEARCH · Search NASA

Results for “Heuristic Optimization”

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 253 records · Page 14
All sourcesNASA NTRSDOE OSTI
NASA NTRS2013

NASA Tech Briefs, May 2013

Topics include: Test Waveform Applications for JPL STRS Operating Environment; Pneumatic Proboscis Heat-Flow Probe; Method to Measure Total Noise Temperature of a Wireless Receiver During Operation; Cursor Control Device Test Battery; Functional Near-Infrared Spectroscopy Signals Measure Neuronal Activity in the Cortex; ESD Test Apparatus for Soldering Irons; FPGA-Based X-Ray Detection and Measurement for an X-Ray Polarimeter; Sequential Probability Ratio Test for Spacecraft Collision Avoidance Maneuver Decisions; Silicon/Carbon Nanotube Photocathode for Splitting Water; Advanced Materials and Fabrication Techniques for the Orion Attitude Control Motor; Flight Hardware Packaging Design for Stringent EMC Radiated Emission Requirements; RF Reference Switch for Spaceflight Radiometer Calibration; An Offload NIC for NASA, NLR, and Grid Computing; Multi-Scale CNT-Based Reinforcing Polymer Matrix Composites for Lightweight Structures; Ceramic Adhesive and Methods for On-Orbit Repair of Re-Entry Vehicles; Self-Healing Nanocomposites for Reusable Composite Cryotanks; Pt-Ni and Pt-Co Catalyst Synthesis Route for Fuel Cell Applications; Aerogel-Based Multilayer Insulation with Micrometeoroid Protection; Manufacturing of Nanocomposite Carbon Fibers and Composite Cylinders; Optimized Radiator Geometries for Hot Lunar Thermal Environments; A Mission Concept: Re-Entry Hopper-Aero-Space-Craft System on-Mars (REARM-Mars); New Class of Flow Batteries for Terrestrial and Aerospace Energy Storage Applications; Reliability of CCGA 1152 and CCGA 1272 Interconnect Packages for Extreme Thermal Environments; Using a Blender to Assess the Microbial Density of Encapsulated Organisms; Mixed Integer Programming and Heuristic Scheduling for Space Communication; Video Altimeter and Obstruction Detector for an Aircraft; Control Software for Piezo Stepping Actuators; Galactic Cosmic Ray Event-Based Risk Model (GERM) Code; Sasquatch Footprint Tool; and Multi-User Space Link Extension (SLE) System.

Source record↗
NASA NTRS2019

High-Performance Computing Optimization for Aladyn – Adaptive Neural Network Molecular Dynamics Mini-Application

This report provides a description and performance evaluation of the optimization techniques for high performance computing (HPC) implementation of the open source Computational Materials mini-application Aladyn (https://github.com/nasa/aladyn). Aladyn is a basic molecular dynamics code written in FORTRAN 2003, which is designed to demonstrate the use of adaptive neural networks (ANNs) in atomistic simulations. The role of ANNs is to efficiently reproduce the very complex energy landscape resulting from the atomic interactions in materials with the accuracy of the more expensive quantum mechanics-based calculations. The ANN is trained on a large set of atomic structures calculated using the density functional theory (DFT) method. While achieving orders of magnitude faster computational performance than DFT, the ANN-based approach was still very computationally demanding compared to the conventional approach of using empirically fitted energy functions. After its initial development, Aladyn was evaluated and optimized by experts at the NASA Advanced Supercomputing (NAS) division to exploit modern supercomputer architectures. The code has been optimized for execution on multicore central processing units (CPUs), including Intel® Skylake microarchitecture, and on graphic accelerators, such as Nvidia® V100 graphic processing units (GPUs), using Open Multi-Processing (OpenMP) and Open Accelerators (OpenACC) programming interfaces. The optimization achieved a speedup of 4.7 times the baseline version on CPU performance and an additional 2.4 times on CPU+GPU performance. Atomistic computer simulations are a fundamental tool in materials research to model material properties form physics-based first principles. Atomic interaction, governed by Quantum Mechanics (QM) require sophisticated and highly computationally demanding mathematical models to calculate [1]. Classical methods use approximate functional forms, empirically fitted through a set of variable parameters to emulate atomic energies as direct functions of atomic coordinates [2]. While empirical potentials are computationally much simpler, allowing simulations of large-scale systems of up to a trillion (1012) atoms [3], they are substantially less accurate compared to quantum calculations and applicable only to very specific atomic configurations or predefined crystallographic phases. A recently suggested approach is to use heuristic machine learning methods [4], such as those based on Adaptive Neural Networks (ANNs) to predict atomic energies, after being trained on a sufficiently large database of QM-calculated structures [5,6]. This approach reduces significantly the computational complexity, allowing for simulations of orders of magnitude larger systems compared to QM-based methods without compromising accuracy. Still, compared to classical methods using empirical energy functions, ANN methods remain two- to three orders of magnitude more computationally demanding. Hence, the computational cost of simulations, together with the need for extensive training of ANNs, still makes the practical implementation of ANN-based methods quite challenging. The purpose of the Aladyn mini-application software [7], available as open source at https://github.com/nasa/aladyn, is to be a testbed for exploring possible optimization strategies to develop highly scalable parallel algorithms for ANN-based atomistic simulations. Aladyn is aimed at utilizing the architecture of the high-end modern highperformance computing (HPC) hardware based on multicore central processing units (CPUs) equipped with graphic processing unit (GPU) accelerators. Specifically, the goal is to optimize the performance on a single HPC compute node, before implementing scaling to multi-node parallelization using message passing interface (MPI). At the same time, the open source code of Aladyn can serve as a training model for students and professors in academia.

Yamakov, Vesselin I.↗
NASA NTRS1988

Experiences with serial and parallel algorithms for channel routing using simulated annealing

Two algorithms for channel routing using simulated annealing are presented. Simulated annealing is an optimization methodology which allows the solution process to back up out of local minima that may be encountered by inappropriate selections. By properly controlling the annealing process, it is very likely that the optimal solution to an NP-complete problem such as channel routing may be found. The algorithm presented proposes very relaxed restrictions on the types of allowable transformations, including overlapping nets. By freeing that restriction and controlling overlap situations with an appropriate cost function, the algorithm becomes very flexible and can be applied to many extensions of channel routing. The selection of the transformation utilizes a number of heuristics, still retaining the pseudorandom nature of simulated annealing. The algorithm was implemented as a serial program for a workstation, and a parallel program designed for a hypercube computer. The details of the serial implementation are presented, including many of the heuristics used and some of the resulting solutions.

Brouwer, Randall Jay↗
NASA NTRS1990

An engineering approach to automatic programming

An exploratory study of the automatic generation and optimization of symbolic programs using DECOM - a prototypical requirement specification model implemented in pure LISP was undertaken. It was concluded, on the basis of this study, that symbolic processing languages such as LISP can support a style of programming based upon formal transformation and dependent upon the expression of constraints in an object-oriented environment. Such languages can represent all aspects of the software generation process (including heuristic algorithms for effecting parallel search) as dynamic processes since data and program are represented in a uniform format.

Rubin, Stuart H.↗
NASA NTRS1997

Optimizing Aerobot Exploration of Venus

Venus Flyer Robot (VFR) is an aerobot; an autonomous balloon probe designed for remote exploration of Earth's sister planet in 2003. VFR's simple navigation and control system permits travel to virtually any location on Venus, but it can survive for only a limited duration in the harsh Venusian environment. To help address this limitation, we develop: (1) a global circulation model that captures the most important characteristics of the Venusian atmosphere; (2) a simple aerobot model that captures thermal restrictions faced by VFR at Venus; and (3) one exact and two heuristic algorithms that, using abstractions (1) and (2), construct routes making the best use of VFR's limited lifetime. We demonstrate this modeling by planning several small example missions and a prototypical mission that explores numerous interesting sites recently documented in the plane tary geology literature.

SPACE EXPLORATION↗
DOE OSTI2024

Heuristic solutions to the single depot electric vehicle scheduling problem with next day operability constraints

This study focuses on the single depot electric vehicle scheduling problem (SDEVSP) within the broader context of the vehicle scheduling problem (VSP). By developing an effective scheduling model using mixed-integer linear programming, we generate bus blocks that accommodate electric vehicles (EVs), ensuring successful completion of each block while considering recharging requirements between blocks and during off-hours. Next day operability constraints are also incorporated, allowing for seamless repetition of blocks on subsequent days. The SDEVSP is known to be computationally complex, deriving optimal solutions unattainable for large-scale problems within reasonable timeframes. To address this, we propose a two-step solution approach: first solving the single depot VSP, and then addressing the block chaining problem (BCP) using the blocks generated in the first step. The BCP focuses on optimizing block combinations to facilitate recharging between consecutive blocks, considering operational constraints. Further, a case study conducted reveals that nearly 100% electrification for Chicago, IL and Austin, TX transit buses is viable yet requires 1.6 EVs at 150-mile range per diesel vehicle.

33 ADVANCED PROPULSION SYSTEMS↗
DOE OSTI2025

Optimization of a Mixed Fleet of Aerial Drones for Medical Supplies: A Case Study of Blood Delivery Logistics

Aerial drones have emerged as an innovative solution for faster transportation of time-sensitive items (e.g., emergency medical supplies), potentially reducing the transmission of contagious diseases and enhancing healthcare availability through contactless autonomous delivery. We study fleet sizing and efficient scheduling of a mixed fleet of drones for delivering time-sensitive medical items having distinct release and due times to minimize the required fleet size and fleet composition, the required number of additional batteries, and the total energy consumption. We continuously track the remaining battery energy of drones to determine the optimal timing for battery replacement, rather than replacing the battery at each node. Using actual drone flight test data, we employed a machine learning (ML) method to estimate the energy consumption of different drone types during flight segments for different operating parameters. We present a novel mixed-integer programming model to efficiently formulate the problem that integrates the estimated energy consumption functions from ML. We propose a new greedy heuristic (GH) algorithm and a customized genetic algorithm (GA) for solving large-scale instances of this problem faster. Results demonstrate that the GH algorithm is substantially faster than the accelerated CPLEX and the GA, while sacrificing the solution quality by a small amount. Results based on an actual blood sample delivery case study from Pendleton, Oregon, United States, show that using a mixed fleet of drones reduces the total cost and total energy consumption up to 18.18% and 28.7%, respectively, compared to using a homogeneous fleet.

29 - ENERGY PLANNING, POLICY AND ECONOMY↗
NASA NTRS2017

Sensitivity Analysis and Uncertainty Quantification of a Mars Ascent Vehicle Concept

The design of a conceptual Mars ascent vehicle is a challenging problem. In order to aid the vehicle and mission concept design it is important to understand the driving design parameters and the expected performance in the presence of model errors and uncertainties. An existing six degree of freedom simulation model is analyzed on a statistical basis using the methods available in the Design Analysis Kit for Optimization and Terascale Applications toolkit. The methods utilized include conventional Monte Carlo techniques, metamodeling via polynomial chaos expansions, and global variance-based sensitivity analyses. Two additional analysis methods referred to as “Monte Carlo filtering” and ”Classification trees” are used to determine which uncertain parameters are driving the performance of the vehicle. Monte Carlo filtering provides a methodology to determine which parameters cause qualitatively different behavior while the classification trees use heuristics to partition the input space and assign probabilities to each partition. These methods serve as qualitative descriptors of model sensitivity while variance-based global sensitivity analysis seeks a quantitative mapping from total output variance to the variance of individual inputs. Application of these techniques to several outputs of a Mars ascent vehicle concept simulation indicates that only a select few input factors dominate their variance.

Noyes, Connor↗
DOE OSTI2024

High-Throughput Microstructural Characterization and Process Correlation Using Automated Electron Backscatter Diffraction

The need to optimize the processing conditions of additively manufactured (AM) metals and alloys has driven advances in throughput capabilities for material property measurements such as tensile strength or hardness. High-throughput (HT) characterization of AM metal microstructure has fallen significantly behind the pace of property measurements due to intrinsic bottlenecks associated with the artisan and labor-intensive preparation methods required to produce highly polished surfaces. This inequality in data throughput has led to a reliance on heuristics to connect process to structure or structure to properties for AM structural materials. In this study, we show a transformative approach to achieve laser powder bed fusion (LPBF) printing, HT preparation using dry electropolishing and HT electron backscatter diffraction (EBSD). This approach was used to construct a library of > 600 experimental EBSD sample sets spanning a diverse range of LPBF process conditions for AM Kovar. This vast library is far more expansive in parameter space than most state-of-the-art studies, yet it required only approximately 10 labor hours to acquire. Build geometries, surface preparation methods, and microscopy details, as well as the entire library of >600 EBSD data sets over the two sample design versions, have been shared with intent for the materials community to leverage the data and further advance the approach. Using this library, we investigated process–structure relationships and uncovered an unexpected, strong dependence of microstructure on location within the build, when varied, using otherwise identical laser parameters.

Characterization and Analytical Technique↗
DOE OSTI2025

FedEFsz: Fair Cross-Silo Federated Learning System With Error-Bounded Lossy Compression

Cross-Silo federated learning systems have been identified as an efficient approach to scaling DNN training across geographically-distributed data silos to preserve the privacy of the training data. Communication efficiency and fairness are two major issues that need to be both satisfied when federated learning systems are deployed in practice. Simultaneously guaranteeing both of them, however, is exceptionally difficult because simply combining communication reduction and fairness optimization approaches often causes non-converged training or drastic accuracy degradation. Here, to bridge this gap, we propose FedEFsz. On the one hand, it integrates the state-of-the-art error-bounded lossy compressor SZ3 into cross-silo federated learning systems to significantly reduce communication traffic during the training. On the other hand, it achieves a high fairness (i.e., rather consistent model accuracy and performance across different clients) through a carefully designed heuristic algorithm that can tune the error-bound of SZ3 for different clients during the training. Extensive experimental results based on a GPU cluster with 65 GPU cards show that FedEFsz improves the fairness across different benchmarks by up to 60.88% and meanwhile reduces the communication traffic by up to 315×.

Cross-Silo Federated Learning Systems↗
NASA NTRS2016

Exact and Heuristic Algorithms for Runway Scheduling

This paper explores the Single Runway Scheduling (SRS) problem with arrivals, departures, and crossing aircraft on the airport surface. Constraints for wake vortex separations, departure area navigation separations and departure time window restrictions are explicitly considered. The main objective of this research is to develop exact and heuristic based algorithms that can be used in real-time decision support tools for Air Traffic Control Tower (ATCT) controllers. The paper provides a multi-objective dynamic programming (DP) based algorithm that finds the exact solution to the SRS problem, but may prove unusable for application in real-time environment due to large computation times for moderate sized problems. We next propose a second algorithm that uses heuristics to restrict the search space for the DP based algorithm. A third algorithm based on a combination of insertion and local search (ILS) heuristics is then presented. Simulation conducted for the east side of Dallas/Fort Worth International Airport allows comparison of the three proposed algorithms and indicates that the ILS algorithm performs favorably in its ability to find efficient solutions and its computation times.

safe & surface operations↗
DOE OSTI2024

Heuristic algorithms for design of integrated monitoring of geologic carbon storage sites

Designs for Risk Evaluation and Management (DREAM) is a tool developed under the National Risk Assessment Partnership (NRAP) to enhance geologic carbon storage safety and efficiency. Using potential leakage scenarios generated externally by the users preferred history-matching approach, DREAM constructs ideal combinations of sensor locations in the right place at the right time to detect as many leaks as possible, detect them as early as possible, and minimize cost. This user-friendly tool, developed in Java, features a window-based GUI for input and a 3D visualization tool for viewing the domain space and optimized monitoring plans. DREAM's latest version accommodates real-world usage by allowing for joint optimization of wellbore point sensor placements and surface geophysics survey geometries, and by using more efficient multi-objective optimization algorithms. We show an example where, these two improvements combined allow us to support containment assurance and go from detecting 80–90 % of the potential CO 2 leakage to +99.7 %, a step-change improvement that can make the deciding difference in whether a site is suitable for geologic carbon storage. Though developed for geologic carbon storage, this tool would be equally applicable in many surface or offshore environmental monitoring projects.

58 GEOSCIENCES↗
NASA NTRS2005

At-Least Version of the Generalized Minimum Spanning Tree Problem: Optimization Through Ant Colony System and Genetic Algorithms

The At-Least version of the Generalized Minimum Spanning Tree Problem (L-GMST) is a problem in which the optimal solution connects all defined clusters of nodes in a given network at a minimum cost. The L-GMST is NPHard; therefore, metaheuristic algorithms have been used to find reasonable solutions to the problem as opposed to computationally feasible exact algorithms, which many believe do not exist for such a problem. One such metaheuristic uses a swarm-intelligent Ant Colony System (ACS) algorithm, in which agents converge on a solution through the weighing of local heuristics, such as the shortest available path and the number of agents that recently used a given path. However, in a network using a solution derived from the ACS algorithm, some nodes may move around to different clusters and cause small changes in the network makeup. Rerunning the algorithm from the start would be somewhat inefficient due to the significance of the changes, so a genetic algorithm based on the top few solutions found in the ACS algorithm is proposed to quickly and efficiently adapt the network to these small changes.

Janich, Karl W.↗
NASA NTRS2011

A Simulation Based Approach to Optimize Berth Throughput Under Uncertainty at Marine Container Terminals

Berth scheduling is a critical function at marine container terminals and determining the best berth schedule depends on several factors including the type and function of the port, size of the port, location, nearby competition, and type of contractual agreement between the terminal and the carriers. In this paper we formulate the berth scheduling problem as a bi-objective mixed-integer problem with the objective to maximize customer satisfaction and reliability of the berth schedule under the assumption that vessel handling times are stochastic parameters following a discrete and known probability distribution. A combination of an exact algorithm, a Genetic Algorithms based heuristic and a simulation post-Pareto analysis is proposed as the solution approach to the resulting problem. Based on a number of experiments it is concluded that the proposed berth scheduling policy outperforms the berth scheduling policy where reliability is not considered.

Golias, Mihalis M.↗
NASA NTRS1992

The damper placement problem for large flexible space structures

The damper placement problem for large flexible space truss structures is formulated as a combinatorial optimization problem. The objective is to determine the p truss members of the structure to replace with active (or passive) dampers so that the modal damping ratio is as large as possible for all significant modes of vibration. Equivalently, given a strain energy matrix with rows indexed on the modes and the columns indexed on the truss members, we seek to find the set of p columns such that the smallest row sum, over the p columns, is maximized. We develop a tabu search heuristic for the damper placement problems on the Controls Structures Interaction (CSI) Phase 1 Evolutionary Model (10 modes and 1507 truss members). The resulting solutions are shown to be of high quality.

Kincaid, Rex K.↗
NASA NTRS1990

SURE (Science User Resource Expert): A science planning and scheduling assistant for a resource based environment

SURE (Science User Resource Expert) is one of three components that compose the SURPASS (Science User Resource Planning and Scheduling System). This system is a planning and scheduling tool which supports distributed planning and scheduling, based on resource allocation and optimization. Currently SURE is being used within the SURPASS by the UARS (Upper Atmospheric Research Satellite) SOLSTICE instrument to build a daily science plan and activity schedule and in a prototyping effort with NASA GSFC to demonstrate distributed planning and scheduling for the SOLSTICE II instrument on the EOS platform. For the SOLSTICE application the SURE utilizes a rule-based system. Development of a rule-based program using Ada CLIPS as opposed to using conventional programming, allows for capture of the science planning and scheduling heuristics in rules and provides flexibility in inserting or removing rules as the scientific objectives and mission constraints change. The SURE system's role as a component in the SURPASS, the purpose of the SURE planning and scheduling tool, the SURE knowledge base, and the software architecture of the SURE component are described.

Thalman, Nancy E.↗
NASA NTRS1988

Dynamic remapping of parallel computations with varying resource demands

The issue of deciding when to invoke a global load remapping mechanism is studied. Such a decision policy must effectively weigh the costs of remapping against the performance benefits, and should be general enough to apply automatically to a wide range of computations. The authors propose a general mapping decision heuristic, then study its effectiveness and its anticipated behavior on two very different models of load evolution. Assuming only that the remapping cost is known, this policy dynamically minimizes system degradation (including the cost of remapping) for each computation step. This policy is quite simple, choosing to remap when the first local minimum in the degradation function is detected. Simulations show that the decision obtained provides significantly better performance than that achieved by never remapping. The authors also observe that the average intermapping frequency is quite close to the optimal fixed remapping frequency.

Nicol, David M.↗
NASA NTRS2008

Spline-Based Smoothing of Airfoil Curvatures

Constrained fitting for airfoil curvature smoothing (CFACS) is a splinebased method of interpolating airfoil surface coordinates (and, concomitantly, airfoil thicknesses) between specified discrete design points so as to obtain smoothing of surface-curvature profiles in addition to basic smoothing of surfaces. CFACS was developed in recognition of the fact that the performance of a transonic airfoil is directly related to both the curvature profile and the smoothness of the airfoil surface. Older methods of interpolation of airfoil surfaces involve various compromises between smoothing of surfaces and exact fitting of surfaces to specified discrete design points. While some of the older methods take curvature profiles into account, they nevertheless sometimes yield unfavorable results, including curvature oscillations near end points and substantial deviations from desired leading-edge shapes. In CFACS as in most of the older methods, one seeks a compromise between smoothing and exact fitting. Unlike in the older methods, the airfoil surface is modified as little as possible from its original specified form and, instead, is smoothed in such a way that the curvature profile becomes a smooth fit of the curvature profile of the original airfoil specification. CFACS involves a combination of rigorous mathematical modeling and knowledge-based heuristics. Rigorous mathematical formulation provides assurance of removal of undesirable curvature oscillations with minimum modification of the airfoil geometry. Knowledge-based heuristics bridge the gap between theory and designers best practices. In CFACS, one of the measures of the deviation of an airfoil surface from smoothness is the sum of squares of the jumps in the third derivatives of a cubicspline interpolation of the airfoil data. This measure is incorporated into a formulation for minimizing an overall deviation- from-smoothness measure of the airfoil data within a specified fitting error tolerance. CFACS has been extensively tested on a number of supercritical airfoil data sets generated by inverse design and optimization computer programs. All of the smoothing results show that CFACS is able to generate unbiased smooth fits of curvature profiles, trading small modifications of geometry for increasing curvature smoothness by eliminating curvature oscillations and bumps (see figure).

Li, W.↗