Постановка задач параметрической оптимизации

 

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

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

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

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

1 – компьютерное моделирование устройства;

2 – составление целевой функции с выбором критериев оптимальности;

3 – поиск экстремума полученной целевой функции и определение оптимальных внутренних параметров устройства.

Моделирование (анализ) РЭС требует наличия соответствующих математических моделей и проводится в основном численными методами. Главным критерием моделирования наряду с необходимой точностью и адекватностью модели является быстродействие, скорость расчета на ЭВМ выходных параметров устройства.

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

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

Критерии качества и ограничения задачи параметрической оптимизации прямо либо опосредованно зависят от выходных параметров объекта проектирования        Y = ( y ₁ , y ₂ ., …, y_m ).

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

Обозначим критерии качества K_{i ,} = K_i ( x ₁ , x ₂ .,…, x_n),  i = 1,…, s, где s – количество критериев качества, а K_i ( X ) – либо один из выходных параметров Y = ( y ₁ , y ₂ .,…, y_m ), либо    K_i ( X ) = f ( X ), где зависимость f ( X ) задана.

 Все ограничения задачи параметрической оптимизации получаются на основе анализа технических требований к параметрам объекта проектирования, содержащихся в ТЗ. Рассмотрим формализацию ограничений на примере выходных параметров Y (для внутренних параметров Х справедливы аналогичные рассуждения).

Технические требования имеют вид y_j = TT_j + D j, где TT_j – желаемое значение параметра y_j, а Dj – его допустимый разброс ( j = 1, …, m ).

Математическая постановка задачи параметрической оптимизации как задачи математического программирования имеет вид

 

K_i=K_i(X) → extr, 

g_l(X) £ ,                                        (6.1)

i = 1, …, s, l = 1, …, L.

 

Множество наборов значений управляемых параметров Х, удовлетворяющих ограничениям g ₁ ( X ) £ , l = 1, …, L называют областью работоспособности, или областью допустимых значений управляемых параметров.

Если функция K_i ( X ) имеет один минимум или максимум в заданной области работоспособности, то ее называют одноэкстремальной (унимодальной), если несколько, то -многоэкстремальной.

 Каждый минимум (максимум) многоэкстремальной функции называют локальным, наименьший (наибольший) из них – глобальным.

Если ограничения на внутренние параметры g_l ( X ) отсутствуют, то задача оптимизации называетсябезусловной, в противном случае – условной.

При практическом проектировании РЭС встают задачи поиска как безусловных, так и условных экстремумов унимодальных и многоэкстремальных функций.

Рассмотрим в качестве примера типичное ТЗ на разработку аналогового устройства – усилителя: «Коэффициент усиления К₀ на средних частотах должен быть не менее 10000, входное сопротивление R _вх не менее 1 МОм, выходное сопротивление R _вых не более 200 кОм, верхняя граничная частота f _в не менее 100 кГц, температурный дрейф нуля U _др не более 50 мкВ/град; усилитель должен нормально функционировать в диапазоне температур от –50 до +60 ⁰С, напряжения источников питания +5 и –5 В, предельные отклонения напряжений не более +0,5 %, усилитель эксплуатируется в стационарной установке, габариты платы 60х40 мм». В данном случае выходными параметрами являются Y = {К o , R _вх , R _вых , f _в , U _др}. 

К внешним воздействиям относятся температура окружающей среды и напряжения источников питания. Управляемыми параметрами являются параметры элементов схемы.

Область работоспособности

X Р = {Xô10000 - К o Ð  0,1-R _вх Ð0, R _вых-200 Ð 0,100- f в Ð 0, 50 - U _др Ð 0}.

 

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

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

Задача параметрической оптимизации (6.1) является многопараметрической, многокритериальной и содержит ограничения, все эти факторы определяют проблемы, возникающие в процессе ее решения. В зависимости от вида критериев качества и ограничений, проводят классификацию задач параметрической оптимизации (задач математического программирования). Если целевая функция и ограничения – линейные функции вида С₀ + С₁Х₁+ С₂Х₂+…+ С _n Х_n, то задача оптимизации называется задачей линейного программирования, в противном случае – задачей нелинейного программирования.

Если целевая функция квадратичная, а ограничения – линейные функции, то задача (6.1) называется задачей квадратичного программирования.

Если целевая функция и ограничения имеют произведения Х₁ Х_{2 …} Х_n, то задачу (6.1) называют задачей геометрического программирования.

