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

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

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

Итак, пусть X1, X2,…,Xn+1 – вершины многогранника на некотором этапе поиска. Определим точки Xh и XL, в которых функция имеет соответственно наибольшее и наименьшее значения:

f(Xh)= , f(XL)= .

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

Xn+2= . (2.6)

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

1). Отражение – проектирование точки Xh через центр тяжести Xn+2 в соответствии с соотношением

Xn+3= Xn+2+a×( Xn+2- Xh), (2.7)

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

2). Растяжение. Если f(Xn+3)£f(XL), то вектор Xn+3- Xn+2 растягивается в соответствии с соотношением

Xn+4= Xn+2+ g×(Xn+3- Xn+2), (2.8)

где g>1 –коэффициент растяжения. Если f(Xn+4)<f(XL), то вершина Xh заменяется на Xn+4 и начинается новый этап поиска снова с операции отражения. В противном случае Xh заменяется на Xn+3 и также осуществляется переход к операции отражения нового этапа.

3). Сжатие. Если f(Xn+3)>f(Xj), "j¹h, то вектор Xh- Xn+2 сжимается в соответствии с формулой

Xn+5= Xn+2+b×( Xh- Xn+2), (2.9)

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

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

Xj = XL + ( Xj – XL)/2, j=1,...,n+1 (2.10)

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

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

, (2.11)

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

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

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

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

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

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

(а,б);

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

 

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