SEARCH · Engineering Papers

Results for “Simulated annealing”

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 55 records · Page 3

All sources NASA NTRS DOE OSTI

NASA NTRS2000

Self-Tuning of Design Variables for Generalized Predictive Control

Three techniques are introduced to determine the order and control weighting for the design of a generalized predictive controller. These techniques are based on the application of fuzzy logic, genetic algorithms, and simulated annealing to conduct an optimal search on specific performance indexes or objective functions. Fuzzy logic is found to be feasible for real-time and on-line implementation due to its smooth and quick convergence. On the other hand, genetic algorithms and simulated annealing are applicable for initial estimation of the model order and control weighting, and final fine-tuning within a small region of the solution space, Several numerical simulations for a multiple-input and multiple-output system are given to illustrate the techniques developed in this paper.

Lin, Chaung↗

NASA NTRS2003

Scheduling Earth Observing Satellites with Evolutionary Algorithms

We hypothesize that evolutionary algorithms can effectively schedule coordinated fleets of Earth observing satellites. The constraints are complex and the bottlenecks are not well understood, a condition where evolutionary algorithms are often effective. This is, in part, because evolutionary algorithms require only that one can represent solutions, modify solutions, and evaluate solution fitness. To test the hypothesis we have developed a representative set of problems, produced optimization software (in Java) to solve them, and run experiments comparing techniques. This paper presents initial results of a comparison of several evolutionary and other optimization techniques; namely the genetic algorithm, simulated annealing, squeaky wheel optimization, and stochastic hill climbing. We also compare separate satellite vs. integrated scheduling of a two satellite constellation. While the results are not definitive, tests to date suggest that simulated annealing is the best search technique and integrated scheduling is superior.

Globus, Al↗

NASA NTRS1992

Phasing of a space based segmented submillimeter wavelength telescope using focal plane measurements

As part of a technology development program for realizing a space based submillimeter telescope, two different approaches to the absolute phasing of a segmented primary mirror using focal plane measurements have been implemented for feasibility. The method of optimization by simulated annealing evaluates the image quality of a point spread function after all the telescope segments have been randomly moved. It accepts each iteration which improves the image quality, as well as a random number of iterations which do not, thus keeping the Strehl in the initialization procedure from falling into local maxima. Methods for determining the annealing schedule, and the step size for random segment movements are presented and discussed. Using phase diversity and a model for the telescope imaging system, a nonlinear least squares algorithm has also been implemented which parameterizes each of the segment actuator movements. Using multiple out of focus images, the segment actuator positions are estimated using an iterative procedure. Nonlinear least squares, although computationally intensive, offers a large savings in the actuator movements over simulated annealing and pairwise phasing methods for large numbers of segments. These algorithms have been integrated into a general simulation program which models the behavior of the telescope under anticipated space conditions.

Levine, B. M.↗

NASA NTRS1987

Performance of a parallel algorithm for standard cell placement on the Intel Hypercube

A parallel simulated annealing algorithm for standard cell placement on the Intel Hypercube is presented. A novel tree broadcasting strategy is used extensively for updating cell locations in the parallel environment. Studies on the performance of the algorithm on example industrial circuits show that it is faster and gives better final placement results than uniprocessor simulated annealing algorithms.

Jones, Mark↗

NASA NTRS2003

A Comparison of Techniques for Scheduling Fleets of Earth-Observing Satellites

Earth observing satellite (EOS) scheduling is a complex real-world domain representative of a broad class of over-subscription scheduling problems. Over-subscription problems are those where requests for a facility exceed its capacity. These problems arise in a wide variety of NASA and terrestrial domains and are .XI important class of scheduling problems because such facilities often represent large capital investments. We have run experiments comparing multiple variants of the genetic algorithm, hill climbing, simulated annealing, squeaky wheel optimization and iterated sampling on two variants of a realistically-sized model of the EOS scheduling problem. These are implemented as permutation-based methods; methods that search in the space of priority orderings of observation requests and evaluate each permutation by using it to drive a greedy scheduler. Simulated annealing performs best and random mutation operators outperform our squeaky (more intelligent) operator. Furthermore, taking smaller steps towards the end of the search improves performance.

Globus, Al↗

NASA NTRS1989

Selection of active member locations in adaptive structures

The effective use of multiple passive and active members in adaptive structures necessitates that these members be optimally distributed throughout the structure. In truss structures, the problem falls into the class of combinatorial optimization for which the solution becomes exceedingly intractable as the problem size increases. This is overcome by using the simulated annealing algorithm to obtain near optimal locations for passive and/or active members. The maximization of the rate of energy dissipation over a finite time period as the measure of optimality is adopted. The selection of optimal locations for both passive and active members is consistently treated through the use of the energy dissipation rate criterion within the simulated annealing algorithm. Numerical examples are used to illustrate the effectiveness of the methodology for large truss structures.

Chen, G.-S.↗

NASA NTRS2004

A Comparison of Techniques for Scheduling Earth-Observing Satellites

Scheduling observations by coordinated fleets of Earth Observing Satellites (EOS) involves large search spaces, complex constraints and poorly understood bottlenecks, conditions where evolutionary and related algorithms are often effective. However, there are many such algorithms and the best one to use is not clear. Here we compare multiple variants of the genetic algorithm: stochastic hill climbing, simulated annealing, squeaky wheel optimization and iterated sampling on ten realistically-sized EOS scheduling problems. Schedules are represented by a permutation (non-temperal ordering) of the observation requests. A simple deterministic scheduler assigns times and resources to each observation request in the order indicated by the permutation, discarding those that violate the constraints created by previously scheduled observations. Simulated annealing performs best. Random mutation outperform a more 'intelligent' mutator. Furthermore, the best mutator, by a small margin, was a novel approach we call temperature dependent random sampling that makes large changes in the early stages of evolution and smaller changes towards the end of search.

Globus, Al↗

NASA NTRS2006

Stochastic Evolutionary Algorithms for Planning Robot Paths

A computer program implements stochastic evolutionary algorithms for planning and optimizing collision-free paths for robots and their jointed limbs. Stochastic evolutionary algorithms can be made to produce acceptably close approximations to exact, optimal solutions for path-planning problems while often demanding much less computation than do exhaustive-search and deterministic inverse-kinematics algorithms that have been used previously for this purpose. Hence, the present software is better suited for application aboard robots having limited computing capabilities (see figure). The stochastic aspect lies in the use of simulated annealing to (1) prevent trapping of an optimization algorithm in local minima of an energy-like error measure by which the fitness of a trial solution is evaluated while (2) ensuring that the entire multidimensional configuration and parameter space of the path-planning problem is sampled efficiently with respect to both robot joint angles and computation time. Simulated annealing is an established technique for avoiding local minima in multidimensional optimization problems, but has not, until now, been applied to planning collision-free robot paths by use of low-power computers.

Fink, Wolfgang↗

NASA NTRS1987

Performance of a parallel algorithm for standard cell placement on the Intel Hypercube

A parallel simulated annealing algorithm for standard cell placement that is targeted to run on the Intel Hypercube is presented. A tree broadcasting strategy that is used extensively in our algorithm for updating cell locations in the parallel environment is presented. Studies on the performance of our algorithm on example industrial circuits show that it is faster and gives better final placement results than the uniprocessor simulated annealing algorithms.

Jones, Mark↗

NASA NTRS1995

Actuator placement for active sound and vibration control of cylinders

Active structural acoustic control is a method in which the control inputs (used to reduce interior noise) are applied directly to a vibrating structural acoustic system. The control concept modeled in this work is the application of in-plane force inputs to piezoceramic patches bonded to the wall of a vibrating cylinder. The cylinder is excited by an exterior noise source -- an acoustic monopole -- located near the outside of the cylinder wall. The goal is to determine the force inputs and sites for the piezoelectric actuators so that (1) the interior noise is effectively damped; (2) the level of vibration of the cylinder shell is not increased; and (3) the power requirements needed to drive the actuators are not excessive. We studied external monopole excitations at two frequencies. A cylinder resonance of 100 Hz, where the interior acoustic field is driven in multiple, off-resonance cylinder cavity modes, and a cylinder resonance of 200 Hz are characterized by both near and off-resonance cylinder vibration modes which couple effectively with a single, dominant, low-order acoustic cavity mode at resonance. Previous work has focused almost exclusively on meeting objective (1) and solving a complex least-squares problem to arrive at an optimal force vector for a given set of actuator sites. In addition, it has been noted that when the cavity mode couples with cylinder vibration modes (our 200 Hz case) control spillover may occur in higher order cylinder shell vibrational modes. How to determine the best set of actuator sites to meet objectives (1)-(3) is the main contribution of our research effort. The selection of the best set of actuator sites from a set of potential sites is done via two metaheuristics -- simulated annealing and tabu search. Each of these metaheuristics partitions the set of potential actuator sites into two disjoint sets: those that are selected to control the noise (on) and those that are not (off). Next, each metaheuristic attempts to improve this initial solution by calculating the change in the objective value when one selected actuator site is turned off and one actuator site that previously was not selected is turned on. All such pairwise exchanges are performed and the exchange that improves the objective the most is made. Eventually the search is unable to improve the objective value and a local optimum (with respect to pairwise exchanges) is reached. Both simulated annealing and tabu search provide mechanisms to escape local optima and allow the search to continue until (hopefully) a global optimum is found. Our experiments with the 100 Hz and 200 Hz cases confirm that both metaheuristics are able to uncover better solutions than those selected based upon engineering judgement alone. In addition, the high quality solutions generated by these metaheuristics, when minimizing interior noise, do not further excite the cylinder shell. Thus, we are able to meet objective (2) without imposing an additional constraint or forming a multiobjective performance measure. An additional observation is that in many cases the amplitude and phase values for several chosen actuator sites were nearly identical. This natural grouping means that fewer control channels are needed and the resulting control system is simpler. Currently no power requirements have been set, so objective (3) cannot be addressed. A set of experiments is planned with a laboratory test article (a cylinder). For these experiments the transfer matrices will be generated experimentally. It is hoped that the predicted performance of the best actuator sites found by our metaheuristics will correlate well with the measured performance.

Kincaid, Rex K.↗

NASA NTRS1994

Design of Ternary Correlation Filters to Reduce Probability of Error

The problem of designing ternary phase and amplitude filters (TPAF's) that reduce the probability of image misclassification for a two-class image set is studied. The Fisher ratio is used as a measure of the correct classification rate, and an attempt is made to maximize this quantity in the filter designs. Given the nonanalytical nature of the design problem, a simulated annealing optimization technique is employed. Computer simulation results are presented for several cases including single in-class and out-of-class image sets and multiple image sets corresponding to the design of synthetic discriminant function filters. Significant improvements are found in expected rates of correct classification in comparison to binary phase-only filters and other TPAF designs. Approaches to accelerate the filter design process are also discussed.

Downie, John D.↗

NASA NTRS1997

Automating the Process of Optimization in Spacecraft Design

Spacecraft design optimization is a difficult problem, due to the complexity of optimization cost surfaces, and human expertise in optimization that is necessary in order to achieve good results. In this paper, we propose the use of a set of generic, metaheuristic optimization algorithms (e.g., generic algorithms, simulated annealing), which is configured for a particular optimization problem by an adaptive problem solver based on artificial intelligence and machine learning techniques. We describe work in progress on OASIS, a system for adaptive problem solving based on these principles.

optimization↗

NASA NTRS1995

Genetic Adaptive Control for PZT Actuators

A piezoelectric transducer (PZT) is capable of providing linear motion if controlled correctly and could provide a replacement for traditional heavy and large servo systems using motors. This paper focuses on a genetic model reference adaptive control technique (GMRAC) for a PZT which is moving a mirror where the goal is to keep the mirror velocity constant. Genetic Algorithms (GAs) are an integral part of the GMRAC technique acting as the search engine for an optimal PID controller. Two methods are suggested to control the actuator in this research. The first one is to change the PID parameters and the other is to add an additional reference input in the system. The simulation results of these two methods are compared. Simulated Annealing (SA) is also used to solve the problem. Simulation results of GAs and SA are compared after simulation. GAs show the best result according to the simulation results. The entire model is designed using the Mathworks' Simulink tool.

Kim, Jeongwook↗

NASA NTRS1989

Efficient mapping algorithms for scheduling robot inverse dynamics computation on a multiprocessor system

Two efficient mapping algorithms for scheduling the robot inverse dynamics computation consisting of m computational modules with precedence relationship to be executed on a multiprocessor system consisting of p identical homogeneous processors with processor and communication costs to achieve minimum computation time are presented. An objective function is defined in terms of the sum of the processor finishing time and the interprocessor communication time. The minimax optimization is performed on the objective function to obtain the best mapping. This mapping problem can be formulated as a combination of the graph partitioning and the scheduling problems; both have been known to be NP-complete. Thus, to speed up the searching for a solution, two heuristic algorithms were proposed to obtain fast but suboptimal mapping solutions. The first algorithm utilizes the level and the communication intensity of the task modules to construct an ordered priority list of ready modules and the module assignment is performed by a weighted bipartite matching algorithm. For a near-optimal mapping solution, the problem can be solved by the heuristic algorithm with simulated annealing. These proposed optimization algorithms can solve various large-scale problems within a reasonable time. Computer simulations were performed to evaluate and verify the performance and the validity of the proposed mapping algorithms. Finally, experiments for computing the inverse dynamics of a six-jointed PUMA-like manipulator based on the Newton-Euler dynamic equations were implemented on an NCUBE/ten hypercube computer to verify the proposed mapping algorithms. Computer simulation and experimental results are compared and discussed.

Lee, C. S. G.↗

NASA NTRS2017

QSPIN: A High Level Java API for Quantum Computing Experimentation

QSPIN is a high level Java language API for experimentation in QC models used in the calculation of Ising spin glass ground states and related quadratic unconstrained binary optimization (QUBO) problems. The Java API is intended to facilitate research in advanced QC algorithms such as hybrid quantum-classical solvers, automatic selection of constraint and optimization parameters, and techniques for the correction and mitigation of model and solution errors. QSPIN includes high level solver objects tailored to the D-Wave quantum annealing architecture that implement hybrid quantum-classical algorithms [Booth et al.] for solving large problems on small quantum devices, elimination of variables via roof duality, and classical computing optimization methods such as GPU accelerated simulated annealing and tabu search for comparison. A test suite of documented NP-complete applications ranging from graph coloring, covering, and partitioning to integer programming and scheduling are provided to demonstrate current capabilities.

Quantu↗

NASA NTRS1991

Optimal spectral windows for microwave diversity imaging

Tomographic microwave diversity imaging is analyzed using linear system theory concepts, and optimal spectral windows for data acquisition are obtained either by considering window position in the spectral domain or by using simulated annealing to find an optimal phase weighting of the object frequency response samples collected over the specified spectral window. This study provides a means of microwave image formation that is applicable under general assumptions. Results of numerical simulations and representative images reconstructed from realistic experimental microwave scattering data are given, demonstrating that the proposed approach is superior to previous image reconstruction methods.

Farhat, Nabil H.↗

NASA NTRS2003

On the Critical Behaviour, Crossover Point and Complexity of the Exact Cover Problem

Research into quantum algorithms for NP-complete problems has rekindled interest in the detailed study a broad class of combinatorial problems. A recent paper applied the quantum adiabatic evolution algorithm to the Exact Cover problem for 3-sets (EC3), and provided an empirical evidence that the algorithm was polynomial. In this paper we provide a detailed study of the characteristics of the exact cover problem. We present the annealing approximation applied to EC3, which gives an over-estimate of the phase transition point. We also identify empirically the phase transition point. We also study the complexity of two classical algorithms on this problem: Davis-Putnam and Simulated Annealing. For these algorithms, EC3 is significantly easier than 3-SAT.

Morris, Robin D.↗

NASA NTRS1994

System Design under Uncertainty: Evolutionary Optimization of the Gravity Probe-B Spacecraft

This paper discusses the application of evolutionary random-search algorithms (Simulated Annealing and Genetic Algorithms) to the problem of spacecraft design under performance uncertainty. Traditionally, spacecraft performance uncertainty has been measured by reliability. Published algorithms for reliability optimization are seldom used in practice because they oversimplify reality. The algorithm developed here uses random-search optimization to allow us to model the problem more realistically. Monte Carlo simulations are used to evaluate the objective function for each trial design solution. These methods have been applied to the Gravity Probe-B (GP-B) spacecraft being developed at Stanford University for launch in 1999, Results of the algorithm developed here for GP-13 are shown, and their implications for design optimization by evolutionary algorithms are discussed.

Pullen, Samuel P.↗