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

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

OCBA определяет количество повторений или время моделирования, необходимое для получения приемлемых или лучших результатов в рамках набора заданных параметров. Это достигается за счет использования асимптотической структуры для анализа структуры оптимального распределения.

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

Интуитивное объяснение

Цель OCBA — обеспечить систематический подход к проведению большого количества симуляций , включая только критические альтернативы, чтобы выбрать лучшую альтернативу.

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

Например, мы можем создать простую симуляцию пяти альтернатив. Цель состоит в том, чтобы выбрать альтернативу с минимальным средним временем задержки. На рисунке ниже показаны предварительные результаты моделирования (т.е. запуск только части необходимого количества повторений моделирования). Понятно, что варианты 2 и 3 имеют значительно меньшее время задержки (выделено красным). Чтобы сэкономить затраты на вычисления (то есть время, ресурсы и деньги, затрачиваемые на процесс запуска моделирования), OCBA предлагает, чтобы для альтернатив 2 и 3 требовалось больше репликаций, а для вариантов 1, 4 и 5 моделирование можно было остановить гораздо раньше. без ущерба для результатов.

Из приведенного выше графика видно, что варианты 2 и 3 имеют наименьшую стоимость. OCBA предлагает проводить дальнейшее моделирование только для вариантов 2 и 3, чтобы минимизировать затраты на вычисления.

Проблема

Основная цель OCBA – максимизировать вероятность правильного выбора (PCS). PCS подчиняется бюджету выборки на данном этапе выборки τ .

${\begin{aligned}\max _{\tau _{1},\tau _{2},\ldots ,\tau _{k}}&\mathrm {PCS} \\{\text{subject to }}&\sum _{i=1}^{k}\tau _{i}=\tau ,\\&\tau _{i}\geq 0,i=1,2,...,k.\qquad (1)\end{aligned}}$

В этом случае $\sum _{i=1}^{k}\tau _{i}=\tau$ обозначает общие вычислительные затраты.

Некоторые расширения OCBA

Эксперты в этой области объясняют, что в некоторых задачах важно знать не только лучшую альтернативу из выборки , но и 5, 10 или даже 50 лучших альтернатив, поскольку у лица, принимающего решения, могут быть другие проблемы, которые могут повлиять на решение, но не смоделировано в симуляции.

По мнению Сехтмана и Ючесана (2008), OCBA также помогает в решении проблем, связанных с определением технико-экономического обоснования. Здесь лица, принимающие решения, заинтересованы только в том, чтобы отличить осуществимые альтернативы от неосуществимых. Кроме того, выбор более простой, но схожей по эффективности альтернативы имеет решающее значение для других лиц, принимающих решения. В этом случае лучший выбор — среди топ-r простейших альтернатив, производительность которых выше желаемого уровня.

Кроме того, Трайлович и Пао (2004) демонстрируют подход OCBA, при котором мы находим альтернативы с минимальной дисперсией , а не с лучшим средним значением. Здесь мы предполагаем неизвестные отклонения, аннулируя правило OCBA (предполагая, что отклонения известны). В 2010 году было проведено исследование алгоритма OCBA, основанного на распределении. Результаты не показывают существенных различий между результатами t-распределения и нормального распределения . Представленные выше расширения OCBA не являются полным списком и еще не полностью изучены и составлены.

Многоцелевой OCBA

Многоцелевое оптимальное распределение бюджета вычислений (MOCBA) — это концепция OCBA, которая применяется к многокритериальным задачам. В типичном MOCBA PCS определяется как

$\Pr\{CS\}\equiv \Pr \left\{\left(\bigcap _{i\in S_{p}}E_{i}\right)\bigcap \left(\bigcap _{i\in {\overline {S}}_{p}}E_{i}^{c}\right)\right\},$

в котором

• $S_{p}$ — наблюдаемое множество Парето ,
• ${\overline {S}}_{p}$ является непарето-множеством, т.е. ${\overline {S}}_{p}=\Theta \backslash S_{p}$,
• $E_{i}$ это событие, которое проектирует $i$ не доминирует над всеми другими конструкциями,
• $E_{i}^{c}$ это событие, которое проектирует $i$ преобладает хотя бы один дизайн.

Мы замечаем, что ошибка I рода $e_{1}$ и ошибка второго рода $e_{2}$ для определения правильного множества Парето соответственно

$e_{1}=1-\Pr \left\{\bigcap _{i\in {\overline {S}}_{p}}E_{i}^{c}\right\}$ и $e_{2}=1-\Pr \left\{\bigcap _{i\in S_{p}}E_{i}\right\}$.

Кроме того, можно доказать, что

$e_{1}\leq ub_{1}=H\left|{\overline {S}}_{p}\right|-H\sum _{i\in {\overline {S}}_{p}}{\max _{j\in \Theta ,j\neq i}\left[\min _{l\in {1,\ldots ,H}}\Pr \left\{{\tilde {J}}_{jl}\leq {\tilde {J}}_{il}\right\}\right]}$

и

$e_{2}\leq ub_{2}=(k-1)\sum _{i\in S_{p}}\max _{j\in \Theta ,j\neq i}\left[\min _{l\in {1,\ldots ,H}}\Pr \left\{{\tilde {J}}_{jl}\leq {\tilde {J}}_{il}\right\}\right],$

где $H$ количество целей, и ${\tilde {J}}_{il}$ следует апостериорному распределению $Normal\left({\bar {J}}_{il},{\frac {\sigma _{il}^{2}}{N_{i}}}\right).$Отметил, что ${\bar {J}}_{il}$ и $\sigma _{il}$ — это среднее и стандартное отклонение наблюдаемых показателей эффективности для объективных $l$ дизайна $i$, и $N_{i}$ это количество наблюдений.

Таким образом, вместо максимизации $\Pr\{CS\}$, мы можем максимизировать его нижнюю границу, т. е. $APCS{-}M\equiv 1-ub_{1}-ub_{2}.$ Предполагая $\tau \rightarrow \infty$, метод Лагранжа можно применить для вывода следующих правил:

$\tau _{i}={\frac {\beta _{i}}{\sum _{j\in \Theta }\beta _{j}}}\tau ,$

в котором

• для дизайна $h\in S_{A}$, $\beta _{h}={\frac {\left({\hat {\sigma }}_{hl_{j_{h}}^{h}}^{2}+{\hat {\sigma }}_{j_{h}l_{j_{h}}^{h}}^{2}/\rho _{h}\right)/{\delta _{hj_{h}l_{j_{h}}^{h}}^{2}}}{\left({\hat {\sigma }}_{ml_{jm}^{m}}^{2}+{\hat {\sigma }}_{j_{m}l_{jm}^{m}}^{2}/\rho _{m}\right)/{\delta _{mj_{m}l_{j_{m}}^{m}}^{2}}}}$,
• для дизайна $d\in S_{B}$, $\beta _{d}={\sqrt {\sum _{i\in \Theta _{d}^{*}}{\frac {\sigma _{dl_{d}^{i}}^{2}}{\sigma _{il_{d}^{i}}^{2}}}\beta _{i}^{2}}}$,

и $\delta _{ijl}={\bar {J}}_{jl}-{\bar {J}}_{il},$

$j_{i}\equiv \arg \max _{j\in \Theta ,j\neq i}\prod _{l=1}^{H}{\Pr \left\{{\tilde {J}}_{jl}\leq {\tilde {J}}_{il}\right\}},$

$l_{j_{i}}^{i}\equiv \arg \min _{l\in {1,\ldots ,H}}\Pr \left\{{\tilde {J}}_{jl}\leq {\tilde {J}}_{il}\right\},$

$S_{A}\equiv \left\{design\;h\in S\mid {\frac {\delta _{hj_{h}l_{j_{h}}^{h}}^{2}}{{\frac {{\hat {\sigma }}_{hl_{j_{h}}^{h}}^{2}}{\alpha _{h}}}+{\frac {{\hat {\sigma }}_{j_{h}l_{j_{h}}^{h}}^{2}}{\alpha _{j_{h}}}}}}<\min _{i\in \Theta _{h}}{\frac {\delta _{ihl_{h}^{i}}^{2}}{{\frac {{\hat {\sigma }}_{il_{h}^{i}}^{2}}{\alpha _{i}}}+{\frac {{\hat {\sigma }}_{hl_{h}^{i}}^{2}}{\alpha _{h}}}}}\right\},$

$S_{B}\equiv S\backslash S_{A},$

$\Theta _{h}={i|i\in S,j_{i}=h},$

$\Theta _{d}^{*}={h|h\in S_{A},j_{h}=d},$

$\rho _{i}=\alpha _{j_{i}}/\alpha _{i}.$

Ограниченная оптимизация

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

Первичный показатель эффективности можно назвать главной целью, тогда как вторичные показатели эффективности называются мерами ограничения. Это подпадает под проблему ограниченной оптимизации . Когда количество альтернатив фиксировано, проблема называется ранжированием и выбором с ограничениями, где цель состоит в том, чтобы выбрать наилучший возможный дизайн, учитывая, что как основная цель, так и меры ограничений должны быть оценены с помощью стохастического моделирования. Метод OCBA для оптимизации с ограничениями (называемый OCBA-CO) можно найти у Pujowidianto et al. (2009) и Ли и др. (2012).

Ключевое изменение заключается в определении PCS. В ограниченной оптимизации есть два компонента: оптимальность и осуществимость. В результате бюджет моделирования может быть распределен для каждого нелучшего проекта либо на основе оптимальности, либо на основе осуществимости. Другими словами, нелучший проект не будет ошибочно выбран как наилучший возможный проект, если он останется либо неосуществимым, либо хуже, чем истинный наилучший возможный проект. Идея в том, что не обязательно тратить большую часть бюджета на определение реализуемости, если конструкция явно хуже лучшей. Точно так же мы можем сэкономить бюджет, распределяя его на основе осуществимости, если дизайн уже лучше самого лучшего с точки зрения основной цели.

Определение осуществимости

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

Определять

• $k$: общее количество дизайнов;
• $m$: общее количество ограничений показателей производительности;
• $c_{j}$: требование контроля $j$ограничение для всех проектов, $j=1,2,...,m$;
• $S_{A}$: набор возможных конструкций;
• $S_{B}$: набор неосуществимых проектов;
• $\mu _{i,j}$: среднее значение образцов моделирования $j$Ограничительная мера и конструкция $i$;
• $\sigma _{i,j}^{2}$: дисперсия выборок моделирования $j$Ограничительная мера и конструкция $i$;
• $\alpha _{i}$: доля общего бюджета моделирования, выделенная на проектирование. $i$;
• ${\bar {X}}_{i,j}$: выборочное среднее выборок моделирования $j$Ограничительная мера и конструкция $i$.

Предположим, что все ограничения заданы в виде $\mu _{i,j}\leq c_{j}$, $i=1,2,...,k,j=1,2,...,m$. Вероятность правильного выбора всех возможных планов равна

${\begin{aligned}\mathrm {PCS} =\mathbb {P} \left(\bigcap _{i\in S_{A}}{\Big (}\bigcap _{j=1}^{m}({\bar {X}}_{i,j}\leq c_{j}){\Big )}\cap \bigcap _{i\in S_{B}}{\Big (}\bigcup _{j=1}^{m}({\bar {X}}_{i,j}>c_{j}){\Big )}\right),\end{aligned}}$

а проблема распределения бюджета для определения осуществимости представлена ​​Гао и Ченом (2017).

${\begin{aligned}\max _{\alpha _{1},\alpha _{2},\ldots ,\alpha _{k}}&\mathrm {PCS} \\{\text{subject to }}&\sum _{i=1}^{k}\alpha _{i}=1,\\&\alpha _{i}\geq 0,i=1,2,...,k.\end{aligned}}$

Позволять $I_{i,j}(x)={\frac {(x-\mu _{i,j})^{2}}{2\sigma _{i,j}^{2}}}$ и $j_{i}\in \mathrm {argmin} _{j\in \{1,...,m\}}I_{i,j}(c_{j})$. Асимптотическое оптимальное правило распределения бюджета имеет вид

${\begin{aligned}{\frac {\alpha _{i}}{\alpha _{i'}}}={\frac {I_{i',j_{i'}}(c_{j_{i'}})}{I_{i,j_{i}}(c_{j_{i}})}},i,i'\in \{1,2,...,k\}.\end{aligned}}$

