Пример расчета экстремума функции методом прямого поиска Хука-Дживса
Постановка задачи. Определить экстремум функции 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 методом Хука-Дживса.
Таким образом, из таблицы видно, что экстремум найден на третьей итерации, точка [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 методом Розенброка.
На второй итерации метода реализован исследующий поиск с помощью дискретных шагов в новой системе координат. Из таблицы видно, что на шаге 3 и 4 происходит «неудача». Поэтому оптимальной точкой исследующего поиска будет точка 2 [2.56; 1.27]. В этой точке опять производится поворот координатных осей, и процедура расчета повторяется.
Популярное: Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (2776)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |