Характерной чертой этого метода является случайный выбор направления движения на каждом шаге, то есть одновременное изменение значений сразу всех факторов. Так, если изображающая точка после i-го шага занимает xm положение в факторном пространстве, то следующий рабочий шаг будет совершен лишь после выполнения пробного эксперимента в точке
xm+1 = xm + z,
где z – случайный вектор определенной длины (рисунок 10.2).
x 2
k+2
k+1
k
x 1
Рисунок 10.2 – Поиск экстремума функции отклика методом случайного поиска
Значения у(xm) и у(xm+z) сравниваются, и производится (i+1)-й рабочий шаг вдоль вектора по направлению к экстремуму. Как правило, длина рабочего шага превышает длину пробного.
Критерием выхода в область экстремума целевой функции (функции отклика) является возрастание числа неудачных шагов, то есть многократное повторение положения, когда у(xm+z) < у(xm).
Достоинство – метод случайного поиска очень прост, но он применим лишь для очень простых ситуаций.
|
|
Основные недостатки метода:
– большая трудоемкость и длительность поиска экстремума;
– возможность ошибки при попадании в область локального экстремума.
Градиентные методы
Градиентные методы имеют несколько разновидностей, различающихся правилами выбора ступеней варьирования и рабочих шагов на каждом этапе движения к экстремуму. Сущность стратегии всех этих разновидностей состоит в том, что на каждом этапе вокруг очередной базовой точки организуют пробные эксперименты, по результатам которых оценивают новое направление градиента, после чего в этом направлении совершают рабочий шаг.
Вектор-градиент в 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).
x 2
L10
L9
L6 L5 L7
L8
Δx2 L4
x20 L1 L0 L2
Δx2 L3
x 1
Δ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-го рабочего шага уменьшается только из-за уменьшения градиента, то есть крутизны наклона поверхности отклика, при приближении к области экстремума, то в методе Кифера-Вольфовица фактический размер рабочего шага уменьшается в прямой зависимости от номера этого шага.
Достоинством метода Кифера-Вольфовица по сравнению с немодифицированным методом является его повышенная точность нахождения экстремальной точки, если поверхность отклика достаточно крутая, а экстремум находится от базовой точки не слишком далеко.
Недостатком является его низкая эффективность в условиях пологих поверхностей отклика. При очень пологих поверхностях отклика этот метод вообще не приводит к цели: рабочие шаги становятся сравнимыми с погрешностями измерения до достижения экстремума. Остальные достоинства и недостатки, а также вся процедура работы такие же, как и в методе градиента.