Оптимизатор

| Векторизован |
в палитре на схеме

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

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

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

При наличии множества критериев, для формализации условия задачи оптимизации, обычно переходят от нескольких частных критериев q1, …, qm к одному общему критерию, который формируется в виде функции частных критериев. Такую процедуру называют свертыванием критериев. В результате получаем общий критерий (целевую функцию)

в виде функции от оптимизируемых параметров. Решение задачи многокритериальной оптимизации сводится к минимизации этого критерия. Один из наиболее часто используемых способов свертывания частных критериев — средний степенной критерий оптимальности. Именно он используется для свертывания критериев оптимизации в SimInTech:

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

Алгоритмы оптимизации

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

Алгоритм Поиск-2

Реализуется алгоритм деления шага пополам при одном оптимизируемом параметре (n = 1) и алгоритм преобразований матрицы направлений при n >1.

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

Направления поиска на k-том этапе задаются матрицей Sk. На очередном этапе производится серия спусков в направлениях векторов s1,...,sn, представляющих собой столбцы матрицы Sk . Векторы перемещений на каждом из спусков равны соответственно g1s1, ..., gnsn. После выполнения спусков матрица направлений преобразуется по формуле

где Λk - диагональная матрица, элементы которой равны λk = γi, если γi ≠0, и λk = 0.5, если γi = 0; Pk - ортогональная матрица.

Умножение на ортогональную матрицу необходимо для изменения набора направлений поиска. Если на всех этапах Pk = i , то направления поиска не изменяются от этапа к этапу и мы имеем алгоритм покоординатного спуска. Очевидно, что выбор матриц Pk существенно влияет на эффективность поиска.

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

Рассмотрим этапы алгоритма в многомерном случае.
  1. Начальная матрица направлений задается диагональной с элементами на главной диагонали, равными начальным приращениям по параметрам.
  2. Выполнить цикл для i = 1, …, n:
    1. Выполнить пробный щаг в направлении si: y = x + si

      Если этот шаг удачный ( f(y) < f(x) ), перейти к пункту c.

    2. Выполнить пробный шаг в противоположном направлении: y = x si

      Если оба пробных шага оказались неудачными, принять λ = 0.5 и перейти к пункту d.

    3. Выполнить спуск в выбранном направлении, в результате получим новую точку поиска x = x + γsi, принять λ = |γ|
    4. Принять si = λsi. Перейти к следующему значению счетчика цикла либо выйти из цикла (если i = n).
  3. Умножить матрицу направлений S на ортогональную матрицу P, задаваемую выражением.
  4. При выполнении условия окончания поиска завершить работу алгоритма, в противном случае - перейти к п.2 с новыми значениями вектора x и матрицы S.
Поиск прекращается при выполнении одного из следующих условий:
  • целевая функция достигла минимума (все требования выполняются);
  • превышено заданное число вычислений целевой функции;
  • приращения по каждому из параметров стали меньше заданного значения;
  • принудительный останов.

Алгоритм Поиск-4

Реализуется алгоритм квадратичной интерполяции при одном оптимизируемом параметре (n = 1) и алгоритм преобразований вращения и растяжения-сжатия (n > 1).

Рассмотрим алгоритм при n > 1. Он основан на выполнении преобразований растяжения - сжатия и преобразований вращения для такого преобразования системы координат, при котором матрица вторых производных (матрица Гессе) приближается к единичной, а направления поиска становятся сопряженными. Этот алгоритм использует квадратичную интерполяцию.

Пусть H - симметричная положительно-определенная матрица. Будем строить последовательность матриц

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

где Λk - диагональная матрица с элементами λi = hii−1/2 (hii - диагональные элементы Hk-1); Pk - ортогональная матрица.

После умножения матрицы Hk−1 слева и справа на Λk получаем матрицу с единичными диагональными элементами. Можно надеяться, что при подходящем выборе ортогональных матриц Pk матрица Hk будет стремиться к единичной. На этом, в частности, основан метод вращений для расчета собственных значений симметричных матриц.

Рассмотрим задачу поиска минимума функции нескольких переменных. На k-м этапе поиска поочередно минимизируется функция в направлениях векторов s1 ,...,sn, представляющих собой столбцы матрицы Sk. Для нахождения точки минимума в направлении si используется квадратичная интерполяция по трем равноотстоящим точкам z = x − asi, x , y = x + asi.

Одновременно для каждого направления вычисляется

После выполнения серии спусков матрица S преобразуется по формуле

где Λk - диагональная матрица, элементы которой определяются по выражению; Pk - некоторая ортогональная матрица.

