SED navigation bar go to NIST home page SED Home Page SED Contacts SED Projects SED Products and Publications Search SED Pages
Contributed Session: Stochastic Process Optimization

Contributed Session: Stochastic Process Optimization

Session Chair: Charles Hagwood, NIST
 

Simulation-Based Optimization of Queueing Networks

Stacy D. Hill
Applied Physics Laboratory, Johns Hopkins Univ.

Michael C. Fu
Univ. of Maryland

Queueing networks provide a mathematical framework for studying a wide variety of physical and engineering systems--computer/communication networks, public transportation networks, and manufacturing production and assembly lines, are a few examples. There has been much interest in optimizing queueing networks (for example, maximizing system throughput or minimizing customer wait-time) by recursive stochastic optimization. Many algorithms rely on detailed modeling information that often requires knowing explicit relationships between adjustable or controllable system parameters and system performance. Real-world systems are often too complex to admit such a detailed analytical description. We apply the stochastic optimization algorithm Simultaneous Perturbation Stochastic Approximation to optimizing queueing networks via simulation. The algorithm is fast and computationally efficient, which makes it attractive in multivariate settings, and, in contrast to techniques that require detailed modeling information, it relies only on measurements of system performance. We illustrate the algorithm s performance on several types of queueing systems.

[Stacy D. Hill, Applied Physics Laboratory, Johns Hopkins Univ., Laurel, MD 20723-6099, USA; stacy.hill@jhuapl.edu ]

 

Optimization of Integral-Based Loss Functions via Simultaneous Perturbation Stochastic Approximation

Nathan L. Kleinman
Johns Hopkins Univ.

The minimization of integral-based loss functions is a complex task found in many practical problems in stochastic optimization. For example, in discrete event dynamic systems (e.g. queueing networks in transportation, manufacturing, and communication systems), we often need to find locally optimal values for many controllable variables or system parameters where the loss function is complicated by multiple integrals. Also, in many of these problems, the loss function is unknown, so that only noisy measurements of the loss function and no gradient measurements are available. We will discuss how simultaneous perturbation stochastic approximation (SPSA) (Spall, 1987, 1992) can be applied to these kinds of problems. Comparisons will be made between SPSA and finite difference stochastic approximation, and some asymptotic distribution and rate-of-convergence results will be discussed. The techniques will be illustrated on a problem in air traffic flow management.

[Nathan L. Kleinman, 7003 Rock Creek Dr., Frederick, MD 21702 USA; kleinman@brutus.mts.jhu.edu ]

 

Evaluation of a Stochastic Signal Timing Estimation Technique for System-Wide Traffic Control

Richard H. Smith
Daniel C. Chin
Applied Physics Laboratory, Johns Hopkins Univ.

A long-standing problem in traffic engineering is the optimization of the flow of vehicles through a given road network. Improving the timing of the traffic signals at intersections in the network is generally the most powerful and cost-effective means of achieving this goal. Recent efforts have resulted in the development of a fundamentally different approach for optimal centralized signal timing control that eliminates the need for an open-loop model of the traffic network dynamics. The approach is based on a neural network (NN) serving as the basis for the control law, with the internal NN weight estimation occurring real-time in closed-loop mode via the simultaneous perturbation stochastic approximation (SPSA) algorithm. This paper investigates the application of such a network-wide (but non-network-model-based) approach and illustrates the approach through a simulation on a nine-intersection, mid-Manhattan, New York network. The simulated traffic network contains varying short and long-term congestion behavior and short-term stochastic, nonlinear effects. The approach results in a net 10% reduction in mean vehicle wait time relative to the performance of the existing, in-place strategy.

[Richard H. Smith, Applied Physics Laboratory, Johns Hopkins Univ., Laurel, MD 20723-6099 USA; richard.smith@jhuapl.edu ]

 

Optimal Sensor Placement for Complex Systems

Payman Sadegh
Institute of Mathematical Modeling, Technical Univ. of Denmark

James C. Spall
Applied Physics Laboratory, Johns Hopkins Univ.

This paper considers the problem of locating sensors on a structure or other object with the aim of maximizing the useful information to be obtained. Our approach involves two fundamental contributions: (1) definition of an appropriate optimality criterion (or performance measure) and (2) description of an efficient and practical algorithm for achieving the optimal placement based on the criterion. The criterion for optimal sensor placement is based on maximizing the overall system response while minimizing the correlation among the sensor outputs (so as to minimize the redundant information being provided by the multiple sensors). To achieve the optimal sensor placement based on the criterion, we present an optimization procedure based on the powerful simultaneous perturbation stochastic approximation (SPSA) approach. SPSA avoids the need for detailed modeling of the sensor response by simply relying on observed sensor response as obtained by limited experimentation with test sensor placements. We will illustrate the approach with the optimal placement of acoustic emission sensors on a steel I-beam.

[James C. Spall, Applied Physics Laboratory, Johns Hopkins Univ., Laurel, MD 20723-6099 USA; james.spall@jhuapl.edu ]

Date created: 6/5/2001
Last updated: 6/21/2001
Please email comments on this WWW page to sedwww@cam.nist.gov.