Оптимальний розподіл бюджету для обчислень (OCBA)

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

У нас є найсучасніший підхід до розумного розподілу бюджету обчислень для ефективної оптимізації моделювання. Мета полягає в тому, щоб знайти найкращий дизайн, використовуючи мінімальний час моделювання. Багато наших співавторів і друзів роблять свій внесок у збагачення цієї сфери.

Моделювання є популярним інструментом для проектування великих, складних стохастичних систем, оскільки аналітичні рішення закритої форми зазвичай не існують для таких проблем. Незважаючи на те, що розвиток нових технологій різко збільшив обчислювальну потужність, ефективність все ще викликає серйозне занепокоєння при використанні моделювання для проектування великих систем, і в цьому випадку потрібно моделювати багато альтернативних проектів. Що ще гірше, для кожного дизайну необхідно виконати кілька прогонів моделювання, щоб виявити стохастичну поведінку систем. Як різко скоротити загальний час обчислень є ключовим питанням у цій темі.

Ключовим компонентом нашої методології є наш новий метод моделювання на основі теорії управління під назвою Оптимальний розподіл бюджету обчислень (OCBA). Підхід OCBA може інтелектуально визначати найефективнішу кількість копій симуляції або довжину симуляції для всіх змодельованих альтернатив. Мета полягає в тому, щоб отримати найвищу якість рішення моделювання, використовуючи фіксований бюджет обчислень, або досягти бажаної якості рішення моделювання, використовуючи мінімальний бюджет обчислень. Чисельне тестування показує, що наш підхід може отримати таку саму якість моделювання, витративши лише одну десяту зусиль на моделювання.

OCBA також ідеально підходить для оптимізації стохастичного моделювання. Основною причиною складності оптимізації моделювання є стохастичний характер оцінювання цільової функції, що означає, що існує основний компроміс між витрачанням обчислювальних зусиль на пошук простору для нових потенційних рішень (дослідження) проти отримання більш точних оцінок цільової функції. при перспективних на сьогодні рішеннях (експлуатації). Іншими словами, скільки бюджету моделювання має бути виділено на додаткові реплікації у вже відвіданих точках, а скільки на реплікації в новостворених точках пошуку, є основним фактором з точки зору ефективності обчислень. Під час процедури OCBA послідовно визначає, які альтернативи дизайну потребують додаткового моделювання та скільки додаткових копій потрібно.

Інтуїтивно зрозуміло, щоб забезпечити правильний вибір найкращої альтернативи, більшу частину обчислювального бюджету слід виділити на ті альтернативи, які є критичними в процесі визначення найкращої альтернативи. Іншими словами, з цими критичними альтернативами необхідно провести більшу кількість симуляцій, щоб зменшити відхилення цих критичних оцінювачів. Загальна ефективність моделювання покращується, оскільки менше обчислювальних зусиль витрачається на моделювання некритичних альтернатив і більше витрачається на критичні альтернативи. Ідеї ​​пояснюються на наступному простому прикладі. Припустимо, ми виконуємо моделювання для 5 альтернатив, щоб визначити альтернативу з мінімальною середньою затримкою. Перш за все, ми проводимо попереднє моделювання для всіх 5 альтернатив. На малюнку 1-(a) наведено приклад їхніх 99% довірчих інтервалів, отриманих під час попереднього моделювання. Зауважте, що невизначеність оцінки зумовлена ​​стохастичними характеристиками системи та використанням моделювання Монте-Карло.

Як показано на малюнку 1-(a), хоча існує невизначеність в оцінці продуктивності для кожної альтернативи, очевидно, що альтернативи 2 і 3 набагато кращі за інші альтернативи, якщо ми маємо намір знайти альтернативу з мінімальним середнім затримка. І тому лише альтернативи 2 і 3 необхідно додатково моделювати, щоб зменшити невизначеність оцінки, щоб правильно визначити найкращу альтернативу. Зупинивши симуляції для альтернатив 1, 4 і 5 раніше, ми можемо значно заощадити на обчисленнях.

Однак те, що насправді відбувається в більшості випадків, не таке тривіальне, як показано на малюнку 1-(a). Більш поширеними є випадки, подібні до іншого прикладу, показаного на малюнку 1-(b), де деякі альтернативи здаються кращими, але не є явно кращими за інші. У таких випадках непросто визначити, які альтернативи можна вилучити з симуляційного експерименту та коли їх слід припинити. OCBA забезпечує систематичний підхід до вирішення цієї проблеми та розподілення циклів моделювання між альтернативами таким чином, щоб ефективність моделювання була максимальною.

Щоб дізнатися більше про OCBA, наступні два документи є хорошою відправною точкою:

Представлення ідей OCBA

Chen, CH та LH Lee, Оптимізація стохастичного моделювання: оптимальний розподіл бюджету для обчислень . World Scientific Publishing Co., 2011.

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

Xu, J., E. Huang, CH Chen і 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), червень 2015 рік

Chen, CH, M. Fu, and L. Shi, "Simulation and Optimization," Tutorials in Operations Research , pp. 247-260, Informs, Hanover, MD, 2008.

Fu, M, CH Chen і L. Shi, "Some Topics for Simulation Optimization", Proceedings of 2008 Winter Simulation Conference , pp. 27-38, Miami, FL, грудень 2008.

Ось ще кілька репрезентативних публікацій про техніку OCBA.

Одна з найпопулярніших робіт OCBA

Chen, CH, J. Lin, E. Yucesan, and SE Chick, "Simulation Budget Allocation for Further Enhancing the Efficiency of Ordinal Optimization", Journal of Discrete Event Dynamic Systems: Theory and Applications , Vol. 10, стор. 251-270, липень 2000 р.

Попередня розробка OCBA

Chen, CH "An Effective Approach to Smartly Allocate Computing Budget for Discrete Event Simulation", Proceedings of 34th IEEE Conference on Decision and Control , стор. 2598-2605, грудень 1995.

Chen, CH "Нижня межа для правильної ймовірності вибору підмножини та її застосування до симуляції системи дискретних подій", Transactions IEEE on Automatic Control , Vol. 41, № 8, стор. 1227-1231, серпень 1996.

Chen, CH, E. Yucesan, L. Dai та HC Chen, "Ефективне обчислення оптимального розподілу бюджету для експерименту моделювання дискретних подій", Transactions IIE , Vol. 42, № 1, стор. 60-70, січень 2010.

OCBA для проблем із кількома цілями

Lee, LH, EP Chew, SY Teng, and D. Goldsman, "Optimal computing budget allocation for multi-Objective Simulation Models", Proceedings of 2004 Winter Simulation Conference , pp. 586-594, 2004.

Е. Дж. Чен і Л. Х. Лі, «Процедура багатоцільового вибору визначення набору Парето», Комп’ютери та дослідження операцій, 36(6) , : 1872-1879, 2009.

С. Тенг, Л. Х. Лі та Е. П. Чу, «Інтеграція зони байдужості з розподілом бюджету багатоцільового обчислення», Європейський журнал операційних досліджень, 203(2): 419-429, 2010.

LH Lee, EP Chew, SY Teng і D. Goldsman (2010). Знаходження набору Парето для багатоцільових імітаційних моделей, які з’являться в транзакціях IIE .

OCBA для вибору оптимальної підмножини найкращих дизайнів (скажімо, 5 найкращих)

Chen, CH, D. He, M. Fu, and LH Lee, "Efficient Simulation Budget Allocation for Selecting an Optimal Subset", Inform Journal on Computing , Vol. 20, № 4, стор. 579-595, 2008.

Zhang, S., LH Lee, EP Chew, J. Xu, and CH Chen, "A Simulation Budget Allocation Procedure for Enhancing the Efficiency of Optimal Subset Selection", IEEE Transactions on Automatic Control , 61(1), 62-75, Січень 2016 року.

OCBA для вибору найкращої альтернативи, коли зразки корельовані

Fu, MC, JQ Hu, CH Chen і X. Xiong, «Розподіл симуляції для визначення найкращого дизайну за наявності корельованої вибірки», інформує Journal on Computing , Vol. 19, № 1, С. 101-111, 2007.

OCBA для моделювання та оптимізації

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

Ніколас, П., «Алгоритм розділення прямокутників для оптимізації стохастичного моделювання», Матеріали 14-ї конференції INFORMS Computing Society , Річмонд, Вірджинія, січень 2015 р.

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

Чу, Е.П., Л.Х. Лі, С.Й. Тенг і Ч.Х. Ко, «Оптимізація диференційованого інвентаризації послуг за допомогою вкладених розділів і MOCBA», Комп’ютери та дослідження операцій , 36(5), : 1703-1710, 2009.

Lee, LH, EP Chew, SY Teng та YK Chen, "Багатоцільовий еволюційний алгоритм на основі моделювання для проблеми розподілу запасних частин літака", European Journal of Operational Research , 189 (2): 476-491, 2008.

Chen, CH, D. He, M. Fu, and LH Lee, "Efficient Simulation Budget Allocation for Selecting an Optimal Subset", Inform Journal on Computing , Vol. 20, № 4, стор. 579-595, 2008.

Shi, L. and CH Chen, "A New Algorithm for Stochastic Discrete Resource Allocation Optimization", Journal of Discrete Event Dynamic Systems: Theory and Applications , Vol. 10, стор. 271-294, липень 2000 р.

Застосування OCBA

Hsieh, L., E. Huang, and CH Chen, "Equipment 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 рік.

Арістотеліс, Т., М. Бастані, Н. Селік і Ч. Ч. Чен, "Система адаптивного моделювання на основі динамічних даних для автоматизованого керування в мікромережах", Транзакції IEEE на 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, Весна 2016 року.

Hsieh, BW, CH Chen, SC Chang, "Efficient Simulation-based Composition of Dispatching Policies by Integrating Ordinal Optimization with Design of Experiment", IEEE Transactions on Automation Science and Engineering , Vol. 4, № 4, стор. 553-568, жовтень 2007.

Ромеро, VJ, DV Ayon, CH Chen, "Демонстрація концепцій імовірнісної порядкової оптимізації для оптимізації безперервної змінної в умовах невизначеності", Optimization and Engineering , Vol. 7, № 3, стор. 343-365, вересень 2006.

Chen, CH, and D. He, "Intelligent Simulation for Alternative Comparison and Application to Air Traffic Management," Journal of Systems Science and System Engineering , Vol. 14, № 1, стор. 37-51, березень 2005.

Chen, CH, K. Donohue, E. Yucesan, and J. Lin, "Optimal Computing Budget Allocation for Monte Carlo Simulation with Application to Product Design", Journal of Simulation Practice and Theory , Vol. 11, № 1, стор. 57-74, березень 2003.

Hsieh, BW, CH Chen і SC Chang, "Scheduling Semiconductor Wafer Fabrication by Using Ordinal Optimization-Based Simulation", IEEE Transactions on Robotics and Automation , Vol. 17, № 5, стор. 599-608, жовтень 2001.

Chen, CH, SD Wu та L. Dai, "Порядкове порівняння евристичних алгоритмів з використанням стохастичної оптимізації", IEEE Transactions on Robotics and Automation , Vol. 15, № 1, стор. 44-56, лютий 1999.

Асоціація з порядковою оптимізацією

Dai, L., CH Chen і JR Birge, "Властивості великої конвергенції двоетапного стохастичного програмування", Journal of Optimization Theory and Applications , Vol. 106, № 3, стор. 489-510, вересень 2000 р.

Ho, YC, CG Cassandras, CH Chen і L. Dai, "Ordinal Optimization and Simulation", Journal of Operational Research Society , Vol. 51, № 4, стор. 490-500, квітень 2000.

Dai, L. and CH Chen, "Швидкість збіжності для порядкового порівняння залежних симуляцій у динамічних системах із дискретними подіями", Journal of Optimization Theory and Applications , Vol. 94, № 1, стор. 29-54, липень 1997 р.

Деякі інші узагальнення та пов’язані роботи

Blanchet, J., J. Liu, and B. Zwart, "Large Deviations Perspective on Ordinal Optimization of Heavy tailed Systems", Proceedings of 2007 Winter Simulation Conference , pp. 489-494, 2007.

Branke, J., SE Chick і C. Schmidt. Вибір процедури відбору. Наука управління 53 1916-1932, 2007.

Чік, С. і К. Іноуе. Нові двоетапні та послідовні процедури вибору найкращої змодельованої системи. Дослідження операцій 49 1609-1624, 2001.

Чік, С. і К. Іноуе. Нові процедури вибору найкращої змодельованої системи за допомогою загальних випадкових чисел. Наука управління 47 1133-1149, 2001.

Глінн, П., С. Джуня. Перспектива великих відхилень щодо порядкової оптимізації. Матеріали 2004 Winter Simulation Conference , 577-585, 2004.

Pujowidianto, NA, LH Lee, CH Chen, CM Yep, "Optimal Computing Budget Allocation for Constrained Optimization", щоб з'явитися в Proceedings of 2009 Winter Simulation Conference , pp. 584-589, Austin, TX, грудень 2009.

Trailovic , L. і LY Pao. 2004. Розрахунок розподілу бюджету для ефективного ранжування та відбору відхилень із застосуванням алгоритмів відстеження цілей. IEEE Transactions on Automatic Control 49 58-67, 2004.

Книги OCBA

1.Нова книга про OCBA була опублікована в 2011 році. Назва книги: «Оптимізація стохастичного моделювання: оптимальний розподіл бюджету для обчислень». У цій книзі детально викладено цю ефективну методологію оптимізації моделювання, від основної ідеї, формальної розробки до найсучаснішого стану. Ви можете замовити його на Amazon.com .

2.Ще одна нова книга, яка розкриває набагато ширшу перспективу порядкової оптимізації, — « Оптимізація стохастичного моделювання для дискретних подійних систем — аналіз збурень, порядкова оптимізація та інше » , опублікована в 2013 році.

Комп'ютерні вихідні коди для OCBA

-Код OCBA C , який також міститься на сторінках 214-218 книги OCBA .

-Код OCBA C++ , люб’язно наданий професором Нурчіном Челіком з Університету Маямі

-Код OCBA JAVA , люб’язно наданий професором Нурчіном Челіком з Університету Маямі

Демо OCBA (і код JAVA)

Демонстрація OCBA за допомогою веб-браузера . Цю демонстрацію OCBA реалізовано А. Джонсоном, Чеол Ю. Парком і Нін Ліном. У демонстрації ви побачите, як OCBA динамічно вибирає гідні проекти для подальшого моделювання.