XIV Аттетков и др. Методы оптимизации (1081420), страница 10
Текст из файла (страница 10)
Лйетоды последовательного поиска и соя2 = (аь + Ьь)/2+ 6, симметричных относительно середины отрезка (ай, Ьь) длины 1ь. После выполнения Ь-го шага будет выделен отрезок (а„ьм Ь1,+1) длины 1ь+1 и вычислено Х = 2Й значений функции. Используя формулу (2.6) для длины отрезка (интереала неопределенности) и полагая 11 = 1, получаем 1 — 26 1 — 2б +2о = ж +2о. 2ж/2 (2.8) Сравнивая (2.8) с (2.5), видим, что скорость сходимости метода дихотомии значительно выше скорости сходимости опта валеного пассивного поиска. Отметим, что после исключения отрезка на ь-м шаге опи- СаННОГО аЛГОРИтМа ТОЧКИ тй1 И жьа ПРИНаДЛЕжат НОВОМУ ОтРезкУ (аял1, Ььч1), пРичем оДна из них ЯвлаетсЯ внУтРенней Дла этого отрезка. Но вычисленное в этой точке значение функции у(х) в методе дихотомии не используют для исключения отрезка на следующем шаге, а проводят вычисления в двух новых точках.
Существуют методы последовательного поиска, в которых на каждом й-м шаге начиная с lс = 2 вычисляют лишь одно новое значение функции в точке, принадлежащей отрезку (алт1, Ья 1). Это значение вместе с Уже вычисленным на пРеДыдущем шаге значением функции во внутренней точке отрезка (ая, Ьь) используют при выполнении процедуры исключения отрезка на следующем шаге последовательного поиска. Метод золотого сечения.
Как известно*, золотым сечением отпрезха называют такое его деление на две неравные части, при котором отношение длины всего отрезка к длине его большей части равно равно отношению длины большей части к длине меньшей. Термин „золотое сечение" ввел Леонардо да Винчи**. Золотое сечение широко применяли при композиционном постро- "Сил Васютинский Н., а также: Коробко В.И. '*Леонардо да Винчи (1452 — 1519) итальянский живописен, скульптор, архитектор, ученый и инженер. 64 2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ енин многих произведений мирового искусства, в том числе в античной архитектуре и в эпоху Возрождения.
Рассмотрим 6-й шаг последовательного поиска. Чтобы выполнить процедуру исключения отрезка на этом шаге, отрезок [аю Ьь) необходимо двумя внутренними точками хы, хель хя1 ( хьз, разделить на три ча- У сти. Эти точки выберем симме- У(х„д трично относительно середины У( 'и) отрезка [аю Ьь) [рис. 2.8) и так, 3 чтобы каждая из них производила золотое сечение отрезка о а, х, х„, ь. х [аю Ьв). В этом случае отрезок [аьтм Ьь ь1) внутри будет содержать одну из точек хям хьз [другая будет одним из концов отрезка), причем эта точка будет производить золотое сечение отрезка [аь м Ьь+1).
Это вытекает из равенства длин отрезков [аю хы) и [хь~, .Ьь). Таким образом, на (к+ 1)-м шаге в одной из точек хь~.1 ~., хь 1з значение функции вычислять нс нужно. При этом отношение (ь/1ь~, длин отрезков сохраняется от шага к шагу, т.е. Рис. 2.8 (ь-н = т = сопИ. (ь-~-! (ь-~-2 [2.9) Число т называют отношением золотого сечения. Последовательный поиск, в котором на к-м шаге каждая из симметрично выбранных на отрезке [аю Ьь) точек хы, хьз осуществляет золотое сечение этого отрезка, называют методом золотова сечения. В этом методе каждое исключение отрезка уменьшает оставшийся отрезок в т раз.
Выясним, чему равно отношение золотого сечения. Так как точки хя1 и хьз, хы ( хьз, выбраны симметрично относительно середины отрезка [аю Ьь), то 2.4. Методы последовательного поиска (см. рис. 2.8). Для определенности будем считать, что на 6-м шаге выбРан отРезок [аы хьз], ТогДа на [6+1)-м шаге оДной из точек деления [а именно правой) будет точка хы.
Значит, Длина 1ьд.з отРезка, .выбиРаемого на (6+1)-м шаге, совпаДает с Длиной отРезка [а, .хы] и веРно Равенство 1ьд.з = 1ь — 1ьдд. Подставляя найденное выражение для 1я 2 в уравнение (2.9), получаем 1ь 1ь~-~ или т =1[(т — 1). Преобразуя это соотношение, приходим к квадратному уравнению т — т — 1 = О, имеющему единственное 2 положительное решение т = — 1,618034. 1+Л Предположим, что отрезком минимизации унимодальной функции 1" (х) является [О, Ц, т.е. а~ = О, б~ = 1 и 1~ = 1.
На первом шаге последовательного поиска [б = 1) на отрезке [О, 1] выбираем две точки х~~ = а~ + (1 — 1[т)6-, = 1 — 1[т и хгз = = а~ + 6~(т = 11т,. осуществляющие золотое сечение отрезка [О, 1]. Вычисляем значения минимизируемой функции в этих точках и выполняем процедуру исключения отрезка. Если 1'[хы) ( 1(хгз), то выбиРаем отРезок [ам хд], т.е, полагаем аз = а~ = О, 62 = хд, .в противном случае выбираем отрезок [хм, 10], т.е.
полагаем аз = хм, 62 = 6~ = 1. Кроме того, в первом случае принимаем хз = тм, а во втором случае хз = х~з. Точка хз — одна из точек, осуществляющих золотое сечение отрезка [аз, 62], меньшая в первом случая и ббльшзя во втором. Если длина вновь полученного отрезка больше заданной допустимой длины е„ингаервада неопределенности~, то следует перейти ко второму шагу алгоритма., на котором одна из точек хзм х22 есть точка хз, а вторую можно найти, например, по формуле аз+ 62 — хз.
На втором шаге алгоритма вычисляем лишь одно значение функции в точке, симметричной хз относительно середины отрезка [а2, 62]. Если же длина 12 отрезка [аз, 62], полученного после первого шага алгоритма, 2. метОды ОднОмеРЯОЙ минимизлции и вычисляем в ней значение функции.
Если хь < хы то хы = хь и хьз = хь, иначе хы — — хь и хьз = хы Пусть для определенности хь < хь (см. рис. 2.8) и хы = х;„ хьз = хь. Если ~(хы) < ~(хьз), то выбираем отрезок (аь,хьз), т.е. полагаем аь сс = аы бь с~ = хьз, хь сс = хы., иначе выбираем отрезок [хьс, бс1, т.е. полагаем аьсс — — хы, бьсс = бы хь,с —— =хин ДлинУ 1ьы нового отРезка [аь.сыбь 1) сРавниваем с е, и принимаем решение, продолжать поиск (при 1ь сс ) е,) или нет (при 1ьсс < е„). В случае прекращения поиска полагаем х„= (аь + бь) /2. Согласно описанию алгоритма, на первом шаге значение функции вычисляют в двух точках, а на каждом из последующих шагов вычисляют лишь одно значение функции. Поэтому после 6 шагов алгоритма значение функции будет вычислено в Ас = 6+ 1 точках.
Поскольку после каждого шага интервал неопределенности уменьшается в т раз, то для длины 1ьтс отрезка [аья м бья 1) получаем 1ььс = 1с,ст~ = 1(т~, а зависимость 1~, длины интервала неопределенности от количества Ас вычисленных значений функции выражается формулой 1 1 1л =1ь-сс = ть т~ (2.10) Алгоритмы методов золотого сечения и дихотомии аналогичны. Различие состоит лишь в том, что в методе дихотомии расстояние 2б между внутренними точками хы, хьз отрезка оказалась меньше е„то поиск прекращают и полагают х,— = (аз+ бз)сс2.
Пусть на 6-м шаге, б > 2, последовательного поиска по методу золотого сечения выбран отрезок [а~, .бь] и в нем точка хь, осуществляющая золотое сечение этого отрезка. Значение ~(хь) функции в этой точке уже вычислено на предыдущем шаге. Находим вторую точку хь золотого сечения по формуле 2.4. Ыетоды последопатеаьиого поиска [аь, Ьь] на каждом й-м шаге остается неизменным, а в методе золотого сечения оно зависит от номера шага поиска и уменьшается с уменьшением длины 1~ отрезка по мере возрастания номера шага. Действительно, в методе золотого сечения на Й-м шаге поиска, внутренними точками отрезка [аь, бь) будут хы = = аь+ (1 — 1(т)1ь и иьз = аь+1ь~т, а расстояние между ними равно тьэ — ты — — (2(т — 1)1ь = (ъ 5 — 2)1ь — 0,2360681ь.
Метод с1эибоначчи. Пусть при поиске точки ж, е [О, Ц, в которой унимодальная на отрезке [О, Ц функция 1(т) принимает наименьшее на этом отрезке значение, можно вычислить ее значения только в двух точках. Тогда предпочтение следует отдать методу дихотомии при д « 1. так как он позволит уменьшить интервал неопределенности почти вдвое, а метод золотого сечения .— лишь в т 1,618 раз. Сравнение (2.8) и (2.10) показывает, что при количестве вычисляемых значений функции Х > 4 эффективность метода золотого сечения становится выше, чем метода дихотомии.
Однако при любом заданном общем числе Дь > 2 вычисляемых значений функции можно построить еще более эффективный метод, состоящий из М вЂ” 1 шагов. Он сочетает преимущество симметричного расположения внутренних точек жы., иьэ на отрезке [иь,бь) относительно его середины, реализованное в методах дихотомии и золотого сечения, с возможностью на каждом шаге изменять отношение 1ь/1ье1 длин сокращаемого и нового отрезков. Как показано при обсуждении метода золотого сечения, в случае выбора внутренних точек симметрично относительно середины отрезка для трех последовательных шагов этого метода выполняется соотношение (2.11) 1ь 1 = 1ь + 1ь.еь й = 2, 3, Построение алгоритма такого метода удобнее начать с последнего шага, но предварительно уточним задачу.
Располагая возможностью вычислить в Х точках хь е [О, Ц, й = 1, Дь, значения унимодальной на отрезке функции 1 (т), необходимо как 68 2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ можно точнее, т.е. с наименее возможной длиной интервала неопределенности, отыскать точку х„наименьшего значения этой функции на отрезке [О, Ц. При выполнении процедуры исключения отрезка на последнем, (Х вЂ” 1)-м шаге имеем отрезок [ал м бм 11 длины 1Н 1 с двумя внутренними точками хм 1 и хл, симметрично расположенными относительно середины отрезка на достаточно малом расстоянии 2д друг от друга У (рис. 2.9).
В этих точках вычиЯхя,) елены значения ~(хл — 1) и ~(хн) Лхл ) 2д функции 1(х). Пусть для определенности ~(.льч) ( У(хм 1): то я гда для нового отрезка [ал;Ьл"] лн ья ' длины1л =1м 1/2+3 внутренней О ая-1 хи хи-1 ьи-~ х будет точка хи, а точка хи 1 совпадет с одним из его концов. В такой ситуации при выборе х, = хн длина интервала неопределенности равна пока неизвестной длине 1у отрезка [ал,. бч), Через 1у можно выразить длину 1л 1 = 21л — 2б отрезка [ау. О бл .1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
