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 397 records · Page 22

PySP : modeling and solving stochastic mixed-integer programs in Python.

Although stochastic programming is a powerful tool for modeling decision-making under uncertainty, various impediments have historically prevented its widespread use. One key factor involves the ability of non-specialists to easily express stochastic programming problems as extensions of deterministic models, which are often formulated first. A second key factor relates to the difficulty of solving stochastic programming models, particularly the general mixed-integer, multi-stage case. Intricate, configurable, and parallel decomposition strategies are frequently required to achieve tractable run-times. We simultaneously address both of these factors in our PySP software package, which is part of the COIN-OR Coopr open-source Python project for optimization. To formulate a stochastic program in PySP, the user specifies both the deterministic base model and the scenario tree with associated uncertain parameters in the Pyomo open-source algebraic modeling language. Given these two models, PySP provides two paths for solution of the corresponding stochastic program. The first alternative involves writing the extensive form and invoking a standard deterministic (mixed-integer) solver. For more complex stochastic programs, we provide an implementation of Rockafellar and Wets Progressive Hedging algorithm. Our particular focus is on the use of Progressive Hedging as an effective heuristic for approximating general multi-stage, mixed-integer stochastic programs. By leveraging the combination of a high-level programming language (Python) and the embedding of the base deterministic model in that language (Pyomo), we are able to provide completely generic and highly configurable solver implementations. PySP has been used by a number of research groups, including our own, to rapidly prototype and solve difficult stochastic programming problems.

99 GENERAL AND MISCELLANEOUS↗

Parallel Heuristics for Scalable Community Detection

Community detection has become a fundamental operation in numerous graph-theoretic applications. It is used to reveal natural divisions that exist within real world networks without imposing prior size or cardinality constraints on the set of communities. Despite its potential for application, there is only limited support for community detection on large-scale parallel computers, largely owing to the irregular and inherently sequential nature of the underlying heuristics. In this paper, we present parallelization heuristics for fast community detection using the Louvain method as the serial template. The Louvain method is an iterative heuristic for modularity optimization. Originally developed by Blondel et al. in 2008, the method has become increasingly popular owing to its ability to detect high modularity community partitions in a fast and memory-efficient manner. However, the method is also inherently sequential, thereby limiting its scalability to problems that can be solved on desktops. Here, we observe certain key properties of this method that present challenges for its parallelization, and consequently propose multiple heuristics that are designed to break the sequential barrier. Our heuristics are agnostic to the underlying parallel architecture. For evaluation purposes, we implemented our heuristics on shared memory (OpenMP) and distributed memory (MapReduce-MPI) machines, and tested them over real world graphs derived from multiple application domains (internet, biological, natural language processing). Experimental results demonstrate the ability of our heuristics to converge to high modularity solutions comparable to those output by the serial algorithm in nearly the same number of iterations, while also drastically reducing time to solution.

clustering, graph algorithms↗

A majorization-minimization approach to design of power distribution networks

We consider optimization approaches to design cost-effective electrical networks for power distribution. This involves a trade-off between minimizing the power loss due to resistive heating of the lines and minimizing the construction cost (modeled by a linear cost in the number of lines plus a linear cost on the conductance of each line). We begin with a convex optimization method based on the paper 'Minimizing Effective Resistance of a Graph' [Ghosh, Boyd & Saberi]. However, this does not address the Alternating Current (AC) realm and the combinatorial aspect of adding/removing lines of the network. Hence, we consider a non-convex continuation method that imposes a concave cost of the conductance of each line thereby favoring sparser solutions. By varying a parameter of this penalty we extrapolate from the convex problem (with non-sparse solutions) to the combinatorial problem (with sparse solutions). This is used as a heuristic to find good solutions (local minima) of the non-convex problem. To perform the necessary non-convex optimization steps, we use the majorization-minimization algorithm that performs a sequence of convex optimizations obtained by iteratively linearizing the concave part of the objective. A number of examples are presented which suggest that the overall method is a good heuristic for network design. We also consider how to obtain sparse networks that are still robust against failures of lines and/or generators.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Adaptive control and noise suppression by a variable-gain gradient algorithm

An adaptive control system based on normalized LMS filters is investigated. The finite impulse response of the nonparametric controller is adaptively estimated using a given reference model. Specifically, the following issues are addressed: The stability of the closed loop system is analyzed and heuristically established. Next, the adaptation process is studied for piecewise constant plant parameters. It is shown that by introducing a variable-gain in the gradient algorithm, a substantial reduction in the LMS adaptation rate can be achieved. Finally, process noise at the plant output generally causes a biased estimate of the controller. By introducing a noise suppression scheme, this bias can be substantially reduced and the response of the adapted system becomes very close to that of the reference model. Extensive computer simulations validate these and demonstrate assertions that the system can rapidly adapt to random jumps in plant parameters.

Merhav, S. J.↗

Scalable Parallel Methods for Analyzing Metagenomics Data at Extreme Scale

The field of bioinformatics and computational biology is currently experiencing a data revolution. The exciting prospect of making fundamental biological discoveries is fueling the rapid development and deployment of numerous cost-effective, high-throughput next-generation sequencing technologies. The result is that the DNA and protein sequence repositories are being bombarded with new sequence information. Databases are continuing to report a Moore’s law-like growth trajectory in their database sizes, roughly doubling every 18 months. In what seems to be a paradigm-shift, individual projects are now capable of generating billions of raw sequence data that need to be analyzed in the presence of already annotated sequence information. While it is clear that data-driven methods, such as sequencing homology detection, are becoming the mainstay in the field of computational life sciences, the algorithmic advancements essential for implementing complex data analytics at scale have mostly lagged behind. Sequence homology detection is central to a number of bioinformatics applications including genome sequencing and protein family characterization. Given millions of sequences, the goal is to identify all pairs of sequences that are highly similar (or “homologous”) on the basis of alignment criteria. While there are optimal alignment algorithms to compute pairwise homology, their deployment for large-scale is currently not feasible; instead, heuristic methods are used at the expense of quality. In this dissertation, we present the design and evaluation of a parallel implementation for conducting optimal homology detection on distributed memory supercomputers. Our approach uses a combination of techniques from asynchronous load balancing (viz. work stealing, dynamic task counters), data replication, and exact-matching filters to achieve homology detection at scale. Results for a collection of 2.56M sequences show parallel efficiencies of ~75-100% on up to 8K cores, representing a time-to-solution of 33 seconds. We extend this work with a detailed analysis of single-node sequence alignment performance using the latest CPU vector instruction set extensions. Preliminary results reveal that current sequence alignment algorithms are unable to fully utilize widening vector registers.

59 BASIC BIOLOGICAL SCIENCES↗

Distributed Louvain Algorithm for Graph Community Detection

In most real-world networks, the nodes/vertices tend to be organized into tightly-knit modules known as communities or clusters, such that nodes within a community are more likely to be “related” to one another than they are to the rest of the network. The goodness of partitioning into communities is typically measured using a well known measure called modularity. However, modularity optimization is an NP-complete problem. In 2008, Blondel, et al. introduced a multi-phase, iterative heuristic for modularity optimization, called the Louvain method. Owing to its speed and ability to yield high quality communities, the Louvain method continues to be one of the most widely used tools for serial community detection. In this paper, we present the design of a distributed memory implementation of the Louvain algorithm for parallel community detection. Our approach begins with an arbitrarily partitioned distributed graph input, and employs several heuristics to speedup the computation of the different steps of the Louvain algorithm. We evaluate our implementation and its different variants using real-world networks from various application domains (including internet, biology, social networks). Our MPI+OpenMP implementation yields about 7x speedup (on 4K processes) for soc-friendster network (1.8B edges) over a state-of-the-art shared-memory multicore implementation (on 64 threads), without compromising output quality. Furthermore, our distributed implementation was able to process a larger graph (uk-2007; 3.3B edges) in 32 seconds on 1K cores (64 nodes) of NERSC Cori, when the state-of-the-art shared-memory implementation failed to run due to insufficient memory on a single Cori node containing 128 GB.

High performance computing, graph algorithms, Dist↗

Reasoning by analogy as an aid to heuristic theorem proving.

When heuristic problem-solving programs are faced with large data bases that contain numbers of facts far in excess of those needed to solve any particular problem, their performance rapidly deteriorates. In this paper, the correspondence between a new unsolved problem and a previously solved analogous problem is computed and invoked to tailor large data bases to manageable sizes. This paper outlines the design of an algorithm for generating and exploiting analogies between theorems posed to a resolution-logic system. These algorithms are believed to be the first computationally feasible development of reasoning by analogy to be applied to heuristic theorem proving.

Kling, R. E.↗

Search Problems in Mission Planning and Navigation of Autonomous Aircraft

An architecture for the control of an autonomous aircraft is presented. The architecture is a hierarchical system representing an anthropomorphic breakdown of the control problem into planner, navigator, and pilot systems. The planner system determines high level global plans from overall mission objectives. This abstract mission planning is investigated by focusing on the Traveling Salesman Problem with variations on local and global constraints. Tree search techniques are applied including the breadth first, depth first, and best first algorithms. The minimum-column and row entries for the Traveling Salesman Problem cost matrix provides a powerful heuristic to guide these search techniques. Mission planning subgoals are directed from the planner to the navigator for planning routes in mountainous terrain with threats. Terrain/threat information is abstracted into a graph of possible paths for which graph searches are performed. It is shown that paths can be well represented by a search graph based on the Voronoi diagram of points representing the vertices of mountain boundaries. A comparison of Dijkstra's dynamic programming algorithm and the A* graph search algorithm from artificial intelligence/operations research is performed for several navigation path planning examples. These examples illustrate paths that minimize a combination of distance and exposure to threats. Finally, the pilot system synthesizes the flight trajectory by creating the control commands to fly the aircraft.

Krozel, James A.↗

Finding diverse ways to improve algebraic connectivity through multi-start optimization

The algebraic connectivity, also known as the Fiedler value, is a spectral measure of network connectivity that can be increased through edge addition. We present an algorithm for producing many diverse ways to add a fixed number of edges to a network to achieve a near optimal Fiedler value. Previous Fielder value optimization algorithms (i.e. the greedy algorithm) output only one solution. Obtaining a single solution is rarely good enough for real-world network redesign problems, as practical constraints (political, physical or financial) may prevent implementation. Our algorithm takes a multi-start optimization approach, adding a random initial edge and then applies a greedy heuristic to improve the Fiedler value. The random choice moves us to a new region of the search space, enabling discovery of diverse solutions. Additionally, we present a Determinantal Point Process framework for quantifying diversity. We then apply a Markov chain Monte Carlo technique to sift through the large number of output solutions and locate a smaller, more manageable collection of highly diverse solutions that can be presented to network redesign engineers. We demonstrate the effectiveness of our algorithm on real-world graphs with varied structures.

97 MATHEMATICS AND COMPUTING↗

Quantum annealing algorithms for Boolean tensor networks

Abstract Quantum annealers manufactured by D-Wave Systems, Inc., are computational devices capable of finding high-quality heuristic solutions of NP-hard problems. In this contribution, we explore the potential and effectiveness of such quantum annealers for computing Boolean tensor networks. Tensors offer a natural way to model high-dimensional data commonplace in many scientific fields, and representing a binary tensor as a Boolean tensor network is the task of expressing a tensor containing categorical (i.e., $$\{0, 1\}$$ { 0 , 1 } ) values as a product of low dimensional binary tensors. A Boolean tensor network is computed by Boolean tensor decomposition, and it is usually not exact. The aim of such decomposition is to minimize the given distance measure between the high-dimensional input tensor and the product of lower-dimensional (usually three-dimensional) tensors and matrices representing the tensor network. In this paper, we introduce and analyze three general algorithms for Boolean tensor networks: Tucker, Tensor Train, and Hierarchical Tucker networks. The computation of a Boolean tensor network is reduced to a sequence of Boolean matrix factorizations, which we show can be expressed as a quadratic unconstrained binary optimization problem suitable for solving on a quantum annealer. By using a novel method we introduce called parallel quantum annealing, we demonstrate that Boolean tensor’s with up to millions of elements can be decomposed efficiently using a DWave 2000Q quantum annealer.

97 MATHEMATICS AND COMPUTING↗

ULAMA: A Utilization-Aware Matching Approach for robust on-demand spatial service brokers

This article investigates an on-demand spatial service broker for suggesting service provider propositions and the corresponding time of service to mobile consumers while meeting the consumer’s maximum travel time and wait time constraints. The goal of the broker is to maximize the number of matched requests while also keeping the “eco-system” functioning and robust against variations in the supply–demand ratio by engaging as many service providers as possible and maintaining providers’ participation to ensure that providers do not drop out. This problem is important because of its many related societal applications in the on-demand and sharing economy (e.g., on-demand ride-hailing services, on-demand food delivery, etc.). Challenges of this problem include the need to satisfy many conflicting requirements of the broker, consumers and service providers and the high computational complexity since solving the problem for a number of available consumers at any time instant is NP-hard. Related work in spatial crowdsourcing and ridesharing has mainly focused on maximizing the number of matched requests and minimizing travel cost, but did not consider the importance of maintaining provider engagement and balancing provider utilization, which could become a priority when the available supply exceeds the demand. In this paper, we propose a Utilization-Aware Matching Approach (ULAMA) which employs novel provider-centric heuristics for balancing the utilization of providers, and a consumer-priority-based greedy matching algorithm that prioritizes consumers for maximizing the number of matched requests. Experimental results show that our proposed approach outperforms related work by achieving the lowest variance in provider utilization while matching all available providers even when supply greatly exceeds demand. Our approach also achieved a larger number of matched requests, particularly when supply exceeds demand and also when both supply and demand are balanced.

97 MATHEMATICS AND COMPUTING↗

Scalable Distributed Memory Community Detection Using Vite

Graph clustering, popularly known as community detection, is a fundamental graph operation used in several applications of relevance for network analysis and cybersecurity. Community detection is an operation of partitioning a network into an arbitrary number of “communities” such that each com munity represents a tightly-knit group of nodes with relatively sparser connections to the rest of the nodes in the network. The need to compute clustering on large-scale networks necessitates the development of efficient parallel algorithms capable of exploiting modern parallel architectures. However, due to their irregular and inherently sequential nature, many of the current algorithms for community detection are challenging to parallelize. In response to the 2018 Graph Challenge, we present Vite which is a distributed-memory parallel community detection method. Vite is a parallelization of the algorithmic template provided by a widely-used serial method (Louvain). Alongside, it uses several heuristics aimed at significantly improving parallelism and performance, while preserving output quality. Using the inputs from the 2018 Graph Challenge (static and streaming), we demonstrate superior performance and high quality solutions based on four parallelization heuristics.

community detection↗

CoSHA: Code for Stellar Properties Heuristic Assignment—for the MaStar Stellar Library

We introduce CoSHA: a Code for Stellar properties Heuristic Assignment. In order to estimate the stellar properties, CoSHA implements a Gradient Tree Boosting algorithm to label each star across the parameter space (T eff , $\mathrm{log}g$, [Fe/H], and [α/Fe]). We use CoSHA to estimate the stellar atmospheric parameters of 22,000 unique stars in the MaNGA Stellar Library (MaStar). To quantify the reliability of our approach, we run internal tests, using both the Göttingen Stellar Library (a theoretical library) and the first data release of MaStar, and external tests, by comparing the resulting distributions in the parameter space with the APOGEE estimates of the same properties. In summary, our parameter estimates span the ranges T eff = [2900, 12,000] K, $\mathrm{log}g=[-0.5,5.6]$, [Fe/H] = [-3.74, 0.81], and αM = [-0.22, 1.17]. We report internal (external) uncertainties of the properties of ${\sigma }_{{T}_{\mathrm{eff}}}\sim 43(240)$ K, ${\sigma }_{\mathrm{log}g}\sim 0.2(0.4)$, σ [Fe/H] ~ 0.16(0.24), and σ [α/Fe] ~ 0.09(0.08). These uncertainties are comparable to those of other methods with similar objectives. Despite the fact that CoSHA is not aware of the spatial distributions of these physical properties in the Milky Way, we are able to recover the main trends known in the literature. The catalog of physical properties for MaStar can be accessed online.

79 ASTRONOMY AND ASTROPHYSICS↗

Decision making and problem solving with computer assistance

In modern guidance and control systems, the human as manager, supervisor, decision maker, problem solver and trouble shooter, often has to cope with a marginal mental workload. To improve this situation, computers should be used to reduce the operator from mental stress. This should not solely be done by increased automation, but by a reasonable sharing of tasks in a human-computer team, where the computer supports the human intelligence. Recent developments in this area are summarized. It is shown that interactive support of operator by intelligent computer is feasible during information evaluation, decision making and problem solving. The applied artificial intelligence algorithms comprehend pattern recognition and classification, adaptation and machine learning as well as dynamic and heuristic programming. Elementary examples are presented to explain basic principles.

Kraiss, F.↗

A positional estimation technique for an autonomous land vehicle in an unstructured environment

This paper presents a solution to the positional estimation problem of an autonomous land vehicle navigating in an unstructured mountainous terrain. A Digital Elevation Map (DEM) of the area in which the robot is to navigate is assumed to be given. It is also assumed that the robot is equipped with a camera that can be panned and tilted, and a device to measure the elevation of the robot above the ground surface. No recognizable landmarks are assumed to be present in the environment in which the robot is to navigate. The solution presented makes use of the DEM information, and structures the problem as a heuristic search in the DEM for the possible robot location. The shape and position of the horizon line in the image plane and the known camera geometry of the perspective projection are used as parameters to search the DEM. Various heuristics drawn from the geometric constraints are used to prune the search space significantly. The algorithm is made robust to errors in the imaging process by accounting for the worst care errors. The approach is tested using DEM data of areas in Colorado and Texas. The method is suitable for use in outdoor mobile robots and planetary rovers.

Talluri, Raj↗

Solving the Grid Optimization Competition Challenge 3 Problem

The Grid Optimization Competition Challenge 3 Problem posed a multiperiod security-constrained unit commitment problem with base-case AC power flow. The problem formulation includes binary unit commitment decisions, nonlinear AC power flow and balance, dispatchable loads, and linearized contingency real power flow, among other features. This talk will present a modified consensus ADMM algorithm, which splits the problem into mixed-integer linear and nonlinear components, as a heuristic solution method for this large-scale mixed integer nonlinear program. We will present some computational results from the competition for our implementation and reflect on the challenges of participating the grid optimization competition.

AC power flow↗

Experience Report for WOPR

One of the purposes of the SQA effort at LLNL is to attempt to determine the 'goodness' of the research codes used for various scientific applications. Typically these are two and three dimensional multi-physics simulation and modeling codes. These legacy research codes are used for applciations such as atmospheric dispersion modeling and analysis and prediction of the performance of engineered systems. These codes are continually subjected to automated regression test suites consisting of verified and validated expected results. Code is managed in repositories. Experience level of developers is high in the knowledge domain, platforms, and languages used. Code size of the multi-physics code used in this study was 578,242 lines excluding comment and blank lines or 5538.7 function points. Languages were 70% C++, 20% C, and 10% Fortran. The code has 130 users and a development team of 14 and an embedded SQE. The code has achieved 100% prime feature test coverage, 73.6% functional test coverage, and 71.5% statement test coverage. The average cyclomatic complexity of the code was 6.25. The codes have evolved over 10 years. Research codes are challenging because there is a desire to balance agility with discipline as well as compliance with DOE standards. Agility is important to allow experimentation with new algorithms and addition of the latest physics features. Discipline is important to increase the quality of the codes. Automation of processes and defect prevention/detection are deployed throughout the software development process. Since resarch codes are a small segment of the software industry, not much information exists in terms of reliability studies on these types of codes. This paper describes attempts to determine the goodness of these research codes. Goodness defined as both correctness of the codes and their fault densities. Correctness is determined by user interviews, peer review; feature based automated testing, and coverage measurement. This paper focuses on the fault density aspect of goodness and reliability of the codes in particular. The approach taken was to use multiple fault density prediction methods and compare results to actual experimentation and other industry studies on fault density. As a result of the predictions and experiments our confidence in the prediction methods was increased and our confidence in the goodness of the code from a fault density perspective was given more context. A large unintended benefit of these experiments was to find defects hidden for years in the codes when using the Monte Carlo reliability testing results to develop heuristic based bug driven tests.

99 GENERAL AND MISCELLANEOUS↗

Aligning parallel arrays to reduce communication

Axis and stride alignment is an important optimization in compiling data-parallel programs for distributed-memory machines. We previously developed an optimal algorithm for aligning array expressions. Here, we examine alignment for more general program graphs. We show that optimal alignment is NP-complete in this setting, so we study heuristic methods. This paper makes two contributions. First, we show how local graph transformations can reduce the size of the problem significantly without changing the best solution. This allows more complex and effective heuristics to be used. Second, we give a heuristic that can explore the space of possible solutions in a number of ways. We show that some of these strategies can give better solutions than a simple greedy approach proposed earlier. Our algorithms have been implemented; we present experimental results showing their effect on the performance of some example programs running on the CM-5.

Sheffler, Thomas J.↗