| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Combining Response Surface Methodology with Numerical Methods for Optimization of Markovian Models
July-September 2006 (vol. 3 no. 3)
pp. 259-269
In general, decision support is one of the main purposes of model-based analysis of systems. Response surface methodology (RSM) is an optimization technique that has been applied frequently in practice, but few automated variants are currently available. In this paper, we show how to combine RSM with numerical analysis methods to optimize continuous time Markov chain models. Among the many known numerical solution methods for large Markov chains, we consider a Gauss-Seidel solver with relaxation that relies on a hierarchical Kronecker representation as implemented in the APNN Toolbox. To effectively apply RSM for optimizing numerical models, we propose three strategies which are shown to reduce the required number of iterations of the numerical solver. With a set of experiments, we evaluate the proposed strategies with a model of a production line and apply them to optimize a class-based queueing system.
[1] 259 M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli, and G. Francheschinis, Modelling with Generalized Stochastic Petri Nets. John Wiley and Sons, 1995.[2] F. Bause, P. Buchholz, and P. Kemper, “A Toolbox for Functional and Quantitative Analysis of DEDS,” Proc. 10th Int'l Conf. Computer Performance Evaluation— Modelling Techniques and Tools (TOOLS '98), LNCS, vol. 1469, pp. 356-359, Springer, 1998.[3] J.T. Blake, A.L. Reibman, and K.S. Trivedi, “Sensitivity Analysis of Reliability and Performability Measures for Multiprocessor Systems,” Proc. ACM SIGMETRICS Conf. Measurement and Modeling of Computer Systems, pp. 177-186, 1988.[4] P. Buchholz and A. Panchenko, “Numerical Analysis and Optimisation of Class Based Queueing,” Proc. 16th European Simulation Multiconf., pp. 543-547, 2002.[5] P. Buchholz and P. Kemper, “Kronecker Based Matrix Representations for Large Markov Models,” Validation of Stochastic Systems, lNCS C. Baier, B.R. Haverkort, H. Hermanns, J.P. Katoen, and M. Siegle, eds., vol. 2925, pp. 256-295. Springer, 2004.[6] P. Buchholz and A. Thümmler, “Enhancing Evolutionary Algorithms with Statistical Selection Procedures for Simulation Optimization,” Proc. ACM Winter Simulation Conf. (WSC), 2005.[7] R.D. Cook and C.J. Nachtsheim, “A Comparison of Algorithms for Constructing Exact D-Optimal Designs,” Technometrics, vol. 22, pp. 315-324, 1980.[8] A. Cumani, “On the Canonical Representation of Homogeneous Markov Processes Modeling Failure— Time Distributions,” J. Microelectronics and Reliability, vol. 22, pp. 583-602, 1982.[9] D.D. Deavours, G. Clark, T. Courtney, D. Daly, S. Derisavi, J.M. Doyle, W.H. Sanders, and P.G. Webster, “The Möbius Framework and Its Implementation,” IEEE Trans. Software Eng., vol. 28, pp. 956-969, 2002.[10] S. Floyd and V. Jacobson, “Link-Sharing and Resource Management Models for Packet Networks,” IEEE/ACM Trans. Networking, vol. 3, pp. 365-386, 1995.[11] B.R. Haverkort, “Markovian Models for Performance and Dependability Modeling,” Formal Methods and Performance Analysis (FMPA '00), LNCS, E. Brinksma, H. Hermanns, and J.-P. Katoen, eds., vol. 2090, pp. 38-83, Springer, 2001.[12] Internet Traffic Archive, ita.ee.lbl.govindex.html, 2005.[13] V. Jacobson, K. Nichols, and L. Zhang, “A Two-Bit Differentiated Service Architecture for the Internet,” Request for Comments, vol. 2638, Internet Eng. Task Force, 1999.[14] S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi, “Optimization by Simulated Annealing,” Science, vol. 220, pp. 671-680, 1983.[15] J.P.C. Kleijnen and R.G. Sargent, “A Methodology for Fitting and Validating Metamodels in Simulation,” European J. Operational Research, vol. 120, pp. 14-29, 2000.[16] A.M. Law and W.D. Kelton, Simulation Modeling and Analysis, third ed. McGraw-Hill, 2000.[17] A. Michalas, M. Louta, P. Fafali, G. Karetsos, and V. Loumos, “Proportional Delay Differentiation Provision by Bandwidth Adaptation of Class-Based Queue Scheduling,” Int'l J. Comm. Systems, vol. 17, pp. 743-761, 2004.[18] A. Miner and D. Parker, “Symbolic Representations and Analysis of Large Probabilistic Systems,” Validation of Stochastic Systems, LNCS, C. Baier, B.R. Haverkort. H. Hermanns, J.P. Katoen, and M. Siegle, eds., vol. 2925, pp. 296-338, Springer, 2004.[19] D.C. Montgomery, Design and Analysis of Experiments, fifth ed. John Wiley and Sons, 2001.[20] D.C. Montgomery and R.H. Myers, Response Surface Methodology: Process and Product Optimization Using Designed Experiments, second ed. John Wiley and Sons, 2002.[21] H.G. Neddermeijer, G.J. vanOortmarssen, N. Piersma, and R. Dekker, “A Framework for Response Surface Methodology for Simulation Optimization,” Proc. ACM Winter Simulation Conf. (WSC), pp. 129-136, 2000.[22] H.P. Schwefel, Evolution and Optimum Seeking. John Wiley & Sons, 1995.[23] W.J. Stewart, Introduction to the Numerical Solution of Markov Chains. Princeton Univ. Press, 1994.[24] A. Thümmler, P. Buchholz, and M. Telek, “A Novel Approach for Fitting Probability Distributions to Real Trace Data with the EM Algorithm,” Proc. Int'l Conf. Dependable Systems and Networks (DSN), 712-721, 2005.[25] D.H. Wolpert and W.G. Macready, “No Free Lunch Theorems for Optimization,” IEEE Trans. Evolutionary Computation, vol. 1, pp. 67-82, 1997.
Index Terms:
Constrained optimization, Markov processes, sparse, structured, and very large systems, performance analysis and design aids, communication networks.
Citation:
Peter Kemper, Dennis M?, Axel Th?mmler, "Combining Response Surface Methodology with Numerical Methods for Optimization of Markovian Models," IEEE Transactions on Dependable and Secure Computing, vol. 3, no. 3, pp. 259-269, July-Sept. 2006, doi:10.1109/TDSC.2006.28
