Как мы уже отметили, задача оптимизации – это задача отыскания таких значений факторов х 1 = х 1* , х 2 = х 2* , …, х k = х k * , при которых функция отклика (у ) достигает экстремального значения у = ext (оптимума).

Известны различные методы решения задачи оптимизации. Одним из наиболее широко применяемых является метод градиента, называемый также методом Бокса-Уилсона и методом крутого восхождения.

Рассмотрим сущность метода градиента на примере двухфакторной функции отклика y = f(x 1 , х 2 ). На рис. 4.3 в фак­торном пространстве изо­бражены кривые равных значений функции отклика (кривые уровня). Точке с координатами х 1 *, х 2 * соответствует экстремаль­ное значение функции от­клика у ext .

Если мы выбе­рем какую-либо точку фак­торного пространства в ка­честве исходной (х 1 0 , х 2 0), то наикратчайший путь к вершине функции откли­ка из этой точки – это путь, по кривой, касательная к которой в каждой точке совпадает с нормалью к кривой уровня, т.е. это путь в направлении гради­ента функции отклика.

Градиент непрерывной однозначной функции y = f (x 1 , х 2) – это вектор, определяемый по направлению градиентом с координатами:

где i, j – единичные векторы в направлении осей координат х 1 и х 2 . Частные производные и характеризуют направление вектора.

Поскольку нам неизвестен вид зависимости y = f (x 1 , х 2), мы не можем найти частные производные , и опреде­лить истинное направление градиента.

Согласно методу градиента в какой-то части факторного пространства выбирается исходная точка (исходные уровни) х 1 0 , х 2 0 . Относительно этих исходных уровней строится сим­метричный двухуровневый план эксперимента. Причем интер­вал варьирования выбирается настолько малым, чтобы ли­нейная модель оказалась адекватной. Известно, что любая кривая на достаточно малом участке может быть аппрокси­мирована линейной моделью.

После построения симметричного двухуровневого плана решается интерполяционная задача, т.е. строится линейная модель:

и проверяется ее адекватность.

Если для выбранного интервала варьирования линейная мо­дель оказалась адекватной, то может быть определено на­правление градиента:

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

где m – положительное число, определяющее величину шага в на­правлении градиента.

Поскольку х 1 0 = 0 и х 2 0 = 0, то .

Определив направление градиента () и выбрав ве­личину шага m , осуществляем опыт на исходном уровне х 1 0 , х 2 0 .

Затем делаем шаг в направлении градиента, т.е. осу­ществляем опыт в точке с координатами . Если значе­ние функции отклика возросло по сравнению с ее значением в исходном уровне, делаем еще шаг в направлении градиен­та, т.е. осуществляем опыт в точке с координатами:

Движение по градиенту продолжаем до тех пор, пока функция отклика не начнет уменьшаться. На рис. 4.3 движение по градиенту соответствует прямой, вы­ходящей из точки (х 1 0 , х 2 0). Она постепенно отклоняется от истинного направления градиента, показанного штриховой линией, вследствие нелинейности функции отклика.

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

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

фи­циент , значит, область экстремума функции откли­ка (область оптимума) еще не достигнута. Определяется новое направление градиента и начинается движение к обла­сти оптимума.

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

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

1) исходные уровни факторов (х j 0) следует выбирать воз­можно ближе к точке оптимума, если есть какая-то априор­ная информация о ее положении;

2) интервалы варьирования (Δх j ) надо выбирать такими, чтобы линейная модель наверняка оказалась адекватной. Границей снизу Δх j при этом является минимальное значе­ние интервала варьирования, при котором функция отклика остается значимой;

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

.

Следовательно, . При меньшем значении т разность функции отклика в исходном уровне и в точке с координа­тами может оказаться незначимой. При большем значении шага возникает опасность проскочить оптимум функ­ции отклика.

Градиентные методы оптимизации

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

В общем случае значение критерия оптимизации R может рассматри­ваться как функция R (х ь хь ..., х п), определенная в л-мерном пространстве. Поскольку не существует наглядного графического изображения я-мерного пространства, воспользуемся случаем двумерного пространства.

Если R (л ь х 2) непрерывна в области D, то вокруг оптимальной точки M°(xi°, х г °) можно провести в данной плоскости замкнутую линию, вдоль ко­торой значение R = const. Таких линий, называемых линиями равных уровней, вокруг оптимальной точки можно провести множество (в зависимости от шага

Среди методов, применяемых для решения задач нелинейного програм­мирования, значительное место занимают методы поиска решений, основан­ные на анализе производной по направлению оптимизируемой функции. Если в каждой точке пространства скалярная функция нескольких переменных принимает вполне определенные значения, то в данном случае имеем дело со скалярным полем (поле температур, поле давлений, поле плотностей и т.д.). Подобным образом определяется векторное поле (поле сил, скоростей и т.д.). Изотермы, изобары, изохроны и т.д. - все это линии (поверхности) равных уровней, равных значений функции (температуры, давления, объема и т.д.). Поскольку от точки к точке пространства значение функции меняется, то ста­новится необходимым определение скорости изменения функции в простран­стве, то есть производной по направлению.

Понятие градиента широко используется в инженерных расчетах при на­хождении экстремумов нелинейных функций. Градиентные методы относятся к численным методам поискового типа. Они универсальны и особенно эффек­тивны в случаях поиска экстремумов нелинейных функций с ограничениями, а также когда аналитическая функция неизвестна совсем. Сущность этих мето­дов заключается в определении значений переменных, обеспечивающих экс­тремум функции цели, путем движения по градиенту (при поиске max) или в противоположном направлении (min). Различные градиентные методы отли­чаются один от другого способом определения движения к оптимуму. Суть заключается в том, что если линии равных уровней R{xu x i) характеризуют графически зависимость R(x\jc?), то поиск оптимальной точки можно вести по-разному. Например, изобразить сетку на плоскости х\, хг с указанием зна­чений R в узлах сетки (рис. 2.13).

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

Численные методы

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

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

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

Выбор узловых точек, проведение экспериментов при определен­ных значениях (уровнях) независимых переменных (при непра­вильном выборе шага изменения фактора либо «пропустим» ха­рактерную особенность изучаемого процесса, либо удлиним про­цедуру и повысим трудоемкость поиска закономерности);

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

Выбор и использование критериев согласия, на основе которых на­ходятся параметры приближающих функций;

Выполнение требований заданной точности к выбору приближаю­щей функции.

В задачах приближения функций многочленами используются три класса

Линейная комбинация степенных функций (ряд Тейлора, много­члены Лагранжа, Ньютона и др.);

Комбинация функций соз пх, ш их (ряды Фурье);

Многочлен, образуемый функциями ехр (-а, г).

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

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

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

Рис. 4.11.

Рис. 4.12.

(двумерный случай)

Вначале выбирают начальную точку Если в одномерном случае (см. подпараграф 4.2.6) из нее можно было

сдвинуться только влево или вправо (см. рис. 4.9), то в многомерном случае число возможных направлений перемещения бесконечно велико. На рис. 4.11, иллюстрирующем случай двух переменных, стрелками, выходящими из начальной точки А, показаны различные возможные направления. При этом движение по некоторым из них дает увеличение значения целевой функции по отношению к точке А (например, направления 1-3), а по другим направлениям приводит к его уменьшению (направления 5-8). Учитывая, что положение точки оптимума неизвестно, считается наилучшим то направление, в котором целевая функция возрастает быстрее всего. Это направление называется градиентом функции. Отметим, что в каждой точке координатной плоскости направление градиента перпендикулярно касательной к линии уровня, проведенной через ту же точку.

В математическом анализе доказано, что составляющие вектора градиента функции у =/(*, х 2 , ..., х п) являются ее частными производными по аргументам, т.е.

&ад/(х 1 ,х 2 ,.= {ду/дху,ду/дх 2 , ...,ду/дх п }. (4.20)

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

У" с координатами:

1§гас1/(х (0)),

или в векторной форме

где X - постоянный или переменный параметр, определяющий длину рабочего шага, ?і>0. На второй итерации снова вычисляют

вектор градиента уже для новой точки.У, после чего по анало-

гичной формуле переходят в точку х^ > и т.д. (рис. 4.12). Для произвольной к- й итерации имеем

Если отыскивается не максимум, а минимум целевой функции, то на каждой итерации делается шаг в направлении, противоположном направлению градиента. Оно называется направлением антиградиента. Вместо формулы (4.22) в этом случае будет

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

длина рабочего шага - расстояние между соседними точками х^

их 1 " - окажется пропорциональном модулю вектора градиента. Можно, наоборот, на каждой итерации выбирать X таким, чтобы длина рабочего шага оставалась постоянной.

Пример. Требуется найти максимум функции

у = 110-2(лг, -4) 2 -3(* 2 -5) 2 .

Разумеется, воспользовавшись необходимым условием экстремума, сразу получим искомое решение: х ] - 4; х 2 = 5. Однако на этом простом примере удобно продемонстрировать алгоритм градиентного метода. Вычислим градиент целевой функции:

grad у = {ду/дх-,ду/дх 2 } = {4(4 - *,); 6(5 - х 2)} и выбираем начальную точку

Л*» = {х}°> = 0; 4°> = О}.

Значение целевой функции для этой точки, как легко подсчитать, равно у[х^ j = 3. Положим, X = const = 0,1. Величина градиента в точке

Зс (0) равна grad y|x^j = {16; 30}. Тогда на первой итерации получим согласно формулам (4.21) координаты точки

х 1) = 0 + 0,1 16 = 1,6; х^ = 0 + 0,1 30 = 3.

у(х (1)) = 110 - 2(1,6 - 4) 2 - 3(3 - 5) 2 = 86,48.

Как видно, оно существенно больше предыдущего значения. На второй итерации имеем по формулам (4.22):

• 1,6 + 0,1 4(4 - 1,6) = 2,56;

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

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

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

Этот способ наиболее прост, нагляден, но движение к оптимуму длительно и метод редко приводит в оптимальную точку. В настоящее время он иногда применяется при машинном эксперименте.

Эти методы обеспечивают движение к оптимуму по прямой перпендикулярной к линиям равного отклика, т. е. в направлении градиента функции отклика.

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

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

Метод градиента (обычный) осуществляется по следующей схеме:

а) выбирают базовую точку;

б) выбирают шаги движения по каждому фактору;

в) определяют координаты пробных точек;

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

д) по результатам опытов вычисляют оценки составляющих вектор-градиента в т. М для каждого i-го фактора:

где H i -шаг движения по X i .

X i – координаты предыдущей рабочей точки.

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

Достоинства метода: простота, более высокая скорость движения к оптимуму.

Недостатки: большая чувствительность к помехам. Если кривая имеет сложную форму, метод может не привести к оптимуму. Если кривая отклика пологая - метод малоэффективен. Метод не даёт информации о взаимодействии факторов.

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

б) Принятие решений после крутого восхождения.

в) Симплексный метод оптимизации.

г) Достоинства и недостатки методов.

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

Этот метод является синтезом лучших черт градиентных методов, метода Гаусса-Зейделя и методов ПФЭ и ДФЭ – как средства получения математической модели процесса. Решение задачи оптимизации данным методом выполняется так, чтобы шаговое движение осуществлялось в направлении наискорейшего возрастания (убывания) параметра оптимизации. Корректировка направления движения (в отличие от градиентных методов) производится не после каждого шага, а по достижению частного экстремума целевой функции. Далее в точках частного экстремума ставится новый факторный эксперимент, составляется новая математическая модель и вновь повторяется крутое восхождение до достижения глобального оптимума. Движение по градиенту начинают из нулевой точки(центра плана).

Метод крутого восхождения предполагает движение к оптимуму по градиенту.

Где i,j,k-единичные векторы в направлении соответствующих координатных осей.

Порядок расчёта .

Исходными данными является математическая модель процесса, полученная любым способом (ПФЭ, ДФЭ и т.д.).

Расчеты проводят в следующем порядке:

а) уравнение регрессии лучше перевести в натуральный вид по формулам кодирования переменных:

где x i -кодированное значение переменной x i ;

X i - натуральное значение переменной x i ;

X i Ц -центральный уровень фактора в натуральном виде;

l i -интервал варьирования фактора x i в натуральном виде.

б) вычисляют шаги движения к оптимуму по каждому фактору.

Для этого вычисляют произведения коэффициентов уравнения регрессии в натуральном виде на соответствующие интервалы варьирования

B i *.l I ,

Затем выбирают из полученных произведений максимальное по модулю,а соответствующий этому произведению фактор принимают за базовый фактор(B a l a). Для базового фактора следует установить шаг движения, который рекомендуется задавать меньшим или равным интервалу варьирования базового фактоpa

Знак шага движения l a ’ должен совпадать со знаком коэффициента уравнения регрессии, соответствующего базовому фактору (B a). Величина шагов для других факторов вычисляется пропорционально базовому по формуле:

Знаки шагов движения также должны совпадать со знаками соответствующих коэффициентов уравнения регрессии.

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

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

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

Если Y® max X i =X i ц +gl i ` ’

если Y® min .X i =X i ц -gl i ` . (5.36)

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

моделирование динамический градиентный полиномиальный

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

i, j, k - единичные векторы в направлении координатных осей факторного пространства, либо по результатам n пробных движений в направлении координатных осей.

Если математическая модель статистического процесса имеет вид линейного полинома, коэффициенты регрессии b i которого являются частными производными разложения функции y = f(X) в ряд Тейлора по степеням x i , то оптимум ищут в направлении градиента с некоторым шагом h i:

пкфв н(Ч)= и 1 р 1 +и 2 р 2 +…+и т р т

Направление корректируют после каждого шага.

Метод градиента вместе с его многочисленными модификациями является распространенным и эффективным методом поиска оптимума исследуемых объектов. Рассмотрим одну из модификаций метода градиента - метод крутого восхождения.

Метод крутого восхождения, или иначе метод Бокса-Уилсона, объединяет в себе достоинства трех методов - метода Гаусса-Зейделя, метода градиентов и метода полного (или дробного) факторного экспериментов, как средства получения линейной математической модели. Задача метода крутого восхождения заключается в том, чтобы шаговое движение осуществлять в направлении наискорейшего возрастания (или убывания) выходной переменной, то есть по grad y(X). В отличии от метода градиентов, направление корректируется не после каждого следующего шага, а при достижении в некоторой точке на данном направлении частного экстремума целевой функции, как это делается в методе Гаусса-Зейделя. В точке частного экстремума ставится новый факторный эксперимент, определяется математическая модель и вновь осуществляется крутое восхождение. В процессе движения к оптимуму указанным методом регулярно проводиться статистический анализ промежуточных результатов поиска. Поиск прекращается, когда квадратичные эффекты в уравнении регрессии становятся значимыми. Это означает, что достигнута область оптимума.

Опишем принцип использования градиентных методов на примере функции двух переменных

при наличии двух дополнительных условий:

Этот принцип (без изменения) можно применить при любом числе переменных, а также дополнительных условий. Рассмотрим плоскость x 1 , x 2 (Рис. 1). Согласно формуле (8) каждой точке соответствует некоторое значение F. На Рис.1 линии F = const, принадлежащие этой плоскости, представлены замкнутыми кривыми, окружающими точку M * , в которой F минимально. Пусть в начальный момент значения x 1 и x 2 соответствуют точке M 0 . Цикл расчета начинается с серии пробных шагов. Сначала величине x 1 дается небольшое приращение; в это время значение x 2 неизменно. Затем определяется полученное при этом приращение величины F, которое можно считать пропорциональным значению частной производной

(если величина всегда одна и та же).

Определение частных производных (10) и (11) означает, что найден вектор с координатами и, который называется градиентом величины F и обозначается так:

Известно, что направление этого вектора совпадает с направлением наиболее крутого возрастания величины F. Противоположное ему направление - это «наискорейший спуск», другими словами, наиболее крутое убывание величины F.

После нахождения составляющих градиента пробные движения прекращаются и осуществляются рабочие шаги в направлении, противоположном направлению градиента, причем величина шага тем больше, чем больше абсолютная величина вектора grad F. Эти условия осуществляются, если величины рабочих шагов и пропорциональны полученным ранее значениям частных производных:

где б - положительная константа.

После каждого рабочего шага оценивается приращение величины F. Если оно оказывается отрицательным, то движение происходит в правильном направлении и нужно двигаться в том же направлении M 0 M 1 дальше. Если же в точке M 1 результат измерения показывает, что, то рабочие движения прекращаются и начинается новая серия пробных движений. При этом определяется градиент gradF в новой точке M 1 , затем рабочее движение продолжается по новому найденному направлению наискорейшего спуска, т. е. по линии M 1 M 2 , и т.д. Этот метод называется методом наискорейшего спуска/крутого восхождения.

Когда система находится вблизи минимума, показателем чего является малое значение величины

происходит переключение на более «осторожный» метод поиска, так называемый метод градиента. От метода наискорейшего спуска он отличается тем, что после определения градиента gradF делается лишь один рабочий шаг, а затем в новой точке опять начинается серия пробных движений. Такой метод поиска обеспечивает более точное установление минимума по сравнению с методом наискорейшего спуска, между тем как последний позволяет быстрее приблизиться к минимуму. Если в процессе поиска точка М доходит до границы допустимой области и хотя бы одна из величин М 1 , М 2 меняет знак, метод меняется и точка М начинает двигаться вдоль границы области.

Эффективность метода крутого восхождения зависит от выбора масштаба переменных и вида поверхности отклика. Поверхность со сферическими контурами обеспечивает быстрое стягивание к оптимуму.

К недостаткам метода крутого восхождения следует отнести:

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

2. Трудность поиска глобального оптимума. Метод применим для отыскания только локальных оптимумов.