Оптимальное распределение вычислительного бюджета (OCBA)

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

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

Моделирование является популярным инструментом для проектирования больших, сложных стохастических систем, поскольку для таких задач обычно не существует аналитических решений в закрытой форме. Несмотря на то, что развитие новых технологий значительно увеличило вычислительную мощность, эффективность по-прежнему вызывает серьезную озабоченность при использовании моделирования для проектирования больших систем, и в этом случае необходимо моделировать множество альтернативных проектов. Что еще хуже, для каждого проекта необходимо выполнить несколько прогонов моделирования, чтобы уловить стохастическое поведение в системах. Ключевой вопрос в этой теме — как резко сократить общее время вычислений.

Ключевым компонентом наших методологий является наша новая теоретико-управляющая техника моделирования под названием «Оптимальное распределение вычислительного бюджета» (OCBA). Подход OCBA может интеллектуально определять наиболее эффективные числа повторений моделирования или продолжительность моделирования для всех моделируемых альтернатив. Цель состоит в том, чтобы получить наивысшее качество решения при моделировании, используя фиксированный бюджет вычислений, или достичь желаемого качества решения при моделировании, используя минимальный бюджет вычислений. Численное тестирование показывает, что наш подход может обеспечить такое же качество симуляции, затратив всего лишь одну десятую усилий на симуляцию.

OCBA также идеально подходит для оптимизации стохастического моделирования. Основной причиной сложности оптимизации моделирования является стохастический характер оценки целевой функции, а это означает, что существует базовый компромисс между выделением вычислительных усилий на поиск в пространстве новых возможных решений (исследование) и получением более точных оценок целевой функции. на перспективных в настоящее время решениях (эксплуатация). Другими словами, какая часть бюджета моделирования должна быть выделена на дополнительные повторения в уже посещенных точках и сколько на повторения в вновь созданных точках поиска, является основным соображением с точки зрения вычислительной эффективности. В процедуре OCBA последовательно определяет, какие варианты дизайна требуют большего моделирования и сколько дополнительных повторений необходимо.

Интуитивно понятно, что для обеспечения правильного выбора наилучшей альтернативы большая часть вычислительного бюджета должна быть выделена на те альтернативы, которые имеют решающее значение в процессе определения наилучшей альтернативы. Другими словами, необходимо провести большее количество симуляций с этими критическими альтернативами, чтобы уменьшить дисперсию этих критических оценок. Общая эффективность моделирования повышается, поскольку на моделирование некритических альтернатив тратится меньше вычислительных ресурсов, а на критические альтернативы — больше. Идеи поясняются на следующем простом примере. Предположим, мы выполняем моделирование для 5 альтернатив, чтобы определить альтернативу с минимальной средней задержкой. Прежде всего, мы проводим предварительное моделирование для всех 5 альтернатив. Рисунок 1-(a) дает пример их 99% доверительных интервалов, полученных в результате предварительного моделирования. Обратите внимание, что неопределенность оценки связана со стохастическими особенностями системы и использованием моделирования Монте-Карло.

Как видно на рис. 1-(а), несмотря на неопределенность в оценке производительности для каждой альтернативы, очевидно, что альтернативы 2 и 3 намного лучше, чем другие альтернативы, если мы намерены найти альтернативу с минимальным средним значением. задерживать. Таким образом, только альтернативы 2 и 3 необходимо дополнительно смоделировать, чтобы уменьшить неопределенность оценки и правильно определить наилучшую альтернативу. Остановив симуляции для альтернатив 1, 4 и 5 раньше, мы можем сэкономить много вычислительных ресурсов.

Однако то, что на самом деле происходит в большинстве случаев, не так тривиально, как показано на рис. 1-(а). Чаще встречаются случаи, подобные другому примеру, показанному на рис. 1-(b), где некоторые альтернативы кажутся лучше, но не явно лучше других. В таких случаях непросто определить, какие альтернативы можно исключить из имитационного эксперимента и когда их следует прекратить. OCBA обеспечивает системный подход к решению этой проблемы и распределению прогонов моделирования по альтернативам таким образом, чтобы эффективность моделирования была максимальной.

Чтобы узнать больше об OCBA, хорошей отправной точкой могут стать следующие две статьи:

Внедрение идей OCBA

Чен, С. Х. и Л. Х. Ли, Оптимизация стохастического моделирования: оптимальное распределение бюджета на вычисления . Мировое научное издательство, 2011.

Сюй Дж., Э. Хуан, Л. Се, Л. Х. Ли, К. С. Цзя и Ч. Чен, «Оптимизация моделирования в эпоху Industrial 4.0 и промышленного Интернета», 10 (4), 310-320, Journal of Simulation , 2016.

Сюй Дж., Э. Хуанг, Ч. Чен и Л. Х. Ли, «Оптимизация моделирования: обзор и исследования в новую эру облачных вычислений и больших данных», Азиатско-Тихоокеанский журнал операционных исследований , 32 (3), июнь. 2015

Чен, К. Х., М. Фу и Л. Ши, «Моделирование и оптимизация», Учебные пособия по исследованию операций , стр. 247–260, Informs, Ганновер, Мэриленд, 2008 г.

Фу, М., Ч. Чен и Л. Ши, «Некоторые темы для оптимизации моделирования», Труды Зимней конференции по моделированию 2008 г. , стр. 27–38, Майами, Флорида, декабрь 2008 г.

Вот еще несколько репрезентативных публикаций о методах OCBA.

Одна из самых популярных статей OCBA

Чен, К. Х., Дж. Лин, Э. Юсесан и С. Е. Чик, «Распределение бюджета моделирования для дальнейшего повышения эффективности порядковой оптимизации», Журнал дискретных событийных динамических систем: теория и приложения , Vol. 10, стр. 251-270, июль 2000 г.

Раннее развитие OCBA

Чен, CH «Эффективный подход к разумному распределению вычислительного бюджета для дискретного моделирования событий», Труды 34-й конференции IEEE по решениям и управлению , стр. 2598-2605, декабрь 1995 г.

Чен, Ч.Х. «Нижняя граница вероятности правильного выбора подмножества и ее применение к моделированию системы дискретных событий», IEEE Transactions on Automatic Control , Vol. 41, № 8, стр. 1227-1231, август 1996 г.

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

OCBA для проблем с несколькими целями

Lee, LH, EP Chew, SY Teng и D. Goldsman, «Оптимальное распределение бюджета вычислений для многоцелевых имитационных моделей», Proceedings of 2004 Winter Simulation Conference , стр. 586-594, 2004.

Э. Дж. Чен и Л. Х. Ли, «Многоцелевая процедура выбора для определения множества Парето», Computers and Operations Research, 36 (6) , : 1872-1879, 2009.

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

Л.Х. Ли, Э.П. Чу, С.И. Тенг и Д. Голдсман (2010). Поиск набора Парето для многокритериальных имитационных моделей, который появится в IIE Transactions .

OCBA для выбора оптимального подмножества лучших проектов (скажем, 5 лучших)

Chen, CH, D. He, M. Fu и LH Lee, "Эффективное распределение бюджета моделирования для выбора оптимального подмножества", сообщает Journal on Computing , Vol. 20, № 4, стр. 579-595, 2008.

Чжан С., Ли Л. Х., Чу Э. П., Сюй Дж., Чен Ч. «Процедура распределения бюджета моделирования для повышения эффективности выбора оптимального подмножества», Транзакции IEEE по автоматическому управлению , 61 (1), 62-75, январь 2016 г.

OCBA для выбора наилучшей альтернативы при корреляции выборок

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

OCBA для моделирования и оптимизации

Чжан С., Дж. Сюй, Л. Х. Ли, Э. П. Чу, В. П. Вонг и Ч. Чен, «Оптимальное распределение бюджета вычислений для оптимизации роя частиц в стохастической оптимизации», IEEE Transactions on Evolutionary Computation, 21 (2) , 206-219 , 2017.

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

Д. Хе, Ли Л. Х., Чен Ч. Х., Фу М. и Вассеркруг С. , «Оптимизация моделирования с использованием метода кросс-энтропии с оптимальным распределением вычислительного бюджета», Транзакции ACM по моделированию и компьютерному моделированию , 2009 г.

Chew, EP, LH Lee, SY Teng и CH Koh, «Оптимизация инвентаризации дифференцированных услуг с использованием вложенных разделов и MOCBA», Computers and Operations Research , 36 (5), : 1703-1710, 2009.

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

Ши, Л. и Чен Ч., "Новый алгоритм стохастической оптимизации распределения дискретных ресурсов", Журнал дискретных событийных динамических систем: теория и приложения , Vol. 10, стр. 271-294, июль 2000 г.

Приложения OCBA

Се, Л., Э. Хуанг и Ч. Чен, «Расширение использования оборудования в области фотолитографии с помощью динамического управления системой с использованием оптимизации многоточечного моделирования с помощью технологии больших данных», IEEE Transactions on Semiconductor Manufacturing Decision, 30 (2) , 166 -175, 2017.

Аристотелис, Т., М. Бастани, Н. Челик, и Ч. Чен, "Динамическая структура адаптивного моделирования, управляемая данными, для автоматизированного управления в микросетях", IEEE Transactions on Smart Grid , 8(1), 209-218, 2017 .

Се, Л., Э. Хуанг, С. Чжан, К. Х. Чанг, Ч. Х. Чен, «Применение многоцелевого имитационного моделирования к корпусированию интегральных схем», Международный журнал моделирования и моделирования процессов , 28 (2), 195–208, Весна 2016.

Се, Б.В., Чен С.Х., Чанг С.К., "Эффективное построение политик диспетчеризации на основе моделирования путем интеграции порядковой оптимизации с планом эксперимента", IEEE Transactions on Automation Science and Engineering , Vol. 4, № 4, стр. 553-568, октябрь 2007 г.

Ромеро, В. Дж., Д. В. Айон, Ч. Чен, "Демонстрация концепций вероятностной порядковой оптимизации для оптимизации с непрерывными переменными в условиях неопределенности", Оптимизация и проектирование , Vol. 7, № 3, стр. 343-365, сентябрь 2006 г.

Чен, С. Х. и Д. Хе, «Интеллектуальное моделирование для сравнения альтернатив и их применения к управлению воздушным движением», Журнал системных наук и системной инженерии , Vol. 14, № 1, стр. 37-51, март 2005 г.

Чен, С. Х., К. Донохью, Э. Юсесан и Дж. Лин, «Оптимальное распределение бюджета на вычисления для моделирования Монте-Карло с применением к дизайну продукта», Журнал практики и теории моделирования , Vol. 11, № 1, стр. 57-74, март 2003 г.

Се, Б.В., Чен С.Х. и Чанг С.К., "Планирование производства полупроводниковых пластин с помощью моделирования на основе порядковой оптимизации", IEEE Transactions on Robotics and Automation , Vol. 17, № 5, стр. 599-608, октябрь 2001 г.

Чен, С. Х., С. Д. Ву и Л. Дай, "Порядковое сравнение эвристических алгоритмов с использованием стохастической оптимизации", IEEE Transactions on Robotics and Automation , Vol. 15, № 1, стр. 44-56, февраль 1999 г.

Ассоциация с порядковой оптимизацией

Дай, Л., Чен Ч. и Бирдж Дж., "Свойства большой сходимости двухэтапного стохастического программирования", Журнал теории и приложений оптимизации , Vol. 106, № 3, стр. 489-510, сентябрь 2000 г.

Ho, YC, CG Cassandras, CH Chen и L. Dai, "Ординальная оптимизация и моделирование", Journal of Operational Research Society , Vol. 51, № 4, стр. 490-500, апрель 2000 г.

Дай, Л. и Чен Ч., «Скорость сходимости для порядкового сравнения зависимых симуляций в динамических системах с дискретными событиями», Журнал теории и приложений оптимизации , Vol. 94, № 1, стр. 29-54, июль 1997 г.

Некоторые другие обобщения и родственные работы

Бланше, Дж., Дж. Лю и Б. Цварт, «Перспектива больших отклонений в порядковой оптимизации систем с тяжелыми хвостами», Труды зимней конференции по моделированию 2007 г. , стр. 489–494, 2007 г.

Бранке Дж., С.Э. Чик и К. Шмидт. Выбор процедуры отбора. Наука управления 53 1916-1932, 2007.

Чик С. и К. Иноуэ. Новые двухэтапные и последовательные процедуры выбора наилучшей моделируемой системы. Исследование операций 49 1609-1624, 2001.

Чик С. и К. Иноуэ. Новые процедуры для выбора лучшей смоделированной системы с использованием обычных случайных чисел. Наука управления 47 1133-1149, 2001.

Глинн П., С. Джунжа. Перспектива больших отклонений в порядковой оптимизации. Материалы зимней конференции по моделированию 2004 г. , 577–585, 2004 г.

Пуджовидианто, Н.А., Ли Л.Х., Чен Ч.Х., Йеп К.М., «Оптимальное распределение бюджета вычислений для оптимизации с ограничениями», опубликовано в Трудах зимней конференции по моделированию 2009 г. , стр. 584–589, Остин, Техас, декабрь 2009 г.

Трайлович Л. и Л.Ю. Пао. 2004. Вычисление распределения бюджета для эффективного ранжирования и выбора отклонений с применением алгоритмов отслеживания целей. IEEE Transactions on Automatic Control 49 58-67, 2004.

Книги OCBA

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

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

Компьютерные исходные коды для OCBA

-OCBA C Code , который также появляется на страницах 214-218 книги OCBA .

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

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

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

Демонстрация OCBA с использованием вашего веб-браузера . Эта демонстрация OCBA реализована А. Джонсоном, Чеолом Ю. Паком и Нин Лин. В демо вы увидите, как OCBA динамически выбирает достойные проекты для дальнейшего моделирования.