Материал: Основы проектирования Р Э С. Комплект учебно-методической документации по дисциплине. Учебное пособие. Самойленко Н.Э., Скоробогатов В.С

97

весовой коэффициент и входит в целевую функцию со знаком плюс или минус.

В мультипликативном методе используется правило: если f (X) max, то 1/ f (X) min при условии, что

f (X) . В отличие от аддитивного метода, частные критерии не складывают, а перемножают. Кроме того, в мультипликативном методе не используют весовые коэффициенты. Целевая функция строится в виде дроби.

Минимаксный метод построения обобщенной целевой функции получил свое название потому, что в нем минимизируется максимальное отклонение частного критерия качества от его наилучшего, желаемого значения (технического требования, оговоренного в ТЗ). Логика минимаксного построения целевой функции заключается в том, что в каждый момент времени в качестве главного выбирается тот из частных критериев качества Ki(X), который в наибольшей степени удален от своего желаемого значения Ki*.

Другими словами, минимизируется ―самый плохой‖ из частных критериев.

Процесс продолжают до тех пор, пока все частные критерии не будут достаточно (с требуемой точностью) близки к своим желаемым значениям (случай в), изображенный на рис. 2.1).

В случае вероятностного (статистического) метода построения обобщенной целевой функции выбирают

f(X)=P(X) max,

где P(X) – вероятность выполнения условий работоспособности, то есть вероятность того, что при наборе значений внутренних параметров X=(x1, x2.,…,xn ) выходные параметры объекта проектирования будут удовлетворять требованиям ТЗ. Для определения вероятности Р(Х) на

98

практике обычно используют метод статистических испытаний (метод Монте-Карло) / 5 /.

4.6.4.Методы перехода от задачи с ограничениями к задаче безусловной оптимизации

Для перехода от задачи параметрической оптимизации с ограничениями (3.21) к задаче без ограничений, или задаче безусловной оптимизации:

Ф(Х) extr (3.22)

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

В методе неопределенных множителей Лагранжа вводятся дополнительные переменные y1,y2.,…,yL, которые называют неопределенными множителями Лагранжа. Их количество равно числу ограничений L в задаче оптимизации (3.4).

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

.

На практике задачи параметрической оптимизации решаются в основном итерационными (пошаговыми) методами, которые называют методами поисковой оптимизации. При этом на каждом шаге поиска значение штрафной функции k(X) уточняется (рассчитывается заново) по формуле:

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

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

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

Таким образом, при небольшом количестве управляемых параметров Х и ограничений gl(X), целесообразно применять метод неопределенных множителей Лагранжа, если проверка принадлежности начальной точки поиска области ХР не слишком трудоемкая задача, то применяем метод барьерных функций, в противном случае – метод штрафных функций, который, хотя и является более универсальным, но впоследствии, в ходе поисковой оптимизации требует большего числа итераций по сравнению с методом барьерных функций.

3.7.5.Задания и вопросы для самостоятельной подготовки

1.Что понимают под многокритериальностью задачи оптимизации?

2.Назовите методы перехода от многокритериальной задачи оптимизации к однокритериальной.

3.Какие методы перехода от задачи с ограничениями к задаче безусловной оптимизации Вы знаете?

учета ограничений.

3.8. Назначение и классификация методов поисковой оптимизации

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

Исходными данными в методах поиска являются требуемая точность метода и начальная точка поиска Х .

Затем выбирается величина шага поиска h, и по некоторому k+1

предыдущей точке Х при k=0,1,2,… Получение новых точек продолжают до тех пор, пока не будет выполнено условие прекращения поиска. Последняя точка поиска считается решением задачи оптимизации. Все точки поиска составляют траекторию поиска.

Методы поиска отличаются друг от друга процедурой

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

Для методов, использующих постоянную величину шага, h следует выбирать значительно меньше точности h ). Если при выбранной величине шага h не удается получить

101

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

В качестве условий прекращения поиска принято использовать следующие:

все соседние точки поиска хуже, чем предыдущая;

Ф(Xk+1 )-Ф(X k) , то есть значения целевой функции Ф(Х) в соседних точках (новой и предыдущей) отличаются друг от друга на величину не больше, чем требуемая точность ;

производные в новой точке поиска практически равны 0, то есть отличаются от 0 на величину, не превышающую точности .

Алгоритм получения новой точки поиска Хk+1 по предыдущей точке Хk свой для каждого из методов поиска,

но всякая новая точка поиска должна быть не хуже предыдущей: если задача оптимизации является задачей поиска минимума, то Ф(Хk+1) Ф(Хk).

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

производные Ф(Х ) , i=1,…,n, а методы второго порядка

xi

используют матрицу вторых производных (матрицу Гессе).

Чем выше порядок производных, тем более обоснованным является выбор новой точки поиска и тем меньше число итераций метода. Но при этом возрастает

102

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

Эффективность поискового метода определяют по числу итераций и по количеству вычислений целевой функции Ф(Х) на каждой итерации метода. Рассмотрим наиболее распространенные методы поиска, расположив их в порядке уменьшения числа итераций.

Для методов поиска нулевого порядка справедливо

