Задача оптимизации. Метод крутого восхождения (Бокса-Уилсона). (МОДЕЛИРОВАНИЕ)

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

Обычно задается некоторый критерий оптимизации (целевая функция) Y, зависящий от вектора управляемых параметров (факторов варьирования)

 

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

Зависимость(8.1) образует некоторую поверхность в (n+1) – мерном пространстве Х₁,Х₂,….,Х_n,Y. Эту поверхность принято называть поверхностью отклика, а отдельные её точки или знания Y в точках фактурного пространства – просто откликом.

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

Решение системы (8.2) является так называемая стационарная точка в которой градиента функции обращается в нуль

где: (8.3.) - направляющий вектор координатной оси Xi

Однако в большинстве практических случаев аналитическая зависимость неизвестна и единственное, чем располагает исследователь – это возможность наблюдать значения отклика при любой комбинации варьируемых факторов(Х₁,Х₂,….,Х_n)

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

Для решения задач оптимизации используются два принципипльно различных подхода:

каким-либо способом определяется полная математическая модель и далее задача решается аналитическим или численным путем.2. Осуществляется экспериментальный поиск стационарной точки в факторном пространстве переменных (Х₁,Х₂,….,Х_n)

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

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

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

И, наконец, третья проблема связана со сложностями введения точностных характеристик локализации точки экстремума. Дело в том, что с ростом размерности факторного пространства резко уменьшается точность определения точки экстремума. Так, например, для 50-мерного гиперкуба попытка локализовать точку экстремума в 10% первоначального объема приводит к факту, что каждая сторона нового гиперкуба (размах варьирования каждого фактора) составит всего от первоначального размера, что, конечно не может удовлетворить исследователя.

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

Если модель сделана в виде полинома второго порядка, то найти оптимальные точки очень просто: т.к. сама модель второго порядка символизирует, что мы находимся в области экстремума. Линейная модель свидетельствует о том, что:

1) мы находимся далеко от вершины холма

2) в силу малости известной области требуется выработка некоторых правил, согласно которым будем двигаться к экстремуму.

Существует несколько путей нахождения:

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

2) метод градиента

3) метод случайного поиска

4) метод крутого восхождения

5) оптимизация в условиях ограничений

Метод крутого восхождения

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

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

Пусть у нас k факторов, которые независимы друг от друга.

Алгоритм.

1. В центре проводим ПФЭ (ДФЭ) с целью получения градиента. При этом результаты эксперимента подвергаются статистическому анализу, который заключается в следующем:

а) проверка воспроизводимости эксперимента (грубые промахи)

б) проверка значимости коэффициентов линейной модели

в) проверка адекватности линейной модели

2. Вычисляются произведения среди них находится max{ } = (b - величина относительная, - абсолютная).

3. Для базового фактора выбирается шаг крутого восхождения (только для базового). Дальше будем обозначать его .

4. Определяются размеры

5. Проводятся т.н. «мысленные опыты», которые заключаются в вычислении предсказанных значений целевой функции в определенных точках факторного пространства. . Для этого независимые переменные линейной модели изменяются с учетом таким образом, чтобы изображающая точка совершала движение в направлении вектора grad y() полученного в пункте 1 занимая последовательно положения .

6. «Мысленные опыты» продолжаются до тех пор, пока выполняется неравенство

7. Некоторые из «мысленных опытов» (обычно через каждые 2-3 «мысленных шага») реализуются в виде эксперимента один раз. Для проверки соответствия «мысленных опытов» и реальности.

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

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

10. Поиск прекращается, когда градиент равен нулю, т.е. все bi оказались незначительными.

Замечания

1)Наиболее эффективно применять МКВ для симметричных функций.

2)Направление движения идет по градиенту и определяется единственным способом из центра плана.