Задачи отыскания экстремального значения функции отклика, когда эта функция зависит не от одного, а от n (n³2) факторов, встречаются на практике несравненно чаще, чем задачи одномерные. В то же время получение их решения оказывается намного более трудоемким. И дело здесь не в простом количественном увеличении размерности задачи и связанным с этим пропорциональным усложнением расчетов. Многомерные задачи поиска принципиальным образом отличаются по своей структуре от задач поиска по одной переменной. Порождаемые этими различиями трудности образно называют "проклятием размерности". Можно назвать три основные проблемы, связанные с этим "проклятием".
Во-первых, при возрастании числа факторов можно ожидать, что функция отклика не сохранит свойство унимодальности, даже если при поочередном изменении факторов обнаруживается, что оно имеет место. Более того, даже когда заранее известно из теоретических соображений, что функция отклика унимодальна, на ход поиска могут сильно влиять некоторые локальные свойства поверхности отклика, не имеющие аналогов в одномерном случае. Речь идет о таких особенностях поверхности, как "овраги", "узкие хребты", "гребни". Даже не вдаваясь в математические определения этих понятий и обращаясь к чисто наглядным представлениям для простейшего двумерного случая, легко понять, насколько сложным может быть путь к экстремуму, насколько сложной может быть и унимодальная функция отклика.
Вторая проблема заключается в трудности сопоставления различных алгоритмов многомерного поиска. Ясно только, что для любого алгоритма возможно подобрать такую функцию отклика, когда она окажется предпочтительнее других, в то же время можно построить и другую функцию отклика, при которой этот алгоритм станет практически неработоспособным.
И, наконец, третья проблема связана со сложностями введения точностных характеристик локализации точки экстремума.
Существует большое число разнообразных методов многомерного поиска. В дальнейшем будут рассмотрены лишь некоторые из них, получившие наибольшее распространение для целей экспериментальной оптимизации. Эти методы можно разделить на две большие группы: на градиентные и неградиентные методы поиска экстремума.
Все градиентные методы основаны на предварительном определении градиента функции отклика f: grad f = (f / x1) × i + (f / x2) × j + ... + (f / xk) × k, где i, j,..., k - единичные векторы в направлении координатных осей.
Предполагается, что функция f непрерывна и однозначна. Если ее разложить в ряд Тейлора в окрестностях точки, в которой берется значение градиента, и ограничиться лишь линейными членами, можно показать, что координаты градиента совпадают с коэффициентами полученного разложения.
Рассмотрим теперь одну из конкретных разновидностей градиентных методов поиска.
— Метод крутого восхождения (МКВ) представляет собой процедуру последовательного перемещения по пути крутого восхождения, т.е. в направлении наибольшего увеличения отклика. Конечно же, если необходима минимизация, то тогда мы говорим о методе крутого (наискорейшего) спуска.
Подобранная модель первого порядка имеет вид: y = b0 + bi × xi, где y - отклик; b0, b1, b2,.., bi,.., bk - коэффициенты регрессии (параметры модели); x1, x2,.., xi,.., xk- факторы; k - количество факторов.
Поверхность отклика первого порядка, т.е. контуры y, представляются рядом параллельных прямых. Направление крутого восхождения - это направление, в котором y возрастает наиболее быстро, оно параллельно нормали к контурам подобранной поверхности отклика. Обычно в качестве пути крутого восхождения мы выбираем линию, проходящую через центр области экспериментирования и нормальную к контурам подобранной поверхности. Таким образом, шаги вдоль этого пути пропорциональны коэффициентам регрессии bi (точнее шаги по каждому из координатных направлений). Фактическая длина шага определяется экспериментатором на основе опыта.
Эксперименты проводятся по линии крутого восхождения до тех пор, пока не перестанет наблюдаться увеличение отклика. Затем для описания отклика можно подобрать новую модель первого порядка и найти новую линию крутого восхождения. Продолжая процедуру таким образом, экспериментатор попадает в окрестность оптимума; об этом обычно свидетельствует неадекватность модели первого порядка. В таком случае для получения более точной оценки положения оптимума проводятся дополнительные эксперименты.
Неградиентные методы поиска отличаются большим разнообразием идей, положенных в их основу. Всех их роднит необходимость совершения пробных шагов с последующим движением в ту сторону, где результаты проб оказались благоприятными.
Рассмотрим, прежде всего, метод покоординатного поиска, называемый также методом Гаусса-Зайделя. Метод состоит в последовательной оптимизации процесса по отдельным факторам при фиксированных значениях остальных. Исходную точку выбирают на основании результатов предшествующих стадий исследования. Анализ результатов экспериментов проводят графически в натуральной системе координат. Исследования осуществляются в несколько циклов. В первом цикле осуществляется движение параллельно одной из осей факторного пространства, определятся наилучшее значение параметра оптимизации и затем в этой наилучшей точке проводится поворот и движение ведется далее параллельно другой оси; подобная процедура продолжается, пока не будут рассмотрены все исследуемые факторы.
Координаты частного оптимума, полученного в первом цикле, используют в качестве исходной точки второго цикла, где варьируются другие переменные. Координаты частного оптимума, полученного во втором цикле, используют в качестве исходной точки третьего цикла и т.д.
Эффективным способом оптимизации является последовательный симплексный метод (ПСМ). Все эксперименты в этом случае надо реализовывать при условиях, отвечающих вершинам правильных n-мерных симплексов. Начальная точка поиска обычно соответствует установленному технологическому регламенту или наилучшему из известных режиму ведения процесса. Эта точка может являться вершиной или центром начального симметричного правильного симплекса. Ориентация начального симплекса может быть произвольной, т.к. наиболее выгодное направление движения не представляется возможным прогнозировать. Размеры симплекса в ПСМ должны быть достаточно малы, но при этом возникает проблема выделения полезного сигнала на фоне шума, а именно, статистически значимого различия значений отклика в вершинах симплекса малых размеров. Эти трудности могут быть преодолены путем накопления результатов повторных наблюдений в вершинах симплекса и сравнения полученных средних арифметических значений. Необходимо по возможности стремиться планировать симплекс возможно больших размеров, т.к. это сокращает количество необходимых повторных наблюдений в вершинах симплекса и ускоряет движение к экстремуму.
Движение к экстремуму поверхности отклика на каждом шаге должно осуществляться посредством перехода от реализуемого симплекса к новому путем отбрасывания наихудшей вершины и построения точки, симметричной к ней относительно центра (n-1)-мерной оставшейся грани симплекса. Каждую i-ую размерную координату зеркальной точки Xn+h h-го симплекса можно вычислить по формуле X (n+h),i = 2 Xgi / n - (n+2) Xqi / n.
Здесь Xgi- i-ая размерная координата g-ой из n+1 вершин рассматриваемого (h-1)-го симплекса, а Xqi- i-ая размерная координата его q-ой отброшенной вершины. Далее таким же образом можно построить последовательные симплексы. При этом иногда может возникнуть ситуация, предусмотренная следующим правилом. Если одно и то же наихудшее значение отклика имеет место в нескольких вершинах рассматриваемого симплекса, то вопрос об отбрасывании одной из них должен быть решен случайным образом, например, с использованием таблицы случайных чисел. Непрерывное смещение симплекса может привести к выходу новой зеркальной точки за границы допустимой области изменения факторов. В этом случае перемещение симплекса осуществляется по следующему правилу. Если в зеркальной точке формируемого симплекса нарушаются факторные или функциональные ограничения, то необходимо вернуться к предыдущему симплексу и отбросить в нем худшую вершину после наихудшей. Иногда это правило приходится применять повторно до тех пор, пока не будет найдена новая зеркальная точка, принадлежащая допустимой области факторного пространства.
Если зеркальная точка нового симплекса является его наихудшей вершиной, т.е. поступательное перемещение симплекса преобразуется в качание относительно противолежащей грани, то это может свидетельствовать о приближении к экстремуму поверхности отклика или о наличии большой ошибки наблюдений. Пока точка экстремума в факторном пространстве остается неподвижной, симплекс постоянно качается (вращается) около некоторой близкой к ней точки. Если же точка экстремума начинает дрейфовать, то вслед за ней перемещается и симплекс, описывая спираль около ее траектории. При этом условия управления объектом будут непрерывно изменяться, приспосабливаясь к дрейфу.
bi × xi, где y - отклик; b0, b1, b2,.., bi,.., bk - коэффициенты регрессии (параметры модели); x1, x2,.., xi,.., xk - факторы; k - количество факторов.
Xgi / n - (n+2) Xqi / n.