Оптимизация на основе моделирования - Simulation-based optimization - Wikipedia

Оптимизация на основе моделирования (также известный как просто оптимизация моделирования) объединяет оптимизация методы в симуляция моделирование и анализ. Из-за сложности моделирования целевая функция может стать трудным и дорогостоящим для оценки. Обычно лежащая в основе имитационная модель является стохастической, так что целевая функция должна оцениваться с использованием методов статистической оценки (называемых выходным анализом в методологии моделирования).

После математического моделирования системы компьютерное моделирование предоставляет информацию о ее поведении. Методы параметрического моделирования могут использоваться для улучшения производительности системы. В этом методе ввод каждой переменной варьируется, при этом другие параметры остаются постоянными, и наблюдается влияние на цель проекта. Это трудоемкий метод, который частично улучшает производительность. Чтобы получить оптимальное решение с минимальными затратами времени и вычислений, задача решается итеративно, при этом на каждой итерации решение приближается к оптимальному. Такие методы известны как «численная оптимизация» или «оптимизация на основе моделирования».^[1]

В имитационном эксперименте цель состоит в том, чтобы оценить влияние различных значений входных переменных на систему. Однако иногда интерес заключается в поиске оптимального значения для входных переменных с точки зрения результатов системы. Одним из способов может быть проведение экспериментов по моделированию для всех возможных входных переменных. Однако этот подход не всегда практичен из-за нескольких возможных ситуаций, и он просто затрудняет проведение экспериментов для каждого сценария. Например, может быть слишком много возможных значений для входных переменных или имитационная модель может быть слишком сложной и дорогой для запуска при неоптимальных значениях входных переменных. В этих случаях цель состоит в том, чтобы найти оптимальные значения для входных переменных, а не пробовать все возможные значения. Этот процесс называется оптимизацией моделирования.^[2]

Конкретные методы оптимизации, основанные на моделировании, могут быть выбраны в соответствии с рисунком 1 на основе типов переменных решения.^[3]

Рис.1 Классификация оптимизации на основе моделирования по типам переменных

Оптимизация существует в двух основных областях исследования операций:

Оптимизация параметрический (статический) - Цель состоит в том, чтобы найти значения параметров, которые являются «статическими» для всех состояний, с целью максимизации или минимизации функции. В этом случае можно использовать математическое программирование, Такие как линейное программирование. В этом сценарии моделирование помогает, когда параметры содержат шум или оценка проблемы потребует чрезмерного компьютерного времени из-за ее сложности.^[4]

Оптимизация контроль (динамический) - Это в основном используется в Информатика и электротехника. Оптимальное управление для каждого состояния, и результаты меняются в каждом из них. Можно использовать математическое программирование, а также динамическое программирование. В этом сценарии моделирование может генерировать случайные выборки и решать сложные и крупномасштабные проблемы.^[4]

Методы оптимизации на основе моделирования

Некоторые важные подходы к оптимизации моделирования обсуждаются ниже. ^[5][6]

Статистическое ранжирование и методы отбора (R / S)

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

Методология поверхности отклика (RSM)

В методология поверхности отклика, цель состоит в том, чтобы найти взаимосвязь между входными переменными и переменными ответа. Процесс начинается с попытки подобрать модель линейной регрессии. Если P-значение окажется низким, будет реализована полиномиальная регрессия более высокой степени, которая обычно является квадратичной. Процесс поиска хорошей взаимосвязи между входными переменными и переменными отклика будет выполняться для каждого теста моделирования. При оптимизации моделирования можно использовать метод поверхности отклика для поиска наилучших входных переменных, которые дают желаемые результаты с точки зрения переменных отклика.^[7]

Эвристические методы

Эвристические методы точность изменения скорости. Их цель - найти хорошее решение быстрее, чем традиционные методы, когда они слишком медленные или не могут решить проблему. Обычно вместо оптимального значения они находят локальное оптимальное; однако значения считаются достаточно близкими к окончательному решению. Примеры таких методов включают: табу поиск и генетические алгоритмы.^[4]

