OPEDo: a tool framework for modeling and optimization of stochastic models

ABSTRACT

A model-based design of systems requires appropriate tool support in many ways. It requires a modeling notation that suits the application problem, a set of analysis techniques that provide qualitative and/or quantitative results, and finally some optimization methods that help a designer to make appropriate design decisions. The challenge is to integrate those components into a homogenous framework such that a model based design takes advantage from synergy effects that result from a sophisticated combination of modeling formalism, analysis and optimization technique. In this paper, we present OPEDo, a tool framework that integrates modeling tools and analysis engines with state-of-the-art optimization methods. With respect to modeling, it contains the ProC/B editor for specifying open process-oriented simulation models, the APNN Toolbox for modeling with stochastic Petri nets, and OMNet++, for modeling using a simulation language. OPEDo provides analysis techniques for stochastic models based on discrete event simulation, based on queueing network analysis and numerical analysis techniques for continuous time Markov chains with the help of HIT, OMNeT++, and APNN Toolbox. Optimization of stochastic models has particular challenges due to the cost of model evaluation and the precision of results that can be achieved, so OPEDo contains specially adjusted variants of a variety of optimization methods, which includes response surface methodology, evolutionary strategies, genetic algorithms, and Kriging metamodeling techniques.

REFERENCES

• 1: Falko Bause , Heinz Beilner , Markus Fischer , Peter Kemper , Markus Völker, The ProC/B Toolset for the Modelling and Analysis of Process Chains, Proceedings of the 12th International Conference on Computer Performance Evaluation, Modelling Techniques and Tools, p.51-70, April 14-17, 2002
• 2: Falko Bause , Peter Buchholz , Peter Kemper, A Toolbox for Functional and Quantitative Analysis of DEDS, Proceedings of the 10th International Conference on Computer Performance Evaluation: Modelling Techniques and Tools, p.356-359, September 14-18, 1998
• 3: Justin Boesel , Barry L. Nelson , Seong-Hee Kim, Using Ranking and Selection to "Clean Up" after Simulation Optimization, Operations Research, v.51 n.5, p.814-825, September 2003 [doi>10.1287/opre.51.5.814.16751]
• 4: P. Buchholz and P. Kemper. Optimization of Markov models with evolutionary strategies based on exact and approximate analysis techniques. Technical report, Submitted for publication, 2006.
• 5: P. Buchholz, D. Müller, and A. Thümmler. Optimization of process chain models with Response Surface Methodology and the ProC/B toolset. In H. Günther, D. Mattfeld, and L. Suhl, editors, Entscheidungsunterstützende Systeme in Supply Chain Management und Logistik, pages 551--573. Physica-Verlag, 2005.
• 6: Peter Buchholz , Axel Thümmler, Enhancing evolutionary algorithms with statistical selection procedures for simulation optimization, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
• 7: E. Jack Chen , W. David Kelton, Comparing systems via stochastic simulation: an enhanced two-stage selection procedure, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
• 8: Michael C. Fu , Fred W. Glover , Jay April, Simulation optimization: a review, new developments, and applications, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
• 9: Donald R. Jones , Matthias Schonlau , William J. Welch, Efficient Global Optimization of Expensive Black-Box Functions, Journal of Global Optimization, v.13 n.4, p.455-492, December 1998 [doi>10.1023/A:1008306431147]
• 10: G. Jungman and D. B. Gough. GSL homepage, http://www.gnu.org/software/gsl/.
• 11: Dennis Muller , Axel Thummler, Combining Response Surface Methodology with Numerical Models for Optimization of Class-Based Queueing Systems, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.550-559, June 28-July 01, 2005 [doi>10.1109/DSN.2005.28]
• 12: Wim C. M. van Beers , Jack P. C. Kleijnen, Kriging interpolation in simulation: a survey, Proceedings of the 36th conference on Winter simulation, December 05-08, 2004, Washington, D.C.
• 13: L. Koenig and A. Law. A procedure for selecting a subset of size m containing the l best of k independent normal populations, with applications to simulation. Communications in Statistics Simulation and Computation, 14:719--734, 1985.
• 14: Averill M. Law , David M. Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1999
• 15: R. Li and A. Sudjianto. Analysis of computer experiments using penalized likelihood in Gaussian Kriging models.
• 16: D. Menasce, V. Almeida, and L. Dowdy. Performance by Design. Pearson Education, Inc., 2004.
• 17: R. H. Myers and D. C. Montgomery. Response Surface Methodology. Wiley, 2002.
• 18: Y. Rinott. On two-stage selection procedures and related probability-inequalities. In Communications in Statistics Theory and Methods A7, pages 799--811, 1978.
• 19: T. J. Santner, B. J. Williams, and W. Notz. Design and Analysis of Computer Experiments. Springer, 2003.
• 20: Hans-Paul Paul Schwefel, Evolution and Optimum Seeking: The Sixth Generation, John Wiley & Sons, Inc., New York, NY, 1993
• 21: James R. Swisher , Sheldon H. Jacobson , Enver Yücesan, Discrete-event simulation optimization using ranking, selection, and multiple comparison procedures: A survey, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.2, p.134-154, April 2003 [doi>10.1145/858481.858484]
• 22: Virginia Torczon, On the Convergence of Pattern Search Algorithms, SIAM Journal on Optimization, v.7 n.1, p.1-25, 1997 [doi>10.1137/S1052623493250780]
• 23: A. Varga. OMNeT++, http://www.omnetpp.org.
• 24: D. H. Wolpert and W. G. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):67--82, April 1997.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Measurement, Performance, Reliability