Автоматика и телемеханика, № 8, 2020

В.П. ГЕРГЕЛЬ, д-р техн. наук (gergel@unn.ru),

К.А. БАРКАЛОВ, канд. физ.-мат. наук (barkalov@vmk.unn.ru)

(Нижегородский государственный университет им. Н.И. Лобачевского)

АДАПТИВНАЯ ГЛОБАЛЬНАЯ ОПТИМИЗАЦИЯ

НА ОСНОВЕ БЛОЧНО-РЕКУРСИВНОЙ СХЕМЫ

РЕДУКЦИИ РАЗМЕРНОСТИ¹

Рассматриваются задачи многомерной многоэкстремальной оптимиза-

ции и численные методы их решения. Об оптимизируемой функции де-

лается лишь общее предположение, что она удовлетворяет условию Лип-

шица с априори неизвестной константой (задачи такого типа часто встре-

чаются в приложениях). Рассмотрено два способа редукции размерности

в задачах многомерной оптимизации: использование кривых Пеано (раз-

верток) и рекурсивная многошаговая схема. Предложена обобщенная схе-

ма, комбинирующая эти два подхода. В новой схеме решение многомерной

задачи сводится к решению семейства задач меньшей размерности, в ко-

торых в свою очередь используются развертки. Реализован адаптивный

алгоритм, в котором все возникающие подзадачи решаются одновремен-

но. Проведены численные эксперименты на нескольких сотнях тестовых

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

размерности.

Ключевые слова: глобальная оптимизация, многоэкстремальные функ-

ции, редукция размерности, кривые Пеано, рекурсивная оптимизация.

DOI: 10.31857/S0005231020080103

1. Введение

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

ϕ(y^∗) = min {ϕ(y) : y ∈ D},

(1)

{

}

y∈R^N :a_i ≤y_i ≤b_i,1≤i≤N

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

дана неявно (функция вида “черный ящик”), а вычисление ее значений свя-

зано с решением задачи численного моделирования и является трудоемкой

операцией.

Любая возможность достоверно оценить глобальный оптимум в многоэкс-

тремальной задаче с функциями вида “черный ящик” принципиально осно-

вана на априорной информации, позволяющей связать возможные значения

¹ Работа выполнена по теме государственного задания (0729-2020-0055) при частичной

поддержке научно-образовательного математического центра (075-02-2020-1483/1).

136

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

таний. Для многих прикладных задач типичной является ситуация, когда

ограниченное изменение вектора параметров y вызывает ограниченное из-

менение значений ϕ(y). Математической моделью, описывающей указанное

предположение, является условие Липшица





ϕ(y^′) - ϕ(y^′′)≤ Ly′ - y′′, y′,y′′ ∈D,

0 < L < ∞.

Предположение липшицевости целевой функции типично для многих подхо-

дов к разработке оптимизационных алгоритмов. Первые методы липшицевой

оптимизации были предложены в начале 70-х гг. XX в. [1-3]; с тех пор дан-

ное направление продолжает активно развиваться [4-8]. Например, многие

известные методы основаны на различных способах разбиения области по-

иска на систему подобластей и последующего выбора наиболее перспектив-

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

функции). Результаты, полученные в данном направлении, представлены в

публикациях [9-13].

В настоящее время для решения задач оптимизации с функциями вида

“черный ящик” широко используются генетические и популяционные алго-

ритмы (см., например, [14, 15]), которые так или иначе основаны на идеях

случайного поиска. В силу простоты реализации и использования они полу-

чили большую популярность, однако по качеству работы (численной оценкой

которого может служить число корректно решенных задач из некоторого на-

бора) они существенно уступают детерминированным алгоритмам [16, 17].

Одним из эффективных детерминированных методов решения задач мно-

гоэкстремальной оптимизации является информационно-статистический

алгоритм глобального поиска. Основы информационно-статистического под-

хода были заложены Ю.И. Неймарком [18, 19] и развиты Р.Г. Стронгиным

[20, 21]. Впоследствии метод, изначально предложенный для решения без-

условных задач, был успешно обобщен для решения задач с невыпуклыми

ограничениями [22, 23] и многокритериальных задач [24]. Для различных ва-

риантов алгоритма были предложены способы распараллеливания, учитыва-

ющие особенности архитектуры современных вычислительных систем [25].

Разработанные методы основаны на редукции исходной многомерной за-

дачи к эквивалентной одномерной или к системе одномерных подзадач с по-

следующим решением одномерных задач эффективными методами оптими-

зации функций одной переменной. Предложено две такие схемы: редукция

на основе кривых, заполняющих пространство (кривых Пеано, или развер-

ток) [26, 27], и схема рекурсивной вложенной оптимизации (многошаговая

схема) [28, 29]. В [30] предложена адаптивная многошаговая схема, суще-

ственно повышающая эффективность оптимизации по сравнению с базовым

прототипом. В данной статье предлагается обобщение адаптивной схемы ре-

дукции размерности, комбинирующее использование вложенной оптимиза-

ции и кривых Пеано. При таком подходе вложенные подзадачи в адаптивной

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

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

137

2. Базовый алгоритм глобального поиска

В качестве базовой задачи рассмотрим одномерную задачу многоэкстре-

мальной оптимизации

(2)

ϕ∗ = ϕ(x^∗

) = min{ϕ(x) : x ∈ [0,1]}

с целевой функцией, удовлетворяющей условию Липшица.

Приведем описание алгоритма глобального поиска (АГП) для решения

базовой задачи в соответствии с [27]. В процессе своей работы АГП порож-

дает последовательность точек xⁱ, в которых вычисляются значения целевой

функции zⁱ = ϕ(xⁱ). Будем называть процесс вычисления значения целевой

функции испытанием.

В соответствии с алгоритмом первые два испытания проводятся в гра-

ничных точках отрезка [0, 1], т.е. x⁰ = 0, x¹ = 1. В этих точках вычисляются

значения целевой функции z⁰ = ϕ(x⁰), z¹ = ϕ(x¹) и устанавливается значе-

ние счетчика k = 1. Точка очередного испытания x^k+1, k ≥ 1, выбирается в

соответствии со следующими правилами.

Шаг 1. Перенумеровать нижним индексом (начиная с 0) точки xⁱ,

0 ≤ i ≤ k, проведенных испытаний в порядке возрастания координаты, т.е.

0 = x₀ < x₁ < ... < x_k = 1.

Сопоставить точкам x_i, 0 ≤ i ≤ k, вычисленные в них значения целевой функ-

ции z_i = ϕ(x_i), 0 ≤ i ≤ k.

Шаг 2. Вычислить максимальное абсолютное значение относительной

первой разности

|z_i - z_i-1|

(3)

µ = max

1≤i≤k

Δ_i

где Δ_i = x_i - x_i-1. Если вычисленное в соответствии с данной формулой зна-

чение равно нулю, то положить µ = 1.

Шаг 3. Для всех интервалов (x_i-1,x_i), 1 ≤ i ≤ k, вычислить значение

(z_i - z_i-1)

(4)

R(i) = rµΔ_i +

− 2(z_i + z_i-1

rµΔ_i

называемое характеристикой интервала; величина r > 1 является парамет-

ром алгоритма.

Шаг 4. Найти интервал (x_t-1,x_t) с максимальной характеристикой

(5)

R(t) = max

R(i).

1≤i≤k

Если максимальная характеристика соответствует нескольким интервалам,

то в качестве t выбрать минимальное число, удовлетворяющее (5).

Шаг 5. Провести новое испытание в точке

z_t - z_t-1

(6)

x^k+1 =

(x_t-1 + x_t) -

2rµ

138

Алгоритм прекращает свою работу при выполнении условия Δ_t < ǫ; здесь

t из (5), а ǫ > 0

заданная точность. В качестве оценки решения задачи

выбираются значения

z^∗k = min

ϕ(xⁱ), x^∗k = arg min ϕ(xⁱ).

0≤i≤k

Теоретические условия, определяющие сходимость алгоритма, представлены

в [27].

3. Редукция размерности

3.1. Редукция размерности с помощью кривых,

заполняющих пространство

Рассмотрим схему редукции размерности, основанную на использовании

кривых, заполняющих пространство (кривых Пеано). Известно, что подобно-

го типа кривые позволяют однозначно отобразить одномерный отрезок [0, 1]

на многомерную область, т.е.

{

}

(7)

{y(x) : 0 ≤ x ≤ 1} =

y ∈ R^N : -2^-1 ≤ y_i ≤ 2^-1,1 ≤ i ≤ N

Отметим, что теоретическая кривая y(x) определяется как предельный

объект. Поэтому при практической реализации может быть построено лишь

некоторое приближение к истинной кривой. Методы построения подобных

аппроксимаций (называемых развертками) рассмотрены в [21, 27]. При этом

точность приближения развертки к истинной кривой y(x) зависит от плот-

ности развертки m (являющейся параметром ее построения) и составляет

величину порядка 2^-m по каждой координате.

Использование подобного рода отображений позволяет свести решение

многомерной задачи (1) к решению эквивалентной ей одномерной

(8)

ϕ(y^∗) = ϕ(y(x^∗

)) = min {ϕ(y(x)) : x ∈ [0, 1]}.

Важным свойством при этом является сохранение ограниченности отно-

сительных разностей функции (см. [27]). Если функция ϕ(y) в области D

удовлетворяла условию Липшица, тогда редуцированная функция ϕ(y(x)),

x ∈ [0,1], будет удовлетворять равномерному условию Гельдера

(9)

|ϕ(y(x₁)) - ϕ(y(x₂))| ≤ H |x₁ - x₂|^1/N ,

где константа Гельдера H связана с константой Липшица L соотношением

√

(10)

H = 2L

N + 3.

Условия (9), (10) позволяют легко обобщить “одномерный” алгоритм из

раздела 2 для решения многомерных задач. Для этого достаточно заменить

длины интервалов Δ_i в формулах (3), (4) на длины

(11)

Δ_i = (x_i - x_i-1)^1/N ,

139

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

формулу

]_N

x_t + x_t-1

