Книги по разным темам Pages:     | 1 |   ...   | 2 | 3 | 4 | 5 | 6 |   ...   | 8 |

a(4) = 1,594 f (a(4) ) = 1, 211;

b(4) = 1,813 f (b(4)) = 1,082;

( * ( x* x13) = 1,713, f f (x13) ) = 1,004.

(4) (4) x2 =1,694 f (x2 ) =1,017;

(3) (3) x1 =1,713 f (x1 ) =1,004;

* Ответ: 8 = [1,594;1,813], x* 1,713, f 1,004.

Метод Фибоначчи Метод Фибоначчи является наилучшим (в смысле максимального уменьшения длины отрезка локализации) среди активных методов поиска.

Согласно методу Фибоначчи, на первом шаге (первой ите( рации) проводятся два вычисления значений f(x) в точках x11) и ( ( ( x21) (причем x11) < x21) ), расположенных симметрично относительно середины отрезка 0 = [a,b]. По результатам вычислений ( ( одна из частей отрезка ([a, x11)] либо [x21),b] ) отбрасывается, при ( ( этом одна из точек (соответственно x21) либо x11) ) уже проведенных вычислений остается внутри отрезка 2 (1). На каждом последующем шаге (последующей итерации) точка очередного вычисления выбирается симметрично оставшейся точки. Таким образом, на первой итерации проводятся два вычисления значений f(x), на каждой последующей - одно вычисление. Поэтому при заданном количестве вычислений N будет выполнено N -шагов (итераций).

( ( При вычислении x1 j) и x2 j ), j = 1, N -1, используются числа Фибоначчи, определяемые следующим образом:

F0 = F1 = 1, Fk = Fk -1 + Fk - 2, k = 2,3,....

Условием окончания вычислений является выполнение заданного количества вычислений N.

Итак, алгоритм поиска минимума унимодальной функции методом Фибоначчи заключается в следующем.

1. Задается N, определяются числа Фибоначчи Fk, k = 0, N +1, выбирается из условия b - a <.

FN +Полагается j=1.

2. На j-й итерации вычисляются FN - j-1 j-1) j-1) (-1)N - j+( x1 j) = a( j-1) + (b( - a( ) -, FN - j+1 FN - j+FN - j j-1) j-1) (-1)N - j+( x2 j) = a( j-1) + (b( - a( ) +, FN - j+1 FN - j+( ( f1( j) = f (x1 j) ), f2( j) = f (x2 j) ).

( ( ( Если f1( j) f2( j), то a( j) = a( j -1), b( j) = x2 j), x2 j +1) = x1 j).

( ( ( Если f1( j) > f2( j), то a( j) = x1 j), b( j) = b( j -1), x1 j +1) = x2 j).

3. Проверяется условие окончания вычислений j = N -1.

Если оно выполняется, то определяются итоговый отрезок локализации, оценки точки минимума x и величины минимума * f = f (x*) и вычисления завершаются.

Если условие не выполняется, то полагается j=j+1 и осуществляется переход к п.2.

Примечание. На j-й, j>1, итерации вычисляется только та точка xi( j), i = 1,2, которая не была определена на предыдущей итерации.

Отметим, что оценкой точки минимума x*является та из точек xi( N -1), i = 1,2, которая осталась внутри итогового отрезка N локализации.

Пример. Определить методом Фибоначчи минимум функции f (x) = x4 - 6x2 +10, заданной на отрезке =[1,3], при N=4.

Решение.

В данном случае будут выполнены N -1 = 3 итерации.

Определяем числа Фибоначчи Fk, k = 1,5 :

F0 = F1 =1, F2 = 2, F3 = 3, F4 = 5, F5 = 8.

b - a 3 - < = = 0,25.

F5 Выбираем =0,1.

Первая итерация FN -2 F(-1)N ( x11) = a(0) + (b(0) - a(0) ) - = + -1) 1 (FN FN F(-1)4 2 2 - 0,- 0,1 =1+ =1+ 0,78 =1,78, F4 FN -1 (-1)N F( x21) = a(0) + (b(0) - a(0) ) + = 1+ (3 -1) + FN FN F(-1)4 3 2 + 0,+ 0,1 = 1+ = 1+1,22 = 2,22.

F4 Вторая итерация FN -3 (-1)N -1 F( x12) = a(1) + (b(1) - a(1) ) - = 1+ (2,22 -1) FN -1 FN -1 F(-1)3 11,22 + 0,- 0,1 = 1+ = 1+ 0,44 = 1,44.

F3 Третья итерация FN -3 (-1)N -2 F( x23) = a(2) + (b(2) - a(2) ) + = 1,44 + (2,22 FN -2 FN -2 F(-1)2 1 0,78 + 0,-1,44) + 0,1 = 1,44 + = 1,44 + 0,44 = 1,88.

F2 Результаты вычислений заносим в табл. 4.4.

Таблица 4.Номер ( ( x1 j ) x2 j) f1( j) f2( j) a( j) b( j) итерации > 0Ч Ч Ч Ч 1 1 1,78* 2,22* 1,028 < 4,719 1 2,2 1,44* 1,78 1,858 > 1,028 1,44 2,3 1,78 1,88* 1,028 < 1,286 1,44 1,Примечание. Знаком * помечаем точки xi( j), i=1,2, вычисляемые на j-й итерации.

Поскольку j=N-1=3, то вычисления завершаются.

Точка минимума локализована на отрезке 4 = [1,44; 1,88], ( * ( x* x13) = 1,78, f f (x13) ) = 1,028.

* Ответ: 4 = [1,44;1,88], x* 1,78, f 1,028.

Метод золотого сечения Недостатком наиболее эффективного метода Фибоначчи является то, что должно быть задано количество вычислений N.

Метод золотого сечения почти столь же эффективен, как и метод Фибоначчи, но при этом не зависит от N. Алгоритм поиска по методу золотого сечения определяется тем же правилом симметрии, что и алгоритм по методу Фибоначчи: на первой итерации выбираются две точки, расположенные симметрично относительно середины исходного отрезка; на каждой последующей итерации выбирается одна точка, расположенная симметрично оставшейся точки. Разница заключается в выборе точек. Метод золотого сечения основан на делении отрезка локализации золотым сечением, т.е. таком делении, когда отношение большей части отрезка ко всему отрезку равно отношению меньшей части к большей A C B AC CB =.

AB AC При таком делении используются две дроби Фибоначчи 3 - 5 5 -Ф1 = 0,382, Ф2 = 0,618, 2 удовлетворяющие условиям Ф1 + Ф2 = 1, Ф1 = (Ф2)2.

В случае метода золотого сечения используются два условия окончания вычислений:

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

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

1. Задается N (либо ), полагается j=1.

2. На j-й итерации вычисляются ( x1 j ) = a( j-1) + Ф1(b( j -1) - a( j -1)), ( x2 j) = a( j-1) + Ф2 (b( j -1) - a( j -1)), ( ( f1( j) = f (x1 j)), f2( j) = f (x2 j) ).

( ( ( Если f1( j) f2( j), то a( j) = a( j-1), b( j) = x2 j), x2 j+1) = x1 j).

( ( ( Если f1( j) > f2( j), то a( j) = x1 j), b( j) = b( j -1), x1 j +1) = x2 j).

3. Проверяется условие окончания вычислений:

Lj +а) j = N -1 либо б).

LЕсли оно выполняется, то определяются итоговый отрезок локализации, оценки точки минимума x и величины минимума * f и вычисления завершаются.

Если условие не выполняется, то полагается j=j+1 и осуществляется переход к п.2.

Пример. Определить методом золотого сечения минимум функции f (x) = x4 - 6x2 +10, заданной на отрезке =[1,3], при N=4.

Решение.

В данном случае будут выполнены N -1 = 3 итерации.

Результаты вычислений заносим в табл. 4.5.

Таблица 4.Номер ( ( итера- x1 j) x2 j ) f1( j) f2( j) a( j) b( j) > ции 0 Ч Ч Ч Ч 1 1 1,764* 2,236* 1,012 < 4,999 1 2,2 1,472* 1,764 1,694 > 1,012 1,472 2,3 1,764 1,944* 1,012 < 1,607 1,472 1,Поскольку j = N -1 = 3, то вычисления завершаются.

Точка минимума локализована на отрезке ( ( 4 = [1,472; 1,944], x* x13) = 1,764, f f (x13) ) = 1,012.

* Ответ: 4 = [1,472;1,944], x* 1,764, f 1,012.

Задачи 1. Определить с помощью пассивного поиска минимум функции f (x) = x2 -3x + 2, заданной на отрезке = [ ] 0, 4 : а) при N=8, = 0,1; б) при N=9.

2. Определить методом дихотомии минимум функции f (x) = x2 -3x + 2, заданной на отрезке = [0, 4], при N=8, = 0,1.

3. Определить методом Фибоначчи минимум функции f (x) = x2 -3x + 2, заданной на отрезке = [0, 4], при N=4, = 0,2.

4. Определить методом золотого сечения минимум функции f (x) = x2 -3x + 2, заданной на отрезке = [0, 4], при N=4.

5. ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ МНОГОЭКСТРЕМАЛЬНЫХ ФУНКЦИЙ На практическом занятии рассматриваются методы отыскания глобального минимума функций одной переменной.

Предполагается, что заданы исходный отрезок = [a,b] и количество вычислений N значений функции f (x). Требуется определить оценки точки глобального минимума x* и величины ми* нимума f = f (x*).

Простейшим методом глобальной оптимизации является так называемое сканирование (метод перебора), которое состоит в последовательном переборе точек xi, i = 1, N. В простейшем случае точки выбираются равномерно. При этом исходный отреb - a зок разбивается на N интервалов длины h =, средними N точками которых и являются xi. Таким образом, h b - a xi = a + (i -1)h + = a + (2i -1), i =1, N. (5.1) 2 2N При записи алгоритмов и решении задач используются следующие обозначения:

* xi и fi*, i=1,2,Е, - соответственно оценки точки глобального минимума и величины глобального минимума, полученные после i вычислений;

- любое число, не принадлежащее исходному отрезку [a,b], т.е. [a,b] ;

* * - число, заведомо большее f, т.е. > f.

Алгоритм поиска глобального минимума методом сканирования заключается в следующем.

* 1. Задаются N, и ; полагается x0 =, f0* =, i = 1.

2. Вычисляются xi и f (xi ).

3. Полагается xi, если f (xi ) < fi*1, * xi = *, если f (xi ) fi*1;

i x -1 f (xi ), если f (xi ) < fi*1, fi* = fi*1, если f (xi ) fi*1.

- 4. Проверяется условие окончания вычислений i=N.

* * Если оно выполняется, то полагается x* x*, f fN и N вычисления завершаются.

Если условие не выполняется, то полагается i=i+1 и осуществляется переход к п.2.

Пример. Определить с помощью сканирования минимум функции f (x) = 2x4 - 8x3 + 8x2 - x, заданной на отрезке = [-1,4], при N=10.

Решение.

Задаем =10, =1000.

Определяем xi с помощью соотношения (5.1):

4 +xi = -1+ (2i -1) = -1,25 + 0,5i, i = 1, 10.

Результаты вычислений заносим в табл. 5.1.

Таблица 5.Номер * xi f (xi) fi*1 xi-отсчета < 1 -0,9,26 < 1000 2 -0,0,883 < 9,26 -0,30,25 0,133 < 0,883 -0,40,751,01 >0,133 0,5 1,25 0,508 > 0,133 0,6 1,75 -1,<0,133 0,72,25 -1,62 -1,< 1,Окончание табл. 5.8 2,75 5,76 > 2,-1,9 3,25 29,8 > 2,-1,10 3,75 82,4 > 2,-1,2,-1,Поскольку i=10=N, то вычисления завершаются.

* Ответ: x* 2,25, f -1,62.

Модификацией сканирования с целью уменьшения количества вычислений является поиск (сканирование) с уточнением.

В этом случае процедура равномерного сканирования выполняется n раз.

На 1-м этапе осуществляется сканирование во всей зоне поиска (на всем отрезке) (0) = [a(0) a, b(0) b]. При этом выполняется N1 вычислений, т.е. исходный отрезок разбивается на b - a N1 отрезков длины h(1) =, в средних точках xi(1) которых Nвычисляются значения функции f (x). В результате определяют*(1) ся оценки x*(1) и fN.

N1 На 2-м этапе осуществляется сканирование на отрезке (1) = [a(1), b(1)], границы которого определяются следующим образом.

( Пусть x*(1) = xk1), k { N1} 1,2,Е,, тогда N( ( a(1) = xk1)1, b(1) = xk1)1, - + ( здесь принято, что x01) a(0), x(1) b(0).

N1 +*(2) *(1) Отметим, что x0 = x*(1), f0*(2) = fN. На 2-м этапе выNполняется N2 вычислений, в результате которых определяются *(2) оценки x*(2) и fN.

N2 Затем выполняются 3-й, 4-й, Е, n-й этапы. Поскольку общее количество вычислений равно N, то N, j = 1, n, должны j удовлетворять условию n N = N.

j j=Итоговыми оценками точки глобального минимума x* и * величины глобального минимума f являются величины x*(n) и Nn *( fN n), т.е.

n * *( x* x*(n), f fN n).

N n n Пример. Определить с помощью поиска с уточнением минимум функции f (x) = 2x4 - 8x3 + 8x2 - x, заданной на отрезке = [-2, 4], при N=10, n=2, N1 =6, N2 =4.

Решение.

Первый этап Задаем =10, =1000.

Определяем xi(1) с помощью следующего соотношения:

b - a xi(1) = a + (2i -1), i = 1, N1.

2NВ итоге получаем 4 + xi(1) = -2 + (2i -1) = -2,5 + i, i = 1,6.

Результаты вычислений заносим в табл. 5.2.

Таблица 5.Номер *(( xi(1) f (xi(1)) xi-1) fi*11) отсчета < 1 56,6 < 1000 -1,2 3,63 < 56,-0,5 -1,3 0,5 0,625 < 3,-0,Окончание табл. 5.4 1,5 -0,< 0,625 0,5 2,5 0,625 > 1,-0,63,551,6 > 1,-0,1,-0,Поскольку i = 6 = N1, то вычисления завершаются. В итоге получаем ( x6(1) = x41) = 1,5, f6(1) = -0,375.

Второй этап ( ( Определяем (1) = [x31), x51) ] = [0,5; 2,5].

* Полагаем x0(2) = 1,5, f0*(2) = -0,375.

Определяем xi(2) с помощью следующего соотношения:

b(1) - a(1) xi(2) = a(1) + ( -1, i = 1, N2.

2i ) 2NВ итоге получаем 2,5 - 0,xi( 2 ) = 0,5 + (2i - 1) = 0,25 + 0,5i, i = 1,4.

Результаты вычислений заносим в табл. 5.3.

Таблица 5.Номер *(2) xi(2) f (xi(2)) fi*(2) xi-отсчета -< 1 0,75 1,01 > 1,-0,2 1,25 0,508 > 1,-0,3 1,75 -1,37 -0,< 1,42,25 -1,62 -1,< 1,2,-1,Поскольку i=4= N2, то вычисления завершаются.

* Ответ: x* 2,25, f -1,62.

Развитием и обобщением поиска с уточнением является поиск с разведкой. В этом случае исходный отрезок локализации разбивается на 2 равных по величине отрезка (зоны) D1 и D2 :

a + b a + b a, [ ] [ ] D1 = = a1,b1, D2 =, b = a2,b2.

2 На первом этапе в каждой из зон проводится разведка. Для этого из общего количества вычислений N выделяется N0 вычислений (в каждой из зон выполняется по N0 / 2вычислений). Цель разведки состоит в выборе одной из зон для дальнейших исследований.

Разведка заключается в сканировании каждой из зон. Обозначим точки, в которых производятся вычисления в зонах D1 и D2, через yi и zi, i = 1, N0 / 2, соответственно. В результате вычислений определяются оценки точек минимума y* / 2 и z* / 2, N N 0 значений минимума f (y* / 2) и f (z* / 2 ) и средние значения MN N 0 и M f (x) в зонах D1 и D2 соответственно:

NN0 2 f ( yi ) f (zi) M1 =, M2 =.

N0 2 N0 i=1 i=Если M1 < M, то для дальнейших исследований выбирается зона D1, в противном случае - зона D2.

На втором этапе осуществляется сканирование выбранного отрезка ( D1 или D2 ), при этом выполняется N-N0 вычислений.

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

* x0 = ( y* / 2 или z* / 2 ), f0* = ( f (y* ) или f (z* / 2 ) ).

N N N0 / 2 N 0 0 * В результате определяются x* и fN - N = f (x* N ), коN -N N 0 0 торые считаются оценками искомых величин, т.е.

* * x* x* N, f fN - N.

N 0 Пример. Определить с помощью поиска с разведкой минимум функции f (x) = 2x4 - 8x3 + 8x2 - x, заданной на отрезке = [-2,4], при N=10, N0 =6.

Решение.

Определяем D1 и D2 :

D1 = [-2,1], D2 = [1, 4].

Первый этап Проводим разведку в D1. Задаем =10, =1000.

Определяем yi с помощью следующего соотношения:

b1 - ayi = a1 + (2i -1), i = 1, N0 2.

NВ итоге получаем 1+ yi = -2 + (2i -1) = -2,5 + i, i = 1,3.

Результаты вычислений заносим в табл. 5.4.

Таблица 5.Номер * yi f (yi ) fi*1 yi -отсчета < 1 -1,56,6 < 1000 2 -0,5 -1,3,63 < 56,3 0,5 0,625 < 3,-0,0,625 0,Поскольку i=3= N0 / 2, то вычисления завершаются. В итоге получаем * * y3 = 0,5, f ( y3 ) = 0,625, 56,6 + 3,63 + 0,M1 = = 20,3.

Проводим разведку в D2. Задаем =10, =1000.

Определяем zi с помощью следующего соотношения:

b2 - azi = a2 + (2i -1), i = 1, N0 2.

NВ итоге получаем 4 -zi = 1+ (2i -1) = 0,5 + i, i = 1,3.

Результаты вычислений заносим в табл. 5.5.

Pages:     | 1 |   ...   | 2 | 3 | 4 | 5 | 6 |   ...   | 8 |    Книги по разным темам