Если целевую функцию можно представить в виде суперпозиции функций f ₁ ( f ₂ ( f ₃ …( f_k (Х))…)) , то задача (6.1) – это задача динамического программирования.

Если целевая функция и ограничения целочисленные функции то задача (6.1) – это задача целочисленного программирования

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

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

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

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

Для того, чтобы оценить, насколько хорошо удовлетворяют требованиям ТЗ значения частных критериев качества при заданном наборе значений внутренних параметров X = ( x ₁ , x ₂ .,…, x_n ), нужно построить обобщенный критерий качества (обобщенную целевую функцию) f (Х), которая одновременно учитывает требования ко всем частным критериям.

Иными словами, от многокритериальной задачи параметрической оптимизации в виде:

 

 K₁(X) ® extr                                                                                  

              . .                                               (6.2)     

 Ks ( X ) ® extr, 

g_l ( X)≤ , l = 1,…, L,

 

необходимо перейти к однокритериальной задаче:

 

f(X) ® extr, 

g_l(X) ≤ , l=1,…,L,                                     (6.3)         

X =( x ₁ , x ₂ .,…, x_n ).

 

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

В методе выделения главного критерия проектировщик выбирает один, наиболее важный с его точки зрения частный критерий качества, который и принимается за обобщенную целевую функцию. Требования к остальным частным критериям учитывают в виде ограничений F (Х) = K_t ( X ), где t – номер наиболее важного частного критерия.

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

При построении целевой функции в аддитивном методе используется соотношение: если f ( X ) ® max, то –f ( X ) ® min.

       Чтобы построить минимизируемую целевую функцию f ^¯ ( X ) ® min, все минимизируемые частные критерии K ^¯ i ( X ) ( ) включают в аддитивную функцию со знаком плюс, то есть прибавляют к целевой функции, а все максимизируемые критерии K ⁺ _i ( X ) ( ) включают в аддитивную функцию со знаком минус, то есть вычитают из целевой функции:

 

       (6.4)

 

или, для максимизируемой целевой функции:

  (6.5)

 

где s – общее число частных критериев,

t – количество минимизируемых критериев.

В нашем примере четыре частных критерия, то есть s = 4,

 t = 2:

K₁(X) ® max,

K₂(X) ® max,

K₃(X) ® min,

K₄(X) ® min.         

 

Пусть l₁ = l₂ = l₃ = l₄ = 0,25, тогда           

 

f(X) = 0,25× K₁(X) +0,25× K₂(X) -0,25× K₃(X) -0,25× K₄(X) ® max,

 

или

 

f(X) = -0,25× K₁(X) -0,25× K₂(X) + 0,25× K₃(X) + 0,25× K₄(X) ®  min.

        

Каждый частный критерий включаетcя в аддитивную целевую функцию по правилу: умножается на весовой коэффициент и входит в целевую функцию со знаком плюс или минус.

В мультипликативном методе используется правило: если f ( X ) ® max, то 1/ f ( X ) ® min при условии, что f ( X ) ¹ 0. В отличие от аддитивного метода, частные критерии не складывают, а перемножают.

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

Если f ( X ) ® min, то в числитель дроби включают произведение всех минимизируемых критериев, а в знаменатель – произведение всех максимизируемых критериев:

                (6.6)

 

или, если целевую функцию нужно максимизировать:

      (6.7)

 

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

 

,      (6.8)

.      (6.9)

 

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

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

 

,     (6.10)

 

где X = ( x ₁ , x ₂ .,…, x_n ), то есть

 

 

         (6.11)

 

Логика минимаксного построения целевой функции заключается в том, что в каждый момент времени в качестве главного выбирается тот из частных критериев качества K_i ( X ), который в наибольшей степени удален от своего желаемого (оптимального) значения K_i ^*. В нашем примере (s = 4) при желаемых значениях K ₁ ^* = 0,2; K ₂ ^* = 1000; K ₃ ^* = 25; K ₄ ^* = 1 по минимаксному методу получим:

 

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

Рассмотрим три ситуации, изображенных на рис. 6.1.

 

                                    Рис. 6.1

 

На оси у откладывается величина ô K_i ( X ) - K_i ^* ô / K_i ^*  для всех частных критериев (i = 1, 2, 3, 4 для нашего примера). В случае а) хуже всего удовлетворяет требованиям ТЗ критерий K ₃ (Х), поэтому f ( X )= ô K ₃ ( X ) - K ₃ ^* ô / K ₃ ^*, то есть в течение некоторого времени усилия оптимизации будут направлены на приближение критерия K ₃ ( X ) к его желаемому значению K ₃ ^*. При этом могут ухудшиться значения других критериев. Например, в случае б) для дальнейшей оптимизации будет выбран критерий K ₁ ( X ).

Процесс продолжают до тех пор, пока все частные критерии не будут достаточно (с требуемой точностью) близки к своим желаемым значениям (случай в), изображенный на рис. 6.1. При этом приведение критериев к нормированному виду ôK_i ( X ) - K_i ^*ô/ K_i ^* необходимо, чтобы в равной степени учитывать изменение критериев независимо от их абсолютных величин (как слишком больших, так и слишком малых, возможно различающихся на несколько порядков).

В случае вероятностного (статистического) метода построения обобщенной целевой функции выбирают        f ( X ) = P ( X ) ® max, где P ( X ) – вероятность выполнения условий работоспособности, то есть вероятность того, что при наборе значений внутренних параметров X = ( x ₁ , x ₂ .,…, x_n ) выходные параметры объекта проектирования будут удовлетворять требованиям ТЗ. Для определения вероятности Р(Х) на практике обычно используют метод статистических испытаний (метод Монте-Карло).

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

 

                                     Ф(Х)  ® extr                     (6.12)      

 

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

В методе неопределенных множителей Лагранжа вводятся дополнительные переменные y ₁ , y ₂ .,…, y_L, которые называют неопределенными множителями Лагранжа. Их количество равно числу ограничений L в задаче оптимизации. Целевая функция (функция Лагранжа) с учетом ограничений строится по формуле:

 

            (6.13)

 

где X = ( x ₁ , x ₂ .,…, x_n ), Y = ( y ₁ , y ₂ .,…, y_m ) , y_l > 0, l = 1, …, L .

Формула (6.14) применима, если задача параметрической оптимизации ставится как задача максимизации, при этом для полученной целевой функции Ф( X , Y ) необходимо найти седловую точку, то есть по переменным X = ( x ₁ , x ₂ .,…, x_n ) проводится поиск максимума, а по переменным Y = ( y ₁ , y ₂ .,…, y_m ) – поиск минимума, то есть

 

                      (6.14)

 

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

В методе штрафных функций целевую функцию задачи безусловной оптимизации получают по формуле:

 

                         Ф(Х) = f ( X )+ q k ( X )  ® extr ,           (6.15)

 

где X = ( x ₁ , x ₂ .,…, x_n ) – набор управляемых параметров,            

  q k ( X ) - штрафная функция,

k - номер итерации (шага) в методе поисковой оптимизации.

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

    (6.16)

 

где r_k = 10 ^k. Формула (6.16) применима, если задача параметрической оптимизации ставилась как задача минимизации.

Логика построения штрафной функции заключается в следующем: внутри области работоспособности ХР  g _l ( X ) < 0, l = 1, …, L , на границе – g_l ( X ) = 0, а вне ХР g_l ( X ) > 0            (рис. 6.2).

 

Рис. 6.2. Построение штрафной функции

 

Целевая функция задачи безусловной оптимизации Ф(Х) должна быть максимально близкой к целевой функции f (Х) задачи с ограничениями внутри области работоспособности X Р = { X = ( x ₁ , x ₂ , …, x_n ) ô gl ( X ) Ð 0 ,            l = 1,…, L} и быть значительно хуже (больше) функции f (Х) вне области работоспособности, то есть при g_l ( X ) > 0.

Действительно, внутри области работоспособности ХР g_l ( X ) Ð  0 , l = 1,…, L , поэтому max {0, gl ( X )} = 0 для всех ограничений, то есть внутри области работоспособности Ф(Х) = f (Х). Если ограничения выполнены, то никакого штрафа на целевую функцию не накладывается. В противном случае, если имеются нарушения одного или нескольких ограничений g_t ( X ) > 0, 1 Ð t Ð L, то каждое из них дает свой вклад в штрафную функцию q k ( X ) в виде квадрата слагаемого          [max {0, gt (Х)}], где max {0, gt (Х)}= gt (Х). Метод штрафных функций часто называют методом внешней точки, потому что при проведении дальнейшей оптимизации поисковыми методами для метода штрафных функций не важно, принадлежит ли начальная точка поиска области работоспособности ХР.

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

 

                         Ф(Х)= f ( X )+ q k ( X )  ® extr ,         (6.17)

 

где k - номер итерации поискового метода, весовой коэффициент r_k=10^-k, а барьерная функция q k ( X) вычисляется по формуле             

         (6.18)

 

Действительно, при приближении к границе              ХР g_l (Х) 0, так как Х Î ХР (метод внутренней точки) g_l ( X ) < 0, l = 1, …, L, поэтому g_l (Х) → –¥. Именно поэтому в формуле (2.56) используется знак минус: q k ( X ) возрастает до бесконечности при приближении к границе области работоспособности.

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

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

 

Методы поисковой оптимизации

 

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

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

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

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

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

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

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

2) çФ( X^{k +1} )–Ф( X ^k )ç £ e, то есть значения целевой функции Ф(Х) в соседних точках (новой и предыдущей) отличаются друг от друга на величину не больше, чем требуемая точность e;

3) , i = 1, …, n, то есть все частные производные в новой точке поиска практически равны 0, то есть отличаются от 0 на величину, не превышающую точности e.

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

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

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

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

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

Для методов поиска нулевого порядка справедливо следующее: в методе случайного поиска нельзя заранее предсказать количество вычислений Ф(Х) на одной итерации N, а в методе покоординатного спуска N £ 2×n, где n- количество управляемых параметров X = ( x ₁ , x ₂ .,…, x_n ).

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

И, наконец, в методе второго порядка - методе Ньютона N = 3 × n ².

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

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

Начнём рассмотрение методов поиска нулевого порядка. В методе случайного поиска исходными данными являются требуемая точность метода e, начальная точка поиска Х⁰ = ( x ₁ ⁰ , x ₂ ⁰ , …, x_n ⁰ ) и величина шага поиска h.

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

 

                           (6.19)   

 

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

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

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

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

 

Рис. 6.3. К методу случайного поиска

 

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

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

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

Исходными данными в методе покоординатного спуска являются величина шага h и начальная точка поиска           Х⁰ = ( x ₁ ⁰ , x ₂ . ⁰,…, x_n ⁰ ). Движение начинаем из точки Х⁰ вдоль оси x₁ в сторону увеличения координаты. Получим пробную точку (x ₁ ^k + h , x ₂ ^k ,…, x_n^k), k = 0. Сравним значение функции Ф(Х) с значением функции в предыдущей точке поиска Х^k.

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

В противном случае, пробную точку исключаем из рассмотрения и получаем новую пробную точку, двигаясь вдоль оси x ₁ в сторону уменьшения координаты. Получим пробную точку (x ₁ ^k – h , x ₂ ^k ,…, x_n^k). Проверяем, если , то продолжаем движение вдоль оси x₂ в сторону увеличения координаты. Получим пробную точку (x ₁ ^k + h , x ₂ ^k ,…, x_n^k), и т.д.

При построении траектории поиска повторное движение по точкам, вошедшим в траекторию поиска, запрещено.

Получение новых точек в методе покоординатного спуска продолжается до тех пор, пока не будет получена точка Х^k, для которой все соседние 2×n пробных точек (по всем направлениям x ₁ , x ₂ , …, x_n в сторону увеличения и уменьшения значения координаты) будут хуже, то есть . Тогда поиск прекращается и в качестве точки минимума выбирается последняя точка траектории поиска Х*= Х ^k.

Рассмотрим работу метода покоординатного спуска на примере (рис. 2.21): n = 2, X = (x ₁ , x ₂), Ф( x ₁ , x ₂ ) ® min,      Ф( x ₁ , x ₂ ) = ( x ₁ – 1)² + ( x ₂ – 2)², h = 1, Х⁰ = (0, 1).

1. Начинаем движение вдоль оси x ₁ в сторону увеличения

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

                                    

        ( x ₁ ⁰ + h , x ₂ ⁰ ) = (1, 1), Ф( ) = (1-1)² + (1-2)² = 1,   

 

                    Ф(Х⁰) = (0-1)² + (1-2)² = 2,

 

то есть

 

Ф( ) < Ф(Х⁰) ® Х¹ = (1, 1).

 

 

                            Рис. 6.4

 

2. Продолжаем движение вдоль оси x ₁ от точки Х¹ в сторону увеличения координаты. Получим пробную точку

 

 =( x ₁ ¹ + h , x ₂ ¹ ) = (2, 1), Ф( ) = (2-1)² + (1-2)² = 2,

 

              Ф(Х¹) = (1-1)² + (1-2)² = 1,

 

то есть Ф( ) > Ф(Х¹) – пробная точка с координатами (2, 1) исключается из рассмотрения, а поиск минимума продолжается из точки Х¹.

3. Продолжаем движение вдоль оси x ₂ от точки Х¹ в сторону увеличения координаты. Получим пробную точку

 

     = ( x ₁ ¹ , x ₂ ¹ + h) = (1, 2), Ф( ) = (1-1)² + (2-2)² = 0,

 

                         Ф(Х¹) = (1-1)² + (1-2)² = 1,

 

то есть

 

Ф( ) < Ф(Х¹) ® Х² = (1, 2).         

  

4. Продолжаем движение вдоль оси x ₂ от точки Х² в сторону увеличения координаты. Получим пробную точку

 

        = ( x ₁ ² , x ₂ ² + h) = (1, 3), Ф( ) = (1-1)² + (3-2)² = 1,

                                                    

              Ф(Х²) = (1-1)² + (2-2)² = 0,

 

то есть Ф( ) > Ф(Х²) – пробная точка с координатами (1, 3) исключается из рассмотрения, а поиск минимума продолжается из точки Х².

    5. Продолжаем движение вдоль оси x ₁ от точки Х² в сторону увеличения координаты. Получим пробную точку

                                          

 = (x ₁ ² + h , x ₂ ² ) = (2, 2), Ф( ) = (2-1)² + (2-2)² =1,

                                                    

Ф(Х²) = (1-1)² + (2 - 2)² = 0,

 

то есть Ф(Х^{^}) > Ф(Х²) – пробная точка с координатами (2, 2) исключается из рассмотрения, а поиск минимума продолжается из точки Х².    

     6. Продолжаем движение вдоль оси x ₁ от точки Х² в сторону уменьшения координаты. Получим пробную точку

 

  = (x ₁ ² - h , x ₂ ²) = (0, 2), Ф( ) = (0-1)²+(2-2)² = 1,

          

                         Ф(Х²) = (1-1)² + (2 - 2)² = 0,

 

то есть Ф( ) > Ф(Х²) – пробная точка с координатами (0, 2) исключается из рассмотрения, а поиск минимума закончен, так как для точки Х² выполнено условие прекращения поиска. Точкой минимума функции Ф( x ₁ , x ₂ ) = (x ₁ – 1)² + (x ₂ – 2)² является Х^* = Х².

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

 

.

 

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

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

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

     – градиентный метод с постоянным шагом,

– градиентный метод с дроблением шага,

– метод наискорейшего спуска,

– метод Давидона-Флетчера-Пауэлла (ДФП),

– двухуровневый адаптивный метод.

В градиентном методе с постоянным шагом исходными данными являются требуемая точность e, начальная точка поиска Х⁰ и шаг поиска h.

Получение новых точек производится по формуле:

 

Х ^k+1 = Х ^k – h × grad Ф ( Х ^k ), k=0,1,2,…          (6.20)

 

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

 

    Х ^k+1 = Х ^k + h × grad Ф ( Х ^k ), k = 0, 1, 2, …         (6.21)

 

Каждая из формул (6.20), (6.21) является векторным соотношением, включающим n уравнений. Например, с учетом Х ^{k +1} = ( x ₁ ^{k +1} , x ₂ ^{k +1} ,…, x_n^{k +1} ), Х ^k =( x ₁ ^k , x ₂ ^k ,…, x_n^k ) :

      (6.22)

 

или, в скалярном виде,

 

              (6.23)

 

В общем виде (2.61) можно записать:

 

            (6.24)

В качестве условия прекращения поиска во всех градиентных методах используется, как правило, комбинация двух условий: çФ( X^{k +1} ) - Ф( X^k ) ç £ e или  для всех i =1, …, n.

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

        Рассмотрим пример поиска минимума градиентным методом с постоянным шагом для той же функции, что и в методе покоординатного спуска: 

 

                     n = 2, X = (x ₁ , x ₂), e =0.1,

Ф( x ₁ , x ₂ ) = ( x ₁ – 1)² + ( x ₂ – 2)² ® min, h = 0,3, Х⁰ = (0, 1).

 

1. Получим точку Х¹ по формуле (2.45):

 

Ф( X ¹ ) = (0.6–1)² + (1.6–2)² = 0.32, Ф( X ⁰ ) = (0 –1)² + (1–2)² = 2.

 

ç Ф( X ¹ ) - Ф( X ⁰ ) ç=1,68 > e = 0,1 Þ продолжаем поиск.

 

2. Получим точку Х² по формуле (2.45):

Ф( X ² ) = (0.84–1)² + (1.84–2)² = 0.05,

Ф( X ¹ ) = (0,6 –1)² + (1,6–2)² = 0,32.

 

ç Ф( X ¹ ) - Ф( X ⁰ ) ç=0,27 > e = 0,1 Þ продолжаем поиск.

 

3. Аналогично получим X³:

 

Ф( X ³ ) = (0.94–1)² + (1.94–2)² = 0.007,

Ф( X ³ ) = (0,84 –1)² + (1,84–2)² = 0,05.

Так как условие прекращения поиска выполнено, найдено Х^* = X ³ = (0.94, 1.94) с точностью e = 0.1.

Траектория поиска для данного примера приведена на рис. 6.5.

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

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

 

                        

 

                                Рис. 6.5

 

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

Исходными данными являются требуемая точность e, начальная точка поиска Х⁰ и начальная величина шага поиска h (обычно h = 1). Получение новых точек производится по формуле:

 

Х ^k+1 = Х ^k – h_k × grad Ф ( Х ^k ), k=0,1,2,…,         (6.25)

 

где h_k – величина шага на k-ой итерации поиска, при h_k должно выполняться условие:

 

Ф(Х ^k – h_k × grad Ф(Х ^k ) ) £ Ф(Х ^k ) - e × h_k × ½ grad Ф(Х ^k ) ½ ².  (6.26)

 

Если величина h_k такова, что неравенство (2.64) не выполнено, то производится дробление шага до тех пор, пока данное условие не будет выполнено.

Дробление шага выполняется по формуле h_k = h_k × a , где 0 < a < 1.Такой подход позволяет сократить число итераций, но затраты на проведение одной итерации при этом несколько возрастают.

Это обеспечивает простоту замены и дополнения процедур, данных и знаний.

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

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

Получение новых точек производится по формуле:

 

Х ^k+1 = Х ^k – h_k × grad Ф ( Х ^k ), k=0,1,2,… ,        (6.27)

 

где h_k = arg min Ф(Х ^k – h_k × grad Ф(Х ^k )), то есть выбор шага производится по результатам одномерной оптимизации по параметру h (при 0 < h < ¥).                    

    Основная идея метода наискорейшего спуска заключается в том, что на каждой итерации метода выбирается максимально возможная величина шага в направлении наискорейшего убывания целевой функции, то есть в направлении вектора-антиградиента функции Ф(Х) в точке Х ^k . (рис. 2.23).

При выборе оптимальной величины шага необходимо из множества Х_М = {Х ½ Х= Х ^k – h × grad Ф(Х ^k ), h Î [0, ¥ )} точек, лежащих на векторе градиенте функции Ф(Х), построенном в точке Х ^k выбрать ту, где функция Ф( h ) = Ф(Х ^k – h × grad Ф(Х ^k )) принимает минимальное значение.

Рис. 6.6

           

Рассмотрим пример поиска минимума для той же функции, что и в градиентном методе с постоянным шагом и в методе покоординатного спуска: 

 

                     n = 2, X = ( x 1, x 2), e = 0.1,

 

       Ф( x 1, x 2) = ( x 1 – 1)² + ( x 2 – 2)² ® min , Х⁰=( 0, 1 ).

 

1. Получим точку Х¹ :

 

X¹ = X₀ – h₁∙grad Ф( X⁰),

 

где h ₁ = arg min Ф( X ⁰ – h ∙ grad Ф( X ⁰ )) при 0 < h < ¥, то есть h ₁ – это аргумент, при котором достигается минимальное значение функции Ф( h ) = Ф(Х⁰ – h × grad Ф(Х⁰)).

 

 

Таким образом, Ф( h ) = 2×(2×h-1)². Теперь нужно найти h, при котором Ф( h ) принимает минимальное значение. В точке экстремума Ф^/(h) = 0:

 

[2×(2×h-1)²]^/_h = 2×2×(2×h-1)×2=8×(2×h-1)=0.

 

Следовательно, h ₁ = 1/2 – оптимальный шаг на первой итерации метода наискорейшего спуска. Тогда

 

Х¹= Х⁰ – 1/2×grad Ф(Х⁰),

то есть     

           

x ₁ ¹ =0 -1/2×[2×(0-1)] = 1, x₂¹ = 1-1/2×[2×(1-2)] = 2 Þ Х¹ = (1, 2).

 

Проверим выполнение условий прекращения поиска в точке поиска Х¹ = (1, 2). Первое условие не выполнено

 

 çФ( X ¹ )-Ф( X ⁰ )ç= ç0-2 ç=2 > e = 0.1, но справедливо

 

 

 