Интуитивно говоря, приведенное выше правило распределения говорит, что (1) для допустимого проекта доминирующее ограничение является самым трудным для правильного обнаружения среди всех ограничений; и (2) для неосуществимого проекта доминирующим ограничением является то, которое легче всего правильно обнаружить среди всех ограничений.

OCBA с ожидаемыми альтернативными издержками

Оригинальный ОКБ максимизирует вероятность правильного выбора (ПКС) лучшей конструкции. На практике еще одним важным показателем является ожидаемая альтернативная стоимость (EOC), которая количественно определяет, насколько далеко среднее значение выбранного проекта от действительно лучшего. Эта мера важна, поскольку оптимизация EOC не только максимизирует вероятность выбора лучшего дизайна, но также гарантирует, что среднее значение выбранного дизайна не будет слишком далеко от среднего значения лучшего дизайна, если лучший проект не будет найден. По сравнению с PCS, EOC наказывает за особенно плохой выбор больше, чем за слегка неправильный выбор, и поэтому его предпочитают нейтральные к риску специалисты и лица, принимающие решения.

В частности, ожидаемая альтернативная стоимость равна

${\begin{aligned}EOC=\mathbb {E} _{\mathcal {T}}[\mu _{\mathcal {T}}-\mu _{t}]=\sum _{i=1,i\neq t}^{k}\delta _{i,t}\mathbb {P} ({\mathcal {T}}=i),\end{aligned}}$

где,

• $k$ – общее количество дизайнов;
• $t$ это действительно лучший дизайн;
• ${\mathcal {T}}$ — случайная величина, реализация которой является наблюдаемым лучшим дизайном;
• $\mu _{i}$ среднее значение образцов моделирования дизайна $i$, $i=1,2,...,k$;
• $\delta _{i,j}=\mu _{i}-\mu _{j}$.

Проблема распределения бюджета с объективной мерой EOC описана Gao et al. (2017)

${\begin{aligned}\min _{\alpha _{1},\alpha _{2},\ldots ,\alpha _{k}}&\mathrm {EOC} \\{\text{subject to }}&\sum _{i=1}^{k}\alpha _{i}=1,\\&\alpha _{i}\geq 0,i=1,2,...,k,\end{aligned}}$

где $\alpha _{i}$ — это доля общего бюджета моделирования, выделенная на проектирование. $i$.Если мы предположим $\alpha _{t}\gg \alpha _{i}$ для всех $i\neq t$, асимптотическое оптимальное правило распределения бюджета для этой задачи имеет вид

${\begin{aligned}&{\frac {\alpha _{t}^{2}}{\sigma _{t}^{2}}}=\sum _{i=1,i\neq t}^{k}{\frac {\alpha _{i}^{2}}{\sigma _{i}^{2}}},\\&{\frac {\alpha _{i}}{\alpha _{j}}}={\frac {\sigma _{i}^{2}/\delta _{i,t}^{2}}{\sigma _{j}^{2}/\delta _{j,t}^{2}}},i\neq j\neq t,\end{aligned}}$

где $\sigma _{i}^{2}$ это дисперсия образцов моделирования дизайна $i$. Это правило размещения совпадает с асимптотическим оптимальным решением задачи (1). То есть, асимптотически говоря, максимизация PCS и минимизация EOC — это одно и то же.

OCBA с входной неопределенностью

Неявным предположением для вышеупомянутых методов OCBA является то, что истинные входные распределения и их параметры известны, тогда как на практике они обычно неизвестны и должны оцениваться на основе ограниченных исторических данных. Это может привести к неопределенности в предполагаемых распределениях входных данных и их параметрах, что может (серьезно) повлиять на качество отбора. Предполагая, что набор неопределенностей содержит конечное число сценариев для основных входных распределений и параметров, Гао и др. (2017) представляет новый подход OCBA, максимизируя вероятность правильного выбора лучшей конструкции при фиксированном бюджете моделирования, где эффективность конструкции измеряется ее производительностью в наихудшем случае среди всех возможных сценариев в наборе неопределенностей.

Веб-демонстрация OCBA

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

Внешние ссылки

• Оптимальное распределение бюджета вычислений (OCBA) для принятия решений на основе моделирования в условиях неопределенности (оптимизация моделирования)