Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Рассмотрим другую реализацию той же идеи.
|
|
Пусть х0 и х1 – две произвольные близкие точки. Как и в предыдущем случае, из каждой точки осуществим градиентные спуски с постоянным шагом a. Получим точки u0 и u1, лежащие в окрестности «дна оврага». Соединяя их прямой, делаем «большой шаг» l в полученном направлении. В результате получим точку х2. Из этой точки осуществим градиентный спуск и получим точку u2. А вот далее, для того чтобы осуществить «овражный шаг», берем предпоследнюю точку u1. Соединяя прямой точки u2 и u1, делаем шаг l в полученном направлении и определяем х3. Дальше аналогичным образом вычисляются х4, х5, ….
Схема овражного метода 2
Шаг 1. Задаются начальное приближение х0, точность решения e1 и e3, шаг a для градиентного спуска, начальное значение l для овражного шага.
Из точки х0 осуществляется градиентный спуск с постоянным шагом a на «дно оврага». В результате получается точка u’0.
В окрестности х0 берется точка х1, из которой тоже осуществляется градиентный спуск на «дно оврага». В результате получается точка u’1. Полагается к=1. Если f(u’0)< f(u’1), то полагаем u0=u’1, u1=u’0. Если f(u’0)> f(u’1), то u0=u’0, u1=u’1.
Шаг 2. Новая точка хк+1 определяется следующим образом. По формуле:
вычисляется точка x'k+1. Из нее осуществляется градиентный спуск и мы получаем точку u`k+1. Если f(u`k+1)< f(uk), то полагаем xk+1= x`k+1 и uk+1= u`k+1.
Иначе уменьшаем овражный шаг l (например в 2 раза l=l/2)и повторяем шаг 2.
Шаг 3.
Если ||uk+1-uk||£ e1 и | f `(uk+1) ||£ e3, то полагаем:
и поиск минимума на этом заканчивается, иначе к=к+1 и переходим к шагу 2.
Метод конфигураций (метод Хука и Дживса)
Алгоритм включает в себя два основных этапа поиска.
а) В начале обследуется окрестность выбранной точки (базисной точки), в результате находится приемлемое направление спуска; б) Затем в этом направлении находится точка с наименьшим значением целевой функции. Таким образом находится новая базисная точка.
 |
Эта процедура продолжается пока в окрестностях базисных точек удается находить приемлемые направления спуска.
Схема алгоритма
Шаг 1. Задаются начальное приближение (первая базисная точка)
,
начальный шаг h для поиска направления спуска, точность решения d(предельное значение для шага h). Присваивается к=0.
Шаг 2. (Первый этап).
Определяется направление минимизации целевой функции
f(x)=f(x(1), x(2), …, x(n)) в базисной точке
. Для этого последовательно дают приращение переменным x(j) в точке хк. Присвоим z=xk. Циклически даем приращение переменным x(j) и формируем z(j)=xk(j)+h, если f(z)< f(xk), если же нет, то z(j)=xk(j)-h, если f(z)< f(xk), иначе z(j)=xk(j). Так для всех j(j=1, 2, …, n).
Шаг 3. Если z=xk, то есть не определилось подходящее направление, то обследование окрестности базисной точки хк повторяется, но с меньшим шагом h (например, h=h/2).
Если h> d, то перейти к шагу 2, то есть повторить обследование точки хк.
Если h£ d, то поиск заканчивается, то есть достигнуто предельное значение для шага h и найти приемлемое направление спуска не удается. В этом случае полагается
Шаг 4. (Второй этап).
Если z¹ xk, то требуется найти новую базисную точку в направлении
вектора z-xk: xk+1=xk + l(z-xk), где l - коэффициент «ускорения поиска».
Определяется такое значение l=lк, при котором достигается наименьшее значение целевой функции в выбранном направлении, то есть функции
f(xk +l(z-xk) = j(l).
В зависимости от способа выбора lк возможны варианты метода:
а) lк=l=const постоянная для всех итераций; б) задается начальное l0=l, а далее lк=lк-1, если f(xk+1)< f(xk), иначе дробим lк, пока не выполнится это условие; в) lк определяется решением задачи одномерной минимизации функции j(l).
Таким образом определяется новая базисная точка xk+1=xk + l(z-xk). Полагаем к=к+1 и поиск оптимального решения повторяется с шага 2.