итерации N, а в методе покоординатного спуска N 2 n, где n- количество управляемых параметров X=( x1, x2.,…,xn).

Для методов поиска первого порядка справедливы следующие оценки: в градиентном методе с постоянным шагом N=2 n; в градиентном методе с дроблением шага N=2 n + n 1, где n1 – число вычислений Ф(Х), необходимых для проверки условия дробления шага; в методе наискорейшего спуска N=2 n+n 2, где n2 – число вычислений Ф(Х), необходимых для расчета оптимальной величины шага; а в методе Давидона – Флетчера - Пауэлла ( Д Ф П )

N=2 n + n 3, где n3 – число вычислений Ф(Х), необходимых для расчета матрицы, приближающей матрицу Гессе ( для величин n1, n2, n3 справедливо соотношение n1< n2<< n3 ).

И, наконец, в методе второго порядка - методе Ньютона N=3 n2. При получении данных оценок предполагается приближенное вычисление производных по формулам конечных разностей / 6 /:

то есть для вычисления производной первого порядка нужно два значения целевой функции Ф(Х), а для второй производной – значения функции в трех точках.

На практике широкое применение нашли метод наискорейшего спуска и метод ДФП, как методы с

103

оптимальным соотношением числа итераций и их трудоемкости.

4.7.Методы поиска нулевого порядка

3.8.1.Метод случайного поиска

Вметоде случайного поиска исходными данными являются

требуемая точность метода , начальная точка поиска Х0=( x10, x2. 0,…,xn0) и величина шага поиска h. Поиск новых точек производится в случайном направлении, на котором и откладывается заданный шаг h , таким образом

получают пробную точку Х и проверяют, является ли пробная точка лучшей, чем предыдущая точка поиска. Для задачи поиска минимума это означает, что :

Если условие (3.22) выполнено, то пробную точку включают

в траекторию поиска ( Х k+1 = Х ) . В противном случае, пробную точку исключают из рассмотрения и производят выбор нового случайного направления из точки Х k, k=0,1,2,… .

Несмотря на простоту данного метода, его главным недостатком является тот факт, что заранее неизвестно, сколько случайных направлений потребуется для получения новой точки траектории поиска Хk+1, что делает затраты на проведение одной итерации слишком большими. Кроме того, поскольку при выборе направления поиска не используется информация о целевой функции Ф(Х), число итераций в методе случайного поиска очень велико.

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

104

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

3.8.2.Метод покоординатного спуска

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

Исходными данными в методе покоординатного спуска являются величина шага h и начальная точка поиска Х0=( x10, x2. 0,…,xn0). Движение начинаем из точки Х0 вдоль оси x1 в сторону

увеличения координаты. Получим пробную

точку X=( x1k+h, x2.k,…,xnk), k=0. Сравним значение функции Ф(Х) с значением функции в предыдущей точке поиска Хk.

Если Ф(Х) Ф(Хk) (мы предполагаем, что требуется решить задачу минимизации Ф(Х), то пробную точку

включают в траекторию поиска ( Х k+1 = Х ) .

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

пробную точку X = ( x1k-h, x2. k,…,xnk ). Проверяем, если

Ф(Х)>Ф(Хk), то продолжаем движение вдоль оси x2 в сторону увеличения координаты. Получим пробную точку

105

X=( x1k, x2.k+h,…,xnk) и т.д. При построении траектории поиска повторное движение по точкам, вошедшим в траекторию поиска, запрещено. Получение новых точек в методе покоординатного спуска продолжается до тех пор, пока не будет получена точка Хk, для которой все соседние 2 n пробных точек ( по всем направлениям x1, x2.,…,xn в сторону увеличения и уменьшения значения координаты)

будут хуже, то есть Ф(Х)>Ф(Хk). Тогда поиск прекращается и в качестве точки минимума выбирается последняя точка траектории поиска Х*= Хk.

З. 9. Методы поиска первого порядка

3. 9. 1. Структура градиентного метода поиска

В методах поиска первого порядка в качестве направления поиска максимума целевой функции Ф(Х) выбирается вектор градиент целевой функции grad (Ф(Хk)), для поиска минимума – вектор антиградиент -grad (Ф(Хk)).

При этом используется свойство вектора градиента указывать направление наискорейшего изменения функции:

Для изучения методов поиска первого порядка важно также следующее свойство: вектор градиент grad (Ф(Хk)), направлен по нормали к линии уровня функции Ф(Х) в точке Хk

106

Линии уровня – это кривые, на которых функция принимает постоянное значение (Ф(Х)=соnst).

В данной главе мы рассмотрим пять модификаций градиентного метода:

градиентный метод с постоянным шагом, градиентный метод с дроблением шага, метод наискорейшего спуска, метод Давидона-Флетчера-Пауэлла, двухуровневый адаптивный метод.

3. 9. 2. Градиентный метод с постоянным шагом В градиентном методе с постоянным шагом исходными

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

соотношением, включающим n уравнений. Например, с учетом Хk+1=( x1k+1, x2. k+1,…,xnk+1), Хk=( x1k, x2. k,…,xnk) формула (3.23) примет

вид: