Методы поиска экстремума функции цели

 

Скалярное значение функции цели (9.7) в пределах возможного изменения вектора x может иметь несколько или множество локальных минимумов и один глобальный x_опт. Выражение (9.7) для глобального минимума справедливо при всех x, принадлежащих пространству Rⁿ , а для локального – только в части этого пространства.

Сами методы поиска целевой функции, т.е. определение x_опт , классифицируется по нескольким признакам:

· по виду искомого минимума – локальные и глобальные;

· по характерной черте метода – с использованием только значений, принимаемых целевой функцией F_ц (x) (методы прямого поиска), или как значений F_ц (x), так и ее первых и вторых производных (градиентные методы);

· по способу перехода от одной точки к другой на каждом шаге поиска – детерминированные и случайные;

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

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

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

 

 

 

Рис. 6.52 Обобщенная структурная схема программы поиска локального и глобального минимума

 

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

Погрупповой метод последовательного поиска. Пусть число переменных параметров есть N и каждый из параметров x_n изменяется с шагом ∆ x_n в пределах от x_n.мин до x_n.макс и принимает M дискретных значений. Тогда при последовательном переборе всех комбинаций множества параметров x_n общее число рассчитываемых вариантов составит Q=M^N. Это число может быть столь большим (например, при M=10 и N=6 значение Q=10⁶), что даже расчет на быстродействующей ЭВМ может оказаться недопустимо длительным. Поголовный перебор всех вариантов можно исключить, если параметры разбить на группы, включающие только взаимозависимые x_n. Далее производится перебор всех x_n только внутри группы с определением набора параметров, соответствующих минимуму целевой функции. Последовательно переходя от одной группы параметров к другой, определяют вектор x_опт, включающий все параметры x_n. Так, например, в приведенном примере из 6-ти параметров при возможности их разбиения на две группы по 3 параметра общее число рассчитываемых вариантов составит Q=2*10³=2000, т.е. почти на три порядка меньше, чем в первом варианте. Однако, воспользоваться таким простым и надежным способом поиска глобального минимума можно только при сильной зависимости параметров внутри одной группы и слабой – между разными.

Покоординатный метод. Здесь сначала дискретно изменяется только параметр x₁ при постоянных значениях всех остальных параметров x_n до тех пор, пока целевая функция не станет минимальной. Полученное значение x₁ фиксируется и в новом цикле начинается изменение параметра x₂ при неизменных значениях остальных параметров и т.д., вплоть до изменения параметра x_n. Подобная процедура повторяется несколько раз, в результате чего определяется вектор x_опт. Как и в предыдущем случае, такой простой алгоритм успешно действует только при слабой зависимости между собой всех параметров x_n.

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

Метод оврагов. Этот метод пригоден для так называемых хорошо организованных функций, при которых переменные параметры x₁,x₂, …, x_n можно разбить на две группы: сильно и слабо влияющие на целевую функцию F_ц. Параметры 1-й группы меняются с относительно большим шагом, 2-й – c малым. После большого шага в рамках 1-й группы параметров производится локальный поиск с малым шагом в рамках 2-й группы параметров. Такая итерационная процедура позволяет относительно быстро продвигаться по так называемому «оврагу» к глобальному минимумy функции цели.

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

Математический пакет программ «Mathcad» предлагает две функции – Maximize и Minimize (обе расположены в категории функций «Решение») – для реализации процедуры оптимизации, связанной с поиском вектора x_опт без вычисления производных функции цели.

С помощью функции Maximize (F, x₁, x₂, …, x_n), где F – функция цели, x₁, x₂, …, x_n – варьируемые параметры объекта оптимизации, осуществляется поиск параметров, соответствующих максимуму функций F.

С помощью функции Minimize (F, x₁, x₂, …, x_n) – минимуму функции F.

 

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

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

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

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

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

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

 

 

f_n1..f_n2 – полоса пропускания;

f_m1..f_m2 – полоса заграждения;

f_S1..f_S2 – полоса частот фазовой характеристики;

B_п(f_k) – полученное затухание фильтра в полосе пропускания на частоте f_k;

B_п.тр(f_k) – требуемое затухание фильтра в полосе пропускания;

B_з(f_k) – полученное затухание фильтра в полосе заграждения на частоте f_k;

B_з.тр(f_k) – требуемое затухание фильтра в полосе заграждения;

φ (f_k) – полученное значение ФЧХ на частоте f = f_k;

φ_тр (f_k) – требуемое значение ФЧХ на той же частоте f = f_k;

V₁, V₂, V₃ – коэффициенты веса, определяющие соотношение требований по затуханию, предъявляющих к полосам пропускания и заграждения, а также другим параметрам.

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

 

Введем обозначения:

A_min – требуемое затухание фильтра в полосе заграждения;

A_max – требуемое затухание (допустимая неравномерность) фильтра в полосе пропускания;

Ω – текучая частота;

Ω_z – нормированная частота среза (отношение граничной частоты полосы заграждения к граничной частоте полосы пропускания);

Н_Аb(Ω) – амплитудно-частотная характеристика ФНЧ;

L_Аb(Ω) – рабочие затухание ФНЧ;

β_b (Ω) – фазо-частотная характеристика ФНЧ;

τ_b(Ω) – групповое время запаздывания;

 

Пусть заданы значения:

A_max: ≤ 2; A_min : ≥ 20; Ω_z: = 1.6;

 

Задаем пределы изменения и шаг изменения текущей частоты:

Ω: = 0.2 * Ωz/100 … 2 * Ωz

 

Wzcp – нормированная частота среза (fгрпн/fв)

Nb – порядок аналогового ФНЧ Баттерворта

Nc – порядок цифрового ФНЧ Чбышева

w – текущая частота

Hb(w) – АЧХ ФНЧ Баттерворта

Нс(w) – ФЧХ ФНЧ Чебышева

τb(w) – групповое время запаздывания ФНЧ Баттерворта

τс(w) – групповое время запаздывания ФНЧ Чебышева

Amin1 – требуемое рабочее ослабление на частоте среза для фильтра Баттерворта

Amin2 – требуемое рабочее ослабление на частоте среза для фильтра Чебышева

Amax1 и Amax2 – допустимые неравномерности в полосе пропускания фильтров Баттерворта и Чебышева

 

Задание начальных данных

 

Допустимые значения группового времени запаздывания (ГВЗ) ФНЧ для аудиосогналов (из норм для трактов звукового вещания)

 

Fb – верхняя частота в спектре звукового сигнала

Amin – рабочее затухание на частоте среза (граничная частота полосы заграждения)

Amax – неравномерность в полосе пропускания

Допустимая неравномерность группового времени запаздывания τd(w)

 

Fb:=10000

 

w1	40/ Fb = 4×10-3	τd(w1)	55 мс
w2	75/ Fb = 7,5×10-3	τd(w2)	24 мс
w3	100/ Fb = 0,01	τd(w3)	20 мс
w4	6400/ Fb = 0,64	τd(w4)	5 мс
w5	7000/ Fb = 0,7	τd(w5)	10 мс
w6	14000/ Fb = 1,4	τd(w6)	8 мс
w7	15000/ Fb = 1,5	τd(w7)	12 мс

 

 

 

 

 

 

 

 

Рис. 6.53 Нормы на ГВЗ

 

Запишем выражения, необходимые для определения τb(w). Сначала определяется минимально необходимый порядок фильтра, удовлетворяющий заданным параметрам.

 

То есть требуется ФНЧ Баттерворта 6-го порядка. Далее следует определить наибольший порядок фильтра, удовлетворяющий требованиям по групповой задержке.

 

 

 

 

 

Запишем функцию цели для нахождения максимального порядка ФНЧ, удовлетворяющего требованиям по τ. Нормированные частоты выбраны 0,64 (по минимально допустимому значению групповой задержки) и 1 (соответствет Fb). Будем искать минимум функции цели, при котором задержка не превышает допустимого значения.

 

 

Введем пределы варьируемых параметров с помощью ключевого слова Given:

 

 

 

Поскольку N – целое число и N может быть меньше 6 для удовлетворения требований по затуханию чем меньше N, тем меньше получается значение τb, то принимаем N=6 и производим проверку на требуемых частотах:

Таким образом, допустимо использование ФНЧ Баттерворта порядка 7, а требуется Nb=6. Следовательно, для Фнч Баттерворта следует принять порядок фильтра равным 6.

Определим теперь требуемый порядок ФНЧ Чебышева:

 

 

То есть требуется ФНЧ Чебышева 4-го порядка. Для него произведем проверку получаемого времени задержки на нормированных частотах 0.64 и 1.

Задание начальных значений параметров

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис 6.54 Групповое время запаздывания (в мс)

 

Таким образом ФНЧ Чебышева 4-го порядка удовлетворяет всем предъявляемым требованиям.

 

 

Рис. 6.55 АЧХ ФНЧ Чебышева 4-го порядка

 

 

 

 

 

 

 

Рис 6.56 Зависимости допустимой и полученных групповых задержек

 

Вопросы для самоконтроля

 

1. Понятие оптимизациив расчетах РЭА

2. Понятие функции цели

3. Меры расхождения при определении функции цели

4. Методы поиска экстремума функции цели

5. Пример записи функции цели при синтезе фильтров