![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Метод Нелдера и Мида относится к методам прямого поиска, в которых используются только значения функции (не требуются значения производных целевой функции). Этот метод является развитием симплексного метода Спендли, Хекста и Химсворта. Симплексом называется регулярный многогранник, т.е. множество -й равноудаленной точки в
(
-мерном пространстве). В двумерном пространстве симплексом является равносторонний треугольник, а в трехмерном пространстве – правильный тетраэдр. Идея метода состоит в сравнении значений целевой функции в
вершинах симплекса и в перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. Эта особенность послужил причиной появления второго названия метода – поиск по деформируемому многограннику. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных, если
.
Кратко метод Нелдера и Мида может быть описан следующим образом: минимизируется функция независимых переменных с использованием
вершин деформируемого многогранника в
. Каждая вершина может быть идентифицирована вектором
, (
), где i – номер вершины многогранника, k – номер очередного этапа поиска. Вершина многогранника, в которой значение
максимально, проектируется через центр тяжести оставшихся вершин. Улучшенные (более низкие) значения целевой функции находятся последовательной заменой точки с максимальным значением
на более хорошие точки с использованием операций отражения, растяжения, сжатия и редукции многогранника, пока не будет найден минимум
, т.е. пока не будет выполнено условие, соответствующее критерию останова алгоритма.
Введем необходимые обозначения и перейдем к подробному описанию метода.
Пусть , (
) является, как было сказано выше, i -й вершиной многогранника на k -м шаге поиска, и пусть значение целевой функции в
равно
. Кроме того, отметим те вершины многогранника (векторы x), в которых целевая функция принимает максимальное и миниимальное значения:
- вершина многогранника, в которой
;
- вершина многогранника, в которой
.
Поскольку многогранник в состоит из
вершин
, пусть
будет центром тяжести всех вершин, исключая
, тогда
. (3.3.1)
Критерием останова алгоритма является выполнение следующего условия:
, (3.3.2)
где - произвольное малое число, а
- значение целевой функции в центре тяжести
.
Начальный многогранник выбирается в виде регулярного симплекса, построенного относительно произвольной точки, или, что проще, нерегулярного (например, симплекс, у i -й вершины которого i -я координата равна 1, а остальные координаты равны 0, n+1–я точка – начало координат). Процедура отыскания вершины в , в которой
имеет лучшее значение (наименьшее), состоит из следующих операций:
A. Инициализация значений: . Определяем вершины начального симплекса.
B. Проверка критерия останова алгоритма. Если неравенство (3.3.2) выполняется, то переход к операции I (все значения функции уже лежат вблизи точки минимума функции ).
C. Подготовительный этап: определяем значения целевой функции в вершинах многогранника, находим наименьшее значение функции и соответствующую ему вершину
, наибольшее значение функции
и соответствующую ему вершину
, вычисляем координаты центра тяжести
.
D. Отражение – проецирование через центр тяжести (см. рис.3.3.1) в соответствии с соотношением
, (3.3.3)
где является коэффициентом отражения;
- центр тяжести, вычисляемый по формуле (3.3.1);
- вершина, в которой функция цели принимает наибольшее из
ее значений на k-м этапе.
Рисунок 3.3.1. Отражение. Рисунок 3.3.2. Растяжение.
E. Если , т.е. направление выбрано правильно, то Растяжение: вектор
растягивается в соответствии с соотношением
, (3.3.4)
где
представляет собой коэффициент растяжения (см. Рис. 3.3.2).
Если , то на место
записывается
, в противном случае на место
записывается
. Затем процедура продолжается с операции H.
F. Если , то
Сжатие: вычисляем
, (3.3.5)
где представляет собой коэффициент сжатия.
Затем на место
записывается
. Затем процедура продолжается с операции H.
Рисунок 3.3.3. Сжатие.
G. Если , то
Редукция: все векторы ,
уменьшаются с коэффициентом (
) с отсчетом от
в соответствии с формулой
,
. (3.3.6)
Затем процедура продолжается с операции H.
H. . Переход к операции В.
I. Конец.
Коэффициенты в вышеописанном алгоритме, как уже было сказано, называются коэффициентами отражения, сжатия и растяжения. Нелдер и Мид рекомендуют брать
и
. Рекомендация основана на результатах экспериментов с различными комбинациями значений. Хотя другие исследователи рекомендуют следующие диапазоны для этих параметров:
,
.
Дата публикования: 2014-11-26; Прочитано: 1091 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!