Source: http://seor.vse.gmu.edu/~cchen9/ocba.html
Wir verfügen über einen hochmodernen Ansatz zur intelligenten Zuweisung von Rechenbudgets für eine effiziente Simulationsoptimierung. Ziel ist es, mit minimaler Simulationszeit das beste Design zu finden. Viele unserer Co-Autoren und Freunde tragen dazu bei, diesen Bereich zu bereichern.
Simulation ist ein beliebtes Werkzeug zum Entwurf großer, komplexer, stochastischer Systeme, da für solche Probleme im Allgemeinen keine geschlossenen analytischen Lösungen existieren. Während der Fortschritt neuer Technologien die Rechenleistung dramatisch erhöht hat, ist die Effizienz immer noch ein großes Problem beim Einsatz von Simulationen für den Entwurf großer Systeme, wobei in diesem Fall viele alternative Entwürfe simuliert werden müssen. Erschwerend kommt hinzu, dass für jedes Design mehrere Simulationsläufe durchgeführt werden müssen, um stochastisches Verhalten in Systemen zu erfassen. Die zentrale Frage in diesem Thema ist die Frage, wie die Gesamtrechenzeit drastisch reduziert werden kann.
Eine Schlüsselkomponente unserer Methoden ist unsere neue kontrolltheoretische Simulationstechnik namens Optimal Computing Budget Allocation (OCBA). Der OCBA-Ansatz kann auf intelligente Weise die effizientesten Simulationsreplikationszahlen oder Simulationslängen für alle simulierten Alternativen ermitteln. Ziel ist es, mit einem festen Rechenbudget die höchste Simulationsentscheidungsqualität zu erreichen oder mit einem minimalen Rechenbudget eine gewünschte Simulationsentscheidungsqualität zu erreichen. Numerische Tests zeigen, dass unser Ansatz die gleiche Simulationsqualität mit nur einem Zehntel des Simulationsaufwands erreichen kann.
OCBA eignet sich auch ideal für die stochastische Simulationsoptimierung. Ein Hauptgrund dafür, dass die Simulationsoptimierung schwierig ist, ist die stochastische Natur der Bewertung der Zielfunktion. Dies bedeutet, dass ein grundlegender Kompromiss zwischen dem Einsatz von Rechenaufwand für die Suche im Raum nach neuen Kandidatenlösungen (Exploration) und dem Erhalt genauerer Schätzungen der Zielfunktion besteht an aktuell erfolgversprechenden Lösungsansätzen (Exploitation). Mit anderen Worten: Wie viel von einem Simulationsbudget für zusätzliche Replikationen an bereits besuchten Punkten und wie viel für Replikationen an neu generierten Suchpunkten bereitgestellt werden sollte, ist eine wichtige Überlegung im Hinblick auf die Recheneffizienz. Im Verlauf ermittelt OCBA nacheinander, welche Entwurfsalternativen mehr Simulation erfordern und wie viele zusätzliche Replikationen erforderlich sind.
Um sicherzustellen, dass die beste Alternative richtig ausgewählt wird, sollte intuitiv ein größerer Teil des Rechenbudgets denjenigen Alternativen zugewiesen werden, die für den Prozess der Ermittlung der besten Alternative von entscheidender Bedeutung sind. Mit anderen Worten: Mit diesen kritischen Alternativen muss eine größere Anzahl von Simulationen durchgeführt werden, um die Varianzen dieser kritischen Schätzer zu verringern. Die Gesamteffizienz der Simulation wird verbessert, da weniger Rechenaufwand für die Simulation unkritischer Alternativen aufgewendet wird und mehr für kritische Alternativen aufgewendet wird. Die Ideen werden anhand des folgenden einfachen Beispiels erläutert. Angenommen, wir führen Simulationen für fünf Alternativen durch, um eine Alternative mit minimaler mittlerer Verzögerung zu ermitteln. Zunächst führen wir eine vorläufige Simulation für alle fünf Alternativen durch. Abbildung 1-(a) zeigt ein Beispiel ihrer 99 %-Konfidenzintervalle, die aus der vorläufigen Simulation ermittelt wurden. Beachten Sie, dass die Unsicherheit der Schätzung auf die stochastischen Eigenschaften des Systems und die Verwendung der Monte-Carlo-Simulation zurückzuführen ist.
Wie in Abbildung 1-(a) zu sehen ist, besteht zwar Unsicherheit bei der Schätzung der Leistung für jede Alternative, es ist jedoch offensichtlich, dass die Alternativen 2 und 3 viel besser sind als die anderen Alternativen, wenn wir beabsichtigen, eine Alternative mit minimalem Mittelwert zu finden Verzögerung. Daher müssen nur die Alternativen 2 und 3 weiter simuliert werden, um die Schätzunsicherheit zu verringern und die beste Alternative korrekt zu identifizieren. Indem wir die Simulationen für die Alternativen 1, 4 und 5 früher stoppen, können wir eine Menge Rechenkosten einsparen.
Was jedoch in den meisten Fällen tatsächlich passiert, ist nicht so trivial wie in Abbildung 1-(a) dargestellt. Es kommt häufiger vor, dass Fälle wie ein weiteres Beispiel in Abbildung 1-(b) auftreten, in denen einige Alternativen besser erscheinen, aber nicht eindeutig besser sind als die anderen. In solchen Fällen ist es nicht einfach zu bestimmen, welche Alternativen aus dem Simulationsexperiment entfernt werden können und wann sie gestoppt werden sollten. OCBA bietet einen systematischen Ansatz, um dieses Problem anzugehen und Simulationsläufe den Alternativen so zuzuordnen, dass die Simulationseffizienz maximiert wird.
Um mehr über OCBA zu erfahren, sind die folgenden beiden Artikel ein guter Ausgangspunkt:
Chen, C. H. und L. H. Lee, Stochastic Simulation Optimization: An Optimal Computing Budget Allocation. World Scientific Publishing Co., 2011.
Xu, J., E. Huang, L. Hsieh, L. H. Lee, Q. S. Jia und C. H. Chen, „Simulationsoptimierung im Zeitalter von Industrial 4.0 und dem Industrial Internet“, 10(4), 310-320, Journal of Simulation , 2016.
Xu, J., E. Huang, C. H. Chen und L. H. Lee, „Simulation Optimization: A Review and Exploration in The New Era of Cloud Computing and Big Data“, Asia-Pacific Journal of Operational Research, 32 (3), Juni 2015
Chen, C. H., M. Fu und L. Shi, „Simulation and Optimization“, Tutorials in Operations Research, S. 247–260, Informs, Hanover, MD, 2008.
Fu, M, C. H. Chen und L. Shi, „Some Topics for Simulation Optimization“, Proceedings of 2008 Winter Simulation Conference, S. 27-38, Miami, FL, Dezember 2008.
Hier finden Sie einige weitere repräsentative Veröffentlichungen zu den OCBA-Techniken.
Eines der beliebtesten OCBA-Papiere
Chen, C. H., J. Lin, E. Yucesan und S. E. Chick, „Simulation Budget Allocation for Further Enhancing the Efficiency of Ordinal Optimization“, Journal of Discrete Event Dynamic Systems: Theory and Applications, Bd. 10, S. 251-270, Juli 2000.
Frühere Entwicklung von OCBA
Chen, C. H. „An Effective Approach to Smartly Allocation Computing Budget for Discrete Event Simulation“, Proceedings of the 34th IEEE Conference on Decision and Control, S. 2598-2605, Dezember 1995.
Chen, C. H. „Eine untere Grenze für die Wahrscheinlichkeit der korrekten Teilmengenauswahl und ihre Anwendung auf diskrete Ereignissystemsimulationen“, IEEE Transactions on Automatic Control, Bd. 41, Nr. 8, S. 1227–1231, August 1996.
Chen, C. H., E. Yucesan, L. Dai und H. C. Chen, „Efficient Computation of Optimal Budget Allocation for Discrete Event Simulation Experiment“, IIE Transactions, Bd. 42, Nr. 1, S. 60-70, Januar 2010.
OCBA für Probleme mit mehreren Zielen
Lee, L. H., E. P. Chew, S. Y. Teng und D. Goldsman, „Optimal Computing Budget Allocation for Multi-Objective Simulation Models“, Proceedings of 2004 Winter Simulation Conference, S. 586–594, 2004.
E.J. Chen und L.H. Lee, „Ein multiobjektives Auswahlverfahren zur Bestimmung eines Pareto-Sets“, Computers and Operations Research, 36(6), : 1872-1879, 2009.
S. Teng, L.H. Lee und E.P. Chew, „Integration der Indifferenzzone mit Multi-Objective Computing Budget Allocation“, European Journal of Operational Research, 203(2): 419-429, 2010.
L. H. Lee, E. P. Chew, S. Y. Teng und D. Goldsman (2010). Finden des Pareto-Sets für Simulationsmodelle mit mehreren Zielen, die in IIE-Transaktionen angezeigt werden sollen.
OCBA für die Auswahl einer optimalen Teilmenge der Top-Designs (z. B. Top 5)
Chen, C. H., D. He, M. Fu und L. H. Lee, „Efficient Simulation Budget Allocation for Selecting an Optimal Subset“, Informs Journal on Computing, Bd. 20, Nr. 4, S. 579-595, 2008.
Zhang, S., L. H. Lee, E. P. Chew, J. Xu und C. H. Chen, „A Simulation Budget Allocation Procedure for Enhancing the Efficiency of Optimal Subset Selection“, IEEE Transactions on Automatic Control, 61(1), 62-75, Januar 2016.
OCBA zur Auswahl der besten Alternative bei korrelierten Proben
Fu, M. C., J. Q. Hu, C. H. Chen und X. Xiong, „Simulation Allocation for Determining the Best Design in the Presence of Corlated Sampling“, Informs Journal on Computing, Bd. 19, Nr. 1, S. 101-111, 2007.
OCBA für Simulation und Optimierung
Zhang, S., J , 2017.
Nicholas, P., „A Dividing Rectangles Algorithm for Stochastic Simulation Optimization“, Tagungsband der 14. INFORMS Computing Society-Konferenz, Richmond, Virginia, Januar 2015.
He, D., L. H. Lee, C. H. Chen, M. Fu und S. Wasserkrug, „Simulation Optimization Using the Cross-Entropy Method with Optimal Computing Budget Allocation“, ACM Transactions on Modeling and Computer Simulation, 2009.
Chew, E. P., L. H. Lee, S. Y. Teng und C.H. Koh, „Differentiated Service Inventory Optimization using Nested Partitions and MOCBA“, Computers and Operations Research, 36(5), : 1703-1710, 2009.
Lee, L. H., E. P. Chew, S.Y. Teng und Y.K. Chen, „Multi-Objective Simulation-based Evolutionary Algorithm for an Aircraft Spare Parts Allocation Problem“, European Journal of Operational Research, 189 (2): 476-491, 2008.
Chen, C. H., D. He, M. Fu und L. H. Lee, „Efficient Simulation Budget Allocation for Selecting an Optimal Subset“, Informs Journal on Computing, Bd. 20, Nr. 4, S. 579-595, 2008.
Shi, L. und C. H. Chen, „A New Algorithm for Stochastic Discrete Resource Allocation Optimization“, Journal of Discrete Event Dynamic Systems: Theory and Applications, Bd. 10, S. 271-294, Juli 2000.
Anwendungen von OCBA
Hsieh, L., E. Huang und C. H. Chen, „Verbesserung der Geräteauslastung im Bereich der Fotolithographie durch eine dynamische Systemsteuerung unter Verwendung von Multi-Fidelity-Simulationsoptimierung mit Big-Data-Technik“, IEEE Transactions on Semiconductor Manufacturing Decision, 30(2), 166 -175, 2017.
Aristotelis, T., M. Bastani, N. Celik und C. H. Chen, „Dynamic Data Driven Adaptive Simulation Framework for Automated Control in Microgrids“, IEEE Transactions on Smart Grid, 8(1), 209-218, 2017.
Hsieh, L., E. Huang, S. Zhang, K. H. Chang, C. H. Chen, „Application of Multi-Fidelity Simulation Modeling to Integrated Circuit Packaging“, International Journal of Simulation and Process Modelling, 28(2), 195-208, Frühjahr 2016.
Hsieh, B. W., C. H. Chen, S. C. Chang, „Efficient Simulation-based Composition of Dispatching Policies by Integrating Ordinal Optimization with Design of Experiment“, IEEE Transactions on Automation Science and Engineering, Bd. 4, Nr. 4, S. 553-568, Oktober 2007.
Romero, V. J., D. V. Ayon, C. H. Chen, „Demonstration of Probabilistic Ordinal Optimization Concepts to Continuous-Variable Optimization Under Uncertainty“, Optimization and Engineering, Bd. 7, Nr. 3, S. 343–365, September 2006.
Chen, C. H. und D. He, „Intelligent Simulation for Alternatives Compare and Application to Air Traffic Management“, Journal of Systems Science and Systems Engineering, Bd. 14, Nr. 1, S. 37–51, März 2005.
Chen, C. H., K. Donohue, E. Yucesan und J. Lin, „Optimal Computing Budget Allocation for Monte Carlo Simulation with Application to Product Design“, Journal of Simulation Practice and Theory, Bd. 11, Nr. 1, S. 57–74, März 2003.
Hsieh, B. W., C. H. Chen und S. C. Chang, „Scheduling Semiconductor Wafer Fabrication by Using Ordinal Optimization-Based Simulation“, IEEE Transactions on Robotics and Automation, Bd. 17, Nr. 5, S. 599-608, Oktober 2001.
Chen, C. H., S. D. Wu und L. Dai, „Ordinal Compare of Heuristic Algorithms Using Stochastic Optimization“, IEEE Transactions on Robotics and Automation, Bd. 15, Nr. 1, S. 44-56, Februar 1999.
Zusammenhang mit ordinaler Optimierung
Dai, L., C. H. Chen und J. R. Birge, „Large Convergence Properties of Two-Stage Stochastic Programming“, Journal of Optimization Theory and Applications, Bd. 106, Nr. 3, S. 489-510, September 2000.
Ho, Y. C., C. G. Cassandras, C. H. Chen und L. Dai, „Ordinal Optimization and Simulation“, Journal of Operational Research Society, Bd. 51, Nr. 4, S. 490-500, April 2000.
Dai, L. und C. H. Chen, „Rate of Convergence for Ordinal Compare of Dependent Simulations in Discrete Event Dynamic Systems“, Journal of Optimization Theory and Applications, Bd. 94, Nr. 1, S. 29–54, Juli 1997.
Einige andere Verallgemeinerungen und verwandte Werke
Blanchet, J., J. Liu und B. Zwart, „Large Deviations Perspective on Ordinal Optimization of Heavy-Tailed Systems“, Proceedings of the 2007 Winter Simulation Conference, S. 489–494, 2007.
Branke, J., S. E. Chick und C. Schmidt. Auswahlverfahren auswählen. Management Science 53 1916-1932, 2007.
Chick, S. und K. Inoue. Neue zweistufige und sequentielle Verfahren zur Auswahl des besten simulierten Systems. Operations Research 49 1609-1624, 2001.
Chick, S. und K. Inoue. Neue Verfahren zur Auswahl des besten simulierten Systems mithilfe gemeinsamer Zufallszahlen. Management Science 47 1133-1149, 2001.
Glynn, P., S. Juneja. Eine Perspektive großer Abweichungen zur ordinalen Optimierung. Tagungsband der Wintersimulationskonferenz 2004, 577-585, 2004.
Pujowidianto, N. A., L. H. Lee, C. H. Chen, C. M. Yep, „Optimal Computing Budget Allocation For Constrained Optimization“, erscheint in Proceedings of 2009 Winter Simulation Conference, S. 584-589, Austin, TX, Dezember 2009.
Trailovic, L. und L. Y. Pao. 2004. Berechnung der Budgetzuweisung für eine effiziente Rangfolge und Auswahl von Varianzen mit Anwendung auf Zielverfolgungsalgorithmen. IEEE Transactions on Automatic Control 49 58-67, 2004.
1. Im Jahr 2011 wurde ein neues Buch über OCBA veröffentlicht. Der Titel des Buches lautet „Stochastic Simulation Optimization: An Optimal Computing Budget Allocation“. Dieses Buch bietet eine umfassende und umfassende Abdeckung dieser effizienten Simulationsoptimierungsmethodik, von der Grundidee über die formale Entwicklung bis hin zum Stand der Technik. Sie können es bei Amazon.com bestellen.
2. Ein weiteres neues Buch, das eine viel breitere Perspektive der ordinalen Optimierung bietet, ist „Stochastic Simulation Optimization for Discrete Event Systems – Perturbation Analysis, Ordinal Optimization, and Beyond“, veröffentlicht im Jahr 2013.
- OCBA C-Code, der auch auf den Seiten 214 - 218 des OCBA-Buches erscheint.
- OCBA C++-Code, mit freundlicher Genehmigung von Prof. Nurcin Celik von der University of Miami
- OCBA JAVA Code, mit freundlicher Genehmigung von Prof. Nurcin Celik von der University of Miami
OCBA-Demo mit Ihrem Webbrowser. Diese Demo von OCBA wird von A. Johnson, Cheol Y. Park und Ning Lin implementiert. In der Demo sehen Sie, wie OCBA dynamisch die geeigneten Designs für die weitere Simulation auswählt.
Gehen Sie zur Seite von Professor Chun-Hung Chen
Gehen Sie zur Seite von Professor Loo Hay Lee
Gehen Sie zur Seite von Professor Q. S. Jia
Gehen Sie zur Seite von Professor Nurcin Celik