Alocarea bugetară de procesarea optimală (OCBA – Optimal Computing Budget Allocation)

Source: http://seor.vse.gmu.edu/~cchen9/ocba.html

Avem o abordare de ultimă generație pentru a aloca în mod inteligent bugetul de calcul pentru optimizarea eficientă a simulării. Scopul este de a găsi cel mai bun design folosind un timp minim de simulare. Mulți dintre coautorii și prietenii noștri contribuie la îmbogățirea acestui domeniu.

Simularea este un instrument popular pentru proiectarea de sisteme mari, complexe, stocastice, deoarece soluțiile analitice în formă închisă nu există în general pentru astfel de probleme. În timp ce progresul noii tehnologii a crescut dramatic puterea de calcul, eficiența este încă o mare preocupare atunci când se utilizează simularea pentru proiectarea sistemelor mari, caz în care trebuie simulate multe modele alternative. Pentru a înrăutăți situația, trebuie efectuate mai multe rulări de simulare pentru fiecare proiect, pentru a surprinde comportamentele stocastice în sisteme. Cum să reduceți dramatic timpul total de calcul este problema cheie în acest subiect.

O componentă cheie a metodologiilor noastre este noua noastră tehnică de simulare control-teoretică numită Optimal Computing Budget Allocation (OCBA). Abordarea OCBA poate determina în mod inteligent cele mai eficiente numere de replicare sau lungimi de simulare pentru toate alternativele simulate. Scopul este de a obține cea mai înaltă calitate a deciziei de simulare folosind un buget de calcul fix sau de a obține o calitate dorită a deciziei de simulare folosind un buget de calcul minim. Testarea numerică arată că abordarea noastră poate obține aceeași calitate a simulării cu doar o zecime din efortul de simulare.

OCBA este, de asemenea, ideal pentru optimizarea simulării stocastice. Un motiv principal pentru care optimizarea simulării este dificilă este natura stocastică a evaluării funcției obiectiv, ceea ce înseamnă că există un compromis de bază între a dedica efort de calcul pentru căutarea spațiului pentru noi soluții candidate (explorare) față de obținerea de estimări mai precise ale funcției obiectiv. la soluţii promiţătoare în prezent (exploatare). Cu alte cuvinte, cât de mult dintr-un buget de simulare ar trebui să fie alocat replicărilor suplimentare în punctele deja vizitate și cât de mult replicărilor din punctele de căutare nou generate este o considerație majoră în ceea ce privește eficiența computațională. În cadrul procedurii, OCBA determină secvenţial care alternative de proiectare necesită mai multă simulare şi câte replicări suplimentare sunt necesare.

În mod intuitiv, pentru a se asigura că cea mai bună alternativă este selectată corect, o parte mai mare a bugetului de calcul ar trebui să fie alocată acelor alternative care sunt critice în procesul de identificare a celei mai bune alternative. Cu alte cuvinte, trebuie efectuat un număr mai mare de simulări cu acele alternative critice pentru a reduce variațiile acestor estimatori critici. Eficiența generală a simulării este îmbunătățită, deoarece este cheltuit mai puțin efort de calcul pentru simularea alternativelor necritice și mai mult este cheltuit pentru alternativele critice. Ideile sunt explicate folosind următorul exemplu simplu. Să presupunem că efectuăm simulări pentru 5 alternative pentru a determina o alternativă cu întârziere medie minimă. În primul rând, efectuăm o simulare preliminară pentru toate cele 5 alternative. Figura 1-(a) oferă un exemplu de intervale de încredere de 99% obținute din simularea preliminară. Rețineți că incertitudinea estimării se datorează caracteristicilor stocastice ale sistemului și utilizării simulării Monte Carlo.

După cum se vede în Figura 1-(a), deși există incertitudine în estimarea performanței pentru fiecare alternativă, este evident că alternativele 2 și 3 sunt mult mai bune decât celelalte alternative, dacă intenționăm să găsim o alternativă cu medie minimă. întârziere. Prin urmare, numai alternativele 2 și 3 trebuie simulate în continuare pentru a reduce incertitudinea estimării pentru a identifica corect cea mai bună alternativă. Oprind mai devreme simulările pentru alternativele 1, 4 și 5, putem economisi o mulțime de costuri de calcul.

Cu toate acestea, ceea ce se întâmplă de fapt în majoritatea cazurilor nu este la fel de banal ca cel prezentat în Figura 1-(a). Este mai frecvent să vedem cazuri ca un alt exemplu prezentat în Figura 1-(b), în care unele alternative par mai bune, dar nu sunt în mod clar mai bune decât celelalte. Nu este simplu în astfel de cazuri să se determine care alternative pot fi eliminate din experimentul de simulare și când ar trebui oprite. OCBA oferă o abordare sistematică pentru a aborda această problemă și a aloca rulările de simulare alternativelor într-un mod în care eficiența simulării este maximizată.

Pentru a afla mai multe despre OCBA, următoarele două lucrări reprezintă un bun punct de plecare:

Introducerea ideilor OCBA

Chen, CH și LH Lee, Stochastic Simulation Optimization: O Optimal Computing Budget Allocation . World Scientific Publishing Co., 2011.

Xu, J., E. Huang, L. Hsieh, LH Lee, QS Jia și CH Chen, „Simulation optimization in the era of Industrial 4.0 and the Industrial Internet”, 10(4), 310-320, Journal of Simulation , 2016.

Xu, J., E. Huang, CH Chen și LH 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), iunie 2015

Chen, CH, M. Fu și L. Shi, „Simulare și optimizare”, Tutoriale în cercetarea operațională , pp. 247-260, Informs, Hanovra, MD, 2008.

Fu, M, CH Chen și L. Shi, „Some Topics for Simulation Optimization”, Proceedings of 2008 Winter Simulation Conference , pp. 27-38, Miami, FL, decembrie 2008.

Iată câteva publicații mai reprezentative despre tehnicile OCBA.

Una dintre cele mai populare lucrări OCBA

Chen, CH, J. Lin, E. Yucesan și SE Chick, „Simulare alocarea bugetului pentru îmbunătățirea în continuare a eficienței optimizării ordinale”, Journal of Discrete Event Dynamic Systems: Theory and Applications , Voi. 10, p. 251-270, iulie 2000.

Dezvoltarea anterioară a OCBA

Chen, CH „An Effective Approach to Smartly Allocate Computing Budget for Discrete Event Simulation”, Proceedings of the 34th IEEE Conference on Decision and Control , pp. 2598-2605, decembrie 1995.

Chen, CH „O limită inferioară pentru probabilitatea corectă de selecție a subsetului și aplicarea sa la simulări ale sistemelor de evenimente discrete”, IEEE Transactions on Automatic Control , voi. 41, nr. 8, p. 1227-1231, august 1996.

Chen, CH, E. Yucesan, L. Dai și HC Chen, „Calcul eficient al alocării optime a bugetului pentru experimentul de simulare a evenimentelor discrete”, IIE Transactions , voi. 42, nr. 1, p. 60-70, ianuarie 2010.

OCBA pentru probleme cu obiective multiple

Lee, LH, EP Chew, SY Teng și D. Goldsman, „Optimal computing budget allocation for multi-obiective simulation models”, Proceedings of 2004 Winter Simulation Conference , pp. 586-594, 2004.

EJ Chen și LH Lee, „O procedură de selecție multi-obiectivă de determinare a unui set Pareto”, Computers and Operations Research, 36(6) , : 1872-1879, 2009.

S. Teng, LH Lee și EP Chew, „Integration of Indifference-zone with Multi-objective Computing Budget Allocation”, Jurnalul European de Cercetare Operațională, 203(2): 419-429, 2010.

LH Lee, EP Chew, SY Teng și D. Goldsman (2010). Găsirea setului Pareto pentru modele de simulare multi-obiective, care să apară în IIE Transactions .

OCBA pentru selectarea unui subset optim de modele de top (să spunem primele 5)

Chen, CH, D. He, M. Fu și LH Lee, „Eficient Simulation Budget Allocation for Selecting an Optimal Subset”, informează Journal on Computing , Vol. 20, nr. 4, p. 579-595, 2008.

Zhang, S., LH Lee, EP Chew, J. Xu și CH Chen, „A Simulation Budget Allocation Procedure for Enhancing the Efficiency of Optimal Subset Selection”, IEEE Transactions on Automatic Control , 61(1), 62-75, ianuarie 2016.

OCBA pentru selectarea celei mai bune alternative atunci când probele sunt corelate

Fu, MC, JQ Hu, CH Chen și X. Xiong, „Alocarea prin simulare pentru determinarea celui mai bun design în prezența eșantionării corelate”, informează Journal on Computing , voi. 19, nr. 1, p. 101-111, 2007.

OCBA pentru simulare și optimizare

Zhang, S., J. Xu, LH Lee, EP Chew, WP Wong și CH Chen, „Optimal Computing Budget Allocation for Particle Swarm Optimization in Stochastic Optimization”, IEEE Transactions on Evolutionary Computation , 21(2), 206-219 , 2017.

Nicholas, P., „A Dividing Rectangles Algorithm for Stochastic Simulation Optimization”, Proceedings of 14th INFORMS Computing Society Conference , Richmond, Virginia, ianuarie 2015.

El, D., LH Lee, CH Chen, M. Fu și S. Wasserkrug , „Simulation Optimization Using the Cross-Entropy Method with Optimal Computing Budget Allocation”, ACM Transactions on Modeling and Computer Simulation , 2009.

Chew, EP, LH Lee, SY Teng și CH Koh, „Differentiated Service Inventory Optimization using Imbricate Partitions and MOCBA”, Computers and Operations Research , 36(5), : 1703-1710, 2009.

Lee, LH, EP Chew, SY Teng și YK Chen, „Algoritm evolutiv bazat pe simulare multi-obiectivă pentru o problemă de alocare a pieselor de schimb pentru aeronave”, Jurnalul European de Cercetare Operațională , 189 (2): 476-491, 2008.

Chen, CH, D. He, M. Fu și LH Lee, „Eficient Simulation Budget Allocation for Selecting an Optimal Subset”, informează Journal on Computing , Vol. 20, nr. 4, p. 579-595, 2008.

Shi, L. și CH Chen, „A New Algorithm for Stochastic Discrete Resource Alocation Optimization”, Jurnalul de sisteme dinamice de evenimente discrete: Teorie și aplicații , voi. 10, p. 271-294, iulie 2000.

Aplicații ale OCBA

Hsieh, L., E. Huang și CH Chen, „Echipment Utilization Enhancement in Photolithography Area through a Dynamic System Control Using Multi-fidelity Simulation Optimization with Big Data Technique”, IEEE Transactions on Semiconductor Manufacturing Decision , 30(2), 166 -175, 2017.

Aristotelis, T., M. Bastani, N. Celik și CH 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, KH Chang, CH Chen, „Application of Multi-Fidelity Simulation Modeling to Integrated Circuit Packaging”, International Journal of Simulation and Process Modeling , 28(2), 195-208, Primavara 2016.

Hsieh, BW, CH Chen, SC Chang, „Compoziția eficientă bazată pe simulare a politicilor de expediere prin integrarea optimizării ordinale cu proiectarea experimentului”, IEEE Transactions on Automation Science and Engineering , voi. 4, nr. 4, p. 553-568, octombrie 2007.

Romero, VJ, DV Ayon, CH Chen, „Demonstrarea conceptelor de optimizare ordinală probabilistică la optimizarea variabilă continuă în condiții de incertitudine”, Optimization and Engineering , voi. 7, nr. 3, p. 343-365, septembrie 2006.

Chen, CH și D. He, „Simularea inteligentă pentru compararea alternativelor și aplicarea la managementul traficului aerian”, Jurnalul de Știință a Sistemelor și Inginerie a Sistemelor , Vol. 14, nr. 1, p. 37-51, martie 2005.

Chen, CH, K. Donohue, E. Yucesan și J. Lin, „Optimal Computing Budget Alocation for Monte Carlo Simulation with Application to Product Design”, Journal of Simulation Practice and Theory , Voi. 11, nr. 1, p. 57-74, martie 2003.

Hsieh, BW, CH Chen și SC Chang, „Scheduling Semiconductor Wafer Fabrication by Using Ordinal Optimization-Based Simulation”, IEEE Transactions on Robotics and Automation , Vol. 17, nr. 5, p. 599-608, octombrie 2001.

Chen, CH, SD Wu și L. Dai, „Compararea ordinală a algoritmilor euristici folosind optimizarea stochastică”, IEEE Transactions on Robotics and Automation , voi. 15, nr. 1, p. 44-56, februarie 1999.

Asociere cu optimizarea ordinală

Dai, L., CH Chen și JR Birge, „Proprietățile de convergență mari ale programării stocastice în două etape”, Jurnalul de Teorie și Aplicații de Optimizare , Voi. 106, nr. 3, p. 489-510, septembrie 2000.

Ho, YC, CG Cassandras, CH Chen și L. Dai, „Ordinal Optimization and Simulation”, Jurnalul Societății de Cercetare Operațională , Vol. 51, nr. 4, p. 490-500, aprilie 2000.

Dai, L. și CH Chen, „Rate of Convergence for Ordinal Comparison of Dependent Simulations in Discrete Event Dynamic Systems,” Journal of Optimization Theory and Applications , Voi. 94, nr. 1, p. 29-54, iulie 1997.

Alte generalizări și lucrări înrudite

Blanchet, J., J. Liu și B. Zwart, „Large Deviations Perspective on Ordinal Optimization of Heavy-Tailed Systems”, Proceedings of the 2007 Winter Simulation Conference , pp. 489-494, 2007.

Branke, J., SE Chick și C. Schmidt. Selectarea unei proceduri de selecție. Management Science 53 1916-1932, 2007.

Chick, S. și K. Inoue. Noi proceduri în două etape și secvențiale pentru selectarea celui mai bun sistem simulat. Cercetare operațională 49 1609-1624, 2001.

Chick, S. și K. Inoue. Noi proceduri pentru a selecta cel mai bun sistem simulat folosind numere aleatorii comune. Management Science 47 1133-1149, 2001.

Glynn, P., S. Juneja. O perspectivă a abaterilor mari asupra optimizării ordinale. Proceedings of the 2004 Winter Simulation Conference , 577-585, 2004.

Pujowidianto, NA, LH Lee, CH Chen, CM Da, „Optimal Computing Budget Allocation For Constrained Optimization”, care va apărea în Proceedings of 2009 Winter Simulation Conference , pp. 584-589, Austin, TX, decembrie 2009.

Trailovic , L. și LY Pao. 2004. Calcularea alocării bugetare pentru ierarhizarea eficientă și selectarea variațiilor cu aplicarea algoritmilor de urmărire țintă. IEEE Transactions on Automatic Control 49 58-67, 2004.

Cărți OCBA

1.O nouă carte despre OCBA a fost publicată în 2011. Numele cărții este „Stochastic Simulation Optimization: An Optimal Computing Budget Allocation”. Această carte oferă o acoperire cuprinzătoare și extinsă asupra acestei metodologii eficiente de optimizare a simulării, de la ideea de bază, dezvoltarea formală, până la stadiul tehnicii. Îl puteți comanda de pe Amazon.com .

2.O altă carte nouă care se extinde la o perspectivă mult mai largă a optimizării ordinale este „ Stochastic Simulation Optimization for Discrete Event Systems - Perturbation Analysis, Ordinal Optimization, and Beyond ” , publicată în 2013.

Codurile sursă pentru computer pentru OCBA

-OCBA C Code , care apare și la paginile 214 - 218 din cartea OCBA .

-Codul OCBA C++ , prin amabilitatea prof. Nurcin Celik de la Universitatea din Miami

-Codul OCBA JAVA , prin amabilitatea prof. Nurcin Celik de la Universitatea din Miami

Demo OCBA (și cod JAVA)

Demo OCBA Folosind browserul dvs. web . Această demonstrație a OCBA este implementată de A. Johnson, Cheol Y. Park și Ning Lin. În demonstrație, veți vedea cum OCBA selectează dinamic modelele demne pentru simulare ulterioară.