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

Симплексом называется n-мерный выпук­лый многогранник, имеющий К+ 1 вершин. Симплекс называется регулярным, если все расстояния между его вершинами равны. Симплексом нулевой размерности является точка, одномерным симплексом - отрезок прямой, двумерным - треугольник, трех­мерным - тетраэдр и т. д.

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

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

Рис. 6. Поиск экстремума функции отклика симплексным методом

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

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

Методы градиента. При оптимизации градиентным методом дви­жение совершается в направлении наибольшего изменения крите­рия оптимизации, т. е. в направлении градиента целевой функции. Причем, как и в методе случайного поиска, направление движения корректируется после каждого рабочего шага, т. е. каждый раа заново определяется значение градиента по результатам специаль­но поставленных пробных экспериментов (рис. 3.3). Поскольку координатами вектора служат коэффициенты при линейных членах разложения функ­ции У(Х) в ряд Тейлора по степеням Xi(i=l, 2,..., £), то соответ­ствующие компоненты вектора градиента могут быть получены, как коэффициенты Ь₁, Ь₂,..., b_k линейной аппроксимации поверхности отклика вблизи исходной точки х₀

Рис. 3.3. Поиск экстремума функции отклика методом градиента

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

р_р - параметр рабочего шага.

Показателем выхода в область оптимума является малое зна­чение модуля градиента | grad У(Х) | ~ 0, т. е. все коэффициенты bi становятся незначимыми или равными нулю.

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

Метод Кифера — Вольфовица. Характерной чертой этого ме­тода является зависимость размеров рабочего и пробного шагов от номера шага h или от расстояния до оптимума (рис. 3.4).

Рис. 3.4. Поиск экстремума функ­ции отклика методом Кифера-Вольфовица

Алгоритм движения к экстремуму по методу Кифера - Воль­фовица тот же, что и в предыдущем методе

В рассматриваемом методе, как и при оптимизации градиент­ным методом, величина шага уменьшается при приближении к экстремуму за счет уменьшения величины градиента grad У, а в ме­тоде Кифера — Вольфовица еще и в связи с уменьшением р_р. Сле­дует сказать, что на практике иногда применяется движение к оптимуму с постоянным шагом в соответствии с алгоритмом

где р_р= const.

Недостатки метода градиента:

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

- определение градиента производится на каждом шаге, что очень трудоемко.

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

Следует также отметить, что метод Бокса - Уилсона предпола­гает регулярное проведение статистического анализа промежуточ­ных результатов на пути к экстремуму. Поиск оптимума методом крутого восхождения выполняется по следую­щему плану.

Рис. 3.5. Поиск экстремума функции отклика методом крутого восхождения

1. Вблизи исходной точки х₀ проводится эксперимент для опре­деления градиента и определяются коэффициенты bi уравне­ния (3.5).

2. Вычисляются произведения bitsXu где AXi — интервал варьи­рования фактора Xi при исследовании поверхности отклика в окрестности исходной точки, т. е. при определении коэффициен­тов bi. Фактор, для которого произведение biAXi будет максималь­ным, принимается за базовый.

3. Для базового фактора выбирается шаг варьирования при движении по направлению к экстремуму Хб- После этого вычис­ляются размеры шагов при крутом восхождении по остальным переменным (А,, -) процесса. Так как при движении к экстремуму по градиенту все исследуемые факторы должны изменяться про­порционально коэффициентам наклона поверхности отклика Ьи то

при этом bi берется со своим знаком.

4. Производятся так называемые «мысленные опыты», которые заключаются в вычислении предсказанных значений функции отклика в точках факторного пространства, лежащих на пути к экстремуму от исходной точки. Иными словами, осуществляется мысленное движение по градиенту к оптимуму в соответствии с (3.5). При этом i-я координата h-и точки на этом пути будет

Отсюда прогнозируемое значение выходного параметра

5. Некоторые из «мысленных опытов» (обычно через 2... 5) реа­лизуются для того, чтобы проверить соответствие аппроксимации «процесса найденной зависимостью. Наблюдаемые значения сравни­ваются с предсказанными; точка, где в реальном опыте получено наиболее благоприятное (в нашем случае - минимальное) значе­ние выходного параметра принимается за новую начальную точ­ку (Хл) следующей серии опытов, поставленных аналогичным об­разом.

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

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

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