Студопедия

КАТЕГОРИИ:

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


Градиентные методы




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

Вектор-градиент в n-факторном пространстве определяется соотношением

grad y = (∂y/∂x1) + (∂y/∂x2) + … + (∂y/∂xk) , (10.4)

где (i=1, 2, …, n) – единичные направляющие векторы (орты), расположенные вдоль факторных осей;

∂y/∂xi – частная производная целевой функции по i-му фактору.

Пробные опыты (по два в точках, расположенных на прямых, параллельных каждой факторной оси и проходящих через базовую точку) проводят с целью получить приближенные оценки частных производных. Рассмотрим две основные разновидности градиентных методов.

Обычный метод градиента осуществляется по следующей процедуре:

1 – Выбирают начальную (базовую) точку 0=(x10; x20; …; xno). На рисунке 10.3 это точка L0.

2 – Выбирают интервал варьирования Δxi по каждому из факторов xi (i=1, 2, …, k), пользуясь уже определенными ранее правилами.

3 – Определяют координаты пробных точек (рисунок 10.3).

 

x2

 

 

L10

L9

L6 L5 L7

L8

Δx2 L4

x20 L1 L0 L2

Δx2 L3

x1

Δx1 x10Δ x1

 

Рисунок 4.3 – Поиск экстремума функции отклика методом градиента

 

Вдоль направления, параллельного факторной оси x1, ими являются точки L1, L2 с координатами

 

(L1) = (x10 – Δx1; x20; …; xko),

(L2) = (x10 + Δx1; x20; …; xko).

то есть варьируют один фактор x1 при стабилизации остальных факторов на базовом уровне. Аналогично вычисляют координаты пробных точек вдоль направлений, параллельных остальным факторным осям x2; x3; …; xk. Вдоль направления, параллельного факторной оси x2, такие точки – L3, L4 с координатами

(L3) = (x10; x20 – Δx2; …; xko),

(L4) = (x10; x20 + Δx2; …; xko).

В пробных точках ставят опыты и получают значения целевой функции Y.

4 – По результатам пробных опытов вычисляют оценки составляющих вектор-градиента в точке L0 для каждого i-го фактора:

(10.5)

В частности, для фактора x1 по результатам опытов в точках L1 и L2 вычисление выполняют по формуле

(10.6)

Как известно, частные производные являются коэффициентами ai (i=1, 2, …, n; i≠0) уравнения плоскости, касательной к поверхности отклика в точке L0:

y = b0 + b1x1 + b2x2 + … + bkxk. (10.7)

Оценки коэффициентов получают по формуле (10.5).

5 – Находят координаты рабочей точки на направлении градиента. Для этого выбирают параметр рабочего шага ρгр и вычисляют координаты первой рабочей точки по всем факторным осям xi (i =1, 2, …, k):

xi1 = xi0 + ρгр . (10.8)

На рисунке 10.3 первой рабочей точкой является точка L5. Чтобы из основной точки L0 попасть в точку L5, от L0 откладывают в масштабе отрезки, равные ρгр и ρгр , причем если <0, то по соответствующему фактору отрезок откладывают в отрицательном направлении от точки L0, то есть для фактора x1 – влево от точки L0, а для фактора x2 – вниз от точки L0. Если >0, то отрезки ρгр откладывают в положительном направлении от основной точки.

6 – Первую рабочую точку принимают за новую базовую точку и вокруг нее организуют новые пробные опыты для оценивания нового направления градиента, после чего совершают новый рабочий шаг (на рисунке 10.3 – в точку L10). В общем случае в каждой m-й рабочей точке по результатам пробных опытов вокруг нее получают оценки составляющих градиента и совершают (m+1)-й рабочий шаг (m = 0, 1, 2, …) в точку с координатами

xi, m+1 = xi m + ρгр . (10.9)

7 – Рабочее движение производят до тех пор, пока на очередном шаге все составляющие градиента не станут пренебрежимо малыми, то есть ≈0 (i=1, 2, …, n). Для этого достаточно, чтобы выполнялось неравенство

ρгр < 1 (10.10)

Если по результатам пробных опытов в (m+1)-й рабочей точке выполняется условие (10.10), то движение к экстремуму прекращают и эту рабочую точку принимают за точку экстремума.

Достоинства метода градиента:

– достаточная простота стратегии;

– повышенная по сравнению с методом Гаусса-Зайделя скорость движения к экстремуму (эффективность).

Недостатки:

– большая чуткость к помехам в отношении выбора направления рабочего движения;

– в случаях, когда поверхность отклика имеет сложную форму, метод градиента может не привести к истинному экстремуму;

– если поверхность отклика достаточно пологая, то в условиях помех метод мало эффективен в смысле точности выхода к экстремуму;

 

Метод Кифера-Вольфовицаявляется разновидностью градиентного метода и отличается от описанного выше обычного метода градиента тем, что если в первом из них размеры интервалов варьирования Δxi при постановке пробных экспериментов и параметр ρгр рабочего шага остаются неизменными на любом рабочем шаге, то в рассматриваемом методе Δxik и ρгрm выбирают в зависимости от номера k рабочего шага:

 

Δxim = Δxi0/(γm),

ρгрm = ρгр0/m, (10.11)

 

где Δxi0 – начальный интервал варьирования в основной точке L0;

ρгр0 – начальное значение параметра рабочего шага;

m – номер рабочего шага (m = 1, 2, …);

γ – постоянная степень, обычно выбираемая в пределах 0 < γ < 0,5. Чаще всего полагают γ=0,25.

Если в методе градиента фактический размер m-го рабочего шага уменьшается только из-за уменьшения градиента, то есть крутизны наклона поверхности отклика, при приближении к области экстремума, то в методе Кифера-Вольфовица фактический размер рабочего шага уменьшается в прямой зависимости от номера этого шага.

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

Недостатком является его низкая эффективность в условиях пологих поверхностей отклика. При очень пологих поверхностях отклика этот метод вообще не приводит к цели: рабочие шаги становятся сравнимыми с погрешностями измерения до достижения экстремума. Остальные достоинства и недостатки, а также вся процедура работы такие же, как и в методе градиента.

 


Поделиться:

Дата добавления: 2015-08-05; просмотров: 56; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты