SEARCH · Search NASA

Results for “greedy 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 73 records · Page 4

All sources NASA NTRS DOE OSTI

DOE OSTI2019

Physics-Informed CoKriging: A Gaussian-Process-Regression-Based Multifidelity Method for Data-Model Convergence

In this work, we propose a new Gaussian process regression (GPR)-based multifidelity method: physics-informed CoKriging (CoPhIK). In CoKriging-based multifidelity methods, the quantities of interest are modeled as linear combinations of multiple parameterized stationary Gaussian processes (GPs), and the hyperparameters of these GPs are estimated from data via optimization. In CoPhIK, we construct a GP representing low-fidelity data using physics-informed Kriging (PhIK), and model the discrepancy between low- and highfidelity data using a parameterized GP with hyperparameters identified via optimization. Our approach reduces the cost of optimization for inferring hyperparameters by incorporating partial physical knowledge. We prove that the physical constraints in the form of deterministic linear operators are satisfied up to an error bound. Furthermore, we combine CoPhIK with a greedy active learning algorithm for guiding the selection of additional observation locations. The eciency and accuracy of CoPhIK are demonstrated for reconstructing the partially observed modified Branin function, reconstructing the sparsely observed state of a steady state heat transport problem, and learning a conservative tracer distribution from sparse tracer concentration measurements.

Yang, Xiu↗

DOE OSTI2016

TH-EF-BRB-07: Novel Hardware and Software Platform for Intermediate Energy 4π Radiotherapy

Purpose: To develop a robust and efficient platform for the optimization and robotic delivery of highly noncoplanar intensity modulated radiotherapy, which enables significant reduction of normal tissue toxicity and escalation of tumor dose. Methods: An innovative high-output compact 3 MV linac was designed for mounting onto a commercial robotic system in order to access the entire 4π beam solution space without moving the patient couch. The use of intermediate energy X-rays for radiotherapy was evaluated in comparison to clinical plans delivered using 6 MV X-rays and a state-of-the-art delivery system. Monte Carlo simulations of a 3 MV percent depth dose curve were performed for intermediate energy dose calculation. The beam model was used to create a convolution/superposition-based dose calculation engine for 3MV X-rays. The 4π greedy column generation algorithm was used for optimized beam selection and fluence map optimization. Results: A detailed design of the first 3 MV linac capable of producing a competitively high dose rate of >800 cGy/min at 100 cm was completed and verified through extensive simulation. The complete linac head including a multileaf collimator can access most of the 4π solution space including the posterior orientations without changing the couch height. When compared to 6 MV clinical plans, the proposed 3 MV 4π plans demonstrated significantly better dose compactness and normal tissue sparing in brain, prostate, and partial breast treatment plans. Conclusion: We demonstrate the design of a highly versatile radiotherapy machine to natively deliver non-coplanar 4π radiotherapy without the need to move the patient during treatment. This novel platform is efficient and capable of providing dosimetry that is 30–50% more compact than existing therapy platforms. The new system is projected to be cost effective due to improved treatment time and automation. NIH R43CA183390, NIH R01CA188300.

60 APPLIED LIFE SCIENCES↗

DOE OSTI2023

Adaptive estimation of quantum observables

The accurate estimation of quantum observables is a critical task in science. With progress on the hardware, measuring a quantum system will become increasingly demanding, particularly for variational protocols that require extensive sampling. Here, we introduce a measurement scheme that adaptively modifies the estimator based on previously obtained data. Our algorithm, which we call AEQuO, continuously monitors both the estimated average and the associated error of the considered observable, and determines the next measurement step based on this information. We allow both for overlap and non-bitwise commutation relations in the subsets of Pauli operators that are simultaneously probed, thereby maximizing the amount of gathered information. AEQuO comes in two variants: a greedy bucket-filling algorithm with good performance for small problem instances, and a machine learning-based algorithm with more favorable scaling for larger instances. The measurement configuration determined by these subroutines is further post-processed in order to lower the error on the estimator. We test our protocol on chemistry Hamiltonians, for which AEQuO provides error estimates that improve on all state-of-the-art methods based on various grouping techniques or randomized measurements, thus greatly lowering the toll of measurements in current and future quantum applications.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2020

Submodular optimization problems and greedy strategies: A survey

The greedy strategy is an approximation algorithm to solve optimization problems arising in decision making with multiple actions. How effective is the greedy strategy compared to the optimal solution? In this survey, we mainly consider two classes of optimization problems where the objective function is submodular. The first is set submodular optimization, which is to choose a set of actions to optimize a set submodular objective function, and the second is string submodular optimization, which is to choose an ordered set of actions to optimize a string submodular function. Our emphasis here is on performance bounds for the greedy strategy in submodular optimization problems. Specifically, we review performance bounds for the greedy strategy, more general and improved bounds in terms of curvature, performance bounds for the batched greedy strategy, and performance bounds for Nash equilibria.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Cholesky-based experimental design for Gaussian process and kernel-based emulation and calibration.

Gaussian processes and other kernel-based methods are used extensively to construct approximations of multivariate data sets. The accuracy of these approximations is dependent on the data used. This paper presents a computationally efficient algorithm to greedily select training samples that minimize the weighted L p error of kernel-based approximations for a given number of data. The method successively generates nested samples, with the goal of minimizing the error in high probability regions of densities specified by users. The algorithm presented is extremely simple and can be implemented using existing pivoted Cholesky factorization methods. Training samples are generated in batches which allows training data to be evaluated (labeled) in parallel. For smooth kernels, the algorithm performs comparably with the greedy integrated variance design but has significantly lower complexity. Numerical experiments demonstrate the efficacy of the approach for bounded, unbounded, multi-modal and non-tensor product densities. We also show how to use the proposed algorithm to efficiently generate surrogates for inferring unknown model parameters from data using Bayesian inference.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2023

gLaSDI: Parametric physics-informed greedy latent space dynamics identification

A parametric adaptive physics-informed greedy Latent Space Dynamics Identification (gLaSDI) method is proposed for accurate, efficient, and robust data-driven reduced-order modeling of high-dimensional nonlinear dynamical systems. In the proposed gLaSDI framework, an autoencoder discovers intrinsic nonlinear latent representations of high-dimensional data, while dynamics identification (DI) models capture local latent-space dynamics. Here, an interactive training algorithm is adopted for the autoencoder and local DI models, which enables identification of simple latent-space dynamics and enhances accuracy and efficiency of data-driven reduced-order modeling. To maximize and accelerate the exploration of the parameter space for the optimal model performance, an adaptive greedy sampling algorithm integrated with a physics-informed residual-based error indicator and random-subset evaluation is introduced to search for the optimal training samples on the fly. Further, to exploit local latent-space dynamics captured by the local DI models for an improved modeling accuracy with a minimum number of local DI models in the parameter space, a -nearest neighbor convex interpolation scheme is employed. The effectiveness of the proposed framework is demonstrated by modeling various nonlinear dynamical problems, including Burgers equations, nonlinear heat conduction, and radial advection. The proposed adaptive greedy sampling outperforms the conventional predefined uniform sampling in terms of accuracy. Compared with the high-fidelity models, gLaSDI achieves 17 to 2,658× speed-up with 1 to 5% relative errors.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2023

A greedy Galerkin method to efficiently select sensors for linear dynamical systems

A key challenge in inverse problems is the selection of sensors to gather the most effective data. In this paper, we consider the problem of inferring the initial condition to a linear dynamical system and develop an efficient control-theoretical approach for greedily selecting sensors. Our method employs a Galerkin projection to reduce the size of the inverse problem, resulting in a computationally efficient algorithm for sensor selection. As a byproduct of our algorithm, we obtain a preconditioner for the inverse problem that enables the rapid recovery of the initial condition. Here, we analyze the theoretical performance of our greedy sensor selection algorithm as well as the performance of the associated preconditioner. Finally, we verify our theoretical results on various inverse problems involving partial differential equations.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2025

Domain Decomposition for Integer Optimal Control with Total Variation Regularization

Total variation integer optimal control problems admit solutions and necessary optimality conditions via geometric variational analysis. In spite of the existence of said solutions, algorithms which solve the discretized objective suffer from high numerical cost associated with the combinatorial nature of integer programming. Hence, such methods are often limited to small and medium-sized problems. We propose a globally convergent, coordinate descent–inspired algorithm that allows tractable subproblem solutions restricted to a partition of the domain. Our decomposition method solves relatively small trust-region subproblems that modify the control variable on a subdomain only. Given nontrivial subdomain overlap, we prove that a global first-order necessary optimality condition is equivalent to a first-order necessary optimality condition per subdomain. We additionally show that a sufficient decrease is achieved on a single subdomain by way of a trust-region subproblem solver using geometric measure–theoretic arguments, which we integrate with a greedy patch selection to prove convergence of our algorithm. In conclusion, we demonstrate the practicality of our algorithm on a benchmark large-scale, PDE-constrained integer optimal control problem and find that our method is faster than the state of the art.

domain decomposition↗

DOE OSTI2024

Comparison of Real-Time Pressure Rail Selection Algorithms for the Hybrid Hydraulic Electric Architecture: Case Study on a Track Loader

Abstract The hybrid hydraulic electric architecture (HHEA) seeks to combine the high power/torque/force density of hydraulics with the efficiency of electric machines. A set of common pressure rails is used to provide a majority of the power and this power is modulated by small electric machines to provide precise control for the operator. The HHEA has been studied in previous work using off-line dynamic programming optimization to determine energy efficient pressure rail selections, but this approach requires drive cycle information apriori. A Lagrange multiplier method has also been investigated where a set of gains (Lagrange multipliers) are optimized off-line with the idea the these gains, once determined, could be used for real-time operation. In this work, three new real-time pressure rail selection algorithms that do not require future drive cycle information are investigated; greedy, torque minimizing, and thresholding. The greedy control is found to only use 1% more energy than the globally optimal dynamic programming solution; but a model of energy loss is required.

24 POWER TRANSMISSION AND DISTRIBUTION↗

DOE OSTI2025

Bayesian Optimized Deep Ensemble for Uncertainty Quantification of Deep Neural Networks: a System Safety Case Study on Sodium Fast Reactor Thermal Stratification Modeling

Deep neural networks (DNNs) are increasingly important to scientific computing and engineering system simulations. Accurate uncertainty quantification (UQ) for DNNs is critical in safety-sensitive engineering domains. Traditional Deep Ensemble (DE) methods, while easy to implement, frequently suffer from poorly calibrated uncertainty estimates and limited predictive accuracy due to reliance on fixed architectures with varied weight initializations. To address these issues, we introduce a workflow that combines Bayesian Optimization (BO) and DE. The workflow is modular, scalable, and integrates parallel BO initialized with Sobol sequences to individually optimize the hyperparameters of each ensemble member. This method enhances ensemble diversity, improves predictive accuracy, and provides reliable uncertainty estimates. We evaluate the proposed BODE approach in a sodium fast reactor thermal stratification modeling case study, where we used a densely connected convolutional neural network to predict turbulent viscosity during the reactor transient with consideration of data noise. We benchmark its performance against several optimization approaches, including baseline deep ensemble, evolutionary algorithm-optimized ensemble, ensemble formed via random search combined with greedy selection, and a BO ensemble using random initialization. Here, our results demonstrate superior performance of the developed BODE approach. In noise-free scenarios, BODE notably reduces incorrect aleatoric uncertainty and significantly enhances predictive accuracy. Under conditions of 5% and 10% Gaussian noise, BODE adaptively quantifies uncertainty proportional to data noise, achieving up to an 80% reduction in root mean square error compared to baseline methods and producing well-calibrated prediction intervals.

Bayesian optimization↗

DOE OSTI2018

Local rewiring algorithms to increase clustering and grow a small world

Abstract Many real-world networks have high clustering among vertices: vertices that share neighbours are often also directly connected to each other. A network’s clustering can be a useful indicator of its connectedness and community structure. Algorithms for generating networks with high clustering have been developed, but typically rely on adding or removing edges and nodes, sometimes from a completely empty network. Here, we introduce algorithms that create a highly clustered network by starting with an existing network and rearranging edges, without adding or removing them; these algorithms can preserve other network properties even as the clustering increases. They rely on local rewiring rules, in which a single edge changes one of its vertices in a way that is guaranteed to increase clustering. This greedy step can be applied iteratively to transform a random network into a form with much higher clustering. Additionally, the algorithms presented grow a network’s clustering faster than they increase its path length, meaning that network enters a regime of comparatively high clustering and low path length: a small world. These algorithms may be a basis for how real-world networks rearrange themselves organically to achieve or maintain high clustering and small-world structure.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2024

Optimizing the location and configuration of disaster resilience hubs under transportation and electric power network failures

Natural disasters often result in failures of transportation network components and blackouts that imperil the wellbeing of vulnerable populations. In response to these events, resilience hubs have been proposed as a pre-disaster planning strategy to improve access to critical services. This paper introduces an optimization-based approach to locate and configure electric power-generating resilience hubs considering the possibility of failures in transportation and electric power systems. The model's objective is to identify hub locations and configurations that maximize transportation accessibility to the hubs and maximize the satisfaction of basic energy needs through hub-generated electric power. Besides a budget constraint, the model accounts for limits on the levels of hub energy generation vis-à-vis community energy demands, and on the transportation network distance of communities to hubs. Three heuristics are presented for the proposed planning problem. The first heuristic is a genetic algorithm (GA) with problem-specific solution generation procedures. The other two heuristics implement greedy search techniques. Numerical experiments were conducted, using data from rural Puerto Rico, to illustrate the application of the proposed model and heuristics, and examine their performance. In the numerical experiments, the GA heuristic found better solutions than the greedy heuristics. Additionally, design solutions consisting of spatially dispersed hubs with low energy generation capacity were better than solutions with spatially concentrated high-capacity hubs. Lastly, across a wide range of hub demand scenarios, only a small number of candidate hub locations consistently ranked among the best locations for establishing a hub.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

DOE OSTI2025

Artificial intelligence driven laser parameter search: Inverse design of photonic surfaces using greedy surrogate-based optimization

Photonic surfaces designed with specific optical characteristics are becoming increasingly crucial for novel energy harvesting and storage systems. The design of these surfaces can be achieved by texturing materials using lasers. The optimal adjustment of laser fabrication parameters to achieve target surface optical properties is an open challenge. Thus, we develop a surrogate-based optimization approach. Our framework employs the Random Forest algorithm to model the forward relationship between the laser fabrication parameters and the resulting optical characteristics. During the optimization process, we use a greedy, prediction-based exploration strategy that iteratively selects batches of laser parameters to be used in experimentation by minimizing the predicted discrepancy between the surrogate model’s outputs and the user-defined target optical characteristics. This strategy allows for efficient identification of optimal fabrication parameters without the need to model the error landscape directly. We demonstrate the efficiency and effectiveness of our approach on two synthetic benchmarks and two specific experimental applications of photonic surface inverse design targets. By calculating the average performance of our algorithm compared to other state of the art optimization methods, we show that our algorithm performs, on average, twice as well across all benchmarks. Additionally, a warm starting inverse design technique for changed target optical characteristics enhances the performance of the introduced approach.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2018

Impala: A Flexible Adaptive Sampling Algorithm for Active Learning

The Implicit Potential Active Learning Algorithm, or impala, is a novel approach to adaptive sampling that allows for the blending of multiple independent query strategies into a common batch active learning framework. This methodology is agnostic to both the underlying learning model and the employed query strategies. In essence, impala treats query strategies as potential functions, which are combined into a probability of candidate selection. The end result is a flexible algorithm that can dynamically balance exploration and exploitation whose inherent variability guards against over-zealous greedy searching.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2016

TH-EF-BRB-05: 4pi Non-Coplanar IMRT Beam Angle Selection by Convex Optimization with Group Sparsity Penalty

Purpose: Integrated beam orientation and fluence map optimization is expected to be the foundation of robust automated planning but existing heuristic methods do not promise global optimality. We aim to develop a new method for beam angle selection in 4π non-coplanar IMRT systems based on solving (globally) a single convex optimization problem, and to demonstrate the effectiveness of the method by comparison with a state of the art column generation method for 4π beam angle selection. Methods: The beam angle selection problem is formulated as a large scale convex fluence map optimization problem with an additional group sparsity term that encourages most candidate beams to be inactive. The optimization problem is solved using an accelerated first-order method, the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA). The beam angle selection and fluence map optimization algorithm is used to create non-coplanar 4π treatment plans for several cases (including head and neck, lung, and prostate cases) and the resulting treatment plans are compared with 4π treatment plans created using the column generation algorithm. Results: In our experiments the treatment plans created using the group sparsity method meet or exceed the dosimetric quality of plans created using the column generation algorithm, which was shown superior to clinical plans. Moreover, the group sparsity approach converges in about 3 minutes in these cases, as compared with runtimes of a few hours for the column generation method. Conclusion: This work demonstrates the first non-greedy approach to non-coplanar beam angle selection, based on convex optimization, for 4π IMRT systems. The method given here improves both treatment plan quality and runtime as compared with a state of the art column generation algorithm. When the group sparsity term is set to zero, we obtain an excellent method for fluence map optimization, useful when beam angles have already been selected. NIH R43CA183390, NIH R01CA188300, Varian Medical Systems; Part of this research took place while D. O’Connor was a summer intern at RefleXion Medical.

60 APPLIED LIFE SCIENCES↗

DOE OSTI2018

Non-algorithmic Capability Gaps for CYCLUS and CYCAMORE Transition Analyses

As part of NEUP-FY16-10512, fuel cycle transition scenarios were simulated using CYCLUS and existing CYCAMORE archetypes. The purpose of this paper is to identify current non-algorithmic gaps in the capabilities necessary for key transition scenarios. The gaps identified through this exercise mainly pertain to the greedy exchange model, and the manual, static parameter of fuel cycle facilities. The scenarios are from the Idaho National Laboratory Nuclear Fuel Cycle Evaluation and Screening Report (Hereby E&S Report). The transition scenarios begin with EG01 and transition to EG23, EG24, EG29, EG30, separately.

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

DOE OSTI2025

Enabling Real-Time Communication in Multi-Agent Systems: A Graph Neural Network Based Approach

Global connectivity enables effective coordination in Multi-Agent Systems (MAS). Solving these connection problems under hardware constraints is an NP-hard non-Euclidean Degree Constrained Minimum Spanning Tree (DCMST) problem. Prior MAS controllers coordinate team movement for task completion and collision avoidance; some considering Line-of-Sight (LOS) maintenance but prioritizing flexibility over guarantees. Evolutionary Algorithms (EA) have been shown to find good solutions for DCMST, but their performance degrades with larger populations required to support a large MAS. We present a method based on edge graph attention networks, trained offline to reduce online computation times. Empirical comparisons with greedy polynomial-time solvers and EA show that our method leverages latent graph information to consistently find constraint-satisfying solutions in less time.

connectivity maintenance↗

DOE OSTI2019

A Tutorial on the Synthesis and Validation of a Closed-Loop Wind Farm Controller Using a Steady-State Surrogate Model

In wind farms, wake interaction leads to losses in power capture and accelerated structural degradation when compared to freestanding turbines. One method to reduce wake losses is by misaligning the rotor with the incoming flow using its yaw actuator, thereby laterally deflecting the wake away from downstream turbines. However, this demands an accurate and computationally tractable model of the wind farm dynamics. This problem calls for a closed-loop solution. This tutorial paper fills the scientific gap by demonstrating the full closed-loop controller synthesis cycle using a steady-state surrogate model. Furthermore, a novel, computationally efficient and modular communication interface is presented that enables researchers to straight-forwardly test their control algorithms in large-eddy simulations. High-fidelity simulations of a 9-turbine farm show a power production increase of up to 11% using the proposed closed-loop controller compared to traditional, greedy wind farm operation.

17 WIND ENERGY↗