Методы поиска экстремумов унимодальных функций

Пользуясь тем же приемом, но вычисляя значение функции в подинтервалах неодинаковое число раз, можно дополнительно повысить эффективность поиска. Вычисляя N значений функций на i последовательно сужаемых интервалах, получим для коэффициента дробления интервала неопределенности

При таком методе поиска целевую функцию приходится вычислять J раз, причем J = N_i. Можно найти оптимальное значение N, при котором J при заданном f д минимально. Зная что i = J/N можно получить

.

Такая функция имеет минимум при N =3. При этом на каждом интервале f _д=0.5, т.е. каждые три измерения позволяют сузить интервалы неопределенности вдвое. Поскольку интервал неопределенности делится каждый раз надвое, то метод получил название метода деления интервала пополам.

На рис.4.6 показано, что три первых вычисленных значения функции позволяют сузить интервал неопределенности вдвое.

Рис. 4.6

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

В общем случае при N ³3 коэффициент дробления интервала неопределенности составит

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

Если значение целевой функции в x ₁ больше, чем в х ₂, т.е. f (x ₁) > f (x ₂), то новый интервал неопределенности z `= z ₁ + z ₂.

Если f (x ₁) < f (x ₂), то z `` = z <sub>2</sub> + z <sub>3</sub>. Задача состоит в том, чтобы одновременно минимизировать z ` и z ``, удовлетворив условиям

 

z 1 + z 2 + z 3 = z

(4.1)

z ₁ > 0; z ₂ > 0; z ₃ > 0.

 

Рис. 4.7

Из равенства (4.1) можно исключить z ₂. Тогда z-z ₃= min и z-z ₁= min.

Так как величина z задана, то правые части уравнений будут тем меньше, чем одновременно большими будут z ₁ и z ₃. Следовательно, оптимум соответствует условию z ₁= z ₃= z /2. Но тогда из (4.1) видно, что z ₂=0, что противоречит условию z ₂>0. Пусть z ₂ имеет очень малое значение e. Тогда из z ₁ и z ₃ вычтем по e/2. В результате после вычислений первой пары значений целевой функции при близких значениях x ₁ и x ₂ интервал неопределенности сузится, как показано на рис. 4.8, и коэффициент дробления на шаге будет равен

 

Рис. 4.8

Очевидно в пределе, при e®0, f _д ®1/2.

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

Рассмотрим метод золотого сечения. Сущность метода состоит в следующем. Интервал неопределенности делится на две части так, чтобы отношение длины большего отрезка к длине всего интервала было бы равно отношению длины меньшего отрезка к большему. На рис. 4.9 показан интервал неопределенности z, состоящий из отрезков z ₁ и z ₂, отношение длин которых определяется правилом золотого сечения

(4.2)

 

e

Рис. 4.9

 

Кроме того, z 1 + z 2 = z.

(4.3)

Из (4.2) следует z ₁² = z ₂ z. Подставим z из (4.3) z = z ₂ + z ₁ и получим

z ₁²= z ₂² + z ₁ z ₂. Разделим обе части на z ₁²

 

Решая это квадратное уравнение, находим для положительного корня значение

На рис. 4.10 показано деление интервала неопределенности в этом соотношении и нанесены соответствующие значения целевой функции, которые позволяют уменьшить интервал неопределенности в 1/0.618 раза.

 

Рис. 4.10

На этой стадии еще не видны преимущества метода золотого сечения перед методом дихотомии, однако они явно проявляются при дальнейшем делении интервала, так как оказывается, что одно из значений целевой функции, которое требуется вычислить на следующем шаге уже известно. Поэтому, чтобы уменьшить неопределенность еще в 1/0.618 раза потребуется дополнительно только одно значение целевой функции в новой точке. После вычисления N значений целевой функции коэффициент дробления интервала неопределенности составляет N -1

f _д = 0,618, где (N -1) - число шагов.