Метод Монте-Карло как разновидность

Имитационного моделирования

Метод Монте-Карло чрезвычайно прост и его идея состоит в следующем. Вместо того чтобы описывать процесс с помощью аналитического аппарата (дифференциальных или алгебраических уравнений), производится «розыгрыш» случайного явления с помощью специально организованной процедуры, включающей в себя случайность и дающей случайный результат. В действительности конкретное осуществление случайного процесса складывается каждый раз по-иному; так же и в результате статистического моделирования мы получаем каждый раз новую, отличную от других реализацию исследуемого процесса. Что она может нам дать? Сама по себе ничего, так же как, скажем, один случай излечения больного с помощью какого-либо лекарства. Другое дело, если таких реализаций получено много. Это множество реализаций можно использовать как некий искусственно полученный статистический материал, который может быть обработан обычными методами математической статистики. После такой обработки могут быть получены любые интересующие нас характеристики: вероятности событий, математические ожидания и дисперсии случайных величин и т. д. При моделировании случайных явлений методом Монте-Карло мы пользуемся самой случайностью как аппаратом исследования, заставляем ее «работать на нас». Нередко такой прием оказывается проще, чем попытки построить аналитическую модель. Для сложных операций, в которых участвует большое число элементов (машин, людей, организаций, подсобных средств), в которых случайные факторы сложно переплетены, метод статистического моделирования, как правило, оказывается проще
аналитического (а нередко бывает и единственно возможным).

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

4.6. Метод деформируемого многогранника (метод Нелдера—Мида)

Впервые метод деформируемого многогранника был предложен Нелдером и Мидом. Они предложили метод поиска, оказавшийся весьма эффективным и легко осуществляемым на ЭВМ. Вспомним, что регулярные многогранники в Eⁿ являются симплексами. Например, как видно из рисунка 4.5, для случая двух переменных регулярный симплекс представляет собой равносторонний треугольник (три точки); в случае трёх переменных регулярный симплекс представляет собой тетраэдр (четыре точки) и т.д.

(а) (б)

Рис.4.5. Регулярные симплексы для случая двух (а) и трёх (б) независимых переменных.

Стрелка на рисунке указывает направление наискорейшего улучшения.

При поиске минимума целевой функции f(x) пробные векторы x могут быть выбраны в точках Eⁿ, находящихся в вершинах симплекса, как было первоначально предложено Спендли, Хекстом и Химсвортом. Из аналитической геометрии известно, что координаты вершин регулярного симплекса определяются следующей матрицей D, в которой столбцы представляют собой вершины, пронумерованные от 1 до (n+1), а строчки – координаты, i принимает значения от 1 до n:

- матрица n X(n+1),

где

где t – расстояние между двумя вершинами.

Например, для n=2 и t=1 треугольник, приведённый на рисунке 4.5, имеет следующие координаты:

Вершина	x_{1, i}	x_{2, i}

	0.965	0.259
	0.259	0.965

Целевая функция может быть вычислена в каждой из вершин симплекса; из вершины, где целевая функция максимальна (см. рис. 4.5), проводится проектирующая прямая через центр тяжести симплекса. Затем строится новый симплекс, называемый отражённым, из оставшихся прежних точек и одной новой точки, расположенной на проектирующей прямой, на надлежащем расстоянии от центра тяжести. Продолжение этой процедуры, в которой каждый раз вычёркивается вершина, где целевая функция максимальна, а также использование правил уменьшения размера симплекса и предотвращения циклического движения в окрестности экстремума позволяют осуществить поиск, не использующий производные и в котором величина шага на любом этапе k фиксирована, а направление поиска можно изменять. На рисунке 4.6 приведены последовательные симплексы, построенные в двумерном пространстве с «хорошей» целевой функцией.

Рис. 4.6. Последовательность регулярных симплексов, полученных при минимизации f(x),
----- проекция

Определённые практические трудности, встречающиеся при использовании регулярных симплексов, а именно отсутствие ускорения поиска и трудности при проведении поиска на искривлённых «оврагах» и «хребтах», привели к необходимости некоторых улучшений методов. Далее будет изложен метод Нелдера и Мида, в котором симплекс может изменять свою форму, и таким образом уже не будет оставаться симплексом. Именно поэтому используем более подходящее название «деформируемый многогранник».

В методе Нелдера и Мида минимизируется функция n независимых переменных с использованием n+1 вершин деформируемого многогранника в Eⁿ. Каждая вершина может быть идентифицирована вектором x. Вершина (точка) в Eⁿ, в которой значение f(x) максимально, проектируется через центр тяжести (центроид) оставшихся вершин. Улучшенные (более низкие) значения целевой функции находятся последовательной заменой точки с максимальным значением f(x) на более «хорошие точки», пока не будет найден минимум f(x).

Более подробно этот алгоритм может быть описан следующим образом.

Пусть, , является i-й вершиной (точкой) в Eⁿ на k-м этапе поиска, k=0, 1, …, и пусть значение целевой функции в равно

Кроме того, отметим те векторы x многогранника, которые дают максимальное и минимальное значения f(x).

Определим

где и

где

Поскольку многогранник в Eⁿ состоит из (n+1) вершин x₁, …, x_n+1, пусть x_n+2 будет центром тяжести всех вершин, исключая x_h.

Тогда координаты этого центра определяются формулой

j= 1, …, n, (4.1)

где индекс j обозначает координатное направление.

Начальный многогранник обычно выбирается в виде регулярного симплекса (но это не обязательно) с точкой 1 в качестве начала координат; можно начало координат поместить в центр тяжести. Процедура отыскания вершины в Eⁿ, в которой f(x) имеет лучшее значение, состоит из следующих операций:

1) отражение – проектирование через центр тяжести в соответствии с соотношением:

(4.2)

где a > 0 является коэффициентом отражения;

– центр тяжести, вычисляемый по формуле 4.1;

вершина, в которой функция f(x) принимает наибольшее из n+1 значений на k-м этапе.

2) растяжение - эта операция заключается в следующем: если то вектор растягивается в соответствии с соотношением:

(4.3)

где g> 1 представляет собой коэффициент растяжения. Если то заменяется на и процедура продолжается снова с операции 1 при k=k+1. В противном случае заменяется на и также осуществляется переход к операции 1 при k=k+1.

3) сжатие - если для всех i¹ h, то вектор сжимается в соответствии с формулой:

(4.4)

где 0< b< 1 представляет собой коэффициент сжатия. Затем заменяем на и возвращаемся к операции 1 для продолжения поиска на (k+1)-м шаге.

4) редукция - если все векторы уменьшаются в 2 раза с отсчётом от в соответствии с формулой:

(4.5)

Затем возвращаемся к операции 1 для продолжения поиска на (k+1)-м шаге.

Критерий окончания поиска, использованный Нелдером и Мидом, состоял в проверке условия:

(4.6)

где e – произвольное малое число,

– значение целевой функции в центре тяжести .

На рисунке 4.7 показана последовательность поиска для функции Розенброка, начиная их x⁽⁰⁾ =[-1, 2 1, 0]^T. Деформируемый многогранник в противоположность жёсткому симплексу адаптируется к топографии целевой функции, вытягиваясь вдоль длинных наклонных плоскостей, изменяя направление в изогнутых впадинах и сжимаясь в окрестности минимума.

Рис.4.7. Поиск минимума функции Розенброка методом деформируемого многогранника, начиная с точки x(0)=[-1, 2 1, 0]^T (числа указывают номер шага).

Коэффициент отражения a используется для проектирования вершины с наибольшим значением f(x) через центр тяжести деформируемого многогранника. Коэффициент g вводится для растяжения вектора поиска в случае, если отражение даёт вершину со значением f(x), меньшим, чем наименьшее значение f(x), полученное до отражения. Коэффициент сжатия b используется для уменьшения вектора поиска, если операция отражения не привела к вершине со значением f(x), меньшим, чем второе по величине (после наибольшего) значение f(x), полученное до отражения.

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

В качестве удовлетворительных значений при оптимизации без ограничений Нелдер и Мид рекомендовали a=1, b=0, 5 g=2. Размеры и ориентация исходного многогранника в некоторой степени влияли на время решения, а значения a, b и g оказывали значительно большее влияние.

Контрольные вопросы

1. Что такое инновационный процесс? Приведи примеры.

2. Алгоритм разработки математической модели?

3. Что такое имитационная модель?

4. Методы имитационной модели. Приведи примеры.

5. Перечисли операции для построения формы деформированного многогранника?

Инженерное проектирование

⇐ Предыдущая 3 4 5 6 7 8910 11 12 Следующая ⇒