Метамодели позволяют исследователям получать надежные приближенные выходные данные модели без проведения дорогостоящих и трудоемких компьютерных симуляций. Следовательно, процесс оптимизации модели может занять меньше времени и затрат на вычисления. ^[8]

Стохастическое приближение

Стохастическое приближение используется, когда функция не может быть вычислена напрямую, а только оценена с помощью зашумленных наблюдений. В этих сценариях этот метод (или семейство методов) ищет экстремумы этих функций. Целевая функция будет:^[9]

${\displaystyle {\underset {{\text{x}}\in \theta }{\min }}f{\bigl (}{\text{x}}{\bigr )}={\underset {{\text{x}}\in \theta }{\min }}\mathrm {E} [F{\bigl (}{\text{x,y}})]}$

${\displaystyle y}$ - случайная величина, представляющая шум.

${\displaystyle x}$ параметр, который минимизирует ${\displaystyle f{\bigl (}{\text{x}}{\bigr )}}$.

${\displaystyle \theta }$ это область определения параметра ${\displaystyle x}$.

Методы оптимизации без производных

Оптимизация без производных является предметом математической оптимизации. Этот метод применяется к определенной задаче оптимизации, когда его производные недоступны или ненадежны. Методы, не использующие производные, создают модель, основанную на значениях выборки функций, или непосредственно создают выборку значений функций без использования подробной модели. Поскольку для него не нужны производные, его нельзя сравнивать с методами, основанными на производных.^[10]

Для задач безусловной оптимизации он имеет вид:

${\displaystyle {\underset {{\text{x}}\in \mathbb {R} ^{n}}{\min }}f{\bigl (}{\text{x}}{\bigr )}}$

Ограничения оптимизации без производных:

1. Некоторые методы не могут обрабатывать задачи оптимизации с более чем несколькими переменными; результаты обычно не такие точные. Тем не менее, существует множество практических случаев, когда методы без производных были успешны в нетривиальных задачах оптимизации моделирования, которые включают случайность, проявляющуюся как «шум» в целевой функции. См., Например, следующие^[5][11].

2. Столкнувшись с минимизацией невыпуклых функций, он покажет свои ограничения.

3. Методы оптимизации без производных относительно просты и легки, но, как и большинство методов оптимизации, при практической реализации (например, при выборе параметров алгоритма) требуется некоторая осторожность.

Динамическое программирование и нейродинамическое программирование

Динамическое программирование

Динамическое программирование касается ситуаций, когда решения принимаются поэтапно. Ключ к решению подобных проблем - найти компромисс между текущими и будущими затратами.^[12]

Одна динамическая базовая модель имеет две особенности:

1) Имеет динамическую систему с дискретным временем.

2) Функция стоимости складывается со временем.

Для дискретных функций динамическое программирование имеет вид:

${\displaystyle x_{k+1}=f_{k}(x_{k},u_{k},w_{k}),k=0,1,...,N-1}$

${\displaystyle k}$ представляет собой индекс дискретного времени.

${\displaystyle x_{k}}$ - это состояние времени k, оно содержит прошлую информацию и подготавливает ее для будущей оптимизации.

${\displaystyle u_{k}}$ - управляющая переменная.

${\displaystyle w_{k}}$ - случайный параметр.

Для функции стоимости она имеет вид:

${\displaystyle g_{N}(X_{N})+\sum _{k=0}^{N-1}g_{k}(x_{k},u_{k},W_{k})}$

${\displaystyle g_{N}(X_{N})}$ стоимость в конце процесса.

Поскольку стоимость не может быть оптимизирована осмысленно, можно использовать ожидаемое значение:

${\displaystyle E\{g_{N}(X_{N})+\sum _{k=0}^{N-1}g_{k}(x_{k},u_{k},W_{k})\}}$

Нейродинамическое программирование

