О реализации параллельного алгоритма для решения многоэкстремальных задач
Рассматривается параллельная реализация метода мультистарта для нахождения решений многоэкстремальных задач на вычислительном кластере в системе MPI. Приведены результаты применения для решения задач выбора непрерывных мощностей из заданного интервала для энергоблоков. Использовался кластер Институт...
Gespeichert in:
| Veröffentlicht in: | Теорія оптимальних рішень |
|---|---|
| Datum: | 2010 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/46670 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | О реализации параллельного алгоритма для решения многоэкстремальных задач / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 3-9. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860255552433553408 |
|---|---|
| author | Лиховид, А.П. |
| author_facet | Лиховид, А.П. |
| citation_txt | О реализации параллельного алгоритма для решения многоэкстремальных задач / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 3-9. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Рассматривается параллельная реализация метода мультистарта для нахождения решений многоэкстремальных задач на вычислительном кластере в системе MPI. Приведены результаты применения для решения задач выбора непрерывных мощностей из заданного интервала для энергоблоков. Использовался кластер Института кибернетики имени В.М. Глушкова СКИТ-3 для проведения вычислительных экспериментов.
Розглянуто паралельну реалізацію метода мультистарта для знахождення рішень багатоекстремальних задач на обчислювальному кластері в системі MPI. Наведено результати застосування для розв’язування задач вибору неперервних потужностей із заданого інтервалу для енергоблоків. Використовувався кластер Інституту кібернетики імені В.М. Глушкова СКІТ-3 для проведення обчислювальних експериментів.
A parallel implementation of multistart method for finding solutions of multiextremal problems on cluster computing complex with MPI system is considered. The results of applications for solving problems of choice of continuous loads from a given interval for power units are presented. For the computational experiments a cluster of the Institute of Cybernetics SCIT-3 was used.
|
| first_indexed | 2025-12-07T18:49:00Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2010, № 9 3
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматривается параллельная
реализация метода мультистар-
та для нахождения решений мно-
гоэкстремальных задач на вычис-
лительном кластере в системе
MPI. Приведены результаты
применения для решения задач
выбора непрерывных мощностей
из заданного интервала для энер-
гоблоков. Использовался кластер
Института кибернетики имени
В.М. Глушкова СКИТ-3 для прове-
дения вычислительных экспери-
ментов.
А.П. Лиховид, 2010
ÓÄÊ 519.8
À.Ï. ËÈÕÎÂÈÄ
Î ÐÅÀËÈÇÀÖÈÈ ÏÀÐÀËËÅËÜÍÎÃÎ
ÀËÃÎÐÈÒÌÀ ÄËß ÐÅØÅÍÈß
ÌÍÎÃÎÝÊÑÒÐÅÌÀËÜÍÛÕ ÇÀÄÀ×1
Введение. В данной работе рассматривается
параллельная реализация метода мульти-
старта для нахождения решений многоэкс-
тремальных задач на вычислительном кла-
стере. Приведены результаты применения
для решения задач выбора непрерывных
мощностей из заданного интервала для энер-
гоблоков [1]. Использовался кластер Инсти-
тута кибернетики имени В.М. Глушкова
СКИТ-3 (суперкомпьютер для реализации
информационных технологий) [2] для прове-
дения вычислительных экспериментов.
Метод мультистарта для нахождения гло-
бального оптимального решения многоэкс-
тремальной задачи можно представить в ви-
де следующей процедуры: с помощью алго-
ритмов локального поиска находятся опти-
мальные локальные решения с различных
начальных точек, генерируемых случайным
или детерминированным образом, и среди
полученных решений выбирается наилучшее
(минимальное или максимальное). При дос-
таточно большом количестве запусков поиска
локальных решений есть вероятность найти
глобальное оптимальное решение. Очевидно,
что этот метод является существенно трудо-
емким, но при этом его легко можно распа-
раллелить и реализовать вычисления, на-
пример, на кластере.
1 Работа выполнена при частичной финансо-
вой поддержке совместного украинско-
российского проекта ДФФД-Ф28.1/005 и РФФИ-
09-01-90413-Укр_ф_а
А.П. ЛИХОВИД
4 Теорія оптимальних рішень. 2010, № 9
Параллельная реализация метода мультистарта. Решение задачи прово-
дится на p процессорах. Сгенерированная случайным образом в "ведущем"
(Master) процессоре начальная точка передается на любой другой свободный
(Slave) процессор с помощью операции пересылки системы MPI. Там происхо-
дит вычисление локального оптимального решения для этой начальной точки с
помощью алгоритма выпуклой оптимизации. Затем найденное оптимальное ре-
шение передается в "ведущий" процессор, где происходит сравнение полученно-
го оптимального решения с наилучшим из найденных до этого момента значе-
нием ("рекордом"). Если текущее решение меньше "рекорда", то оно становится
"рекордом". По истечении заданного количества запусков поиска локального
решения значение "рекорда" принимается за решение исходной задачи.
Приведенный параллельный метод мультистарта был реализаван на языке
программирования С++ в программной среде MPI [3]. Для нахождения локаль-
ных решений многоэкстремальной задачи использовался r -алгоритм [4]. Про-
веден ряд численных экспериментов на кластерном комплексе СКИТ-3 Институ-
та кибернетики для решения задач загрузки энергоблоков, результаты которых
приводятся далее.
Нелинейная модель загрузки энергоблоков. Пусть энергоблок i может
работать в режимах мощностей из заданного непрерывного диапазона
[ , ]low up
i iP P , где
low
iP – нижняя граница по его мощности, а
up
iP – верхняя гра-
ница. Пусть функция затрат условного топлива ( )if x является функцией от ар-
гумента [ , ]low up
i i
x P P∈ и заданы потребности в электроэнергии для каждого пе-
риода
tE . Рассмотрим следующую оптимизационную задачу :
*
,
=1 =1
= min ( )
T N
C i i t
t i
f f x∑∑ (1)
при ограничениях
,
=1
= , = 1, , ,
N
i t t
i
x E t T∀∑ K (2)
, , = 1, , , = 1, , .low up
i i t iP x P i N t T≤ ≤ ∀ ∀K K (3)
Здесь ,( )i i tf x – функция затрат условного топлива для i -го энергоблока, кото-
рая для тестового примера имеет следующий вид:
3 2
, , , ,( ) = ( ) ( ) ( ) ,i i t i i t i i i t i i i t i if x a x b x c x d− ∆ + − ∆ + − ∆ +
где , , , ,i i i i ia b c d ∆ – заданные параметры.
Используя метод точных штрафных функций [4] сведем задачу (1)–(3) к за-
даче безусловной минимизации следующей негладкой функции:
О РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА …
Теорія оптимальних рішень. 2010, № 9 5
, 1 , 2 , ,
=1 =1 =1 =1 =1 =1
( ) = ( ) | | max{0, , }.
N T T N T N
up low
i i t i t t i t i i i t
i t t i t i
F x f x Q x E Q x P P x+ − + − −∑∑ ∑ ∑ ∑∑ (4)
Здесь
1Q и
2Q – штрафные множители, соответствующие учету с помощью не-
гладких штрафов ограничений (2) в форме равенств и ограничений (3) в форме
неравенств.
Функция (4) является многоэкстремальной. Для нахождения ее глобального
оптимального решения использовался вышеописанный параллельный метод
мультистарта, в котором для поиска локальных решений был выбран
r -алгоритм [4].
Вычислительный эксперимент. Для вышеописанной тестовой задачи про-
водился вычислительный эксперимент со следующими параметрами: количество
энергоблоков равнялось 10, что, например, соответствует количеству энергобло-
ков для Криворожской ТЭС. Число интервалов в планируемом было равным 24.
Значения потребностей в электрической энергии для 24 интервалов выбирались
как соответствующие реальным пиковым потребностям в течении суток (рис. 1).
Мощности энергоблоков были приняты в интервале 120–280. График функции
затрат условного топлива для каждого энергоблока для тестового примера пока-
зан на рис. 2.
Количестово генерируемых точек для метода мультистарта и, соответствен-
но, запусков поиска локального решения равнялось 25. Эти точки генерирова-
лись случайным образом с помощью функции равномерного распределения.
Общее количество процессоров кластера варьировалось от 1 до 26.
А.П. ЛИХОВИД
6 Теорія оптимальних рішень. 2010, № 9
РИС. 1. Потребности в электрической энергии для тестового примера
РИС. 2. График функции затрат для тестового примера
При реализации параллельных алгоритмов, проводится исследование уско-
О РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА …
Теорія оптимальних рішень. 2010, № 9 7
рения и эффективности параллельного алгоритма. Ускорение вычисляется по
формуле
0 / , 1, ,i iS t t i n= = K , где
0t – время работы последовательного алгорит-
ма, а it – время решения задачи параллельным алгоритмом с использованием i
процессоров. Говорят, что достигнуто линейное ускорение, если
0 / , 1, ,it t i i n= ∀ = K . Второй исследуемой величиной является эффективность
параллельного алгоритма, которая вычисляется по формуле /i iE S i= .
Результаты вычислительных экспериментов для тестовой задачи приведены
в таблице. Здесь n – общее число процессоров, t – время решения задачи в се-
кундах, _N slave – число slave-процессоров, iS – ускорение, iE – эффектив-
ность параллельного алгоритма.
На рис. 3 показаны зависимости времени решения тестового примера от ко-
личества использованных процессоров, на рис. 4 – график ускорения в сравне-
нии с «идеальным» линейным ускорением.
В процессе вычислений найдено несколько различных локальных опти-
мальных решений, среди которых выбрано решение с наименьшим значением
функции затрат.
ТАБЛИЦА. Время решения, ускорение и эффективность
n N_slave t
iS iE
1 0 68,47 1 1,00
2 1 87,99 0,78 0,39
3 2 35,24 1,94 0,65
4 3 24,54 2,79 0,70
8 7 14,25 4,80 0,60
11 10 10,43 6,56 0,60
16 15 7,26 9,43 0,59
21 20 5,6 12,23 0,58
26 25 3,32 20,62 0,79
А.П. ЛИХОВИД
8 Теорія оптимальних рішень. 2010, № 9
68,47
87,99
35,24
24,54
14,25
10,43
7,26
5,6
3,32
0
10
20
30
40
50
60
70
80
90
100
1 2 3 4 8 11 16 21 26
Количество процессоров
В
р
е
м
я
р
е
ш
е
н
и
я
РИС. 3. Зависимость времени решения от количества процессоров
0,78
1,94
2,79
4,80
6,56
9,43
12,23
20,62
1
2
3
7
10
15
20
25
0,00
5,00
10,00
15,00
20,00
25,00
30,00
Slave-процессоры
У
с
к
о
р
е
н
и
е
кластер
идеал
РИС. 4. Ускорение для тестового примера
О РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА …
Теорія оптимальних рішень. 2010, № 9 9
Из таблицы и рис. 4 видно, что, например, для семи slave-процессоров время
решения задачи уменьшается в 4,8 раза, для десяти – в 6,56 раза, двадцати – в
12,23 раза, а для двадцати пяти – в 20,62 раза.
Заключение. Результаты вычислительных экспериментов для задачи
загрузки энергоблоков подтверждают возможность применения параллельной
реализации метода мультистарта для решения различных практических невы-
пуклых экстремальных задач на кластере. Данный метод можно усовершенство-
вать, например, используя значение "рекорда" для принятия решения о преры-
вании процесса поиска локального оптимума.
О.П. Лиховид
ПРО РЕАЛІЗАЦІЮ ПАРАЛЕЛЬНОГО АЛГОРИТМУ ДЛЯ РОЗВ’ЯЗУВАННЯ
БАГАТОЕКСТРЕМАЛЬНИХ ЗАДАЧ
Розглянуто паралельну реалізацію метода мультистарта для знахождення рішень багатоекст-
ремальних задач на обчислювальному кластері в системі MPI. Наведено результати застосу-
вання для розв’язування задач вибору неперервних потужностей із заданого інтервалу для
енергоблоків. Використовувався кластер Інституту кібернетики імені В.М. Глушкова СКІТ-3
для проведення обчислювальних експериментів.
O.P. Lykhovyd
ON IMPLEMENTATION OF PARALLEL ALGORITHM FOR SOLVING MULTIEXTREMAL
PROBLEMS
A parallel implementation of multistart method for finding solutions of multiextremal problems on
cluster computing complex with MPI system is considered. The results of applications for solving
problems of choice of continuous loads from a given interval for power units are presented. For the
computational experiments a cluster of the Institute of Cybernetics SCIT-3 was used.
1. Стецюк П.И., Пилиповский А.В. Математическая модель оптимальной загрузки
мощностей энергосистемы с учетом их маневренности // Праці IV міжнар. шк.-
семінару "Теорія прийняття рішення". – Ужгород: УжНУ, 2008. – С. 159.
2. Кластерный комплекс Института кибернетики. Кластерный комплекс СКИТ.
https://icybcluster.org.ua/.
3. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург,
2002. – 608 с.
4. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. –
Киев: Наук. думка, 1979. – 199 с.
Получено 31.03.2010
|
| id | nasplib_isofts_kiev_ua-123456789-46670 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T18:49:00Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Лиховид, А.П. 2013-07-06T05:50:50Z 2013-07-06T05:50:50Z 2010 О реализации параллельного алгоритма для решения многоэкстремальных задач / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 3-9. — Бібліогр.: 4 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/46670 519.8 Рассматривается параллельная реализация метода мультистарта для нахождения решений многоэкстремальных задач на вычислительном кластере в системе MPI. Приведены результаты применения для решения задач выбора непрерывных мощностей из заданного интервала для энергоблоков. Использовался кластер Института кибернетики имени В.М. Глушкова СКИТ-3 для проведения вычислительных экспериментов. Розглянуто паралельну реалізацію метода мультистарта для знахождення рішень багатоекстремальних задач на обчислювальному кластері в системі MPI. Наведено результати застосування для розв’язування задач вибору неперервних потужностей із заданого інтервалу для енергоблоків. Використовувався кластер Інституту кібернетики імені В.М. Глушкова СКІТ-3 для проведення обчислювальних експериментів. A parallel implementation of multistart method for finding solutions of multiextremal problems on cluster computing complex with MPI system is considered. The results of applications for solving problems of choice of continuous loads from a given interval for power units are presented. For the computational experiments a cluster of the Institute of Cybernetics SCIT-3 was used. Работа выполнена при частичной финансовой поддержке совместного украинско-российского проекта ДФФД-Ф28.1/005 и РФФИ-09-01-90413-Укр_ф_а ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень О реализации параллельного алгоритма для решения многоэкстремальных задач Про реалізацію паралельного алгоритму для розв’язування багатоекстремальних задач On implementation of parallel algorithm for solving multiextremal problems Article published earlier |
| spellingShingle | О реализации параллельного алгоритма для решения многоэкстремальных задач Лиховид, А.П. |
| title | О реализации параллельного алгоритма для решения многоэкстремальных задач |
| title_alt | Про реалізацію паралельного алгоритму для розв’язування багатоекстремальних задач On implementation of parallel algorithm for solving multiextremal problems |
| title_full | О реализации параллельного алгоритма для решения многоэкстремальных задач |
| title_fullStr | О реализации параллельного алгоритма для решения многоэкстремальных задач |
| title_full_unstemmed | О реализации параллельного алгоритма для решения многоэкстремальных задач |
| title_short | О реализации параллельного алгоритма для решения многоэкстремальных задач |
| title_sort | о реализации параллельного алгоритма для решения многоэкстремальных задач |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/46670 |
| work_keys_str_mv | AT lihovidap orealizaciiparallelʹnogoalgoritmadlârešeniâmnogoékstremalʹnyhzadač AT lihovidap prorealízacíûparalelʹnogoalgoritmudlârozvâzuvannâbagatoekstremalʹnihzadač AT lihovidap onimplementationofparallelalgorithmforsolvingmultiextremalproblems |