Global optimization method based on the selective averaging coordinate with restrictions.pdf Среди существующих методов поиска глобального минимума перспективны рандомизированные подходы. Они часто построены на сочетании случайного просмотра области поиска X и локальных детерминированных алгоритмов поиска минимума. В отличие от алгоритмов метода стохастической аппроксимации существенным продвижением при конструировании алгоритмов глобальной оптимизации является осознание того факта, что для более гарантированного движения к глобальному экстремуму необходимо проводить усреднение оптимизируемой функции во всей заданной области, где нужно отыскивать экстремум. На этом базируются подходы А. А. Красовского, А. И. Каплинского, А. И. Пропоя. Авторы используют потенциальные функции. Другой способ отыскания глобального экстремума основан на селективном усреднении (также во всей заданной области на начальном этапе поиска) не самой оптимизируемой функции, а искомых координат. Такой способ предложен в работах [1-3]; его развивает и автор [4-11] данной статьи. Производится параллельный расчёт всех искомых переменных. Решаем задачу поиска глобального минимума функции при изменении непрерывных переменных внутри допустимой области: f (x) = min. (1) xeX 1. Метод синтеза алгоритмов глобальной оптимизации Вводим последовательность {pS(y), s = 1,2,...} непрерывных, положительных в R+ функций, таких, что для любых y < z (где y, z с R1) последовательность {PS (У)/PS (z), s = 1, 2,...} монотонно нарастает с ростом s : lim pS (y)/pS (z) = w; y < z . Считаем, что известны точная верхняя fmax = sup f (x) и точная нижняя fmin = inf f (x) границы минимизируемой xeX xeX функции f (x). Справедлив следующий результат: Ps (g min (-)) _ Л f (-) - fm -min limj X Ps min (x) dx, Ps,min(x) = f ^ ( '' , gmin(-) = f-^f^ . (2) X J Ps (gmin (t)) dt fmax - fmin X Безразмерная неотрицательная переменная gmin( -) лежат в интервале [0; 1]. Заметим, что в (2) можно и не переходить к безразмерной переменной g min (-). Достаточно положить gmin (-) = f (-). Предельные свойства сохраняются. Использование безразмерных переменных придает алгоритмам универсальность. В качестве ядер ps (g) могут использоваться, например: 1) экспоненциальное в степени s : exp(-sg), 2) гиперболическое в степени s : g~s, 3) линейное (r =1), параболическое (r =2), кубическое (r =3) и т. д. в степени s: ps(g) = (1 -gr)s, r = 1, 2, 3, •••. Эти виды ядер конструируются по единому образцу. За основу берется убывающая в интервале [0; 1] функция p(g) (с максимумом в точке g = 0), а затем эта функция возводится в степень s: Ps (g) = (р(g))s. Для таких p(g) всегда 1 < (p(y)/ p(z)) при y < z . Следовательно, ядра ps (g) удовлетворяют основному условию для ядер. Перечисленный набор ядер ps (g) пока достаточен для решения задач глобальной минимизации. При увеличении s растет «селективность» (способность к локализации положения глобального экстремума) нормированного ядра ps min (-). В пределе (при s ) ядро стремятся к многомерной дельта-функции с особой точкой - = -min . Усреднение в правой части формулы (2) позволяют предсказывать положение глобального экстремума при фиксированной степени s , которую будем называть «степенью селективности ядра». Приведенный результат позволяет построить целый спектр практически реализуемых быстросходящихся алгоритмов, обеспечивающих поиск глобального экстремума с вероятностью, близкой к единице. Укажем возможный вариант класса алгоритмов (при различных параметрах 0 < у , q е {1, 2, • • •} , 0 < s и различных формах ядра) поиска глобального минимума: ( V/9 J -P's,min (-) d- A-V+1 = Yq -l+1 = -v - -V I 9 P's,min (-) dv = 1, m , (3) xi=n n x , n=[-1 -A-! , -+д—] x^x[ -m-д-m, -m+A-m ], l = 0, 1, 2, •••; [0 < yq, q е {1, 2, •••}, 0 < s]. Здесь l - номер итерации; y9 , 9, s - подбираемые фиксированные параметры; П1 - прямоугольная область в окрестности точки -1. При 0 < y9 ^ 1 всегда A-V+1 < y9A-V, v = 1, m . Отсюда следует конечно-шаговое (и достаточно быстрое) сжатие области поиска до заданных малых размеров. Алгоритмам (3) можно придать более привычный вид и осуществить в них приближенное вычисление интеграла. В области X, если она задана ограничениями неравенствами и не является узким «жгутом», размещается n пробных точек x(i), i = 1, n . В них вычисляется минимизируемая функция f(i) = f (x(i)), i = 1, n , и операция интегрирования заменяется суммированием. При получении пробных точек x(i), i = 1, n , последовательно генерируются равномерно распределённые точки в прямоугольной области П8 с центром в точке x1 : xV° = xV + AxV • mV°, uV e [-1; 1], v = Гт, i = 1, 2, •••, (4) и из них оставляется n точек, попадающих в допустимую область X. Пробные точки лежат теперь в области X1 =П1 П X . Исходная точка x0 и размеры Ax0 прямоугольной области П0 выбираются так, чтобы П0 охватывала допустимую область X или ту её часть, где расположен искомый глобальный экстремум. В результате указанного перехода от интегрирования к соответствующему суммированию алгоритмы (3) приобретают следующий вид: V/ q x +1 1 • 1 — • 1+1 • 1 1 ■ (i) q—(i) -(i) _ ps (gmm ) g(i) = f ' - fm s,min ^max fm £ ps (gm n) j=1 i =1 1) 0,8

Скачать электронную версию публикации