Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Рассмотрим другую реализацию той же идеи.






Пусть х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.


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал