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

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

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

– координатного спуска [3, 7, 12, 23, 26, 30, 35, 41, 62, 74, 93]. Наилучшими оказались вариант поискового алгоритма, предложенного автором, метод деформируемого многогранника (ДМ) и метод статистического градиента (СГ). Поскольку алгоритмы методов ДМ и СГ претерпели при реализации лишь незначительные модификации, то в данном

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

Суть предлагаемого алгоритма поискового метода (ПМ) 0-го порядка заключается в проведении серии пробных испытаний критерия Q(X ) и сокращении по результатам пробных испытаний области поиска экстремума за счет исключения из рассмотрения тех

участков области допустимых значений варьируемых параметров, в которых значения Q(X )

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

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

параметров X i min и X i max , i [1, K] и значение начального порогового уровня Qn(0) .

Поиск минимума функции Q(X ) с помощью предлагаемого алгоритма осуществляется следующим образом. На каждом шаге поиска K раз ( K - размерность выборки) оценивается величина целевой функции Q( X (k ) ) , i [1, K] . Составляющие каждого

из векторов генерируются из области допустимых значений варьируемых параметров. Для каждого значения Q( X (k ) ) проверяется выполнение условия Q( X (k ) ) Qn(k ) , где Qn(k ) -

109

пороговое значение обобщенного критерия на k -ом шаге. При выполнении этого условия испытание считается успешным.

По всем успешным испытаниям проводится учет соответствующих им величин

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

глобального минимума [24], т. к. они обязательно попадут в область допустимых значений

X (k ) .

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

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

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

Константы , 1, 2 необходимо выбирать осмотрительно, так как от них существенным образом зависит количество оценок Q(X ) , затраченных на поиск экстремума,

110

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

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

алгоритма данного типа.

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

Количество шагов оптимизации и число выполняемых на них оценок Q(X ) ,

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

Так, при Nis <100, процесс поиска экстремума часто прекращается в результате потери области оптимума. В тех же случаях, когда этого не происходило, на поиск решения необходимо было затратить почти такое же суммарное количество вычислений целевой функции Q(X ) , как при Nis =100 или при Nis =125. При размерности выборки Nis >170

область оптимума не терялась, однако в большинстве случаев на поиск затрачивалось в среднем на 100-200 оценок целевой функции Q(X ) больше, чем при Nis =100 или Nis =125.

Количество шагов оптимизации оставалось при этом прежним. Это можно объяснить следующим причинами.

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

Поэтому для случая, когда начальное число испытаний в серии невелико (30-70), а

допустимая область достаточно широка, плотность распределения испытаний будет низкая,

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

111

увеличения вероятности потери области решения. Это подтверждается также тем обстоятельством, что при Nis >170 результаты оптимизации исследуемых УЦОС в смысле суммарного количества оценок целевой функции Q(X ) были хуже, чем при Nis =100..170.

Наиболее оптимальным оказался размер выборки порядка 100 – 170, а допустимая степень

уменьшения Nis в процессе оптимизации равна 15-20% [41].

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

следующем шаге оптимизации [41].

Весьма существенным является выбор начального порогового значения целевой

функции Qn(0) . Чрезмерное уменьшение Qn(0) увеличивает вероятность потери области

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

экстремума. В то же время выбор заведомо большого не дает существенного

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

путем решения тестовых задач. Эти соотношения организованы в виде правил продукции в соответствии с рекомендациями, приведенными в [82].

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

значительно больше интервала, в котором выполняется условие Q(X (k ) ) Qn(k ) , что может

привести к потере области оптимума. В этой ситуации целесообразно повторить шаг,

112

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

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

векторов X (jk ) , j [1, N] располагаются по всей допустимой области, зависит правильность

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

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

варьируемого вектора:

X i( j ) 10lg X нi ij (lg Xвi lg X нi ).

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

Эффективность рассмотренного алгоритма практически не зависит от количества варьируемых параметров и от положения начальной точки поиска (только определение

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

3.2 Алгоритм минимизации среднестепенных критериев оптимальности

УЦОС

113