Этап установления границ интервала

На этом этапе сначала выбирается исходная точка, а затем на основе правила исключения строится относительно широкий интер­вал, содержащий точку оптимума. Обычно поиск граничных точек такого интервала проводится с помощью эвристических методов поиска, хотя в ряде случаев можно также использовать методы, экстраполяции. В соответствии с одним из эвристических методов, который был предложен Свенном [1], (k+1)-я пробная точка опре­деляется по рекуррентной формуле

где х₀— произвольно выбранная начальная точка, Δ — подбирае­мая некоторым способом величина шага. Знак Δ определяется путем сравнения значений f(x₀), f(x₀+|Δ |) и f(x₀— |Δ |). Если

то, согласно предположению об унимодальности, точка минимума должна располагаться правее точки х₀и величина Δ выбирается положительной. Если изменить знаки неравенств на противопо­ложные, то Δ следует выбирать отрицательной. Если же

то точка минимума лежит между х₀—|Δ | и х₀+|Δ | и поиск гранич­ных точек завершен. Случай, когда

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

Пример 2.5

Рассмотрим задачу минимизации функции f(х)=(100—х)² при заданной начальной точке х₀=30и величине шага |Δ |=5.

Знак Δ определяется на основе сравнения значений

Так как

то величина Δ должна быть положительной, а координата точки минимума х* должна быть больше 30. Имеем x₁=x₀+Δ =35. Далее х₂=х₁+2Δ =45, f(45)=3025< f(x₁),

следовательно, х*< 185. Таким образом, шесть шагов вычислений x* позволили выявить интервал 65£ x*£ 185, в котором располо­жена точка х*. Заметим, что эффективность поиска граничных точек непосредственно зависит от величины шага Δ. Если Δ велико, то получаем грубые оценки координат граничных точек, и построен­ный интервал оказывается весьма широким. С другой стороны, если Δ мало, для определения граничных точек может потребоваться достаточно большой объем вычислений.

Этап уменьшения интервала

 

После того как установлены границы интервала, содержащего точку оптимума, можно применить более сложную процедуру умень­шения интервала поиска с целью получения уточненных оценок координат оптимума. Величина подинтервала, исключаемого на каждом шаге, зависит от расположения пробных точек x_lи x₂ внутри интервала поиска. Поскольку местонахождение точки оптимума априори неизвестно, целесообразно предположить, что размещение пробных точек должно обеспечивать уменьшение интервала в од­ном и том же отношении. Кроме того, в целях повышения эффек­тивности алгоритма необходимо потребовать, чтобы указанное от­ношение было максимальным. Подобную стратегию иногда назы­вают минимаксной стратегией поиска.

Метод деления интервала пополам. Рас­сматриваемый метод позволяет исключать в точности половину интервала на каждой итерации. Иногда этот метод называют трех­точечным поиском на равных интервалах, поскольку его реализация основана на выборе трех пробных точек, равномерно распределен­ных в интервале поиска. Ниже приводится описание основных шагов поисковой процедуры, ориентированной на нахождение точки ми­нимума функции f(x) в интервале (а, b).

Шаг 1. Положить х_т=(а+b)/2и L=b—а. Вычислить значе­ние f(x_m).

Ш а г 2. Положить x₁=a+L/4 и х₂=b—L/4. Заметим, что точ­ки x₁, x_m и х₂делят интервал (a, b) на четыре равные части. Вычис­лить значения f(x₁) и f(x₂).

Ш а г 3. Сравнить f(x₁) и f(x_m).

(1) Если f(x₁)< f(x_m), исключить интервал (х_т, b), положив b=х_т. Средней точкой нового интервала поиска становится точка х₁. Сле­довательно, необходимо положить х_т=х₁.

Перейти к шагу 5.

(2) Если f(x₁)> f(x_m), перейти к шагу 4.

Ш а г 4. Сравнить f(x₂) и f(x_m).

(1) Если f(x₂)< f(x_m), исключить интервал (а, х_т), положив а=х_т. Так как средней точкой нового интервала становится точка х₂положить х_т=х₂. Перейти к шагу 5.

(2) Если f(x₂)³ f(x_m), исключить интервалы (a, x₁) и (х₂, b). Поло­жить a=x₁ и b=х₂. Заметим, что х_т продолжает оставаться средней точкой нового интервала. Перейти к шагу 5.

Ш а г 5. Вычислить L=b—а. Если величина |L|мала, закон­чить поиск. В противном случае вернуться к шагу 2.

Замечания

1. На каждой итерации алгоритма исключается в точности по­ловина интервала поиска.

2. Средняя точка последовательно получаемых интервалов всег­да совпадает с одной из пробных точек x₁, x₂или х_т, найденных на предыдущей итерации. Следовательно, на каждой итерации тре­буется не более двух вычислений значения функции.

3. Если проведено п вычислений значения функции, то длина полученного интервала составляет (1/2)^n/2 величины исходного интервала.

4. В работе [2] показано, что из всех методов поиска на равных интервалах (двухточечный, трехточечный, четырехточечный и т. д.) трехточечный поиск, или метод деления интервала пополам, отли­чается наибольшей эффективностью.

Пример 2.6. Метод деления интервала пополам

Минимизировать f(х)=(100—x)² в интервале 60£ x £ 150. Здесь a=60, b=150 и L=150-60=90.

Таким образом, исключаются интервалы (60; 82, 5) и (127, 5; 150). Длина интервала поиска уменьшается с 90 до 45.

Итерация 2

Таким образом, интервал неопределенности равен (93, 75; 116, 25)

Итерация 3

а=93, 75 b=116, 25, х_т=105,

L = 116, 25—93, 75=22, 5,

x₁=99, 375, х₂=110, 625,

f(x₁)=0, 39< f(105)=25.

Таким образом, исключается интервал (105; 116, 25). Новый ин­тервал неопределенности равен (93, 75; 105), его средняя точка есть 99, 375 (точка х₁на итерации 3). Отметим, что за три итерации (шесть вычислений значения функции) исходный интервал поиска длины 90 уменьшился до величины (90)(1/2)³=11, 25.

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

1. Если количество пробных точек принимается равным двум, то их следует размещать на одинаковых расстояниях от середины интервала.

 

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

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

Руководствуясь этими выводами, рассмотрим симметричное рас­положение двух пробных точек на исходном интервале единичной длины, которое показано на рис. 2.11. (Выбор единичного интервала обусловлен соображениями удобства.) Пробные точки отстоят от граничных точек интервала на расстоянии t. При таком симметрич­ном расположении точек длина остающегося после исключения ин­тервала всегда равна t независимо от того, какое из значений функ­ции в пробных точках оказывается меньшим. Предположим, что исключается правый подынтервал. На рис. 2.12 показано, что оставшийся подынтервал длины t содержит одну пробную точку, расположенную на расстоянии (1—t) от левой граничной точки.

Для того чтобы симметрия поискового образца сохранялась, расстояние (1-t) должно составлять t-ю часть длины интервала (которая равна t). При таком выборе t следующая подобная точка размещается на расстоянии, равной t-й части длины интервала, от правой граничной точки интервала (рис.2.13)

Рис. 2.12. Интервалы, полученные методом золотого сечения

 

Отсюда следует, что при выборе t в соответствии с условием 1-t =t² симметрия поискового образца, показанного на рис. 2.11, сохраняется при переходе к уменьшенному интервалу, который изображен на рис. 2.13. Решая это квадратное уравнение, получаем

откуда положительное решение t=0, 61803…. Схема поиска, при которой пробные точки делят интервал в этом отношении, известна

под названием поиска с помощью метода золотого сечения. Заметим, что после первых двух вычислений значений функции каждое по­следующее вычисление позволяет исключить подынтервал, величина которого составляет (1—t)-ю долю от длины интервала поиска. Следовательно, если исходный интервал имеет единичную длину, то величина интервала, полученного в результате N вычислений зна­чений функции, равна t^N-1. Можно показать, что поиск с помощью метода золотого сечения является асимптотически наиболее эффек­тивным способом реализации минимаксной стратегии поиска.

 

Пример 2.7. Метод золотого сечения

Опять рассмотрим задачу из примера 2.6, в которой требуется

минимизировать f(х)=(100—х)²в интервале 60£ x £ 150. Для того чтобы перейти к интервалу единичной длины, проведем замену переменной, положив w=(x—60)/90. Таким образом, задача принимает следующий вид:

минимизировать f(w)—(40—90w)²

при ограничении 0£ w £ 1.

Итерация 1. I₁=(0, 1); L₁=l. Проведем два первых вычисления значений функции:

Так как f(w)₂< f(w₁) и w₂< w₁, интервал w≥ w₁ исключается.

Итерация 2. I₂=(0; 0, 618); L₂=0, 618=t. Следующее вы­числение значения функции проводится в точке

Так как f(w₃)> f(w₂) и w₃< w₂, интервал w≤ w₃исключается.

Итерация 3. I₃=(0, 236; 0, 618), L₃=0, 382=t². Следующее вычисление значения функции проводится в точке, расположенной на расстоянии t ´ (длина полученного интервала) от левой гра­ничной точки интервала, или на расстоянии (1—t) ´ (длина ин­тервала) от правой граничной точки. Таким образом,

Так как f(w₄)< f(w₂) и w₄> w₂, интервал w£ w₂ исключается.

В результате получен следующий интервал неопределенности: 0, 382£ w £ 0, 618 для переменной w, или 94, 4£ x £ 115, 6 для перемен­ной х.

Если в процессе поиска проведено шесть вычислений значений функции, то длина результирующего интервала для переменной wравна

что соответствует интервалу длины 8, 1 для переменной х. Для срав­нения напомним, что в аналогичной ситуации метод деления интер­вала пополам привел к получению интервала длины 11, 25.

В общем случае если правая и левая граничные точки интервала неопределенности (обозначим их через XR и XL) известны, то ко­ординаты всех последующих пробных точек, получаемых в соответ­ствии с методом золотого сечения, можно вычислить по формулам

w= XR—tⁿ или w= XL + tⁿ

в зависимости от того, какой подынтервал был исключен на преды­дущей итерации — левый или правый. В приведенных выше форму­лах через tⁿ обозначена п-ястепень t, где п — количество вычисле­ний значений функции.

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

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

Поделиться:

Популярное:

1. I ЭТАП (1-3 ст.) ОВОДНЕНИЕ ИКРИНКИ И ПОЯВЛЕНИЕ БЛАСТОДИСКА
2. I этап. Теория рыночных структур (1880-1910 гг.)
3. II этап (середина XVII в. - середина XIX в.) – психология как наука о сознании.
4. III. Второй этап: образ питания археоантропов
5. IV. Третий этап: образ питания палеоантропов
6. VII. Второй этап компоновки редуктора
7. XII. НИКАКИХ ГРАНИЦ (1971 г.)
8. ІІ. Этапы научного исследования
9. А. Расходы домашних хозяйств, фирм, государства, заграницы
10. Адсорбция на границе твердое тело – раствор
11. Алгоритм действия фельдшера на догоспитальном этапе
12. Американцы за границей, 1890–1914 годы