то есть все частные производные с точностью e можно считать равными нулю, точка минимума найдена: Х*=Х¹=(1, 2). Траектория поиска приведена на рис. 6.7.

Таким образом, метод наискорейшего спуска нашел точку минимума целевой функции за одну итерацию (из-за того, что линии уровня функции Ф( x ₁ , x ₂ ) = (x ₁ – 1)² + (x ₂ – 2)². ((x ₁ – 1)² + (x ₂–2)² = const – уравнение окружности, и вектор антиградиент из любой точки точно направлен в точку минимума – центр окружности).

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

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

 

                     Рис. 6.7

 

Исходными данными являются требуемая точность e, начальная точка поиска Х⁰ и начальная величина шага поиска h (обычно ). Получение новых точек производится по формуле:

 

Х ^k+1 = Х ^k – h_k+1 × grad Ф(Х^k), k = 0,1,2,…,        (6.28)

 

где шаг h_{k +1} может быть рассчитан по одной из двух формул: h_{k +1} = h_k + l _{k +1} × a _k, или h_{k +1} = h_k × exp ( l _{k +1} × a _k ). В качестве понижающего коэффициента выбирают обычно l _k =1/ k, где        k – номер итерации поискового метода.

Смысл применения коэффициента l _k заключается в том, что на каждой итерации производится некоторая корректировка величины шага, при этом чем больше номер итерации метода поиска, тем ближе очередная точка поиска к точке экстремума и тем аккуратнее (меньше) должна быть корректировка шага с тем, чтобы не допустить удаления от точки экстремума.

Величина a _k определяет знак такой корректировки (при a _k>0 шаг увеличивается, а при a _k<0 уменьшается):                                                               

                                           Ù

           a _k =sign{(grad Ф ( Х ^k ),grad Ф ( Х ))},

 

то есть a _k – это знак скалярного произведения векторов                                                                       градиентов целевой функции в точках Х ^k и , где            = Х ^k – h_k × grad Ф(Х ^k ) пробная точка, а h_k – это шаг, который был использован для получения точки Х ^k на предыдущей итерации метода.

Знак скалярного произведения двух векторов позволяет оценить величину угла между данными векторами (обозначим этот угол b). Если b < 90°, то скалярное произведение должно быть положительным, в противном случае – отрицательным. С учетом вышеизложенного нетрудно понять принцип корректировки величины шага в двухуровневом адаптивном методе. Если угол между антиградиентами b < 90° (острый угол), то направление поиска из точки Х ^k выбрано правильно, и величину шага можно увеличить (рис. 6.8).

Рис. 6.8. Выбор направления поиска при b < 90°

 

Если же угол между антиградиентами b > 90° (тупой угол), то направление поиска из точки Х ^k удаляет нас от точки минимума Х*, и шаг нужно уменьшить (рис. 6.9).

    Рис. 6.9. Выбор направления поиска при b > 90°

 

Метод носит название двухуровневого, так как на каждой итерации поиска анализируются не одна, а две точки и строятся два вектора антиградиента.

Это, конечно, увеличивает затраты на проведение одной итерации, но позволяет проводить адаптацию (настройку) величины шага h_{k +1} на поведение случайных факторов.

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

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

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

 

j (Х) = Ф(Х⁰) + (Х - Х⁰) ^т × grad Ф(Х⁰) + ½ G ( X ⁰ ) × (Х - Х⁰), (6.29)                                                                               

 

где G ( X ⁰ ) - матрица Гессе (гессиан, матрица вторых производных), вычисленная в точке Х⁰:

 

               ¶ ²Ф(Х )¶ ²Ф(Х ) . . . ¶ ²Ф(Х )                                             

             ¶ x ₁ ²        ¶ x ₁ ¶ x ₂                    ¶ x ₁ ¶ x_n

G ( X ) = ¶ ²Ф(Х )¶ ²Ф(Х ) . . . ¶ ²Ф(Х )                                             

              ¶ x ₂ ¶ x ₁    ¶ x ₂ ²                     ¶ x ₂ ¶ x_n

            ¶ ²Ф(Х )¶ ²Ф(Х ) . . .  ¶ ²Ф(Х )                                             

                    ¶ x_n ¶ x ₁  ¶ x_n ¶ x ₂                        ¶ x_n ^{2     .}

 

Формула (2.67) представляет собой первые три члена разложения функции Ф(Х) в ряд Тейлора в окрестности точки Х⁰, поэтому при аппроксимации функции Ф(Х) функцией j (Х) возникает ошибка не более чем ½½Х-Х⁰½½³.

С учетом (2.67) в методе Ньютона исходными данными являются требуемая точность e, начальная точка поиска Х⁰ и получение новых точек производится по формуле:

 

Х ^{k +1} = Х ^k – G ^-1 (Х ^k ) × grad Ф(Х^k), k=0,1,2,…, (6.30)

 

где G ^-1 (Х ^k ) – матрица, обратная к матрице Гессе, вычисленная в точке поиска Х ^k ( G (Х ^k ) × G ^-1 (Х ^k ) = I,                          

 

   1 0 … 0                                                      

I =        0 1 … 0 - единичная матрица.

0 0 … 1

 

Рассмотрим пример поиска минимума для той же функции, что и в градиентном методе с постоянным шагом и в методе покоординатного спуска: 

 

                       n = 2, X = ( x ₁ , x ₂ ), e = 0.1,

       Ф( x ₁ , x ₂ ) = ( x ₁ – 1)² + ( x ₂ – 2)² ® min , Х⁰=( 0, 1 ).

1. Получим точку Х¹:

 

X¹ = X⁰ – G^–1(X⁰)∙grad Ф(X⁰),

 

где

grad Ф(X⁰) = (2∙(x₁⁰–1)), 2∙(x₁⁰–1) = (–2, –2), то есть

или

x ₁ ¹ = 0 – (1/2∙(–2) + 0∙(–2)) = 1,

x ₂ ¹ = 1 – (0∙(–2) + 1/2∙(–2)) = 2,

X ¹ = (1, 2).

 

Проверим выполнение условий прекращения поиска: первое условие не выполнено

 

       çФ( X ¹ )-Ф( X ⁰ )ç= ç0 - 2 ç = 2 > e = 0.1,

 

но справедливо

 

то есть все частные производные с точностью e можно считать равными нулю, точка минимума найдена: Х* = Х¹ = (1, 2). Траектория поиска совпадает с траекторией метода наискорейшего спуска (рис. 2.24).

Главным недостатком метода Ньютона являются затраты на вычисление обратного гессиана G ^-1 (Х ^k ) на каждой итерации метода.

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

Достоинством данного метода является то, что он не требует вычисления обратного гессиана, а в качестве направления поиска в методе ДФП выбирается направление –Н _k × grad Ф(Х^k), где Н _k - положительно определенная симметричная матрица, которая заново рассчитывается на каждой итерации (шаге метода поиска) и приближает обратный гессиан G ^-1 (Х ^k ) (Н _k ® G ^-1 (Х ^k ) с увеличением k).        

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

Вычислительная процедура метода ДФП включает следующие шаги.

Исходными данными являются требуемая точность e, начальная точка поиска Х⁰ и начальная матрица Н₀ (обычно единичная матрица, Н₀ = I ).

1. На k-ой итерации метода известны точка поиска Х^k и матрица Н _k    (k = 0,1,…).

2. Обозначим направление поиска

 

                   d_k = -Н _k × gradФ(Х^k).

 

Находим оптимальную величину шага l _k в направлении d_k с помощью методов одномерной оптимизации (так же, как в методе наискорейшего спуска выбиралась величина в направлении веrтора антиградиента)

З. Обозначим v_k = l _k × d_k и получим новую точку поиска Х ^{k +1} = X^k + v_k .

4. Проверяем выполнение условия прекращения поиска .

Если ½v_k½£ e или ½grad Ф(Х ^{k +1} )½£ e , то решение найдено Х^* = Х ^{k +1}. В противном случае продолжаем вычисления.

5. Обозначим u_k = gradФ(Х^k+1) - gradФ(Х^k) и матрицу Н _{k +1} рассчитаем по формуле:

 

             H_{k +1} = H _k + A _k + B_k,                              (6.31)

 

где A_k = v _k . v _k ^T / (v _k ^T × u_k )_,   B_k = - H_k × u _k . u _k ^T . H _k / (u _k ^T × H_k × u_k )_.

A_k  и В _k – это вспомогательные матрицы размера n х n (v _k ^T соответствует вектору-строке, v _k означает вектор-столбец, результатом умножения n-мерной строки на n-мерный столбец является скалярная величина (число), а умножение столбца на строку дает матрицу размера n x n).

6. Увеличиваем номер итерации на единицу и переходим к пункту 2 данного алгоритма.

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

        

---

Дата добавления: 2019-09-13; просмотров: 1075; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!