Для квадратичной целевой функции матрица SkT H Sk , где H - матрица Гессе, совпадает с матрицей Hk . Таким образом, при надлежащем выборе матриц Pk для квадратичной функции получаем SkT H Ski и направления поиска приближаются к сопряженным. В рассматриваемом алгоритме матрицы Pk одинаковы на всех этапах и определяются по формуле формуле.

Этапы работы алгоритма Поиск-4 аналогичны рассмотренным выше этапам алгоритма Поиск-2.

Алгоритм Симплекс

Используется метод «деформируемого многогранника» Недлера и Мида.

В методе Нелдера-Мида минимизируется функция n независимых переменных с использованием n+1 вершин деформируемого многогранника. Каждая вершина может быть идентифицирована вектором x . Вершина (точка), в которой значение f(x) максимально, проектируется через центр тяжести (центроид) оставшихся вершин. Улучшенные (меньшие) значения целевой функции находятся последовательной заменой точки с максимальным значением f(x) на более “хорошие” точки, пока не будет найден минимум f(x).

Далее кратко излагается суть алгоритма.

Пусть xi(k) = [xi1(k),..., xij(k),..., xin(k)]T, i = 1,..., n+1, является i-й вершиной (точкой) на k-том этапе поиска, k = 0, 1,..., и пусть значение целевой функции в xi(k) равно f(xi(k)). Также отметим векторы многогранника, которые дают максимальное и минимальное значения.

Определим f(xh(k)) = max{f(x1(k)),...,f(xn+1(k))},

где xh(k) = xi(k) , и

f(xl(k)) = min{f(x1(k)),...,f(xn+1(k)),

где xl(k) = xi(k).

Поскольку многогранник в En состоит из (n+1) вершин x1,...,xn+1, пусть xn+2 будет центром тяжести всех вершин, исключая xh.

Тогда координаты этого центра определяются формулой

где индекс j обозначает координатное направление.

Начальный симплекс обычно (не всегда) выбирается в виде регулярного симплекса, причем начало координат можно поместить в центр тяжести. Процедура отыскания вершины в En , в которой f(x) имеет лучшее значение, состоит из следующих операций:
  • Отражение - проектирование xh(k) через центр тяжести в соответствии с выражением

    где a является коэффициентом отражения; xn+2(k) - центр тяжести, вычисляемый по формуле; xh(k) - вершина, в которой функция f(x) принимает наибольшее из n+1 ее значений на k - том этапе.

  • Растяжение. Эта операция состоит в следующем: если f(xn+3(k)) <= f(xl(k)), то вектор(xn+3(k)−xn+2(k)) растягивается в соответствии с соотношением

    где g >1 представляет собой коэффициент растяжения.

    Если f(xn+4(k)) < f(xl(k)) , то xh(k) заменяется на xn+4(k) и процедура продолжается снова с операции 1 при k = k+1. В противном случае xh(k) заменяется на xn+3(k) и также осуществляется переход к операции 1 при k = k+1.

  • Сжатие. Если f(xn+3(k)) > f(xi(k)) для всех i < > h , то вектор (xh(k)−xn+2(k)) сжимается в соответствии с формулой

    где 0 < b <1 представляет собой коэффициент сжатия.

    Затем xh(k) заменяем на xn+5(k) и возвращаемся к операции 1 для продолжения поиска на (k+1) шаге.

  • Редукция. Если f(xn+5(k)) > f(xh(k)), все векторы (xi(k)−xl(k)), i = 1, ..., n +1, уменьшаются в 2 раза с отсчетом от xl(k) в соответствии с формулой
    Затем возвращаемся к операции 1 для продолжения поиска на (k + 1) шаге.

Критерий окончания поиска- проверка условия

где e - произвольное малое число, а f(xn+2(k)) - значение целевой функции в центре тяжести xn+2(k).

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

После того, как деформируемый многогранник подходящим образом масштабируется, его размеры должны поддерживаться неизменными, пока изменения в топологии задачи не потребуют применения многогранника другой формы. Анализ, проведенный Нелдером и Мидом, показал, что компромиссное значение a = 1. Ими также рекомендованы значения b = 0.5, g = 2. Более поздние исследования показали, что рекомендуются диапазоны 0.4≤b≤ 0.6, 2.8 ≤g≤3.0, причем при 0< b < 0.4 существует вероятность того, что из-за уплощения многогранника будет иметь место преждевременное окончание процесса, а при b>0.6 может потребоваться большее число шагов для достижения окончательного решения.

Алгоритм наискорейшего спуска

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

или

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

решая одномерную задачу минимизации с использованием некоторого метода. В этом случае получаем алгоритм наискорейшего спуска. Если λ определяется в результате одномерной минимизации, то градиент в точке очередного приближения будет ортогонален направлению предыдущего спуска ∇f()⟂k.

Метод сопряженных градиентов

В алгоритме наискорейшего спуска на каждом этапе поиска используется только текущая информация о функцииf(k) и градиенте ∇f(k). В алгоритмах сопряженных градиентов используется информация о поиске на предыдущих этапах спуска.

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

При выборе весов используется только текущий градиент и градиент в предыдущей точке.

В начальной точке 0 направление спуска 0 = −∇f(0) :

где λ0 выбирается из соображений минимальности целевой функции в данном направлении

Новое направление поиска

где ω1 выбирается так, чтобы сделать направления 1 и 0 сопряженными по отношению к матрице H :

Для квадратичной функции справедливы соотношения:

где Δ = 0,

Если положить = 1, тогда 10 = λ0 0 и

Воспользуемся выражением выше, чтобы исключить (0)T из уравнения. Для квадратичной функции H = HT , поэтому транспонировав выражение и умножив справа на H−1, получим

и далее

Следовательно, для сопряженности 0 и 1

Вследствие изложенных ранее свойств сопряженности все перекрестные члены исчезают. Учитывая, что 0 = −∇f(0) и, следовательно,

получим для ω1 следующее соотношение:

Направление поиска 2 строится в виде линейной комбинации векторов −∇f(2), 0, 1, причем так, чтобы оно было сопряженным с 1.

Если распространить сделанные выкладки на 2, 3, ..., опуская их содержание и учитывая, что (k)Tf(k+1) = 0 приводит к ∇Tf(k)∇f(k+1) = 0, можно получить общее выражение для ωk:

Все весовые коэффициенты, предшествующие ωk, что особенно интересно, оказываются нулевыми.

Полностью алгоритм описывается следующей последовательностью действий:
  1. В точке начального приближения 0 вычисляется 0 = ∇f(0) .
  2. На k-м шаге с помощью одномерного поиска в направлении k определяется минимум функции, то есть решается задача
    и находится очередное приближение k+1 = k + λk · k.
  3. Вычисляется f(k+1) и ∇f(k+1).
  4. Определяется направление k+1 = −∇f(k+1) + ωk+1 · k.
  5. Алгоритм заканчивается, если ||k|| < ε, где ε - заданная величина.

После n+1 итераций ( k = n), если не произошёл останов алгоритма, процедура циклически повторяется с заменой 0 на n+1и возвратом на первый пункт алгоритма. Если исходная функция является квадратичной, то (n+1)-е приближение даст точку экстремума данной функции. Описанный алгоритм с построением ωk по формулам соответствует методу сопряженных градиентов Флетчера-Ривса.

В модификации Полака-Рибьера (Пшеничного) метод сопряженных градиентов отличается только вычислением

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

Свойства

Работа с блоком оптимизации.

На вход блока подается вектор критериев оптимизации. На основании их значений, используя численные методы оптимизации, происходит подбор значения вектора параметров оптимизации так, чтобы значения критериев лежали в необходимом диапазоне. Рассмотрим примеры использования блока оптимизации параметров модели. В пакет поставки SimInTech входит набор демонстрационных проектов, в том числе показывающих работу блока оптимизации. Проекты находятся по адресу "\Demo\Оптимизация". Откроем проект "\в динамике\в динамике.prt". Синусоидальный сигнал подается на две системы — эталонную и настраиваемую. Далее вычитатель определяет сигнал рассогласования между системами и подает его на вход блока оптимизации, который, осуществляя сравнения сигнала рассогласования с его целевым значением, а также применяя методы численной оптимизации, генерирует на выходе некий корректирующий множитель, на который домножается сигнал настраиваемой системы с целью минимизации отклонения от эталонной. В данном случае параметром оптимизации является некий корректирующий коэффициент, а критерием оптимизации — величина рассогласования между выходами эталонной и настраиваиваемой системами. В ходе динамического расчета в течение одного цикла моделирования системы, блок оптимизации подбирает такой корректирующий коэффициент для настраиваемой системы, что сигнал рассогласования между эталонной и настраиваемой системами стремится к нулю. Второй пример "\c повторениями расчётов\С повторениями расчётов.prt" показывает работу блока в режиме повторения расчетов. В данном примере источник равномерного шума аналогично подается на две системы — некую эталонную и настраиваемую. Затем вычитатель формирует сигнал рассогласования, подаваемый на блок RMS, считающий среднеквадратичное отклонение сигнала рассогласования за один полный цикл расчета системы. Блок оптимизации рассчитывает корректирующий коэффициент, пытаясь минимизировать среднеквадратичное отклонение. В итоге, за несколько последовательных расчетов модели, сигнал рассогласования стал стремиться к нулю, и форма сигналов практически совпала. Таким образом системе понадобилось 5 последовательных расчетов, чтобы скорректировать сигнал настраиваемой системы так , чтобы он совпадал с эталонной.