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) = {F1(X), F2(X)..., Fn(X)},
где Fi(X) - скалярные функции цели.
Задачи оптимизации с векторной функцией цели часто называют многокритериальными. Для их решения разработаны специальные методы, но их невозможно использовать без какой-либо информации об относительной важности каждой из скалярных функций цели, качественной или количественной.
Одним из таких методов является оптимизация по Парето. Для векторной функции цели F(X) решение называется оптимальным по Парето, если оно не может быть улучшено ни по одной из частных (скалярных) функций цели Fi(X) без ухудшения по какой-либо другой из них. В результате расчета получается не единственное решение, а целая область, из которой уже вручную или автоматизированно выбирается действительно оптимальное решение, используя информацию об относительной важности каждой из скалярных функций цели. Можно учитывать при этом и не формализуемые критерии. Оптимальность по Парето чаще используется в экономических задачах, но ее можно иногда применять и при оптимизации ГТД.
Наиболее употребительными являются различные методы свертки, когда векторная функция цели сводится к скалярной по различным алгоритмам, использующим информацию об относительной важности каждой из скалярных функций цели и другие данные. Например, хорошие результаты дает метод квадратичной функции потерь. В нем используются предельно достижимые значения скалярных функций цели Fi при данном режиме и ограничениях. Они иногда могут быть взяты ориентировочно по литературным данным, а чаще получаются при вспомогательных оптимизациях по каждой из i скалярных функций цели. После их завершения записываются формулы для взвешенных квадратов невязок
,
где - текущее значение скалярной функции цели
- предельно достижимое значение скалярной функции цели;
- вес, учитывающий относительную важность i-й функции цели.
Значения весов всегда положительны. Они чаще всего определяются по экспертным оценкам, и в них всегда присутствует элемент субъективности. Обычно при назначении весов выдерживается условие
но оно не является обязательным.
Квадратичная функция потерь имеет следующий вид:
Она является сверткой векторной функцией цели, полностью ее заменяет, а поэтому используется вместо нее в качестве единой скалярной функции цели.
Иногда используются более простые методы свертки, например
или
В этих случаях вместо можно брать любые опорные значения функций цели. Часто для упрощения полагают
,
но эти упрощения, конечно, ухудшают качество спроектированного изделия.
При сложности определения весов с достаточной степенью точности более удобен минимаксный метод свертки, который менее чувствителен к погрешностям весов. В этом методе минимизируется максимальная из невязок, т.е.
(5.8)
После свертки оптимизация по скалярным функциям цели ведется одним из обычных методов, описанных выше.
,
- текущее значение скалярной функции цели
- предельно достижимое значение скалярной функции цели;
- вес, учитывающий относительную важность i-й функции цели.
можно брать любые опорные значения функций цели. Часто для упрощения полагают
,
(5.8)