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

3.1 Поисковый алгоритм оптимизации обобщенных критериев

В рассматриваемом случае задача оптимального проектирования УЦОС сводится к решению задачи минимизации скалярной функции полезности. С учетом ограничений на переменные и способов свертывания ЛКО она решается как задача нелинейного программирования (НЛП) с ограничениями [3, 5, 7, 13, 18, 93]

, (3.1)

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

Возможные методы решения задачи НЛП типа (3.1) можно разбить на две группы: методы без вычисления производных (методы 0 – го порядка) и методы, использующие производные (методы 1 – го и 2 – го порядков) [3, 13, 34, 93]. Методы первой группы используются в тех случаях, когда не требуется гладкость и непрерывность целевой функции. Кроме того, их часто применяют на начальном этапе оптимизации, когда требуется выйти в окрестность решения, или получить хорошее начальное приближение. Методы второй группы сходятся намного быстрее и они эффективны на промежуточном и заключительном этапах процесса поиска оптимума.

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

Для выбора методов решения задачи НЛП (3.1) целесообразно воспользоваться методикой, предложенной в [3]и развитой в работах [25, 53], которая позволяет провести тестовые испытания алгоритмов и программ оптимизации и с большой степенью достоверности отобрать коллектив наилучших конкурирующих алгоритмов. При практических исследованиях, для выбора коллектива оптимизирующих алгоритмов 0 – го порядка, сравнивались программы, реализующие алгоритмы Гаусса – Зейделя, различные варианты случайного поиска, деформируемого многогранника, Флетчера – Пауэлла, попарно – координатного спуска [3, 7, 12, 23, 26, 30, 35, 41, 62, 74, 93]. Наилучшими оказались вариант поискового алгоритма, предложенного автором, метод деформируемого многогранника (ДМ) и метод статистического градиента (СГ). Поскольку алгоритмы методов ДМ и СГ претерпели при реализации лишь незначительные модификации, то в данном пункте рассматривается только особенности поискового алгоритма.

Суть предлагаемого алгоритма поискового метода (ПМ) 0-го порядка заключается в проведении серии пробных испытаний критерия и сокращении по результатам пробных испытаний области поиска экстремума за счет исключения из рассмотрения тех участков области допустимых значений варьируемых параметров, в которых значения оказались большими некоторого порогового для данного шага оптимизации уровня [41]. При этом учитываются ограничения, накладываемые на варьируемые параметры и выходные характеристики в различных точках допустимой области изменения варьируемых параметров. В результате происходит постепенная локализация области решения до определения точки оптимума.

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

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

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

Метод можно отнести к методам поиска глобального экстремума, так как если на -ом шаге оптимизации наименьшим оказалось значение из области локального минимума, то из-за отсутствия связи между и центром распределения пробных значений , на следующем шаге будут моделироваться значения и из области глобального минимума [24], т. к. они обязательно попадут в область допустимых значений .

Поиск экстремума с помощью метода прекращается, если выполняются условия:

(3.2)

или

(3.3)

где ; -максимально допустимая величина целевой функции; и ₂ - минимально допустимые величины уменьшения целевой функции и интервалов изменения варьируемых параметров.

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

Константы , ₁, ₂ необходимо выбирать осмотрительно, так как от них существенным образом зависит количество оценок , затраченных на поиск экстремума, время решения задачи и успешность поиска в целом. Экспериментальные исследования показывают, что вполне удовлетворительными являются следующие значения этих констант:

Значение  выбирается с учетом необходимой точности получения решения данной экстремальной задачи.

Использование алгоритма для решения практических задач оптимизации характеристик УЦОС показывает [41], что при помощи рассматриваемого алгоритма область оптимума локализуется достаточно быстро (15-20 шагов). Но внутри ее сходимость очень сильно замедляется и конечный результат оптимизации за приемлемое число оценок целевой функции удается получить редко. Этот результат практического исследования алгоритма является вполне закономерным и лишний раз иллюстрирует особенности алгоритма данного типа.

Следует отметить ряд особенностей рассматриваемого алгоритма, оказывающих существенное влияние на его работу.

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

Так, при <100, процесс поиска экстремума часто прекращается в результате потери области оптимума. В тех же случаях, когда этого не происходило, на поиск решения необходимо было затратить почти такое же суммарное количество вычислений целевой функции , как при =100 или при =125. При размерности выборки >170 область оптимума не терялась, однако в большинстве случаев на поиск затрачивалось в среднем на 100-200 оценок целевой функции больше, чем при =100 или =125. Количество шагов оптимизации оставалось при этом прежним. Это можно объяснить следующим причинами.

Существенное сокращение области поиска происходит на первых шагах оптимизации. Поэтому для случая, когда начальное число испытаний в серии невелико (30-70), а допустимая область достаточно широка, плотность распределения испытаний будет низкая, и возможна потеря области допустимых решений. На последующих шагах оптимизации область допустимых значений варьируемых параметров существенно сужается и число оценок может быть уменьшено по сравнению с первоначальным, практически без увеличения вероятности потери области решения. Это подтверждается также тем обстоятельством, что при >170 результаты оптимизации исследуемых УЦОС в смысле суммарного количества оценок целевой функции были хуже, чем при =100..170. Наиболее оптимальным оказался размер выборки порядка 100 – 170, а допустимая степень уменьшения в процессе оптимизации равна 15-20% [41].

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

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

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

(3.4)

Увеличение согласно соотношению (3.4) происходит до тех пор, пока число успешных испытаний не превысит допустимого минимума K_min. При исследовании рассматриваемого алгоритма использовалось значение K_min=6.

Существенна для работы алгоритма оказывается эффективность генератора равномерно распределенных случайных чисел. От того насколько равномерно значения векторов , располагаются по всей допустимой области, зависит правильность принятия решения о сокращении области поиска. В практической процедуре поискового алгоритма используется генератор ЛП-последовательности [84, 85], обладающий на сегодняшний день наилучшим свойством равномерного покрытия области. Генерация точек ЛП-последовательности осуществляется в работе арифметическим алгоритмом, описанным в [85]. Для перевода точки _j в произвольный гиперпараллелепипед, задаваемый параметрическими ограничениями, используется линейное преобразование:

(3.5)

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

(3.6)

Схема алгоритма поискового метода оптимизации обобщенных критериев оптимальности приведена на рис. 3.1.

Рис. 3.1. Схема алгоритма метода поисковой оптимизации обобщенных критериев

Эффективность рассмотренного алгоритма практически не зависит от количества варьируемых параметров и от положения начальной точки поиска (только определение ). Даже в худших случаях (большое число варьируемых параметров, значительная удаленность начальной точки поиска X⁽⁰⁾ от оптимума) алгоритм обеспечивает поиск области решения с достаточно высокой точностью и скоростью. Особо следует отметить, что при этом ищется область глобального оптимума. Это создает все предпосылки для успешного использования алгоритма на первых шагах поиска оптимума при решении задач параметрической оптимизации УЦОС.