Нейродинамическое программирование - то же самое, что и динамическое программирование, за исключением того, что первое имеет концепцию аппроксимационных архитектур. Он сочетает в себе искусственный интеллект, алгоритмы моделирования и методы функционального подхода. «Нейро» в этом термине происходит от сообщества искусственного интеллекта. Это означает научиться принимать более совершенные решения на будущее с помощью встроенного механизма, основанного на текущем поведении. Наиболее важной частью нейродинамического программирования является создание обученной нейросети для решения оптимальной задачи.^[13]

Ограничения

Оптимизация на основе моделирования имеет некоторые ограничения, такие как сложность создания модели, которая имитирует динамическое поведение системы таким образом, который считается достаточно хорошим для ее представления. Другая проблема - сложность определения неконтролируемых параметров как реальной системы, так и моделирования. Более того, можно получить только статистическую оценку реальных значений. Определить целевую функцию непросто, поскольку это результат измерений, который может нанести вред решениям.^[14][15]

Рекомендации

1. Нгуен, Ань-Туан, Сигрид Райтер и Филипп Риго. "Обзор методов оптимизации на основе моделирования, применяемых для анализа производительности зданий.."Прикладная энергия 113 (2014): 1043–1058.
2. Карсон, Иоланда и Ану Мария. "Оптимизация моделирования: методы и приложения." Материалы 29-й зимней конференции по моделированию.. Компьютерное общество IEEE, 1997.
3. Джалали, Хамед и Иннеке Ван Ньивенхейз. "Оптимизация моделирования при пополнении запасов: классификация. »IIE Transactions 47.11 (2015): 1217-1235.
4. Абхиджит Госави, Оптимизация на основе моделирования: методы параметрической оптимизации и обучение с подкреплением, Springer, 2-е издание (2015 г.)
5. Фу, Майкл, редактор (2015). Справочник по оптимизации моделирования. Springer.
6. Сполл, Дж. К. (2003). Введение в стохастический поиск и оптимизацию: оценка, моделирование и управление. Хобокен: Вайли.
7. Рахими Мазрае Шахи, М., Фаллах Мехдипур, Э. и Амири, М. (2016), Оптимизация с использованием методологии моделирования и поверхности отклика с приложением для планирования движения поездов в метро. Intl. Пер. в соч. Res., 23: 797–811. Дои:10.1111 / itor.12150
8. Юсефи, Милад; Юсефи, мусульманин; Феррейра, Рикардо Полей Мартинс; Ким, Чжун Хун; Фольятто, Флавио С. (2018). «Хаотический генетический алгоритм и подход к метамоделированию ансамбля Adaboost для оптимального планирования ресурсов в отделениях неотложной помощи». Искусственный интеллект в медицине. 84: 23–33. Дои:10.1016 / j.artmed.2017.10.002. PMID  29054572.
9. Пауэлл, В. (2011). Приближенное динамическое программирование, снимающее проклятия размерности (2-е изд., Серия Wiley по вероятности и статистике). Хобокен: Вайли.
10. Conn, A.R .; Шейнберг, К.; Висенте, Л. Н. (2009). Введение в оптимизацию без производных. Серия книг MPS-SIAM по оптимизации. Филадельфия: СИАМ. Проверено 18 января 2014.
11. Фу, М.С., Хилл, С.Д. Оптимизация дискретных систем событий с помощью стохастической аппроксимации одновременных возмущений. IIE транзакции 29, 233–243 (1997). https://doi.org/10.1023/A:1018523313043
12. Купер, Леон; Купер, Мэри В. Введение в динамическое программирование. Нью-Йорк: Pergamon Press, 1981.
13. Ван Рой, Б., Бертсекас, Д., Ли, Ю., & Цициклис, Дж. (1997). Подход нейродинамического программирования к управлению запасами ритейлера. Материалы конференции IEEE по решениям и контролю, 4, 4052-4057.
14. Прасетио, Ю. (2005). Оптимизация сложных стохастических систем на основе моделирования. Вашингтонский университет.
15. Дэн Дж. И Феррис Майкл. (2007). Оптимизация на основе моделирования, ProQuest диссертации и тезисы