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 379 records · Page 21

Data analytics and optimization of an ice-based energy storage system for commercial buildings

Ice-based thermal energy storage (TES) systems can shift peak cooling demand and reduce operational energy costs (with time-of-use rates) in commercial buildings. The accurate prediction of the cooling load, and the optimal control strategy for managing the charging and discharging of a TES system, are two critical elements to improving system performance and achieving energy cost savings. This study utilizes data-driven analytics and modeling to holistically understand the operation of an ice–based TES system in a shopping mall, calculating the system’s performance using actual measured data from installed meters and sensors. Results show that there is significant savings potential when the current operating strategy is improved by appropriately scheduling the operation of each piece of equipment of the TES system, as well as by determining the amount of charging and discharging for each day. A novel optimal control strategy, determined by an optimization algorithm of Sequential Quadratic Programming, was developed to minimize the TES system’s operating costs. Three heuristic strategies were also investigated for comparison with our proposed strategy, and the results demonstrate the superiority of our method to the heuristic strategies in terms of total energy cost savings. Specifically, the optimal strategy yields energy costs of up to 11.3% per day and 9.3% per month compared with current operational strategies. A one-day-ahead hourly load prediction was also developed using machine learning algorithms, which facilitates the adoption of the developed data analytics and optimization of the control strategy in a real TES system operation.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

Suppressing Quantum Circuit Errors Due to System Variability

We present a quantum circuit optimization technique that takes into account the variability in error rates that is inherent across present-day noisy quantum computing platforms. This method can be run after qubit routing or postcompilation and consists of computing isomorphic subgraphs to input circuits and scoring each using heuristic cost functions derived from system calibration data. Using an independent standard algorithmic test suite, we show that it is possible to recover on average nearly 40% of missing fidelity using better qubit selection via efficient to compute cost functions. We demonstrate additional performance gains by considering qubit placement over multiple quantum processors. The overhead from these tools is minimal with respect to other compilation steps, such as qubit routing, as the number of qubits increases. As such, our method can be used to find qubit mappings for problems at the scale of quantum advantage and beyond.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

A Scalable Distributed Louvain Algorithm for Large-Scale Graph Community Detection

We present a new distributed community detection algorithm for large graphs based on the Louvain method. We exploit a distributed delegate partitioning to ensure the workload and communication balancing among processors. In addition, we design a new heuristic strategy to carefully coordinate the community constitution in a distributed environment, and ensure the convergence of the distributed clustering algorithm. Our intensive experimental study has demonstrated the scalability and the correctness of our algorithm with various large-scale real-world and synthetic graph datasets using up to 32,768 processors.

Computer Science↗

Hierarchical Clock Synchronization in MPI

We present a new distributed community detection algorithm for large graphs based on the Louvain method. We exploit a distributed delegate partitioning to ensure the workload and communication balancing among processors. In addition, we design a new heuristic strategy to carefully coordinate the community constitution in a distributed environment, and ensure the convergence of the distributed clustering algorithm. Our intensive experimental study has demonstrated the scalability and the correctness of our algorithm with various large-scale real-world and synthetic graph datasets using up to 32,768 processors

Computer Science↗

A Shifted Block Lanczos Algorithm 1: The Block Recurrence

In this paper we describe a block Lanczos algorithm that is used as the key building block of a software package for the extraction of eigenvalues and eigenvectors of large sparse symmetric generalized eigenproblems. The software package comprises: a version of the block Lanczos algorithm specialized for spectrally transformed eigenproblems; an adaptive strategy for choosing shifts, and efficient codes for factoring large sparse symmetric indefinite matrices. This paper describes the algorithmic details of our block Lanczos recurrence. This uses a novel combination of block generalizations of several features that have only been investigated independently in the past. In particular new forms of partial reorthogonalization, selective reorthogonalization and local reorthogonalization are used, as is a new algorithm for obtaining the M-orthogonal factorization of a matrix. The heuristic shifting strategy, the integration with sparse linear equation solvers and numerical experience with the code are described in a companion paper.

Grimes, Roger G.↗

Constrained Graph Optimization: Interdiction and Preservation Problems

