Методы поисковой оптимизации. Метод Гаусса-Зайделя. Метод крутого восхождения Бокса-Уилсона

Страницы работы

Содержание работы

Тема         7:             Методы поисковой оптимизации

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

Оптимизацией называется процесс нахождения наилучших значений целевой функции y (критерия оптимизации).

Если критерий оптимизации у есть функция входных управляемых параметров x1, x2,...,xn :

у=f(x1, x2,...,xn)

где n- число факторов, то задача оптимизации сводится к отысканию таких значений факторов

,

при которых целевая функция у достигает экстремума (минимума или максимума).

Решение, т.е. отыскание вектора  может быть аналитическим (1) и экспериментальным (2).

(1). В случае, когда целевая функция у задана используют известное свойство функций, имеющих экстремум, а именно, в точке экстремума первая производная этой функции обращается в ноль. Таким образом, для n-факторного пространства, чтобы найти вектор , находят n частных производных по каждому из n-факторов и решают систему уравнений:

(2). В случае, когда целевая функция у неизвестна  используют экспериментальные методы поисковой оптимизации, основными из которых являются:

а) метод Гаусса-Зайделя;

б) метод градиента;

в) метод крутого восхождения Бокса-Уилсона;

г) симплексный метод.

Каждый из методов включает в себя 2 процедуры:

(а) определение направления движения к экстремуму с помощью пробных опытов;

(б) «рабочее» движение в сторону экстремума.

1.  Метод Гаусса-Зайделя.

Метод Гаусса-Зайделя предусматривает поочерёдное нахождение частных экстремумов целевой функции по каждому фактору xi ( i=1,2,…,n ). При этом на каждом i-м этапе стабилизируют n-1 факторов и варьируют только один i-й фактор.

Рис. Метод Гаусса-Зайделя

Графическая интерпретация метода дана на рисунке на примере двух факторов x1 и x2 . Функция отклика у изображена топографическим способом с помощью замкнутых линий постоянного уровня у (у=const).

До начала исследований форма функции отклика, естественно, неизвестна, т. е. исследователь на момент планирования не видит этих линий. (Они видны на рисунке, чтобы понять как работает метод). Путь движения обозначен точками М. Задачу поиска максимума решают в несколько этапов:

Этап I: Поиск частного экстремума при движении по х1 со стабилизацией всех остальных факторов.

1.1  Выбор начальной точки М0 ( х10; х20;…; хn0 )

      (чаще в центре области исследования)

1.2  Выбор интервала варьирования х1 по фактору х1. Размер х1 определяет скорость движения к экстремуму.

1.3  Определение координаты пробных точек М1 10+х1; х20;…; хn0) и М210-х1; х20;…;хn0).

1.4  Определение у(М1) и у(М2) в результате проведения пробных опытов.

1.5  Определение направления движения в сторону большего у(Мi): например, если у(М2)> у(М1), то рабочее движение совершают на один шаг по направлению вектора  в точку М3.

1.6  Продолжение движения аналогичным образом продолжается до реализации условия у(Мк)< у(Мк-1), которое указывает на достижение частного экстремума в точке Мк-1. На рисунке это М5.

Этап II: Поиск частного экстремума при движении по х2 со стабилизацией всех остальных факторов.

Порядок проведения поиска тот же, что и для этапа I. За новую базовую точку принимают Мк-110±х1*(к-2); х20;…; хn0), а х2 варьируют на х2. После достижения частного экстремума по фактору х2 , точку нового экстремума принимают за новую базовую точку. На рисунке это М10.

Первый цикл продвижения к экстремуму заканчивается n-м этапом, на котором стабилизируют все факторы, кроме хn. Если экстремум не достигнут, то выполняют следующий цикл поиска по аналогичной схеме.

Экстремум считается достигнутым, если при движении в любую сторону по всем  n-факторным осям значения отклика y оказываются меньшими.

Достоинства метода Гаусса-Зайделя: простота и наглядность.

Недостатки: (1) слишком долгий путь к главному экстремуму, особенно при большом числе факторов n; (2) метод не даёт информации о взаимодействиях факторов.

2. Метод градиента

Сущность метода заключается в том, что направление движения к экстремуму задаёт направление градиента. Вектор-градиент в n–факторном пространстве определяется соотношением

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

- единичные направляющие векторы, расположенные вдоль факторных осей.

x1

 

x10

 

Рис. Метод градиента

Последовательность метода

1.1       Выбор начальной точки L0(X10,X20,..,Xn0)

(Методика выбора одинакова для всех методов).

1.2       Выбор интервала варьирования  ΔXi по каждому фактору

(Методика выбора одинакова для всех методов).

1.3    Определение координат пробных точек. Пробные точки выбираются вдоль направлений всех факторных осей. В случае двух-факторного пространства это четыре точки:

L1(X10- ΔX1; X20);                 L2(X10+ΔX1; X20);

L3(X10; X20- ΔX2);                 L4(X10; X20+ ΔX2);

1.4 Определение целевой функции y в пробных точках, в результате проведения опытов.

1.5 Определение координат рабочей точки L(X11,X21,..,Xn1) на направлении градиента. Для рассматриваемого примера координаты  L5(x11,x21) рассчитываются по формуле:

                                                           Xi1 = Xi0 + rгрai0,

где Хi0- координата базовой точки L0 по i-му фактору;

ρгр- параметр рабочего шага; назначается исследователем;

аi0- оценка вектор-градиента в точке L0 для каждого i-го фактора:

В частности для факторов х1 и х2 вычисление а10 и а20 производится по формулам:

1.6. Повторение цикла, состоящего из пп. 1.3 - 1.5 (проведение новых пробных опытов /оценивание нового направления градиента / рабочий шаг в точку с координатами Xi, k+1 = Xik + rгрaik).

1.7 Рабочее движение производят до тех пор пока составляющие градиента не станут пренебрежимо малыми, т. е. все аi,к+10. В рассматриваемом примере за экстремум принимают точку L15 (рис.)

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

Похожие материалы

Информация о работе