Задача оптимизации в конструировании

3. Метод дихотомии
В выше приведенных методах значения целевой функции определяются при постоянном приращении независимой переменной х. Если снять это ограничение, то эффективность поиска можно повысить.
В методе дихотомии (греч. dicha – на две части, + tome – сечение – последовательное деление на две части) интервал неопределенности делится пополам. Определение целевой функции осуществляется при значениях х, отстоящих от половинной точки на , т.е. в паре точек. Величина  должна быть небольшой, но в то же время достаточной, чтобы различить, какая из пары точек лучше по значению функции F(x) (рис. 4.19).

Рисунок 4.19.

Из рис. 4.19а видно, что неизвестный оптимум в правой части F(х₂) > F(х₁). Новый интервал неопределенности снова делится пополам и возле его середины проводится опять пара измерений на расстоянии . На рис. 4.19б показаны несколько шагов определения экстремума.

Коэффициент дробления

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


4. Метод «золотого сечения»
В предыдущих методах из трех значений целевой функции, найденных в интервале неопределенности, в дальнейшем используется только два, а третье не используется.
В методе «золотого сечения» целевая функция находится в точках интервала неопределенности, расположенных таким образом, чтобы каждое значение целевой функции давало новую полезную информацию. Метод основан на задаче, которая в «Началах» Эвклида известна как задача о «золотом сечении».
Определение целевой функции производится в точке, которая делит интервал неопределенности на две неравные части так, что отношение длины большей части к длине всего отрезка (интервала неопределенности) равно отношению длины меньшего отрезка к длине большего (или все наоборот).


F(x) L
l₁ l₂
0 а b

Рисунок 4.20.

Из рисунка:

Кроме того L = l₁ + l₂.
Из (*) имеем:
Делим на :
Решаем это квадратное уравнение и получаем:

Это соотношение длин двух последовательных интервалов сохраняется постоянным в этом методе.
Если принять l₁ = 0,618, то l₂ = 0,618l₁ = 0,618² = 0,382 = ².
На первом шаге испытания проводятся в двух точках х₁ и х₂ (рис. 4.21а).
М – новый интервал неопределенности.
Расстояние между точками х₁ и х₂ равно:
= 1 – 20,382 = 0,236.
Этот отрезок симметричен относительно центра и составляет от отрезка 0,618

а от отрезка 0,382

Рисунок 4.21.

Интервал неопределенности после второго шага уменьшается в 0,618 раз.

При N > 2 эффективность метода выше, чем у метода дихотомии.
Измерения проводятся на каждом шаге в двух точках, причем одна точка известна из предыдущего шага при поиске оптимума (она повторяется на следующем шаге: рис. 4.21б).
Коэффициент дробления f = 0,618^N–1. Интересная закономерность: наибольшее сокращение последующих интервалов неопределенности достигается при определении целевой функции в точках, равноудаленных от центра.
На рис. 4.21б приведены несколько шагов поиска экстремума методом «золотого сечения».
Для оценки интервала неопределенности на k-й итерации точки х_k и х_k+1 определяются по формулам:

и

где
После N итераций длина интервала неопределенности составляет .