[|z_t - z_t-1|

(12)

x^k+1 =

- sign(z_t - z_t-1)

3.2. Многошаговая схема редукции размерности

Многошаговая схема редукции размерности (схема вложенной оптимиза-

ции) основана на известном соотношении [21, 25]

(13)

minϕ(y) = min

min

ϕ(y),

y∈D

y₁∈[a₁,b₁]

y₂∈[a₂,b₂]

y_N ∈[a_N ,b_N ]

которое позволяет свести решение исходной многомерной задачи (1) к реше-

нию семейства рекурсивно связанных одномерных подзадач.

Для формального описания многошаговой схемы введем семейство функ-

ций, определяемых в соответствии с соотношениями

(14)

ϕN (y1, . . . , yN ) ≡ ϕ(y1, . . . , yN),

(15)

ϕi(y1, . . . , yi) =

min

ϕi+1(y1, . . . , yi, yi+1),

1 ≤ i ≤ N - 1.

y_i+1∈[a_i+1,b_i+1]

Тогда, в соответствии с (13), для решения многомерной задачи (1) доста-

точно решить одномерную задачу

(16)

ϕ∗ = min ϕ₁(y₁

y₁∈[a₁,b₁]

Однако каждое вычисление значения функции ϕ₁ в некоторой фиксирован-

ной точке y₁ предполагает решение одномерной задачи оптимизации второго

уровня

(17)

ϕ₁(y₁) = min ϕ₂(y₁,y₂

y₂∈[a₂,b₂]

Вычисление значений функции ϕ₂ в свою очередь требует одномерной мини-

мизации функции ϕ₃ и т.д. вплоть до решения задачи

(18)

ϕN-1(y1, . . . , yN-1) = min ϕN (y1, . . . , yN )

y_N ∈[a_N ,b_N ]

на последнем уровне рекурсии.

Возникающие при этом подзадачи и взаимосвязи между ними отображены

на рис. 1. Наглядно видно, что структура взаимосвязей имеет форму дерева,

причем функции ϕ_N (y₁, . . . , y_N ) на N-м уровне являются листьями дерева

задач, их значения вычисляются непосредственно.

Для описанной выше многошаговой схемы было предложено обобщение

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

и вложенной оптимизации [31].

Рассмотрим y как вектор, состоящий из векторов (блочных переменных)

(19)

y = (y₁,y₂,...,y_N) = (u₁,u₂,...,u_M

140

min j₁(y₁)

y1 Î[a1, b1]

min j₂(y₁, y2)

min j₂(y

…

y2 Î[a2, b2]

…

min j₃(y₁, y2

, y₃)

min j₃(y₁, y2

, y₃)

…

y3 Î[a3, b3]

Рис. 1. Взаимосвязи между подзадачами в многошаговой схеме.

где i-я блочная переменная, т.е. вектор u_i, состоит из взятых последова-

тельно компонент вектора y, т.е. u₁ = (y₁, y₂, . . . , yN1 ), u₂ = (yN1+1, yN₁+2,

...,yN1+N₂),... ,uM = (yN-N_M+1,yN-N_M+2,... ,yN), а N1+N2+...+NM =N.

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

схемы (13) может быть переписано в форме

(20)

minϕ(y) = min

min

... min

ϕ(y),

y∈D

u₁∈D₁

u₂∈D₂

u_M ∈D_M

где подобласти D_i, 1 ≤ i ≤ M, являются проекциями исходной области поис-

ка D на подпространства, соответствующие переменным u_i, 1 ≤ i ≤ M.

Способ решения задачи (1) на основе соотношения (20) будет в целом

повторять (14)-(16). Необходимо лишь заменить исходные переменные y_i,

1 ≤ i ≤ N, на блочные переменные u_i, 1 ≤ i ≤ M.

При этом вложенные подзадачи

(21)

ϕi(u1, . . . , ui) = min ϕi+1(u1, . . . , ui, ui+1),

1 ≤ i ≤ M - 1,

u_i+1∈D_i+1

будут многомерными, что является основным отличием от исходной многоша-

говой схемы. Для решения многомерных подзадач может быть использована

схема редукции размерности на основе кривых Пеано.

3.3. Блочная адаптивная схема редукции размерности

Решение возникающего множества подзадач вида (15) (для многошаговой

схемы) или вида (21) (для блочной многошаговой схемы) может быть органи-

зовано различными способами. Очевидный способ (детально проработанный

в [28, 32, 33] для многошаговой схемы и в [31, 34] для блочной многошаговой

схемы) основан на решении подзадач в соответствии с рекурсивным порядком

их порождения. Однако здесь возникает потеря значительной части инфор-

мации о целевой функции.

141

Иным подходом является адаптивная схема, в которой все подзадачи ре-

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

многомерной задаче и за счет этого ускорять процесс ее решения. Для случая

одномерных подзадач данный подход был теоретически обоснован и апро-

бирован в [30, 35, 36]. Настоящая статья предлагает обобщение адаптивной

схемы для случая многомерных подзадач.

Перед изложением новой схемы организации вычислений еще раз отметим,

что в рамках исходной многошаговой схемы (или же ее блочного варианта)

порождаемые подзадачи решаются строго последовательно; получаемая в ре-

зультате иерархическая схема порождения и решения подзадач (в виде дере-

ва) представлена на рис. 1. Построение этого дерева происходит динамически

в процессе решения исходной задачи (1). При этом вычисление одного зна-

чения функции ϕ_i(y₁, y₂, . . . , y_i) на i-м уровне требует полного решения всех

задач одного из поддеревьев уровня i + 1.

Адаптивная многошаговая схема редукции размерности изменяет поря-

док решения подзадач: они будут решаться не по одной (в соответствии с их

иерархией в дереве задач), а одновременно, т.е. будет существовать некото-

рое множество подзадач, находящихся в процессе решения. В рамках новой

схемы:

• для вычисления значения функции i-го уровня из (21) порождается новая

задача уровня i + 1, в которой проводится только одно испытание, после

чего новая порожденная задача включается в множество уже имеющихся

задач, подлежащих решению;

• итерация глобального поиска состоит в выборе одной (наиболее перспек-

тивной) задачи из множества имеющихся задач, в которой проводится одно

испытание; точка проведения нового испытания определяется в соответ-

ствии с алгоритмом из подраздела 3.1;

• в качестве минимальных значений функций из (21) используются их теку-

щие оценки, полученные на основе накопленной поисковой информации.

Краткое описание основных шагов блочной адаптивной схемы редукции

размерности состоит в следующем. Пусть вложенные подзадачи вида (21)

решаются с помощью алгоритма глобального поиска, описанного в подраз-

деле 3.1. Тогда каждой подзадаче (21) можно присвоить некоторое число-

вое значение, называемое характеристикой этой задачи. В качестве такой

характеристики можно взять значение R(t) из (5), т.е. максимальную харак-

теристику интервалов, сформированных в данной задаче. В соответствии с

правилом вычисления характеристик (4) чем выше значение характеристики,

тем более перспективной является подзадача для продолжения поиска в ней

глобального минимума исходной задачи (1). Поэтому на каждой итерации вы-

бирается подзадача с максимальной характеристикой для проведения в ней

очередного испытания. Это испытание либо приводит к вычислению значе-

ния целевой функции ϕ(y) (если выбранная подзадача принадлежала уровню

j = M), либо порождает новые подзадачи согласно (21) при j ≤ M - 1. В по-

следнем случае новые порожденные задачи добавляются к текущему множе-

ству задач, вычисляются их характеристики и процесс повторяется. Заверше-

ние процесса оптимизации происходит, когда в корневой задаче выполняется

условие остановки алгоритма, решающего эту задачу.

142

Отметим новые элементы предлагаемой схемы редукции размерности:

•

В адаптивной многошаговой схеме все порождаемые задачи решаются сов-

местно - на каждой итерации выбирается одна (наиболее перспективная)

подзадача из множества подзадач, в которой проводится одно испытание.

Такой подход, с одной стороны, требует одновременного хранения поиско-

вой информации во всех решаемых подзадачах. С другой стороны, он поз-

воляет (при необходимости) увеличивать необходимую точность решения

задачи (1) без проведения повторного решения всех подзадач (21). Напри-

мер, начальная стадия оптимизации может быть выполнена с достаточно

грубой точностью, что позволит быстро получить некоторую оценку ре-

шения; далее (после анализа результатов) точность может быть повышена

и процесс глобального поиска может быть продолжен;

•

В исходной многошаговой схеме редукции размерности решение каждой

возникающей подзадачи проводится “до конца”, т.е. порождения новой под-

задачи не произойдет, пока не будет решена текущая подзадача. Но точ-

ка u_i ее решения, вообще говоря, не будет совпадать с i-й компонентой

вектора решения y^∗ = (u^∗1, . . . , u^∗i, . . . , u^∗M ) исходной многомерной задачи.

В адаптивной схеме подобные бесперспективные подзадачи могут быть от-

бракованы уже на начальном этапе их решения;

•

Наличие правила выбора подзадачи при выполнении очередной итерации

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

соответствующие разным правилам выбора подзадачи. Например, как ис-

ходная многошаговая схема редукции размерности, так и схема редукции

размерности с помощью единственной кривой Пеано могут быть получены

как частные случаи нового подхода;

•

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

организовать их параллельное решение и эффективно задействовать ре-

сурсы современных вычислительных систем. Некоторые результаты в дан-

ном направлении представлены в [37].

4. Результаты экспериментов

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

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

из некоторого класса. Будем использовать два класса многоэкстремальных

тестовых функций (GKLS Simple, GKLS Hard), описанных в [38].

В [36, 39] было экспериментально установлено, что алгоритм глобального

поиска (АГП) как с использованием разверток, так и в сочетании с адаптив-

ной схемой редукции размерности превосходит многие известные алгоритмы

глобальной оптимизации, включая методы DIRECT и DIRECTl. Поэтому в

данном исследовании ограничимся сравнением вариантов АГП в сочетании с

различными схемами редукции размерности.

Для сравнения эффективности работы алгоритмов будем использовать

два критерия: среднее число испытаний и операционные характеристики.

Операционной характеристикой алгоритма называется функция P (k), опре-

деляемая как доля задач из рассматриваемой серии, для решения которых

потребовалось не более чем k испытаний. Задачу будем считать решенной,

143

Рис. 2. Операционные характеристики на классах GKLS Simple (а) и Hard (б),

N = 2.

если алгоритм сенерирал точку yk очередного испытания в окрестности

решения y^∗, т.е.

y^k - y^∗

< δ ∥b - a∥, где δ = 10^-2, a и b границы области

поиска D.

Первая серия экспериментов была проведена на двумерных задачах клас-

сов GKLS Simple и GKLS Hard (100 функций каждого класса). В табл. 1

представлено среднее число испытаний, выполненных АГП с использовани-

ем разверток (K_e), многошаговой схемы (K_n) и адаптивной многошаговой

схемы (K_a). На рис. 2 приведены операционные характеристики алгоритмов,

полученные на указанных классах задач. Сплошная линия соответствует ал-

горитму с использованием разверток, точечная линия адаптивной много-

шаговой схеме, штриховая линия многошаговой схеме. Результаты экспе-

риментов показывают, что АГП с использованием адаптивной многошаговой

схемы демонстрирует примерно одинаковое быстродействие по сравнению с

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

многошаговую схему. Поэтому в дальнейших экспериментах ограничимся

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

Вторая серия экспериментов была проведена на четырехмерных зада-

чах классов GKLS Simple и GKLS Hard (100 функций каждого класса).

В табл. 2 представлено среднее число испытаний, выполненных АГП с ис-

Таблица 1. Среднее число испытаний на классах

GKLS Simple и Hard, N = 2

GKLS Simple

GKLS Hard

K_e

252

674

K_n

697

1252

K_a

279

815

Таблица 2. Среднее число испытаний на классах

GKLS Simple и Hard, N = 4

GKLS Simple

GKLS Hard

K_a

21 747

35 633

K_ba

15 942

33 206

144

Рис. 3. Операционные характеристики на классах GKLS Simple (а) и Hard

(б ), N = 4.

Рис. 4. Операционные характеристики на классе GKLS Simple, N = 6.

пользованием адаптивной многошаговой схемы (K_a) и блочной адаптивной

схемы (K_ba) с формированием двух уровней подзадач одинаковой размерно-

сти N₁ = N₂ = 2. Отметим, что при использовании исходного варианта адап-

тивной многошаговой схемы при решении задачи размерности N = 4 форми-

руется четыре уровня одномерных подзадач, что усложняет их обработку.

На рис. 3 приведены операционные характеристики алгоритмов, получен-

ные на классах GKLS Simple и GKLS Hard. Точечная линия соответствует

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

схемы. Результаты экспериментов показывают, что использование блочной

адаптивной схемы дает ощутимый выигрыш по числу испытаний (до 35 %)

по сравнению с исходной схемой редукции размерности.

Последняя серия экспериментов была проведена на шестимерных задачах

класса GKLS Simple (100 функций). Сравнивалась работа АГП с использова-

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

подзадач одинаковой размерности N₁ = N₂ = 3. Среднее число испытаний,

выполненных АГП с использованием разверток, составило 102 987, тогда как

с использованием блочной адаптивной схемы

75390. На рис. 4 приведе-

ны операционные характеристики алгоритмов. Точечная линия соответству-

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

схемы.

145

5. Заключение

В данной статье предложена обобщенная адаптивная схема редукции раз-

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

ние кривых Пеано и схему вложенной (рекурсивной) оптимизации. Для ре-

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

Приведена вычислительная схема алгоритма, рассмотрены основные вопро-

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

Проведены вычислительные эксперименты на серии тестовых задач с целью

сравнения эффективности различных схем редукции размерности. Результа-

ты экспериментов показывают, что использование блочной адаптивной схемы

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

ходимое для решения задачи с заданной точностью.

СПИСОК ЛИТЕРАТУРЫ

Евтушенко Ю.Г. Численный метод поиска глобального экстремума функций

(перебор на неравномерной сетке) // Журн. вычисл. матем. и матем. физ. 1971.

T. 11. № 6. С. 1390-1403.

Пиявский С.А. Один алгоритм отыскания абсолютного экстремума функций //

Журн. вычисл. матем. и матем. физ. 1972. Т. 12. № 4. С. 888-896.

Shubert B.O. A Sequential Method Seeking the Global Maximum of a Function //

SIAM J. Numer. Anal. 1972. V. 9. P. 379-388.

Jones D.R., Perttunen C.D., Stuckman B.E. Lipschitzian Optimization without the

Lipschitz Constant // J. Optim. Theory Appl. 1993. V. 79. No. 1. P. 157-181.

Pinter J.D. Global Optimization in Action (Continuous and Lipschitz Optimization:

Algorithms, Implementations and Applications). Dordrecht: Kluwer Acad. Publish-

ers, 1996.

Žilinskas J. Branch and Bound with Simplicial Partitions for Global Optimization //

Math. Model. Anal. 2008. V. 13. No. 1. P. 145-159.

Евтушенко Ю.Г., Малкова В.У., Станевичюс А.-И.А. Распараллеливание про-

цесса поиска глобального экстремума // АиТ. 2007. № 5. C. 46-58.

Evtushenko Yu.G., Malkova V.U., Stanevichyus A.A. Parallelization of the Global

Extremum Searching Process // Autom. Remote Control. 2007. V. 68. No. 5.

P. 787-798.

Евтушенко Ю.Г., Малкова В.У., Станевичюс А.-И.А. Параллельный поиск гло-

бального экстремума функций многих переменных // Журн. вычисл. матем. и

матем. физ. 2009. Т. 49. № 2. C. 255-269.

Jones D.R. The DIRECT global optimization algorithm / Floudas C.A., Parda-

los P.M. (eds.) The Encyclopedia of Optimization. Second Edition. Springer, 2009.

P. 725-735.

10.

Paulavičius R.,

Žilinskas J., Grothey A. Investigation of Selection Strategies in

Branch and Bound Algorithm with Simplicial Partitions and Combination of Lips-

chitz Bounds // Optim. Lett. 2010. V. 4 (1). P. 173-83.

11.

Evtushenko Y.G., Posypkin M.A. A Deterministic Approach to Global Box-

Constrained Optimization // Optim. Lett. 2013. V. 7 (4). P. 819-829.

12.

Квасов Д.Е., Сергеев Я.Д. Методы липшицевой глобальной оптимизации в за-

дачах управления // АиТ. 2013. № 9. C. 3-19.

Kvasov D.E., Sergeyev Ya.D. Lipschitz Global Optimization Methods in Control

Problems // Autom. Remote Control. 2013. V. 74. No. 9. P. 1435-1448.

146

13.

Paulavičius R.,

Žilinskas J. Advantages of Simplicial Partitioning for Lipschitz

Optimization Problems with Linear Constraints // Optim. Lett. 2016. V. 10 (2).

P. 237-246.

14.

Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. Уч. пос.

М.: Физматлит, 2004.

15.

Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы,

вдохновленные природой. Уч. пос. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014.

16.

Kvasov D.E., Mukhametzhanov M.S. Metaheuristic vs. Deterministic Global Opti-

mization Algorithms. The Univariate Case // Appl. Math. Comput. 2018. V. 318.

P. 245-259.

17.

Sergeyev Y., Kvasov D., Mukhametzhanov M. On the Efficiency of Nature-Inspired

Metaheuristics in Expensive Global Optimization with Limited Budget // Sci. Rep.

V. 8 (1). Art. No. 435.

18.

Неймарк Ю.И., Стронгин Р.Г. Поиск экстремума функций по принципу макси-

мума информации // АиТ. 1966. № 11. С. 113-118.

Neimark Yu.I., Strongin R.G. Function Extremum Search with the Use of Informa-

tion Maximum Principle // Autom. Remote Control. 1966. V. 27. No. 1. P. 101-105.

19.

Неймарк Ю.И., Стронгин Р.Г. Информационный подход к задаче поиска экс-

тремума функций // Изв. АН СССР, Технич. кибернетика. 1966. № 1. С. 17-26.

20.

Стронгин Р.Г. Многоэкстремальная минимизация // АиТ. 1970. № 7. С. 63-67.

Strongin R.G. Multiextremal Minimization // Autom. Remote Control. 1970. V. 31.

No. 7. P. 1085-1088.

21.

Стронгин Р.Г. Численные методы в многоэкстремальных задачах (информаци-

онно-статистические алгоритмы). М.: Наука, 1978.

22.

Стронгин Р.Г., Маркин Д.Л. Минимизация многоэкстремальных функций при

невыпуклых ограничениях // Кибернетика. 1986. № 4. С. 63-69.

23.

Маркин Д.Л., Стронгин Р.Г. Метод решения многоэкстремальных задач с невы-

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

оптимума // Журн. вычисл. матем. и матем. физ. 1987. Т. 27. № 1. С. 52-61.

24.

Маркин Д.Л., Стронгин Р.Г. О равномерной оценке множества слабоэффектив-

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

Журн. вычисл. матем. и матем. физ. 1993. Т. 33. № 2. С. 195-205.

25.

Стронгин Р.Г., Гергель В.П., Гришагин В.А., Баркалов К.А. Параллельные вы-

числения в задачах глобальной оптимизации. М.: Изд-во МГУ, 2013.

26.

Стронгин Р.Г. Параллельная многоэкстремальная оптимизация с использова-

нием множества разверток // Журн. вычисл. матем. и матем. физ. 1991. T. 31.

№ 8. С. 1173-1185.

27.

Strongin R.G., Sergeev Ya.D. Global Optimization with Non-Convex Constraints.

Sequential and Parallel Algorithms. Dordrecht: Kluwer Acad. Publishers, 2000.

28.

Grishagin V.A., Sergeyev Y.D., Strongin R.G. Parallel Characteristical Algorithms

for Solving Problems of Global Optimization // J. Glob. Optim. 1997. V. 10 (2).

P. 185-206.

29.

Sergeyev Y., Grishagin V. Parallel Asynchronous Global Search and the Nested Op-

timization Scheme // J. Comput. Anal. Appl. 2001. V. 3 (2). P. 123-145.

30.

Gergel V., Grishagin V., Gergel A. Adaptive Nested Optimization Scheme for Mul-

tidimensional Global Search // J. Glob. Optim. 2016. V. 66 (1). P. 35-51.

31.

Barkalov K., Gergel V. Multilevel Scheme of Dimensionality Reduction for Parallel

Global Search Algorithms / OPT-i 2014

1st Int. Conf. on Engineering and Applied

Sciences Optimization. Proc. 2014. P. 2111-2124.

147

32. Sergeyev Y., Grishagin V. Parallel Asynchronous Global Search and the Nested Op-

timization Scheme // J. Comput. Anal. Appl. 2001. V. 3 (2). P. 123-145.

33. Gergel V., Grishagin V., Israfilov R. Local Tuning in Nested Scheme of Global Op-

timization // Procedia Computer Sci. 2015. V. 51 (1). P. 865-874.

34. Barkalov K., Lebedev I. Solving Multidimensional Global Optimization Problems

using Graphics Accelerators // CCIS. 2016. V. 687. P. 224-235.

35. Grishagin V., Israfilov R., Sergeyev Y. Comparative Efficiency of Dimensionality

Reduction Schemes in Global Optimization // AIP Conf. Proc. 2016. V. 1776. Art.

No. 060011.

36. Grishagin V., Israfiov R., Sergeyev Y. Convergence Conditions and Numerical

Comparison of Global Optimization Methods Based on Dimensionality Reduction

Schemes // Appl. Math. Comput. 2018. V. 318. P. 270-280.

37. Gergel V., Grishagin V., Israfilov R. Parallel Dimensionality Reduction for Multiex-

tremal Optimization Problems // LNCS. 2019. V. 11657. P. 166-178.

38. Gaviano M., Lera D., Kvasov D.E., Sergeyev Ya.D. Software for Generation of

Classes of Test Functions with Known Local and Global Minima for Global Op-

timization // ACM Trans. Math. Software. 2003. V. 29. P. 469-480.

39. Sovrasov V. Comparison of Several Stochastic and Deterministic Derivative-Free

Global Optimization Algorithms // LNCS. 2019. V. 11548. P. 70-81.

Статья представлена к публикации членом редколлегии Б.Т. Поляком.

Поступила в редакцию 23.07.2019

После доработки 29.10.2019

Принята к публикации 30.01.2020

148