The maximum flow, shortest path, and maximum matching problems are a set of basic graph problems that are critical in theoretical computer science and applications. Constrained graph optimization, a variation of these basic graph problems involving modification of the underlying graph, is equally important but sometimes significantly harder. In particular, one can explore these optimization problems with additional cost constraints. In the preservation case, the optimizer has a budget to preserve vertices or edges of a graph, preventing them from being deleted. The optimizer wants to find the best set of preserved edges/vertices in which the cost constraints are satisfied and the basic graph problems are optimized. For example, in shortest path preservation, the optimizer wants to find a set of edges/vertices within which the shortest path between two predetermined points is smallest. In interdiction problems, one deletes vertices or edges from the graph with a particular cost in order to impede the basic graph problems as much as possible (for example, delete edges/vertices to maximize the shortest path between two predetermined vertices). Applications of preservation problems include optimal road maintenance, power grid maintenance, and job scheduling, while interdiction problems are related to drug trafficking prevention, network stability assessment, and counterterrorism. Computational hardness results are presented, along with heuristic methods for approximating solutions to the matching interdiction problem. Also, efficient algorithms are presented for special cases of graphs, including on planar graphs. The graphs in many of the listed applications are planar, so these algorithms have important practical implications.

97 MATHEMATICS AND COMPUTING↗

Prosumer-Based Distributed Autonomous Cyber-Physical Architecture for Ultra-reliable Green Electricity Internetworks

This project, the first of its kind, proposes a new architecture for decentralized management and control of future electricity grids with millions of decision-makers. These economically motivated decision-makers are called prosumers (producer-consumers). Prosumers can produce, consume, and/or store electricity and make strategic decisions enabled by communication networks. Prosumers can be as large as a utility or as small as an electric vehicle or a smart house with a home energy management system. The report first provides an impression of the functionality envisioned in prosumer-based smart grids and the philosophy behind their design. The architecture is intended to provide a platform for many possibilities in service definition and trading. The functionality of the architecture is identified by functional and non-functional requirements related to decentralized control and optimization. In this report, three key technologies are proposed for enabling distributed operation and control in prosumer-based smart grids. The first technology is a cyber-infrastructure model, which provides an underlying framework for distributed communication and computation in smart grids. The model is based on service-oriented computing paradigm and is compatible with the existing service-oriented technologies, used in enterprise computing, such as Web Services. However, it extends these technologies for handling the hard-to-predict real-time aspects of smart grids by introducing resource-aware service deployment and quality-of-service (QoS)-aware service monitoring phases. The second technology is a distributed frequency regulation (DFR) framework, which can ensure midterm frequency stability while avoiding inter-area oscillations and using a limited control effort. DFR can complement today’s Automatic Generation Control (AGC) systems by providing an advanced protocol for coordination between AGC systems of different prosumers. The main advantage of the DFR technology is that each frequency regulator only needs to communicate with its neighbors in the network. The efficacy of DFR is shown through simulations on real-world electric energy systems of different scale and complexity. The third technology introduced in this project is decentralized unit commitment (DUC) for heterogeneous prosumers. The DUC technology is a new scalable method for formulating and solving a distributed energy scheduling problem. The algorithm extends the alternating direction method of multipliers (ADMM) and includes several heuristics to mitigate oscillations and traps in local optimality that result from the nonconvexity of unit commitment. The main advantages of DUC is that it can solve the unit commitment problem for large-scale power systems of more than 3,000 nodes faster than the state-of-the-art, centralized methods, and that it is scalable to energy scheduling problems of prosumer systems of any size. In summary, this report illustrates that the distributed architecture for prosumer-based power grids is an enabler of transforming aging power grids into sustainable, resilient, reliable, and efficient smart grids with some desirable functionalities similar to the Internet.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Dynamic Load Balancing Based on Constrained K-D Tree Decomposition for Parallel Particle Tracing

Particle tracing is a fundamental technique in flow field data visualization. In this work, we present a novel dynamic load balancing method for parallel particle tracing. Specifically, we employ a constrained k-d tree decomposition approach to dynamically redistribute tasks among processes. Each process is initially assigned a regularly partitioned block along with duplicated ghost layer under the memory limit. During particle tracing, the k-d tree decomposition is dynamically performed by constraining the cutting planes in the overlap range of duplicated data. This ensures that each process is reassigned particles as even as possible, and on the other hand the new assigned particles for a process always locate in its block. Result shows good load balance and high efficiency of our method.

Zhang, Jiang↗

Iterative procedures for space shuttle main engine performance models

Performance models of the Space Shuttle Main Engine (SSME) contain iterative strategies for determining approximate solutions to nonlinear equations reflecting fundamental mass, energy, and pressure balances within engine flow systems. Both univariate and multivariate Newton-Raphson algorithms are employed in the current version of the engine Test Information Program (TIP). Computational efficiency and reliability of these procedures is examined. A modified trust region form of the multivariate Newton-Raphson method is implemented and shown to be superior for off nominal engine performance predictions. A heuristic form of Broyden's Rank One method is also tested and favorable results based on this algorithm are presented.

Santi, L. Michael↗

Data-centric framework for crystal structure identification in atomistic simulations using machine learning

Atomic-level modeling performed at large scales enables the investigation of mesoscale materials properties with atom-by-atom resolution. The spatial complexity of such cross-scale simulations renders them unsuitable for simple human visual inspection. Instead, specialized structure characterization techniques are required to aid interpretation. These have historically been challenging to construct, requiring significant intuition and effort. Here we propose an alternative framework for a fundamental structural characterization task: classifying atoms according to the crystal structure to which they belong. Our approach is data-centric and favors the employment of Machine Learning over heuristic rules of classification. A group of data-science tools and simple local descriptors of atomic structure are employed together with an efficient synthetic training set. We also introduce the first standard and publicly available benchmark data set for evaluation of algorithms for crystal-structure classification. Further, it is demonstrated that our data-centric framework outperforms all of the most popular heuristic methods—especially at high temperatures when lattices are the most distorted—while introducing a systematic route for generalization to new crystal structures. Moreover, through the use of outlier detection algorithms our approach is capable of discerning between amorphous atomic motifs (i.e., noncrystalline phases) and unknown crystal structures, making it uniquely suited for exploratory materials synthesis simulations.

36 MATERIALS SCIENCE↗

An ILP based Algorithm for Optimal Customer Selection for Demand Response in SmartGrids

Demand Response (DR) events are initiated by utilities during peak demand periods to curtail consumption. They ensure system reliability and minimize the utility’s expenditure. Selection of the right customers and strategies is critical for a DR event. An effective DR scheduling algorithm minimizes the curtailment error which is the absolute difference between the achieved curtailment value and the target. State-of-the-art heuristics exist for customer selection, however their curtailment errors are unbounded and can be as high as 70%. In this work, we develop an Integer Linear Programming (ILP) formulation for optimally selecting customers and curtailment strategies that minimize the curtailment error during DR events in SmartGrids. We perform experiments on real world data obtained from the University of Southern California’s SmartGrid and show that our algorithm achieves near exact curtailment values with errors in the range of 10 -7 to 10 -5 , which are within the range of numerical errors. We compare our results against the state-of-the-art heuristic being deployed in practice in the USC SmartGrid. We show that for the same set of available customer strategy pairs our algorithm performs 103 to 107 times better in terms of the curtailment errors incurred.

97 MATHEMATICS AND COMPUTING↗

Efficient tree decomposition of high-rank tensors [Efficient decomposition of high-rank tensors]

Tensors are a natural way to express correlations among many physical variables, but storing tensors in a computer naively requires memory which scales exponentially in the rank of the tensor. This is not optimal, as the required memory is actually set not by the rank but by the mutual information amongst the variables in question. Representations such as the tensor tree perform near-optimally when the tree decomposition is chosen to reflect the correlation structure in question, but making such a choice is non-trivial and good heuristics remain highly context-specific. In this work I present two new algorithms for choosing efficient tree decompositions, independent of the physical context of the tensor. The first is a brute-force algorithm which in most cases produces optimal decompositions but is generally impractical for high-rank tensors, as the number of possible choices grows exponentially in rank. Here, the second is a greedy algorithm, and while it is not optimal it performs extremely well in numerical experiments while having runtime which makes it practical even for tensors of very high rank.

97 MATHEMATICS AND COMPUTING↗

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.↗

Fast and Accurate Support Vector Machines on Large Scale Systems

Support Vector Machines (SVM) is a supervised Machine Learning and Data Mining (MLDM) algorithm, which has become ubiquitous largely due to its high accuracy and obliviousness to dimensionality. The objective of SVM is to find an optimal boundary --- also known as hyperplane --- which separates the samples (examples in a dataset) of different classes by a maximum margin. Usually, very few samples contribute to the definition of the boundary. However, existing parallel algorithms use the entire dataset for finding the boundary, which is sub-optimal for performance reasons. In this paper, we propose a novel distributed memory algorithm to eliminate the samples which do not contribute to the boundary definition in SVM. We propose several heuristics, which range from early (aggressive) to late (conservative) elimination of the samples, such that the overall time for generating the boundary is reduced considerably. In a few cases, a sample may be eliminated (shrunk) pre-emptively --- potentially resulting in an incorrect boundary. We propose a scalable approach to synchronize the necessary data structures such that the proposed algorithm maintains its accuracy. We consider the necessary trade-offs of single/multiple synchronization using in-depth time-space complexity analysis. We implement the proposed algorithm using MPI and compare it with libsvm--- de facto sequential SVM software --- which we enhance with OpenMP for multi-core/many-core parallelism. Our proposed approach shows excellent efficiency using up to 4096 processes on several large datasets such as UCI HIGGS Boson dataset and Offending URL dataset.

Vishnu, Abhinav↗

Computational Tools and Algorithms for Designing Customized Synthetic Genes

Advances in DNA synthesis have enabled the construction of artificial genes, gene circuits, and genomes of bacterial scale. Freedom in de novo design of synthetic constructs provides significant power in studying the impact of mutations in sequence features, and verifying hypotheses on the functional information that is encoded in nucleic and amino acids. To aid this goal, a large number of software tools of variable sophistication have been implemented, enabling the design of synthetic genes for sequence optimization based on rationally defined properties. The first generation of tools dealt predominantly with singular objectives such as codon usage optimization and unique restriction site incorporation. Recent years have seen the emergence of sequence design tools that aim to evolve sequences toward combinations of objectives. The design of optimal protein-coding sequences adhering to multiple objectives is computationally hard, and most tools rely on heuristics to sample the vast sequence design space. In this review, we study some of the algorithmic issues behind gene optimization and the approaches that different tools have adopted to redesign genes and optimize desired coding features. We utilize test cases to demonstrate the efficiency of each approach, as well as identify their strengths and limitations.

60 APPLIED LIFE SCIENCES↗

Algorithm to solve a chance-constrained network capacity design problem with stochastic demands and finite support

Here, we consider the problem of determining the capacity to assign to each arc in a given network, subject to uncertainty in the supply and/or demand of each node. This design problem underlies many real-world applications, such as the design of power transmission and telecommunications networks. We first consider the case where a set of supply/demand scenarios are provided, and we must determine the minimum-cost set of arc capacities such that a feasible flow exists for each scenario. We briefly review existing theoretical approaches to solving this problem and explore implementation strategies to reduce run times. With this as a foundation, our primary focus is on a chance-constrained version of the problem in which α% of the scenarios must be feasible under the chosen capacity, where α is a user-defined parameter and the specific scenarios to be satisfied are not predetermined. We describe an algorithm which utilizes a separation routine for identifying violated cut-sets which can solve the problem to optimality, and we present computational results. We also present a novel greedy algorithm, our primary contribution, which can be used to solve for a high quality heuristic solution. We present computational analysis to evaluate the performance of our proposed approaches.

97 MATHEMATICS AND COMPUTING↗

Hyper-Heuristics to Automatically Target Code to Computer Architectures

With each new generation of High Performance Computing (HPC) architecture, the gap between peak theoretical performance and the observed performance is growing. The goal of this research is to develop a tool to utilize hyper-heuristics to target code to a computational environment. In order to test this, sorting algorithms will be evolved on several different architectures. The final solutions will then migrate to all other architectures and their fitnesses compared. If the natively-evolved algorithms out-perform all others, then it can be concluded that the tool successfully targeted its solutions to the architecture of origin. This is the first step towards creating a program-agnostic tool for optimizing code to the native environment. The results are pending testing on the high performance cluster. If it can be shown that the tool is able to optimize solutions for the environment, then the door opens to automatically optimizing entire programs.

97 MATHEMATICS AND COMPUTING↗

Tools of the Future: How Decision Tree Analysis Will Impact Mission Planning

The universe is infinitely complex; however, the human mind has a finite capacity. The multitude of possible variables, metrics, and procedures in mission planning are far too many to address exhaustively. This is unfortunate because, in general, considering more possibilities leads to more accurate and more powerful results. To compensate, we can get more insightful results by employing our greatest tool, the computer. The power of the computer will be utilized through a technology that considers every possibility, decision tree analysis. Although decision trees have been used in many other fields, this is innovative for space mission planning. Because this is a new strategy, no existing software is able to completely accommodate all of the requirements. This was determined through extensive research and testing of current technologies. It was necessary to create original software, for which a short-term model was finished this summer. The model was built into Microsoft Excel to take advantage of the familiar graphical interface for user input, computation, and viewing output. Macros were written to automate the process of tree construction, optimization, and presentation. The results are useful and promising. If this tool is successfully implemented in mission planning, our reliance on old-fashioned heuristics, an error-prone shortcut for handling complexity, will be reduced. The computer algorithms involved in decision trees will revolutionize mission planning. The planning will be faster and smarter, leading to optimized missions with the potential for more valuable data.

Otterstatter, Matthew R.↗