АДАПТИВНЫЕ ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ ДЛЯ МНОГОМЕРНОЙ МНОГОЭКСТРЕМАЛЬНОЙ ОПТИМИЗАЦИИ
76
УДК 519.85
А. В. ГЕРГЕЛЬ
АДАПТИВНЫЕ ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ ДЛЯ МНОГОМЕРНОЙ МНОГОЭКСТРЕМАЛЬНОЙ ОПТИМИЗАЦИИ
Рассматриваются методы решения многомерных многоэкстремальных задач, использующие многошаговую схему редукции размерности. Предложена новая схема параллельного глобального поиска на основе адаптивной многошаговой схемы редукции размерности.
Ключевые слова: многомерная многоэкстремальная оптимизация, алгоритмы параллельного глобального поиска, адаптивная многошаговая схема редукции размерности.
Задачи многомерной многоэкстремальной оптимизации обладают вычислительной
сложностью, что определяется, прежде всего, экспоненциальным ростом объема вычислений
при увеличении размерности (числа варьируемых параметров). Кроме того, во многих слу-
чаях расчет значений функционалов оптимизационной задачи (целевой функции и ограниче-
ний) требует существенного объема вычислений, поскольку зачастую связан с проведением
вычислительного эксперимента с той или иной математической моделью исследуемого
объекта, системы или явления. Именно на такие вычислительно-трудоемкие задачи ориенти-
рована разработка параллельных методов многомерной многоэкстремальной оптимизации в
настоящей работе.
Задачи многомерной многоэкстремальной оптимизации и многошаговая схема ре-
дукции размерности. Задача многомерной многоэкстремальной оптимизации может быть
представлена как проблема поиска наименьшего значения действительной функции φ(y)
φ(y*) = min{φ(y): y∈D},
(1)
где D есть область поиска, представляющая собой некоторый гиперпараллелепипед
N-мерного евклидова пространства.
Многие методы решения многомерных многоэкстремальных оптимизационных задач
используют многошаговую схему редукции размерности, согласно которой решение задачи
(1) может быть получено посредством решения последовательности „вложенных“ одномер-
ных задач (см., например, [1—3]):
min
y∈D
ϕ ( y) =
min y1∈[a1,b1]
…
min yN∈[aN ,bN ]
ϕ ( y1,
...,
yN
)
.
(2)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10
Адаптивные параллельные вычисления для многомерной многоэкстремальной оптимизации 77
Согласно выражению (2), решение многомерной многоэкстремальной задачи оптимиза-
ции сводится к решению одномерной задачи:
ϕ*
= min
y∈D
ϕ ( y) =
min y1∈[a1,b1]
ϕ1( y1)
,
(3)
где
ϕ i ( yi ) = ϕi ( y1, ...,
yi ) =
min yi [+1∈ ai+1,bi+1]
ϕi+1( y1, ...,
yi ,
yi+1) ,
1≤i < N ,
(4)
ϕN ( y1, ..., yN ) = ϕ ( y1, ..., yN ) .
(5)
Правила (3)—(5) определяют множество задач
Fl ={ϕ i ( yi ), 1≤ i ≤ l} ,
(6)
порождаемых в соответствии с многошаговой схемой редукции. Количество задач в множе-
стве Fl в процессе поиска может изменяться: увеличиваться при переходе к следующей переменной и уменьшаться по завершении решения какой-либо из задач (можно отметить, что
при этом количество задач не превышает размерности решаемой задачи N). При этом актив-
ной — решаемой — в множестве Fl является только одна задача — с максимальным номером варьируемой переменной.
Многошаговой схеме редукции размерности присущи определенные недостатки — так,
например, вычисления являются избыточными, поскольку решение исходной задачи оптими-
зации сводится к минимизации одномерных функций в раздельных подобластях области
поиска.
Для повышения эффективности глобального поиска может быть предложена обобщен-
ная (адаптивная) многошаговая схема редукции размерности, в которой осуществляется од-
новременное решение всех задач множества Fl из (6). В этом случае при решении каждой задачи множества Fl могут быть использованы результаты решения всех других задач семейства и, кроме того, решение задач может осуществляться параллельно с использованием много-
процессорных многоядерных вычислительных систем [4]. Применение высокопроизводи-
тельных компьютеров позволит существенно повысить сложность решаемых задач глобаль-
ной оптимизации.
Выполнение итерации глобального поиска для любой задачи множества Fl с номером переменной, меньшим, чем N (N есть размерность решаемой задачи), будет порождать новую
одномерную задачу вида (4), и, тем самым, количество задач в семействе Fl может оказаться значительным (десятки и сотни тысяч).
Вычислительная схема параллельного глобального поиска для адаптивной мно-
гошаговой схемы редукции размерности. Введем множество номеров задач семейства Fl из множества (6):
L = {1, 2, … , l}
и пусть для проведения вычислений имеется p>1 процессоров. Распределим имеющиеся зада-
чи между процессорами — данное распределение можно зафиксировать при помощи соот-
ветствующего разделения множества L на подмножества:
Π = {π1, π2, … , πp}, πi = {js : js ∈L, 1≤s≤ li}, 1 ≤ i ≤ p, ∀ i∈L ∃ j : i∈πj, ∀ i,j ⇒ πi∩πj ={∅},
(7)
где πi (1 ≤ i ≤ p) есть множество задач, распределенных для решения на процессоре i. Построенная схема является децентрализованной — все процессоры работают парал-
лельно и самостоятельно генерируют точки проведения испытаний. С другой стороны, между
процессорами существует информационное взаимодействие — при получении в какой-то за-
даче новой улучшенной оценки минимального значения оптимизируемой функции эта оценка
должна передаваться задаче-родителю. Поскольку решаемые задачи теперь распределены
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10
78 А. В. Гергель
между процессорами, то передача получаемых оценок может приводить к сложным инфор-
мационным зависимостям между процессорами. Для минимизации числа таких зависимостей
распределение решаемых оптимизационных задач между процессорами должно быть согла-
совано со структурой задач.
Для решения проблемы распределения задач между процессорами может быть предло-
жена простая и эффективная децентрализованная схема вычислений, в которой в достаточной
степени учитывается иерархическая структура зависимости решаемых задач оптимизации.
Пусть номера терминальных задач (задач, в которых номер варьируемой переменной
равен n) образуют множество
Ln = {ij : ij ∈L, 1 ≤ j ≤ ln}. Распределим терминальные задачи между процессорами и представим применяемое
распределение по аналогии с (7) при помощи множества:
Πn = {π0, π1, π2, … , πp}, π0= L Ln, πi = {js : js ∈ Ln, 1 ≤ s ≤ li}, 1 ≤ i ≤ p,
(8)
∀ i∈L ∃ j : i∈πj, ∀ i,j ⇒ πi ∩ πj ={∅}.
В (8) каждое подмножество πi определяет список терминальных задач, распределенных
для решения на процессоре i. Подмножество π0 содержит номера всех структурных задач (за-
дач с уровнем, меньшим n). Вопрос распределения задач подмножества π0 по процессорам необходимо разрешить дополнительно; в наиболее простом случае для задач данного под-
множества можно выделить дополнительный процессор. Новая схема (8) отличается система-
тическим характером информационных взаимодействий между процессорами. Процессоры с
терминальными задачи пересылают получаемые оценки минимальных значений исходной
оптимизируемой задачи только управляющему процессору. Управляющий процессор зани-
мается обработкой только структурных задач без выполнения трудоемких вычислений значе-
ний функционалов исходной решаемой задачи. При этом управляющий процессор может по-
рождать терминальные задачи и в этом случае задачи должны переправляться для выполне-
ния на те или иные процессоры с терминальными задачами.
Работа выполнена при поддержке РФФИ (грант № 07-01-00467-а) и Совета по грантам Президента Российской Федерации по государственной поддержке ведущих научных школ Российской Федерации (грант № НШ-4694.2008.9).
СПИСОК ЛИТЕРАТУРЫ
1. Стронгин Р. Г. Численные методы в многоэкстремальных задачах. М.: Наука, 1978.
2. Strongin R. G., Sergeyev Ya. D. Global Optimization with non-convex constraints: Sequential and parallel algorithms. Dordrecht: Kluwer Academic Publishers, 2000.
3. Городецкий С. Ю., Гришагин В. А. Нелинейное программирование и многоэкстремальная оптимизация. Н. Новгород: Изд-во ННГУ, 2007.
4. Гергель В. П. Теория и практика параллельных вычислений. М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2007.
Александр Викторович Гергель
Сведения об авторе — Нижегородский государственный университет им Н. И. Лобачевского,
кафедра математического обеспечения ЭВМ; программист 1 категории; E-mail: gergelm@unn.ru
Рекомендована институтом
Поступила в редакцию 10.03.09 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10
УДК 519.85
А. В. ГЕРГЕЛЬ
АДАПТИВНЫЕ ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ ДЛЯ МНОГОМЕРНОЙ МНОГОЭКСТРЕМАЛЬНОЙ ОПТИМИЗАЦИИ
Рассматриваются методы решения многомерных многоэкстремальных задач, использующие многошаговую схему редукции размерности. Предложена новая схема параллельного глобального поиска на основе адаптивной многошаговой схемы редукции размерности.
Ключевые слова: многомерная многоэкстремальная оптимизация, алгоритмы параллельного глобального поиска, адаптивная многошаговая схема редукции размерности.
Задачи многомерной многоэкстремальной оптимизации обладают вычислительной
сложностью, что определяется, прежде всего, экспоненциальным ростом объема вычислений
при увеличении размерности (числа варьируемых параметров). Кроме того, во многих слу-
чаях расчет значений функционалов оптимизационной задачи (целевой функции и ограниче-
ний) требует существенного объема вычислений, поскольку зачастую связан с проведением
вычислительного эксперимента с той или иной математической моделью исследуемого
объекта, системы или явления. Именно на такие вычислительно-трудоемкие задачи ориенти-
рована разработка параллельных методов многомерной многоэкстремальной оптимизации в
настоящей работе.
Задачи многомерной многоэкстремальной оптимизации и многошаговая схема ре-
дукции размерности. Задача многомерной многоэкстремальной оптимизации может быть
представлена как проблема поиска наименьшего значения действительной функции φ(y)
φ(y*) = min{φ(y): y∈D},
(1)
где D есть область поиска, представляющая собой некоторый гиперпараллелепипед
N-мерного евклидова пространства.
Многие методы решения многомерных многоэкстремальных оптимизационных задач
используют многошаговую схему редукции размерности, согласно которой решение задачи
(1) может быть получено посредством решения последовательности „вложенных“ одномер-
ных задач (см., например, [1—3]):
min
y∈D
ϕ ( y) =
min y1∈[a1,b1]
…
min yN∈[aN ,bN ]
ϕ ( y1,
...,
yN
)
.
(2)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10
Адаптивные параллельные вычисления для многомерной многоэкстремальной оптимизации 77
Согласно выражению (2), решение многомерной многоэкстремальной задачи оптимиза-
ции сводится к решению одномерной задачи:
ϕ*
= min
y∈D
ϕ ( y) =
min y1∈[a1,b1]
ϕ1( y1)
,
(3)
где
ϕ i ( yi ) = ϕi ( y1, ...,
yi ) =
min yi [+1∈ ai+1,bi+1]
ϕi+1( y1, ...,
yi ,
yi+1) ,
1≤i < N ,
(4)
ϕN ( y1, ..., yN ) = ϕ ( y1, ..., yN ) .
(5)
Правила (3)—(5) определяют множество задач
Fl ={ϕ i ( yi ), 1≤ i ≤ l} ,
(6)
порождаемых в соответствии с многошаговой схемой редукции. Количество задач в множе-
стве Fl в процессе поиска может изменяться: увеличиваться при переходе к следующей переменной и уменьшаться по завершении решения какой-либо из задач (можно отметить, что
при этом количество задач не превышает размерности решаемой задачи N). При этом актив-
ной — решаемой — в множестве Fl является только одна задача — с максимальным номером варьируемой переменной.
Многошаговой схеме редукции размерности присущи определенные недостатки — так,
например, вычисления являются избыточными, поскольку решение исходной задачи оптими-
зации сводится к минимизации одномерных функций в раздельных подобластях области
поиска.
Для повышения эффективности глобального поиска может быть предложена обобщен-
ная (адаптивная) многошаговая схема редукции размерности, в которой осуществляется од-
новременное решение всех задач множества Fl из (6). В этом случае при решении каждой задачи множества Fl могут быть использованы результаты решения всех других задач семейства и, кроме того, решение задач может осуществляться параллельно с использованием много-
процессорных многоядерных вычислительных систем [4]. Применение высокопроизводи-
тельных компьютеров позволит существенно повысить сложность решаемых задач глобаль-
ной оптимизации.
Выполнение итерации глобального поиска для любой задачи множества Fl с номером переменной, меньшим, чем N (N есть размерность решаемой задачи), будет порождать новую
одномерную задачу вида (4), и, тем самым, количество задач в семействе Fl может оказаться значительным (десятки и сотни тысяч).
Вычислительная схема параллельного глобального поиска для адаптивной мно-
гошаговой схемы редукции размерности. Введем множество номеров задач семейства Fl из множества (6):
L = {1, 2, … , l}
и пусть для проведения вычислений имеется p>1 процессоров. Распределим имеющиеся зада-
чи между процессорами — данное распределение можно зафиксировать при помощи соот-
ветствующего разделения множества L на подмножества:
Π = {π1, π2, … , πp}, πi = {js : js ∈L, 1≤s≤ li}, 1 ≤ i ≤ p, ∀ i∈L ∃ j : i∈πj, ∀ i,j ⇒ πi∩πj ={∅},
(7)
где πi (1 ≤ i ≤ p) есть множество задач, распределенных для решения на процессоре i. Построенная схема является децентрализованной — все процессоры работают парал-
лельно и самостоятельно генерируют точки проведения испытаний. С другой стороны, между
процессорами существует информационное взаимодействие — при получении в какой-то за-
даче новой улучшенной оценки минимального значения оптимизируемой функции эта оценка
должна передаваться задаче-родителю. Поскольку решаемые задачи теперь распределены
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10
78 А. В. Гергель
между процессорами, то передача получаемых оценок может приводить к сложным инфор-
мационным зависимостям между процессорами. Для минимизации числа таких зависимостей
распределение решаемых оптимизационных задач между процессорами должно быть согла-
совано со структурой задач.
Для решения проблемы распределения задач между процессорами может быть предло-
жена простая и эффективная децентрализованная схема вычислений, в которой в достаточной
степени учитывается иерархическая структура зависимости решаемых задач оптимизации.
Пусть номера терминальных задач (задач, в которых номер варьируемой переменной
равен n) образуют множество
Ln = {ij : ij ∈L, 1 ≤ j ≤ ln}. Распределим терминальные задачи между процессорами и представим применяемое
распределение по аналогии с (7) при помощи множества:
Πn = {π0, π1, π2, … , πp}, π0= L Ln, πi = {js : js ∈ Ln, 1 ≤ s ≤ li}, 1 ≤ i ≤ p,
(8)
∀ i∈L ∃ j : i∈πj, ∀ i,j ⇒ πi ∩ πj ={∅}.
В (8) каждое подмножество πi определяет список терминальных задач, распределенных
для решения на процессоре i. Подмножество π0 содержит номера всех структурных задач (за-
дач с уровнем, меньшим n). Вопрос распределения задач подмножества π0 по процессорам необходимо разрешить дополнительно; в наиболее простом случае для задач данного под-
множества можно выделить дополнительный процессор. Новая схема (8) отличается система-
тическим характером информационных взаимодействий между процессорами. Процессоры с
терминальными задачи пересылают получаемые оценки минимальных значений исходной
оптимизируемой задачи только управляющему процессору. Управляющий процессор зани-
мается обработкой только структурных задач без выполнения трудоемких вычислений значе-
ний функционалов исходной решаемой задачи. При этом управляющий процессор может по-
рождать терминальные задачи и в этом случае задачи должны переправляться для выполне-
ния на те или иные процессоры с терминальными задачами.
Работа выполнена при поддержке РФФИ (грант № 07-01-00467-а) и Совета по грантам Президента Российской Федерации по государственной поддержке ведущих научных школ Российской Федерации (грант № НШ-4694.2008.9).
СПИСОК ЛИТЕРАТУРЫ
1. Стронгин Р. Г. Численные методы в многоэкстремальных задачах. М.: Наука, 1978.
2. Strongin R. G., Sergeyev Ya. D. Global Optimization with non-convex constraints: Sequential and parallel algorithms. Dordrecht: Kluwer Academic Publishers, 2000.
3. Городецкий С. Ю., Гришагин В. А. Нелинейное программирование и многоэкстремальная оптимизация. Н. Новгород: Изд-во ННГУ, 2007.
4. Гергель В. П. Теория и практика параллельных вычислений. М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2007.
Александр Викторович Гергель
Сведения об авторе — Нижегородский государственный университет им Н. И. Лобачевского,
кафедра математического обеспечения ЭВМ; программист 1 категории; E-mail: gergelm@unn.ru
Рекомендована институтом
Поступила в редакцию 10.03.09 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10