7 / 14
Fitness( ) дается сравнительная оценка нового и предыдущего реше-
ний, на основании которой новое решение может быть принято или
отвергнуто. Если новое решение отвергнуто, то происходит переход к
функции Scattering( ), реализующей алгоритм Метрополиса. Для ска-
нирования области, перспективной на минимум, применяются функ-
ции Perturbation( ) и Small_Perturbation( ). Новое решение принимается,
если оно лучше предыдущего (абсорбция); если найденное решение
хуже предыдущего, то происходит переход в отдаленную область про-
странства поиска (рассеяние), что позволяет преодолевать локальные
минимумы. Эффективность описанного поиска глобального решения
алгоритмом значительно повышается при одновременном использова-
нии большого числа частиц. Такой подход реализует алгоритм M-PCA,
который непосредственно ориентирован на применение в среде па-
раллельных вычислений. Наилучшее решение определяется с учетом
данных о всех частицах, участвующих в процессе. Единственный за-
даваемый параметр для алгоритма M-PCA — число итераций.
Рассматриваются новые гибридные алгоритмы, интегрирующие
стохастический алгоритм M-PCA и детерминированные алгоритмы
локальной минимизации. Метод гиперболической сглаживающей
функции реализован в работе [17]. Первый гибридный алгоритм
M-PCAGHS объединяет стохастический алгоритм M-PCA сканиро-
вания пространства переменных и детерминированный градиентный
локальный поиск, использующий метод гиперболической сглаживаю-
щей функции GHS. Второй гибридный алгоритм с локальным поиском
симплекс-методом Нелдера – Мида представлен в работе [18]. Тре-
тий гибридный алгоритм объединяет алгоритм M-PCA глобального
сканирования и детерминированный метод SFC кривой, заполняющей
пространство (метод редукции размерности задачи), при локальном
поиске. При реализации метода SFC исходная многомерная задача
глобальной оптимизации редуцируется к эквивалентной одномер-
ной. Так, поиск глобального минимума удовлетворяющей условию
Липшица (8) функции
F
(
x
)
,
x
∈
R
N
, на гиперкубе эквивалентен
определению глобального минимума одномерной функции
f
(
z
)
на
единичном интервале [19]:
f
(
z
) =
F
(
p
(
z
))
,
z
∈
[0
,
1]
, где
p
(
z
)
—
кривая Пеано. При этом для функции
f
(
z
)
выполняется условие Гель-
дера
|
f
(
z
0
)
−
f
(
z
00
)
| ≤
H
k
z
0
−
z
00
k
1
/N
,
z
0
, z
00
∈
[0
,
1]
, с константой
Гельдера
H
= 2
L
√
N
+ 3
. Здесь
L
— константа Липшица исходной
многомерной функции
F
(
x
)
.
Выбор метода редукции размерности задачи, который предназна-
чен собственно для поиска глобального экстремума, обусловлен тем,
что во многих случаях градиентные алгоритмы сходятся медленно и
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2016. № 2
71