СТРУКТУРЫ ДАННЫХ ДЛЯ РЕАЛИЗАЦИИ АДАПТИВНЫХ

 
77 
Одним из подходов к решению задачи (1)-(2) является диагональ-
ный  подход [3], обобщающий  характеристические  алгоритмы [4] на 
многомерный  случай.  Идея  данного  подхода  заключается  в 
последовательном  разбиении  области  поиска D на  множество  гипе-
ринтервалов D
i
 и вычислении функции f(x) в вершинах главных диаго-
налей  получаемых  гиперинтервалов.  Для  каждого  гиперинтервала  D
i
 
вычисляется его характеристика R
i
, отражающая «пригодность» дан-
ного  гиперинтервала  для  последующего  разбиения.  Характеристики 
выбираются так, что чем больше значение R
i
, тем больше вероятность 
нахождения точки глобального минимума f(x) в D
i
. На каждой итера-
ции алгоритма очередному разбиению подвергается гиперинтервал D
t
 
с максимальным значением характеристики R
t
, т.е. 
 
 
t = arg max {R
i
 | 1 
≤ i ≤ m(k)}, (3) 
 
где m(k) есть число гиперинтевалов D
i
 на текущей k-й итерации алго-
ритма. Разбиение D
t
 осуществляется гиперплоскостями, параллельны-
ми координатным плоскостям и проходящими через некоторую точку 
главной диагонали D
t.
  
Традиционно применяемыми стратегиями разбиения являются де-
ление пополам и деление на 2
N
 [3]. Как было показано в [2], при дан-
ных стратегиях генерируется множество избыточных точек испытания 
f(x), что приводит как к замедлению работы алгоритма, так и к увели-
чению машинной памяти для хранения необходимой информации. Из-
быточность точек испытания является следствием двух факторов: 
1. Каждый гиперинтервал D
i
 содержит более двух точек, в которых 
вычисляется функция f(x). 
2. Теряется пространственная связь между гиперинтервалами, по-
лученными на разных итерациях алгоритма. 
В работе [2] была предложена новая стратегия, которая преодоле-
вает недостатки традиционных стратегий разбиения области поиска D. 
Данная стратегия генерирует последовательность новых непрерывных 
кривых,  заполняющих  пространство («space-filling curves»), 
–
 адаптивных диагональных кривых (АДК). Обычно в численных алго-
ритмах  используется  аппроксимация  некоторой  кривой  (например, 
кривой Пеано, см. [1]), заполняющей пространство, с заданным поряд-
ком разбиения (одинаковым для всей области D). Порядок же разбие-
ния  АДК  отличается  в  разных  подобластях D: чем  больше  точность 
поиска, 
тем 
сильнее 
АДК 
разбивается 
в 
подобластях, 

78 
предположительно  содержащих  точки  глобального  минимума 
функции f(x). Разбиению области D из (2) на текущем шаге алгоритма 
соответствует  АДК  с  начальной  точкой  в  вершине  a  и  конечной – в 
вершине b, которая образована главными диагоналями подобластей D
i
. 
Новая  АДК  строится  путем  подразбиения  текущей  АДК  в  пределах 
выбранного гиперинтервала D
t
 (см. (3)) без изменеия остальных участ-
ков  кривой,  причем  D
t
  разбивается  на  три  гиперинтервала  равного 
объема  двумя  параллельными  гиперплоскостями,  проходящими  пер-
пендикулярно стороне D
t
 с наибольшей длиной. Таким образом, АДК 
остается неразрывной в течение всего процесса разбиения. В силу сво-
его построения АДК является фрактальным объектом.  
Методы,  использующие  АДК,  не  генерируют  избыточных  точек 
испытания f(x) и вычисляют f(x) непосредственно в N-мерной области 
D без преобразования аргумента функции, что позволяет в ходе поиска 
использовать не только значения функции f(x) в точках D, но и значе-
ния градиента f(x), увеличивая тем самым скорость работы алгоритма 
поиска.  

жүктеу/скачать 1,64 Mb.

Достарыңызбен бөлісу: