Материал: Методы оптимального проектирования устройств цифровой обработки сигналов. Борисов В.И

При использовании соотношения (2.47) вычислительные затраты характеризуются числом обращений к вычислению значений : для вычисления градиента – 2N, для вычисления матрицы Гессе - (2N²+1) обращений, где N - размерность вектора варьируемых параметров .

Эффективность приведенных способов расчета производных была исследована на классе тестовых задач оптимизации УЦОС. Результаты тестирования послужили основой для определения численных значений критериев адаптации при проблемно – адаптивной организации подсистемы расчета производных обобщенных критериев оптимальности УЦОС. К примеру, по результатам тестирования для использованного в данной работе варианта алгоритма соряженных градиентов величину s наиболее целесообразно вычислять как наименьший положительный корень кубического уравнения (2.48).

Отметим, что реализованные на основе численных производных методы оптимизации оказываются, по существу, методами 0 – го порядка [3]. Действительно, заменяя , например, конечно – разностной формулой (2.47), фактически используем лишь значения обобщенного критерия , вычисленные при определенных значениях аргумента.

Суть предлагаемого алгоритма поискового метода (ПМ) 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⁽⁰⁾ от оптимума) алгоритм обеспечивает поиск области решения с достаточно высокой точностью и скоростью. Особо следует отметить, что при этом ищется область глобального оптимума. Это создает все предпосылки для успешного использования алгоритма на первых шагах поиска оптимума при решении задач параметрической оптимизации УЦОС.