ОПТИМИЗАЦИЯ МЕТОДАМИ ПОСЛЕДОВАТЕЛЬНОЙ ДИХОТОМИИ, ФИБОНАЧЧИ И ЗОЛОТОГО СЕЧЕНИЯ

Цель работы. Ознакомление с методами оптимального одномерного поиска. Метод последовательной дихотомии, метод поиска Фибоначчи, метод золотого сечения.

Задание: 1. Изучить методы оптимального одномерного поиска.

2. Провести оптимизацию процесса или свойства продукции (с учетом вашего задания), описываемого уравнением регрессии у₁, методом золотого сечения, а уравнением регрессии у₂ – методом Фибоначчи.

 

Основные сведения

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

Предположим, что точка экстремума достигается при каком-то значении фактора X* из заранее известного интервала (X_min, Х_max), называемого интервалом неопределенности. Требуется с помощью наименьшего количества опытов в максимальной степени сократить размеры этого интервала, последовательно исключая из рассмотрения те точки, в которых нахождение экстремума невозможно. При этом предполагается, что функция отклика у(X) унимодальна, т.е. обладает единственным экстремумом в точке X* и не имеет участков постоянства, т.е. для всех Х₁< Х₂< Х* справедливо у(X₁) < у(Х₂), а для X*< Х₃< X₄ верно у (Х₃)> у(Х₄).

В этих условиях для того, чтобы уменьшить длину исходного интервала неопределенности L=Х_max-X_min, необходимо иметь как минимум два опыта в некоторых точках Х₁ и Х₂, таких, что X_min< X₁< X₂< Х_max.

Могут иметь место только три варианта исходов подобного экспериментирования:

a) у(X₁) < у(Х₂) -тогда максимум наверняка находится в точке Х*> Х₁, и первоначальный интервал неопределенности превратится в новый – (X₁, X_mах);

б) у(X₁) > у(Х₂) - в этом случае максимум может располагаться лишь в точке Х*< Х₂, и исходный интервал неопределенности следует заменить на (X_min, Х₂);

в) у(X₁) = у(Х₂) - случай весьма редкий, означающий, что экстремальная точка находится между значениями Х₁ и Х₂, новый интервал неопределенности будет (X₁, Х₂).

Существуют различные методы размещения указанных точек на каждом этапе экспериментирования. Для их сопоставления будем использовать показатель эффективности Е соответствующего плана эксперимента как отношение длин начального интервала неопределенности L и полученного после реализации N опытов L_N:

Е = L / L_N (2.1)

Метод последовательной дихотомии предусматривает размещение на каждом этапе экспериментирования сразу двух новых точек, расположенных симметрично относительно середины интервала неопределенности на расстоянии ∆ ℓ друг от друга. Здесь ∆ ℓ - малая величина, ограниченная снизу разрешающей способностью ∆ ℓ _доп в измерении величины X. Значение ∆ ℓ _доп - это та минимальная разница между соседними наблюдениями X, которая может быть обнаружена инструментально, с помощью тех измерительных средств, которые имеются в распоряжении экспериментатора. Координаты первых двух точек равны:

X₁ = (Х_max + X_min - ∆ ℓ )/2; X₂ = (Х_max + X_min + ∆ ℓ )/2 (2.2)

Координаты экспериментальных точек на последующих этапах исследования определяются по аналогичным формулам с учетом новых границ получающегося интервала неопределенности.

Длина интервала неопределенности после проведения k-й пары опытов равна:

L_N = L/2^k + (1 - 1/2^k)·∆ ℓ , N = 2k (2.3)

Тогда показатель эффективности метода приближенно можно считать равным ( ∆ ℓ ≈ 0 ) Е ≈ 2k=2^N/2.

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

δ ≥ L_N/ L =[l/2^k + (l - l/2^k)· ∆ ℓ _доп]/ L, N = 2k (2.4)

С практической точки зрения желательно при данном числе опытов использовать максимально возможное значение ∆ ℓ . Поэтому, определив с помощью формулы 2.4 число опытов N, целесообразно найти подобное значение ∆ ℓ из условия

δ = l/2^k + (l - l/2^k)· ∆ ℓ / L, k= N /2, т.е.

∆ ℓ = (δ ·2^k – l)·L / (2^k - l) (2.5)

Затем использовать это ∆ ℓ при планировании эксперимента. Ясно, что ∆ ℓ ≥ ∆ ℓ _доп. При этом следует задаваться такой относительной погрешностью δ, чтобы абсолютная ошибка ∆ ε =δ -L была бы не меньше, чем 2 ∆ ℓ _доп, т.е. δ ≥ 2 ∆ ℓ _доп / L, т.к. только в этом случае все экспериментальные точки удалены друг от друга не ближе, чем на ∆ ℓ _доп.

Метод поиска Фибоначчи базируется на использовании чисел Фибоначчи F_k, определяемых рекуррентным соотношением вида:

F_k= F_k-1+ F_k-2, К> 1, F_о=F₁=S.

Планирование эксперимента производится следующим образом.

Координаты X₁ - первого эксперимента определяются по формуле:

Х₁ = X_min + (F_N-l ^. L + (-S)^N· ∆ ℓ ) / F_N (2.6)

Здесь ∆ ℓ ≥ ∆ ℓ _доп. - малая величина, играющая ту же роль, что и в методе последовательной дихотомии.

Вторая точка X₂ - располагается в исходном интервале L симметрично первой. Учитывая, что в каждый очередной интервал неопределенности попадает один предыдущий эксперимент, то для продолжения поиска новую точку следует располагать в этом интервале симметрично оставшимся. Если обозначить, через X(j) координату оставшейся точки на j-ом этапе поиска, а S_1j и S_2j - соответственно левую и правую границы очередного интервала неопределенности, то координата X_j+1 новой точки задается соотношением:

X_j+1 = S_1j + S_2j - X_j (2.7)

Длина интервала неопределенности после проведения N опытов составляет:

L_N = L·(S+F_N-2 · ∆ ℓ )/F_N (2.8)

Теперь можно определить показатель эффективности метода Е. В первом приближении он равен Е≈ F_N

В методе поиска оптимума Фибоначчи предварительное определение необходимого числа опытов является обязательным, т.к. значение N используется при расчете координат первой точки согласно формуле 2.6

Для определения N следует задаться допустимой относительной погрешностью в определении положения экстремума δ и величиной ∆ ℓ _доп. Тогда N можно найти с помощью соотношения:

δ ≥ L_N / L = (1 + F_N-2.· ∆ ℓ _доп /L) / F_N (2.9)

Значения F_N приведены в таблице 2.1.

Таблица 2.1. Числа Фибоначчи

номер
FN
номер
FN

 

После вычисления N можно определить наибольшее ∆ ℓ ( ∆ ℓ ≥ ∆ ℓ _доп), гарантирующее прежнее значение δ и максимальное удаление экспериментальных точек друг от друга, что весьма желательно:

∆ ℓ = (F_N·δ - 1)·L/F_N-2 (2.10)

В методе поиска оптимума Фибоначчи последняя точка всегда располагается на расстоянии δ от одной из предыдущих. При этом, задаваемое значение δ должно соразмеряться с ∆ ℓ _доп, т.е. δ ≥ 2∆ ℓ _доп / L.

 

Метод золотого сечения является частной разновидностью метода Фибоначчи и отличается от него лишь тем, что в методе золотого сечения нет необходимости в обязательном предварительном определении общего числа опытов N. Координаты Х₁ -первой точки в этом методе - находятся по формуле:

Х₁ = X_min + q·L (2.11)

где q= lim (F _N-2 / F_N)= 0.382 (N→ ∞ ).

Вторая точка расположена симметрично относительно середины интервала:

Х₂ = Х_max - (Х₁-Х_min)

В остальном алгоритм нахождения оптимума данным методом не отличается от алгоритма метода оптимизации Фибоначчи.

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

Деление отрезка подобным образом восходит еще к Евклиду и называется " золотым сечением". Отсюда и наименование метода.

Его эффективность после реализации N опытов будет равна:

E=1 / (l-q)^N =l / 0, 618 ^N-1

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

δ ≥ L_N / L = 1 / Е= 0, 618 ^N-1 (2.12)

Если, как в предыдущих примерах, δ =0.05, то N=8.

В методе золотого сечения последняя точка будет располагаться на расстоянии S=(l-2q)L_N-1 от одной из предыдущих точек.

L_N-1 =0, 618^N-2·L и S=(1-2q)·0, 618^N-2·L = 0, 236·0, 618^N-2·L.

Очевидно, что обязательно должно быть S ≥ ∆ ℓ _доп. Отсюда можно получить ограничение на задаваемое значение погрешности δ, обусловленное наличием допустимого приращения ∆ ℓ _доп:

δ ≥ 0, 618_.· ∆ ℓ _доп / 0, 236·L = 2.619 _.· ∆ ℓ _доп / L.

Рассмотрим примеры применения рассмотренных методов поиска оптимума. Пусть известно, что функция отклика принимает максимальное значение при некотором значении X из диапазона 0-1000. Требуется определить положение экстремума с погрешностью, не превышающей 5% от исходного диапазона, если допустимое разрешение измерительного устройства ∆ ℓ _доп =5.

По условию L=1000; δ =0.05. Основные этапы расчета по рассмотренным методам оптимизации представлены в таблице 2.2.

Таблица 2.2. Результаты поиска оптимума разными методами

 

Номер экспери- мента j	Координаты эксперимен- тальных точек Хj	Отклик y(Xj)	Интервал неопределенности после опыта Хj
Границы интервала S1j- S2j	Длина L j,
Метод последовательной дихотомии
			0- 1000 490 - 1000 490 - 1000 490 - 755 490 - 755 612- 755 612 - 755 674 - 755 674 - 755 674 - 724
Метод поиска Фибоначчи
	618.8 381.2 762.5 856.3 712.6 668.7 718.6	-51609	0- 1000 381.2- 1000 618.8 - 1000 618.8- 856.3 618.3 - 762.5 668.7 - 762.5 618.8- 718.6	618.8 381.2 237.5 143.7 93.8 49.9
Метод золотого сечения
		-51124	0- 1000 382 - 1000 618 - 1000 618- 854 618- 764 674 - 764 674 - 730 674 - 708

 

В случае метода последовательной дихотомии в соответствии с формулой 2.5:

δ =0, 05≥ 1/2^k + (1 - 1/2^k)· 5 / 1000,

откуда легко найти подходящее значение k =5, N=10. Соответствующее значение ∆ ℓ равно:

∆ ℓ = (δ ·2^k – l)·L / (2^k - l)=(0.05 • 2⁵-1)·1000 / (2⁵-1)=19, 35≈ 20.

X₁ = (Х_max + X_min - ∆ ℓ )/2=(1000+0-20) /2=490

X₂ = (Х_max + X_min + ∆ ℓ )/2 = =(1000+0+20) /2= 510.

Значение отклика в точке Х₂ больше соответствующего значения отклика в точке X₁ т.е. у(X₂)> у(X₁), экстремум находится в интервале между X₁ и Х_max, (490 в 1000). Производим измерения в точках внутри этого нового интервала:

X₃ = (Х_max + X₁ - ∆ ℓ )/2=(1000+490-20) /2=735

X₄ = (Х_max + X₁ + ∆ ℓ )/2 = =(1000+490+20) /2= 755.

Из таблицы 2.2 видно, что значение отклика в точке Х₄ меньше соответствующего значения отклика в точке Х₃, т.е. у(X₄)> у(X₃), поэтому экстремум находится в интервале между Х₁ и Х₄ (490 и 755). Производим измерения в точках внутри этого нового интервала:

X₅ = (Х₄ + X₁ - ∆ ℓ )/2=(755+490-20) /2=612

X₆ = (Х₄ + X₁ + ∆ ℓ )/2 = =(755+490+20) /2= 632.

Значение отклика в точке Х₆ больше соответствующего значения отклика в точке X₅ т.е у(X₆)> у(X₅), однако Х_{5, 6} < Х₄, экстремум находите в интервале между Х₄ и Х₅ (612 и 755); Производим измерения в точках внутри интервала по той же схеме:

X₇ = (Х₄ + X₅ - ∆ ℓ )/2=(755+612-20) /2=674

X₈ = (Х₄ + X₅ + ∆ ℓ )/2 = =(755+612+20) /2= 694.

Значение отклика в точке Х₈ больше значения отклика в точке Х₇: т.е у(X₈)> у(X₇), однако Х_{8, 7} < Х₄, поэтому экстремум находится между Х₇ и Х₄ в интервале 674-755. Производим последнее измерение в точках внутри этого нового интервала:

X₉ = (Х₄ + X₇ - ∆ ℓ )/2=(755+674-20) /2=704

X₁₀ = (Х₄ + X₇ + ∆ ℓ )/2 = =(755+674+20) /2= 724.

Поскольку значение отклика в точке Х₁₀ больше значения отклика в точке Х₉: т.е у(X₁₀)> у(X₉), экстремум находится в интервале между Х₇ и Х₁₀ (674 и 724).

На этом поиск может считаться законченным.

Нахождение оптимума методом Фибоначчи. Пусть, как и раньше, L=1000, ∆ ℓ _доп =5; δ =0.05. По формуле 2.9 подбираем подходящее значение N. Оно равно 7.

Действительно, δ =0.05> l/F₇+(F₅/F₇)· (5/1000)=l/21+(8/21)(5/1000)= 0.0495.

Значение ∆ ℓ , рекомендуемое для использования в эксперименте, здесь равно:

∆ ℓ =(F₇·0.05-1)·1000/F₅= (21 · 0.05-l)·1000/8=50/8=6.

В методе золотого сечения координаты Х₁ (первой точки) находятся по формуле (2.11):

Х₁ = X_min + q·L=0+0, 382·1000=382

Вторая точка расположена симметрично относительно середины интервала: Х₂ = Х_max - (Х₁-Х_min) = 1000-(382-0) = 618

Значение отклика в точке Х₂ больше соответствующего значения отклика в точке Х₁: т.е у(X₂)> у(X₁), экстремум находится в интервале между Х₁ и Х_max (382 и 1000). Производим измерения в точке внутри этого нового интервала:

Х₃ = Х_max - (Х₂-Х₁) = 1000-(618-382) = 764

Значение отклика в точке Х₃ больше соответствующего значения отклика в точке Х₂: т.е у(X₃)> у(X₂), поэтому экстремум находится в интервале между Х₂ и Х_max (618 и 1000).

Производим измерения в точке внутри этого нового интервала:

Х₄= Х_max - (Х₃-Х₂)=1000-(764-618) = 854

Значение отклика в точке Х₄ меньше соответствующего значения отклика в точке X₃: т.е у(X₄)> у(X₃), экстремум находится в интервале между Х₂> и Х₄ (618 и 854). Производим измерения в точке внутри интервала по той же схеме:

Х₅ = Х₂+ q ·7 = 618 + 0.382 · 236 = 708

Значение отклика в точке Х₅ больше соответствующего значения отклика в точке Х₃: т.е у(X₅)> у(X₃), поэтому экстремум находится в интервале между Х₂ и Х₃ (618 и 764). Производим измерения в точке внутри этого нового интервала:

Х₆ = Х₂+ q ·7 = 618 + 0.382 · 146 = 674

Поскольку, как это видно из таблицы 2.2, значение отклика в точке Х₆ меньше соответствующего значения отклика в точке Х₅: т.е у(X₆)> у(X₅), экстремум находится в интервале между Х₆ и Х₃ (674 в 764). Производим измерения в точке внутри этого нового интервала по той же схеме:

Х₇= Х₃ - (Х₅-Х₆)= 764·(708-674) = 730

Из таблицы 2.2 видно, что значение отклика в точке Х₇ меньше соответствующего значения отклика в точке – Х₅: т.е у(X₇)> у(X₅), поэтому экстремум находится в интервале между Х₆ и Х₇ (674 и 730). Производим измерения в точке внутри этого нового интервала:

Х₈ =Х₆+ q ·L = 674 + 0.382·56 = 696

Поскольку значение отклика в точке X₈ больше значения отклика в точке Х₅: : т.е у(X₇)> у(X₅), экстремум находится в интервале между Х₆ и Х₅ (674 и 708). На этом поиск может считаться завершенным.

Сопоставление трех указанных методов между собой позволяет сделать такие выводы: наибольшей эффективностью обладает метод поиска Фибоначчи; однако, метод золотого сечения немногим уступает ему в эффективности, но более прост в расчетах. Метод последовательной дихотомии наименее эффективен, хотя и представляется наиболее простым и доступным.

Задание для самостоятельной работы

1. По результатам лабораторной работы №4 (методические указания №1 ) провести оптимизацию процесса или свойства продукции (с учетом вашего задания). Оптимизацию процесса, описываемого уравнением регрессии у₁, осуществитьметодом золотого сечения, а уравнением регрессии у₂ – методом Фибоначчи.

2. Провести сравнительный анализ методов оптимизации.

3. Сделать выводы по работе.

Содержание и оформление отчета

5. Титульный лист, содержащий информацию о студенте (группа, фамилия, номер варианта);

6. Тема, цель и индивидуальное задание.

7. Результат выполнения работы в соответствии с индивидуальным заданием.

8. Выводы по лабораторной работе.

Контрольные вопросы

1. Что такое оптимизация, и с какой целью ее проводят?

2. Какие методы оптимизации вы знаете? В чем сущность и алгоритм оптимизации по методу золотого сечения?

3. В чем сущность и алгоритм оптимизации методом Фибоначчи?

4. В чем сущность и алгоритм оптимизации методом последовательной дихотомии?

5. В чем сходство и различие методов оптимального многомерного и одномерного поиска?

6. Как определяется окончание процедуры оптимизации в случае одномерного поиска?

7. Назовите количественные критерии эффективности методов оптимизации? Какой их физический и математический смысл?

 

 

Лабораторная работа №3

 

⇐ Предыдущая12345Следующая ⇒

Поделиться: