Поиск по деформируемому многограннику

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

В методе деформируемого многогранника, как и в предыдущем методе, функция n независимых переменных минимизируется с использованием n+1 вершин многогранника. Вершина, в которой значение функции f(X) максимально, проектируется через центр тяжести оставшихся вершин. Улучшенные значения функции f(X) находятся последовательной заменой точки с максимальным значением f(X) на более “хорошие” точки, пока не будет найден минимум f(X).

Итак, пусть X¹, X²,…,Xⁿ⁺¹ – вершины многогранника на некотором этапе поиска. Определим точки X^h и X^L, в которых функция имеет соответственно наибольшее и наименьшее значения:

f(X^h)= , f(X^L)= .

Центр тяжести всех вершин, исключая X^h, определим по формуле

Xⁿ⁺²= . (2.6)

Процедура отыскания вершины, в которой f(X) имеет лучшее значение, состоит из четырех операций.

1). Отражение – проектирование точки X^h через центр тяжести Xⁿ⁺² в соответствии с соотношением

Xⁿ⁺³= Xⁿ⁺²+a×( Xⁿ⁺²- X^h), (2.7)

где a>0 – коэффициент отражения, Xⁿ⁺² – центр тяжести, вычисляемый по формуле (2.6).

2). Растяжение. Если f(Xⁿ⁺³)£f(X^L), то вектор Xⁿ⁺³- Xⁿ⁺² растягивается в соответствии с соотношением

Xⁿ⁺⁴= Xⁿ⁺²+ g×(Xⁿ⁺³- Xⁿ⁺²), (2.8)

где g>1 –коэффициент растяжения. Если f(Xⁿ⁺⁴)<f(X^L), то вершина X^h заменяется на Xⁿ⁺⁴ и начинается новый этап поиска снова с операции отражения. В противном случае X^h заменяется на Xⁿ⁺³ и также осуществляется переход к операции отражения нового этапа.

3). Сжатие. Если f(Xⁿ⁺³)>f(X^j), "j¹h, то вектор X^h- Xⁿ⁺² сжимается в соответствии с формулой

Xⁿ⁺⁵= Xⁿ⁺²+b×( X^h- Xⁿ⁺²), (2.9)

где (0;1)- коэффициент сжатия. Вершина Xh заменяется на Xn+5 и выполняется вновь операция отражения на новом этапе поиска.

4). Редукция. Если f(Xn+3)f(Xh), то все векторы Xj- XL уменьшаютcя, например, в 2 раза с отсчетом от XL в соответствии с формулой

X^j = X^L + ( X^j – X^L)/2, j=1,...,n+1 (2.10)

Далее возвращаемся к операции отражения для продолжения поиска на новом этапе.

Критерий окончания поиска может быть выбран в виде условия

, (2.11)

где 0– достаточно малое число.

Геометрическая иллюстрация описанных процедур для пространства E² приведена на рис.2 и 3.

Рис 2. Пробные точки , , ,

для перехода к новому многограннику.

Так как величина aÎ(0;1], то выбор точек и соответствует отражению; bÎ(0;1), поэтому выбор точки соответствует сжатию, а g>1 и выбор точки приводит к растяжению симплекса.

Рис.3. Новые многогранники, полученные в результате процедур отражения

(а,б);

сжатия (в); растяжения (г).

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