О ПОСТРОЕНИИ СЕМЕЙСТВА МНОЖЕСТВЕННЫХ РАЗВЕРТОК НА ОСНОВЕ КРИВЫХ ПЕАНО ДЛЯ ПАРАЛЛЕЛЬНОГО РЕШЕНИЯ ЗАДАЧ ГЛОБАЛЬНО-ОПТИМАЛЬНОГО ПОИСКА
100
УДК 519.853.4
А. В. СЫСОЕВ
О ПОСТРОЕНИИ СЕМЕЙСТВА МНОЖЕСТВЕННЫХ РАЗВЕРТОК НА ОСНОВЕ КРИВЫХ ПЕАНО ДЛЯ ПАРАЛЛЕЛЬНОГО РЕШЕНИЯ ЗАДАЧ
ГЛОБАЛЬНО-ОПТИМАЛЬНОГО ПОИСКА
Предложена схема построения модифицированной множественной развертки на основе кривых Пеано. Схема позволяет многократно увеличить число используемых процессоров для параллельного решения задач глобальнооптимального поиска.
Ключевые слова: кривые Пеано, множественная развертка, параллельные вычисления, задачи глобальной оптимизации, модифицированная множественная развертка.
Отображения, называемые кривыми (развертками) Пеано, сопоставляют любой липши-
{ }цевой в гиперкубе P = v ∈ RN : − 2−1 ≤ vi ≤ 2−1, 1 ≤ i ≤ N функции ϕ( y) одномерную функ-
цию ϕ( y(x)) , удовлетворяющую на отрезке [0, 1] равномерному условию Гельдера с показа-
телем 1/N.
Алгоритм вычисления кривой Пеано с любой заданной точностью подробно описан, на-
пример, в работе [1]. Требуемая точность указывается целым числом M (номер разбиения), кото-
рое определяет допустимую максимальную погрешность оценки каждой координаты кривой y(x) для любого заданного значения аргумента x, равную 2–(M+1). Значения точек кривой сопоставляют равномерной с шагом 2–NM сетке на отрезке [0, 1] равномерную с шагом 2–M сетку в гиперкубе P.
Редукция многомерных задач глобальной оптимизации к одномерным с помощью раз-
верток сохраняет непрерывность и равномерную ограниченность разностей при ограничен-
ной вариации аргумента, однако теряет часть информации о близости точек в многомерном
пространстве, поскольку у точки x на отрезке [0, 1] имеются две соседние точки, тогда как у соответствующей ей точки y(x) ∈ P — соседние по 2N направлениям.
Возможен следующий способ учета этой информации [2]. Вводится гиперкуб
{ }P0 = v ∈ RN : − 2−1 ≤ vi ≤ 3⋅ 2−1, 1 ≤ i ≤ N
(1)
с длиной ребра, равной двум, и семейство гиперкубов
{ }Pl = v ∈ RN : − 2−1 ≤ vi + 2−l ≤ 3⋅ 2−1, 1 ≤ i ≤ N , 1 ≤ l ≤ L,
(2)
где гиперкуб Pl+1 получается путем сдвига гиперкуба Pl вдоль главной диагонали на шаг –2–l по каждой координате, и для каждого гиперкуба Pl, 0 ≤ l ≤ L, вводится своя развертка yl(x)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 10
О построении семейства множественных разверток на основе кривых Пеано
101
типа кривой Пеано, отображающая отрезок [0, 1] на этот гиперкуб. Приближенное построе-
ние развертки yl(x) для точности, соответствующей разбиению с номером M + 1, порождает в гиперкубе Pl равномерную сетку с шагом 2–M по каждой координате.
Построенная множественная развертка позволяет естественным образом организовать
параллельную схему поиска глобального оптимума, используя для расчетов с каждой из L
разверток отдельный процессор. Однако масштабируемость в этом случае ограничена усло-
вием, которое накладывает приближенное построение каждой отдельной развертки, – L + 1
УДК 519.853.4
А. В. СЫСОЕВ
О ПОСТРОЕНИИ СЕМЕЙСТВА МНОЖЕСТВЕННЫХ РАЗВЕРТОК НА ОСНОВЕ КРИВЫХ ПЕАНО ДЛЯ ПАРАЛЛЕЛЬНОГО РЕШЕНИЯ ЗАДАЧ
ГЛОБАЛЬНО-ОПТИМАЛЬНОГО ПОИСКА
Предложена схема построения модифицированной множественной развертки на основе кривых Пеано. Схема позволяет многократно увеличить число используемых процессоров для параллельного решения задач глобальнооптимального поиска.
Ключевые слова: кривые Пеано, множественная развертка, параллельные вычисления, задачи глобальной оптимизации, модифицированная множественная развертка.
Отображения, называемые кривыми (развертками) Пеано, сопоставляют любой липши-
{ }цевой в гиперкубе P = v ∈ RN : − 2−1 ≤ vi ≤ 2−1, 1 ≤ i ≤ N функции ϕ( y) одномерную функ-
цию ϕ( y(x)) , удовлетворяющую на отрезке [0, 1] равномерному условию Гельдера с показа-
телем 1/N.
Алгоритм вычисления кривой Пеано с любой заданной точностью подробно описан, на-
пример, в работе [1]. Требуемая точность указывается целым числом M (номер разбиения), кото-
рое определяет допустимую максимальную погрешность оценки каждой координаты кривой y(x) для любого заданного значения аргумента x, равную 2–(M+1). Значения точек кривой сопоставляют равномерной с шагом 2–NM сетке на отрезке [0, 1] равномерную с шагом 2–M сетку в гиперкубе P.
Редукция многомерных задач глобальной оптимизации к одномерным с помощью раз-
верток сохраняет непрерывность и равномерную ограниченность разностей при ограничен-
ной вариации аргумента, однако теряет часть информации о близости точек в многомерном
пространстве, поскольку у точки x на отрезке [0, 1] имеются две соседние точки, тогда как у соответствующей ей точки y(x) ∈ P — соседние по 2N направлениям.
Возможен следующий способ учета этой информации [2]. Вводится гиперкуб
{ }P0 = v ∈ RN : − 2−1 ≤ vi ≤ 3⋅ 2−1, 1 ≤ i ≤ N
(1)
с длиной ребра, равной двум, и семейство гиперкубов
{ }Pl = v ∈ RN : − 2−1 ≤ vi + 2−l ≤ 3⋅ 2−1, 1 ≤ i ≤ N , 1 ≤ l ≤ L,
(2)
где гиперкуб Pl+1 получается путем сдвига гиперкуба Pl вдоль главной диагонали на шаг –2–l по каждой координате, и для каждого гиперкуба Pl, 0 ≤ l ≤ L, вводится своя развертка yl(x)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 10
О построении семейства множественных разверток на основе кривых Пеано
101
типа кривой Пеано, отображающая отрезок [0, 1] на этот гиперкуб. Приближенное построе-
ние развертки yl(x) для точности, соответствующей разбиению с номером M + 1, порождает в гиперкубе Pl равномерную сетку с шагом 2–M по каждой координате.
Построенная множественная развертка позволяет естественным образом организовать
параллельную схему поиска глобального оптимума, используя для расчетов с каждой из L
разверток отдельный процессор. Однако масштабируемость в этом случае ограничена усло-
вием, которое накладывает приближенное построение каждой отдельной развертки, – L + 1