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

Алгоритм (схема поиска показана на рис. 1)

1. Выбираем начальное приближение (т1)

2. В окрестности точки находим градиент (на схеме показан окружностью со стрелкой)

3. Определяем локальный экстремум в направлении градиента (на схеме черная линия с точками)

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

4. В точке локального экстремума находят градиент (т2, т3).

5. Далее действуют как в пунктах 3 и 4 до тех пор пока градиент не станет равен нулю (т4).

Это место и считают глобальным экстремумом.

Для повышения точности расчета начальное приближение выбирают в различных местах (если поверхность отклика имеет несколько вершин ).

Преимущества метода:

1. Дает точное решение

2. Достаточно экономичен

Недостатки метода:

1. Варьируемые параметры должны быть непрерывными.

Рис. 1. Схема метода крутого восхождения.

Градиентный метод

Алгоритм (схема поиска показана на рис. 2)

1. Выбирается начальное приближение (т1)

2. Определяется градиент в окрестности точки (на схеме показан окружностью со стрелкой)

3. В направлении градиента делается шаг, величина которого зависит от градиента (т2)

4. Определяется новое направление градиента.

5. Пункты 2-4 повторяют до тех пор, пока градиент не станет равным нулю (т3-4)

Метод примерно соответствует предыдущему со всеми преимуществами и недостатками.

Рис. 2. Схема градиентного метода.

Примеры «методов оптимизации, не использующих производные»

Метод Зейделя

Алгоритм (схема поиска показана на рис. 3)

1. Выбирается начальное приближение (т1)

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

3. После этого производится поиск экстремума в направлении другой оси координат (т3)

4. Так поступают со всеми варьируемыми параметрами, а результат считают оптимальным решением (т3)

Для получения более точного решения изменяют положение начальной точки.

Преимущества метода:

1. Простота алгоритма

2. Варьируемые параметры могут быть как непрерывны, так и дискретно задаваемые

Недостатки метода:

1. Не дает точного решения

2. Не экономичен

Рис. 3. Схема поиска метода Зейделя.

Симплексный метод (Метод Нелдера – Мида )

Алгоритм (схема поиска показана на рис. 4)

1. В качестве начального приближения выбирается симплекс. Для n- варьируемых параметров он представляет собой n+1 многогранник (на схеме треугольник нп)

2. Вычисляется значение функции цели во всех вершинах.

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

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

Преимущества:

1. Дает достаточно точное решение

2. Варьируемые переменные могут быть дискретно изменяемые.

Недостатки:

Уступает по скорости и точности градиентному методу.

Рис. 4. Схема поиска симплексного метода.

Особенности оптимизации при векторной функции цели

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

F(X) = {F₁(X), F₂(X)..., F_n(X)},

где F_i(X) - скалярные функции цели.

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

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

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

,

где - текущее значение скалярной функции цели

- предельно достижимое значение скалярной функции це­ли;

- вес, учитывающий относительную важность i-й функции цели.

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

но оно не является обязательным.

Квадратичная функция потерь имеет следующий вид:

Она является сверткой векторной функцией цели, полностью ее заме­няет, а поэтому используется вместо нее в качестве единой скалярной функции цели.

Иногда используются более простые методы свертки, например

или

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

,

но эти упрощения, конечно, ухудшают качество спроектированного изделия.

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

(5.8)

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