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

Данный метод состоит в том, что для минимизации функции ппеременныхf(х) в n-мерном пространстве строится многогранник, содержащий (п + 1) вершину. Очевидно, что каждая вершина соответствует некоторому векторух.Вычисляются значения целевой функцииf(х) в каждой из вершин многогранника, определяются максимальное из этих значений и соответствующая ему вершинах[h].Через эту вершину и центр тяжести остальных вершин проводится проецирующая прямая, на которой находится точках[q] с меньшим значением целевой функции, чем в вершинех[h] (рис. 7.5). Затем исключается вершинах[h].Из оставшихся вершин и точкиx[q] строится новый многогранник, с которым повторяется описанная процедура. В процессе выполнения данных операций многогранник изменяет свои размеры, что и обусловило название метода.

Рис. 7.5 ‑ Геометрическая интерпретация метода деформируемого многогранника

Введем следующие обозначения:

x[i, k] =(x₁[i, k], …,x_j[i, k], …,x_n[i, k])^T

где i = 1, ..., п+ 1;k =0, 1, ..., - i-я вершина многогранника наk-м этапе поиска;х[h, k]—вершина, в которой значение целевой функции максимально, т. е.f(х[h, k] = max{f(x[1,k]), …,f(x[n+1,k])};х[l,k]-вершина, в которой значение целевой функции минимально, т. е.f(х[l,k]) =min {f(x[1,k]), …,f(x[n+1,k])};х [п+2,k]-центр тяжести всех вершин, за исключениемх[h, k]. Координаты центра тяжести вычисляются по формуле

Алгоритм метода деформируемого многогранника состоит в следующем.

1. Осуществляют проецирование точки х[h, k] через центр тяжести:

x[n+3, k] =x[n+2, k] + a(x[n+2, k] - x[h, k]) ,

где а> 0 - некоторая константа. Обычноа =1.

2. Выполняют операцию растяжения вектора х[n+3, k]- х[n+2, k]:

x[n+4, k] =x[n+2, k] + (x[n+3, k] - x[n+2, k]),

где > 1 - коэффициент растяжения. Наиболее удовлетворительные результаты получают при 2,8 <=<= 3.

Если f(x[n+4,k]) <f(х[l,k]), тох[h , k] заменяют наx[n+4, k] и продолжают вычисления с п. 1 приk = k +1. В противном случаех[h, k] заменяют нах[n+3, k] и переходят к п. 1 приk = k+ 1.

3. Если f(x[n+3, k])> f(х[i, k])для всехi, не равныхh,то сжимают векторx[h, k] - x[n+2, k]:

x[n+5, k] =x[n+2, k] +(х[h, k] – x[n+2, k] ), где> 0 - коэффициент сжатия. Наиболее хорошие результаты получают при 0,4 <=<= 0,6.

Затем точку х[h, k] заменяют нах[n+5, k] и переходят к п. 1 приk = k+ 1.

4. Если f(x[n+3, k])>f(x[h, k]), то все векторых[i, k] - х[l,k] . i=1,...,п + 1, уменьшают в два раза:

x[i, k] = x[l, k] + 0,5(x[i, k] - x[l, k]) .

Затем переходят к п. 1 при k= k+ 1.

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

, (7.10)

где e = (е₁ ,..., е_n)‑ заданный вектор.

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