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 271 records · Page 15

Adaptive laser link reconfiguration using constraint propagation

This paper describes Harris AI research performed on the Adaptive Link Reconfiguration (ALR) study for Rome Lab, and focuses on the application of constraint propagation to the problem of link reconfiguration for the proposed space based Strategic Defense System (SDS) Brilliant Pebbles (BP) communications system. According to the concept of operations at the time of the study, laser communications will exist between BP's and to ground entry points. Long-term links typical of RF transmission will not exist. This study addressed an initial implementation of BP's based on the Global Protection Against Limited Strikes (GPALS) SDI mission. The number of satellites and rings studied was representative of this problem. An orbital dynamics program was used to generate line-of-site data for the modeled architecture. This was input into a discrete event simulation implemented in the Harris developed COnstraint Propagation Expert System (COPES) Shell, developed initially on the Rome Lab BM/C3 study. Using a model of the network and several heuristics, the COPES shell was used to develop the Heuristic Adaptive Link Ordering (HALO) Algorithm to rank and order potential laser links according to probability of communication. A reduced set of links based on this ranking would then be used by a routing algorithm to select the next hop. This paper includes an overview of Constraint Propagation as an Artificial Intelligence technique and its embodiment in the COPES shell. It describes the design and implementation of both the simulation of the GPALS BP network and the HALO algorithm in COPES. This is described using a 59 Data Flow Diagram, State Transition Diagrams, and Structured English PDL. It describes a laser communications model and the heuristics involved in rank-ordering the potential communication links. The generation of simulation data is described along with its interface via COPES to the Harris developed View Net graphical tool for visual analysis of communications networks. Conclusions are presented, including a graphical analysis of results depicting the ordered set of links versus the set of all possible links based on the computed Bit Error Rate (BER). Finally, future research is discussed which includes enhancements to the HALO algorithm, network simulation, and the addition of an intelligent routing algorithm for BP.

Crone, M. S.↗

ScaWL: Scaling k-WL (Weisfeiler-Lehman) Algorithms in Memory and Performance on Shared and Distributed-Memory Systems

The k-dimensional Weisfeiler-Lehman (k-WL) algorithm—developed as an efficient heuristic for testing if two graphs are isomorphic—is a fundamental kernel for node embedding in the emerging field of graph neural networks. Unfortunately, the k-WL algorithm has exponential storage requirements, limiting the size of graphs that can be handled. This work presents a novel k-WL scheme with a storage requirement orders of magnitude lower while maintaining the same accuracy as the original k-WL algorithm. Due to the reduced storage requirement, our scheme allows for processing much bigger graphs than previously possible on a single compute node. For even bigger graphs, we provide the first distributed-memory implementation. Our k-WL scheme also has significantly reduced communication volume and offers high scalability. Our experimental results demonstrate that our approach is significantly faster and has superior scalability compared to five other implementations employing state-of-the-art techniques.

algorithims↗

A Parallel Algorithm for the Vehicle Routing Problem

The vehicle routing problem (VRP) is a dicult and well-studied combinatorial optimization problem. We develop a parallel algorithm for the VRP that combines a heuristic local search improvement procedure with integer programming. We run our parallel algorithm with as many as 129 processors and are able to quickly nd high-quality solutions to standard benchmark problems. We assess the impact of parallelism by analyzing our procedure's performance under a number of dierent scenarios.

Groer, Christopher S↗

Optimizing wind farm siting to reduce power system impacts of wind variability

We introduce and solve two variants of a biobjective optimization model to reduce the negative impact of wind variability on the power system by strategically locating wind farms. The first model variant considers average changes in wind power over time; the second captures extreme fluctuations in wind power. A complementary set of wind sites is selected with the aim of minimizing both residual demand and the variability in residual demand. Because exact optimization is computationally intensive, we develop two heuristics—forward and backward greedy algorithms—to find approximate solutions. The results are compared with the exact optimization results for a well-selected subset of the data as well as to the results from selecting sites based on average wind alone. The two models are solved using demand data and potential wind sites for the Southwest Power Pool. Though both objectives can be improved by adding more sites, for a fixed number of sites, minimizing residual demand and variability in residual demand are competing objectives. Here, we find an approximate efficient frontier to compare trade-offs between the two objectives. We also vary the parameter in the heuristic that controls how the two objectives are prioritized. For the case study, the backward greedy algorithm is more effective at reducing the wind power variability than the forward greedy algorithm. Furthermore, using the backward algorithm for the full dataset is more effective than solving the exact optimization on a subset of the data when the results are evaluated using the full dataset.

17 WIND ENERGY↗

A simple levelset contact algorithm for large overlap removal and robust preloads

A simple approach to simulate contact between deformable objects is presented which relies on levelset descriptions of the Lagrangian geometry and an optimization-based solver. Modeling contact between objects remains a significant challenge for computational mechanics simulations. Common approaches are either plagued by lack of robustness or are exceedingly complex and require a significant number of heuristics. In contrast, the levelset contact approach presented herein is essentially heuristic free. Furthermore, the presented algorithm enables resolving and enforcing contact between objects with a significant amount of initial overlap. Examples demonstrating the feasibility of this approach are shown, including the standard Hertz contact problem, the robust removal of overlap between two overlapping blocks, and overlap-removal and pre-load for a bolted configuration.

42 ENGINEERING↗

Avoiding Selection Bias in Generating Examples of Plans in the Presence of Heuristic Error

It is generally understood that heuristic error hurts the performance of search algorithms, measured in terms of search effort. Hence there is an interest in understanding how to reduce heuristic error. One way to do this is to learn a heuristic from a set of examples of plans generated offline, e.g. bootstrapping methods. In this paper, we consider how some methods for generating examples of plans may skew the training set in the presence of heuristic errors. Initial theoretical results show that duplicate detection is one source of selection bias in the canonical A* algorithm. We introduce a duplicate selection scheme for A* that avoids selection bias in generating cost-optimal examples, without compromising memory efficiency, and develop ideas in the satisficing setting. We evaluate our approach on n x m grids with multiple cost-optimal solutions and synthetic heuristic error. Finally, we attempt to extend these ideas to the problem of generating extreme examples of plans.

Alison S Paredes↗

Selecting Observation Platforms for Optimized Anomaly Detectability under Unreliable Partial Observations

Diagnosers for keeping track on the occurrences of special events in the framework of unreliable partially observed discrete-event dynamical systems were developed in previous work. This paper considers observation platforms consisting of sensors that provide partial and unreliable observations and of diagnosers that analyze them. Diagnosers in observation platforms typically perform better as sensors providing the observations become more costly or increase in number. This paper proposes a methodology for finding an observation platform that achieves an optimal balance between cost and performance, while satisfying given observability requirements and constraints. Since this problem is generally computational hard in the framework considered, an observation platform optimization algorithm is utilized that uses two greedy heuristics, one myopic and another based on projected performances. These heuristics are sequentially executed in order to find best observation platforms. The developed algorithm is then applied to an observation platform optimization problem for a multi-unit-operation system. Results show that improved observation platforms can be found that may significantly reduce the observation platform cost but still yield acceptable performance for correctly inferring the occurrences of special events.

97 MATHEMATICS AND COMPUTING↗

New Results on Communication- and Memory-Aware Load Balancing Model and Algorithms

While load balancing in distributed-memory computing has been well-studied, we present an innovative approach to this problem: a unified, reduced-order model that combines three key components to describe “work” in a distributed system: computation, communication, and memory. Our model enables an optimizer to explore complex tradeoffs in task placement, such as augmented parallelism, at the expense of data replication increasing memory usage. We propose a fully distributed, heuristic-based load balancing optimization algorithm, and demonstrate that it quickly finds close-to-optimal solutions. We formalize the complex optimization problem as a mixed-integer linear program, and compare it to our strategy. Finally, we show that when applied to an electromagnetics code, our approach obtains up to 2.3x speedups for the imbalanced execution.

97 MATHEMATICS AND COMPUTING↗

Optimal Integration of Departures and Arrivals in Terminal Airspace

Coordination of operations with spatially and temporally shared resources, such as route segments, fixes, and runways, improves the efficiency of terminal airspace management. Problems in this category are, in general, computationally difficult compared to conventional scheduling problems. This paper presents a fast time algorithm formulation using a non-dominated sorting genetic algorithm (NSGA). It was first applied to a test problem introduced in existing literature. An experiment with a test problem showed that new methods can solve the 20 aircraft problem in fast time with a 65% or 440 second delay reduction using shared departure fixes. In order to test its application in a more realistic and complicated problem, the NSGA algorithm was applied to a problem in LAX terminal airspace, where interactions between 28% of LAX arrivals and 10% of LAX departures are resolved by spatial separation in current operations, which may introduce unnecessary delays. In this work, three types of separations - spatial, temporal, and hybrid separations - were formulated using the new algorithm. The hybrid separation combines both temporal and spatial separations. Results showed that although temporal separation achieved less delay than spatial separation with a small uncertainty buffer, spatial separation outperformed temporal separation when the uncertainty buffer was increased. Hybrid separation introduced much less delay than both spatial and temporal approaches. For a total of 15 interacting departures and arrivals, when compared to spatial separation, the delay reduction of hybrid separation varied between 11% or 3.1 minutes and 64% or 10.7 minutes corresponding to an uncertainty buffer from 0 to 60 seconds. Furthermore, as a comparison with the NSGA algorithm, a First-Come-First-Serve based heuristic method was implemented for the hybrid separation. Experiments showed that the results from the NSGA algorithm have 9% to 42% less delay than the heuristic method with varied uncertainty buffer sizes.

terminal airspace↗

Adaptive continuity-preserving simplification of street networks

While street network data are nearly universally available, their representation is usually transportation-based. However, for many types of analyses, e.g., urban morphology or network science, unprocessed transportation-based street network data is unsuitable, making a cumbersome manual simplification process necessary. To address this challenge, in this paper we propose an algorithm for simplification of street networks, based on the detection of network portions that need to be simplified, and continuity-preserving heuristics that generate new geometries. The algorithm, released in the open-source Python package neatnet, facilitates the generation of morphological networks and generalises to various geographical contexts without a need to alter the parameters, while offering better performance than other available solutions.

Fleischmann, Martin [Charles University, Prague, C↗

Promise of Graph Sparsification and Decomposition for Noise Reduction in QAOA: Analysis for Trapped-Ion Compilations

We develop new approximate compilation schemes that significantly reduce the expense of compiling the Quantum Approximate Optimization Algorithm (QAOA) for solving the Max-Cut problem. Our main focus is on compilation with trapped-ion simulators using Pauli-X operations and all-to-all Ising Hamiltonian HIsing evolution generated by Molmer-Sorensen or optical dipole force interactions, though some of our results also apply to standard gate-based compilations. Our results are based on principles of graph sparsification and decomposition; the former reduces the number of edges in a graph while maintaining its cut structure, while the latter breaks a weighted graph into a small number of unweighted graphs. Though these techniques have been used as heuristics in various hybrid quantum algorithms, there have been no guarantees on their performance, to the best of our knowledge. This work provides the first provable guarantees using sparsification and decomposition to improve quantum noise resilience and reduce quantum circuit complexity. For quantum hardware that uses edge-by-edge QAOA compilations, sparsification leads to a direct reduction in circuit complexity. For trapped-ion quantum simulators implementing all-to-all HIsing pulses, we show that for a (1−ϵ) factor loss in the Max-Cut approximation (ϵ>0), our compilations improve the (worst-case) number of HIsing pulses from O(n2) to O(nlog(n/ϵ)) and the (worst-case) number of Pauli-X bit flips from O(n2) to O(nlog(n/ϵ)ϵ2) for n-node graphs. This is an asymptotic improvement for any constant ϵ>0. We demonstrate that significant improvements to the approximation ratio are obtained using decomposition in simulated trapped-ion experiments with dephasing noise. We further present a generic argument showing that sparsification results in an exponentially improved circuit fidelity lower bound in digital computing schemes based on one- and two-qubit gates, which are relevant to a wide variety of hardwares such as superconducting qubits and certain neutral atom or trapped ion setups, and more sophisticated noise models. We anticipate these approximate compilation techniques will be useful tools in a variety of future quantum computing experiments.

Moondra, Jai [Georgia Institute of Technology]↗

An evaluation of low-cost heuristics for matrix bandwidth and profile reductions

Hundreds of heuristics have been proposed to resolve the problems of bandwidth and profile reductions since the 1960s. We found 132 heuristics that have been applied to these problems in reviews of the literature. Among them, 14 were selected for which no other simulation or comparison revealed that the heuristic could be superseded by any other algorithm in the analyzed articles with respect to bandwidth or profile reduction. We also considered the computational costs of the heuristics during this process. Therefore, these 14 heuristics were selected as potentially being the best low-cost methods to solve the bandwidth and/or profile reduction problems. Results of the 14 selected heuristics are evaluated in this work. For evaluation on the set of test problems, a metric based on the relative percentage distance to the best possible bandwidth or profile is proposed. The most promising heuristics for several application areas are identified. Moreover, it was found that the FNCHC and GPS heuristics showed the best overall results in reducing the bandwidth of symmetric and asymmetric matrices among the evaluated heuristics, respectively. In addition, the NSloan and MPG heuristics showed the best overall results in reducing the profile of symmetric and asymmetric matrices among the heuristics among the evaluated heuristics, respectively.

97 MATHEMATICS AND COMPUTING↗

Ridge-Valley Graphs: Combinatorial Ridge Detection Using Jacobi Sets

Ridges are one of the key feature of interest in areas such as computer vision and image processing. Even though a significant amount of research has been directed to defining and extracting ridges some fundamental challenges remain. For example, the most popular ridge definition (height ridge) is not invariant under monotonic transformations and its global structure is typically ignored during numerical computations. Furthermore, many existing algorithm are based on numerical heuristics and are rarely guaranteed to produce consistent results. In this paper a small change to the height ridge definition gives a definition that is consistent with the desired invariants. Nevertheless, we show that this definition results in similar structures compared to the most common traditional approach and that both formulations are equivalent for quadratic functions. Furthermore, this definition can be cast in the form of a degenerate Jacobi set, which allows insights into the global structure of ridges. In particular, we introduce the Ridge-Valley graph as the complete description of all ridges in an image. Analyzing this graph reveals similar invariants to those found for traditional ridge formulations, such as the fact that ridges do not merge. Finally, using the connection to Jacobi sets we describe a new combinatorial algorithm to extract the Ridge-Valley graph from sampled images that is guaranteed to produce a valid structure.

97 MATHEMATICS AND COMPUTING↗

Parallel Algorithms for Efficient Computation of High-Order Line Graphs of Hypergraphs

This paper considers structures of systems beyond dyadic (pairwise) interactions and investigates mathematical modeling of multi-way interactions and connections as hypergraphs, where captured relationships among system entities are set-valued. To date, in most situations, entities in a hypergraph are considered connected as long as there is at least one common ``neighbor''. However, minimal commonality sometimes discards the ``strength'' of connections and interactions among groups. To this end, considering the ``width'' of a connection, referred to as the \emph{$s$-overlap} of neighbors, provides more meaningful insights into how closely the communities or entities interact with each other. In addition, $s$-overlap computation is the fundamental kernel to construct the line graph of a hypergraph, a low-order approximation of the hypergraph which can carry significant information about the original hypergraph. Subsequent stages of a data analytics pipeline then can apply highly-tuned graph algorithms on the line graph to reveal important features. Given a hypergraph, computing the $s$-overlaps by exhaustively considering all pairwise entities can be computationally prohibitive. To tackle this challenge, we develop efficient algorithms to compute $s$-overlaps and the corresponding line graph of a hypergraph. We propose several heuristics to avoid execution of redundant work and improve performance of the $s$-overlap computation. Our parallel algorithm, combined with these heuristics, is orders of magnitude (more than $10\times$) faster than the naive algorithm in all cases and the SpGEMM algorithm with filtration in most cases (especially with large $s$ value).

hypergraph algorithms, graph algorithms, parallel ↗

End-to-end protocol for high-quality quantum approximate optimization algorithm parameters with few shots

The quantum approximate optimization algorithm (QAOA) is a quantum heuristic for combinatorial optimization that has been demonstrated to scale better than state-of-the-art classical solvers for some problems. For a given problem instance, QAOA performance depends crucially on the choice of the parameters. While average-case optimal parameters are available in many cases, meaningful performance gains can be obtained by fine-tuning these parameters for a given instance. This task is especially challenging, however, when the number of circuit executions (shots) is limited. In this work, we develop an end-to-end protocol that combines multiple parameter settings and fine-tuning techniques. We use large-scale numerical experiments to optimize the protocol for the shot-limited setting and observe that optimizers with the simplest internal model (linear) perform best. We implement the optimized pipeline on a trapped-ion processor using up to 32 qubits and 5 QAOA layers, and we demonstrate that the pipeline is robust to small amounts of hardware noise. To the best of our knowledge, these are the largest demonstrations of QAOA parameter fine-tuning on a trapped-ion processor in terms of two-qubit gate count.

quantum algorithms & computation↗

Heuristic Sonification Methods for Electromagnetic Signals Report

Sonification algorithms convert information to audible representations. The 2025 Seed Money project “Exploring Electromagnetic Signals through Sonification” seeks to create machine-learning based methods to convert electromagnetic signals to sound for human interpretation. However, as a precursor to ML-based methods, some heuristic methods have been investigated in preparation for the seed project. This report covers some example methods, applied to the “Flaming Moes” dataset of unintended radiative emissions (URE), with some simple metrics to study the device discrimination properties of the sonification as well as the “pleasantness” of the methods.

42 ENGINEERING↗

SQUARE: Strategic Quantum Ancilla Reuse for Modular Quantum Programs via Cost-Effective Uncomputation

Compiling high-level quantum programs to machines that are size constrained (i.e. limited number of quantum bits) and time constrained (i.e. limited number of quantum operations) is challenging. In this paper, we present SQUARE (Strategic QUantum Ancilla REuse), a compilation infrastructure that tackles allocation and reclamation of scratch qubits (called ancilla) in modular quantum programs. At its core, SQUARE strategically performs uncomputation to create opportunities for qubit reuse. Current Noisy Intermediate-Scale Quantum (NISQ) computers and forward-looking Fault-Tolerant (FT) quantum computers have fundamentally different constraints such as data locality, instruction parallelism, and communication overhead. Our heuristic-based ancilla-reuse algorithm balances these considerations and fits computations into resource-constrained NISQ or FT quantum machines, throttling parallelism when necessary. To precisely capture the workload of a program, we propose an improved metric, the "active quantum volume," and use this metric to evaluate the effectiveness of our algorithm. Furthermore, our results show that SQUARE improves the average success rate of NISQ applications by 1.47X. Surprisingly, the additional gates for uncomputation create ancilla with better locality, and result in substantially fewer swap gates and less gate noise overall. SQUARE also achieves an average reduction of 1.5X (and up to 9.6X) in active quantum volume for FT machines.

compiler optimization↗

Mota Mapper: A Multi-Objective Topology-Aware Mapper Library

Mota is a library that provides several heuristics for mapping tasks to compute ranks (processes) on a networked computer cluster or supercomputer. It was originally designed for task placement of adaptive mesh refinement codes (AMR). It is multi-objective in the sense that it simultaneously balances (potentially multiple types of) computational load on each rank as well as the communication traffic between the boxes. The heuristics used for mapping include algorithms such as greedy list assignment and space-filling curves, as well as algorithms from graph analysis such as adjacency matrix bandwidth reduction, recursive bisection, and greedy graph placement.

Chan, Cy↗