Мегаобучалка Главная | О нас | Обратная связь


Пример расчета экстремума функции методом прямого поиска Хука-Дживса



2015-12-14 2776 Обсуждений (0)
Пример расчета экстремума функции методом прямого поиска Хука-Дживса 0.00 из 5.00 0 оценок




Постановка задачи. Определить экстремум функции f(x)=(x1-2)4+( x1-2x2)2 с точностью e=0,05 для начального приближения Х(0)=[2.5; 2.5].

Расчет экстремума методом Хука-Дживса для поставленной задачи реализован средствами EXСEL. Результаты расчета представлены в таблице 2.2, а траектория поиска приведена на рисунке 2.2.

 

Таблица 2.2.

Результаты расчетов минимума функции f(x)=(x1-2)4+( x1-2x2)2 методом Хука-Дживса.

Исследующий поиск
х1 х2 f(X) S1 S2 λ1 λ2
2.500 2.500 6.3125 0.500 -1.000 0.0500 -0.100
3.000 1.500 1.0000
Поиск по образцу
х1 х2 f(X) λ1 λ2 ||X(k+1) - X(k)|| Критерий
2.500 2.500 6.3125 0.05 -0.1 1.0125 Не достигнут
2.550 2.400 5.1540
2.600 2.300 4.1296
2.650 2.200 3.2410
2.700 2.100 2.4901
2.750 2.000 1.8789
2.800 1.900 1.4096
2.850 1.800 1.0845
2.900 1.700 0.9061
2.950 1.600 0.8770
3.000 1.500 1.0000
Исследующий поиск
х1 х2 f(X) S1 S2 λ1 λ2
2.950 1.600 0.8770 -0.300 -0.275 -0.03 -0.0275
2.650 1.375 0.1885
Поиск по образцу
х1 х2 f(X) λ1 λ2 ||X(k+1) - X(k)|| Критерий
2.950 1.600 0.8770 -0.03 -0.0275 0.5049 Не достигнут
2.920 1.573 0.7670
2.890 1.545 0.6674
2.860 1.518 0.5777
2.830 1.490 0.4971
2.800 1.463 0.4253
2.770 1.435 0.3616
2.740 1.408 0.3055
2.710 1.380 0.2566
2.680 1.353 0.2144
2.650 1.325 0.1785
2.620 1.298 0.1484
2.590 1.270 0.1236
2.560 1.243 0.1039
2.530 1.215 0.0888
2.500 1.188 0.0780
2.470 1.160 0.0712
2.440 1.133 0.0680
2.410 1.105 0.0681
Исследующий поиск
х1 х2 f(X) S1 S2 λ1 λ2
2.440 1.133 0.0680 -0.201 -0.013 -0.0201 -0.0013
2.239 1.119 0.0033
Поиск по образцу
х1 х2 f(X) λ1 λ2 ||X(k+1) - X(k)|| Критерий
2.440 1.133 0.0680 -0.0201 -0.0013 0.0492 Достигнут
2.420 1.131 0.0558
2.400 1.130 0.0451
2.380 1.129 0.0357
2.360 1.127 0.0277
2.339 1.126 0.0209
2.319 1.125 0.0153
2.299 1.123 0.0108
2.279 1.122 0.0073
2.259 1.121 0.0048
2.239 1.119 0.0033
2.219 1.118 0.0026
2.199 1.117 0.0028

Таким образом, из таблицы видно, что экстремум найден на третьей итерации, точка [2.199;1.117] является минимумом заданной функции с точностью 0,05.

 

 

 
 

Рис.2.2. Графическая иллюстрация поиска экстремума функции методом прямого поиска Хука-Дживса.

Метод Розенброка

Метод Розенброка является итерационной процедурой, имеющей некоторое сходство с исследующим поиском Хука и Дживса. Отличие состоит в том, что с помощью дискретных шагов или одномерной оптимизации поиски осуществляются вдоль системы ортонормированных направлений S1(k), …, Sn(k), полученных при помощи процедуры Грама-Шмидта.

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

;

;

;

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

;

,

где ||ai|| - норма ai, являющаяся вектором перехода из X(k) в X(k+1) по направлениям.

Векторы ai рассчитываются по формуле:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

где - величина шага, равная переходу из X(k) в X(k+1) по направлениям.

Алгоритм метода Розенброка с минимизацией по направлению.

Начальный этап. Пусть e> 0 - скаляр, используемый в критерии остановки. Выбрать в качестве координатные направления, начальную точку X(1), положить Y(1) = X(1), k = j = 1 и перейти к основному этапу.

Основной этап. Шаг 1. Найти lj* - оптимальное решение задачи минимизации f(Y(j) + lj ) и положить Y(j+1) = Y(j) + lj* . Если j < n, то заменить j на j + 1 и вернуться к шагу 1. В противном случае перейти к шагу 2.

Шаг 2. Положить X(k+1) = Y(n+1). Если ||X(k+1) - X(k)|| < e, то остановиться; в противном случае положить Y(1) = X(k+1), заменить k на k + 1, положить j = 1 и перейти к шагу 3.

Шаг 3. Построить новое множество линейно независимых и взаимно ортогональных направлений в соответствии с (2.5) и (2.6). Обозначить новые направления через и вернуться к шагу 1.

Алгоритм метода Розенброка с дискретным шагом.

Начальный этап. Выбрать число e> 0 для остановки алгоритма, коэффициент растяжения a>1 и коэффициент сжатия bÎ (-1, 0). Взять в качестве координатные направления и выбрать l1, …, ln >0 начальную длину шага вдоль каждого из направлений. Выбрать начальную точку X(1), положить Y(1) = X(1), k = j = 1. При этом X(k) - координаты минимальной точки на k-той итерации, Y(j) - координаты точки на j-том шаге каждой итерации. Перейти к основному этапу.

Основной этап. Шаг 1. Если f(Y(j) + lj ) < f(Y(j)), то шаг по j-му направлению считается “успешным”. Положить Y(j+1) =Y(j) + lj и заменить lj на alj. Если же f(Y(j) + lj ) ³ f(Yj), то шаг считается “неудачным”. Положить Y(j+1) = Y(j) и заменить lj на blj. Если j < n, то заменить j на j + 1 и вернуться к шагу 1. В противном случае, т.е. при j = n перейти к шагу 2.

Шаг 2. Если f(Y(n+1)) < f(Y(1)), т. е. если хотя бы один спуск по направлению при шаге 1 оказался успешным, положить Y(1) = Y(n+1), j = 1 и повторить шаг 1. Пусть f(Y(n+1)) = f(Y(1)), т.е. каждый из n последних спусков по направлению на шаге 1 был неудачным. Если f(Y(n+1)) < f(X(k)), т.е. по крайней мере один удачный спуск встретился в течении k-й итерации на шаге 1, то перейти к шагу 3. Если f(Y(n+1)) = f(X(k)), т.е. не было не одного удачного спуска по направлению, то остановиться. При этом X(k) является приближенным оптимальным решением, если |lj| < eдля всех j. В противном случае положить Y(1) = Y(n+1), j = 1 и перейти к шагу 1.

Шаг 3. Положить X(k+1) = Y(n+1). Если ||X(k+1) - X(k)|| < e, то остановиться; X(k+1) - приближенное оптимальное решение. В противном случае вычислить l1, …, ln из соотношения построить новые направления, обозначить их через положить Y(1) = X(k+1), заменить k на k + 1 положить j = 1 и перейти к шагу 1.

Дискретные шаги выбираются вдоль n направлений поиска на шаге 1. Если движение вдоль Sj оказалось успешным, то lj заменяется на alj, если же на этом направлении постигла неудача, то lj заменяется на blj. Так как b< 0, то неудача приводит к сдвигу в обратном направлении вдоль j-го вектора на следующей реализации шага 1. Шаг 1 повторяется до тех пор, пока неудача будет иметь место при спуске по каждому направлению поиска. В этом случае строятся новые направления поиска.

Пример расчета экстремума функции методом Розенброка с дискретным шагом.

Постановка задачи. Минимизировать f(X) = (x1 - 2)4 + (х1 - 2х2)2 с точностью e=0,01. Эта функция имеет минимум в точке X* = [2 1]Т, где f(X) = 0. Выбираем начальное приближение X(1) = [2.5 2.5]Т и параметры алгоритма: l1 = l2 = 0,5; a = 3; b= 0,5; направления начального поиска совпадают с координатными осями = [1 0]Т, = [0 1]Т.

Исследующий поиск.

Вычислим f(Y(2)) в точке 2

Y(2) =

Здесь f(Y(2)) = 5,0, т.е. имеет место “удача”, поэтому шаг по х1 увеличивается l1 = 3×0,5 =1,5. Затем вычисляем f(Y(3)) в точке 3

Y(3) =

Здесь f(Y(3)) = 10,0, т. е. “неудача”, поэтому шаг по х2 уменьшается и направление изменяется на противоположное l2 = -0,5×0,5 = -0,25.

При наличии одной “удачи” поиск продолжаем. Считаем Y(1) = Y(3).

Вычисляем f(Y(2)) в точке 4

Y(2) =

Здесь f(Y(2))=39,31, что говорит о “неудаче”, поэтому величина шага уменьшается l1 = -1,5×0,5 = -0,75.

Рассчитываем f(Y(3)) в точке 5

Y(3) =

Здесь f(Y(5)) = 3,25. Следовательно, шаг является успешным, l2 = 3×0,25 = 0,75

Поиск продолжается аналогичным образом до 9 точки. На этом первый исследующий поиск заканчивается, т. к. два последних расчета 8 и 9 неудачны. В качестве результата принимается координата [3 1,5] 7 точки, которая обозначается за X(2) = Y(1).

Построение новых направлений поиска.Новое направление совпадает с вектором перехода из X(1) в X(2), а достраивается ортогонально к . Рассчитаем единичные направления по формуле (2.5), а векторы а1(1) и а2(1) по формуле (2.6).

Определяем составляющие шага где перехода из X(1) = [2.5 2.5]Т в X(2) = [3 1,5]Т. =3-2,5=0,5, =1,5-2,5=-1

Находим компоненты векторов

а1(1) = 0,5× ; а2(1) = -1× ;

Рассчитываем направления и

=[0,45-0,89]T

b2(1)= ;

На этом завершена первая итерация метода. Точка с 10 по 13 соответствуют результатам исследующего поиска на второй итерации. После 16 итераций получается следующий результат: X(*) = [1,99959 0,99979]; f(X(*)) = 0,285×10‑13, что указывает на высокую эффективность метода. Результаты расчетов двух итераций метода с использованием табличного процессора EXСEL представлены в таблице 2.3. Траектория поиска приведена на рис.2.3.

Таблица 2.3

Расчет минимума функции f(X) = (x1 - 2)4 + (х1 - 2х2)2 методом Розенброка.

1. Исследующий поиск
x1 x2 s1 s2 f(x)
2.50 2.50     6.313
3.00 2.50 0.50 0.00 5.000
3.00 3.00 0.00 0.50 10.000
4.50 2.50 1.50 0.00 39.313
3.00 2.25 0.00 -0.25 3.250
2.25 2.25 -0.75 0.00 5.066
3.00 1.50 0.00 -0.75 1.000
3.38 1.50 0.38 0.00 3.715
3.00 -1.25 0.00 -2.25 31.250
1. Поворот осей
  x1 x2 ||R|| f(x)  
  3.00 1.50   1.000  
λ 0.50 -1.00      
a1 0.50 -1.00 1.118    
a2 0.00 -1.00 1.000    
b2 -0.4 -0.21 0.452    
S1 0.45 -0.89      
S2 -0.8854 -0.465      
2. Исследующий поиск в новой системе координат
x1 x2 s1 s2 f(x)
3.00 1.50     1.000
3.22 1.05 0.22 -0.45 3.492
2.56 1.27 -0.44 -0.23 0.097
2.45 1.49 -0.11 0.22 0.328
1.23 0.57 -1.33 -0.70 0.361

На второй итерации метода реализован исследующий поиск с помощью дискретных шагов в новой системе координат. Из таблицы видно, что на шаге 3 и 4 происходит «неудача». Поэтому оптимальной точкой исследующего поиска будет точка 2 [2.56; 1.27]. В этой точке опять производится поворот координатных осей, и процедура расчета повторяется.



2015-12-14 2776 Обсуждений (0)
Пример расчета экстремума функции методом прямого поиска Хука-Дживса 0.00 из 5.00 0 оценок









Обсуждение в статье: Пример расчета экстремума функции методом прямого поиска Хука-Дживса

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

Популярное:
Как построить свою речь (словесное оформление): При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою...
Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние...



©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (2776)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.006 сек.)