Одержано 02.06.2021; Виправлено 09.06.2021; Прийнято 24.06.2021

Надруковано 30.06.2021; Вперше Online 01.07.2021

https://doi.org/10.34229/2707-451X.21.2.1

Попередня  |  Повний текст  |  Наступна

 

УДК 519.854

Про ефективність роботи портфелів алгоритмів дискретної оптимізації

І.В. Сергієнко ,   В.П. Шило,   В.О. Рощин,   П.В. Шило ^*

Інститут кібернетики імені В.М. Глушкова НАН України, Київ

^* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

Вступ. При розв’язанні дискретних оптимізаційних задач великої розмірності виникає необхідність обробки великих обсягів інформації за прийнятний час. Ефективне розв’язання таких задач можливе тільки на багатопроцесорних обчислювальних комплексах. Проте не існує простого способу адаптувати існуючі алгоритми оптимізації для повної реалізації потужностей цих комплексів. Такі обчислювальні ресурси не можна використовувати без ефективних паралельних методів. У зв'язку з цим важливу роль відіграють об’єднання (портфелі і команди) алгоритмів для розпаралелювання процесу розв’язання задач дискретної оптимізації.

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

Результати. Розглянуто однорідні і неоднорідні портфелі алгоритмів. Для задачі про максимальний зважений розріз графу, що має численні практичні застосування, створено однорідні портфелі двох стохастичних алгоритмів локальної оптимізації. Наведено результати експериментальних досліджень, які підтверджують їхню ефективність.

Висновки. Портфелі алгоритмів можна використовувати для розв’язання інших класів задач дискретної оптимізації з метою прискорення обчислювального процесу. В подальшому доцільно також використовувати обмін отриманою інформацією між алгоритмами, тобто розглядати команди і портфелі команд алгоритмів. Обмін інформацією дасть змогу посилити кращі якості алгоритмів, що призведе до зменшення часу їхньої роботи і покращення якості розв’язків.

 

Ключові слова: дискретна оптимізація, портфелі алгоритмів, експериментальні розрахунки.

 

Цитувати так: Сергієнко І.В., Шило В.П., Рощин В.О., Шило П.В. Про ефективність роботи портфелів алгоритмів дискретної оптимізації. Cybernetics and Computer Technologies. 2021. 2. С. 5–12. https://doi.org/10.34229/2707-451X.21.2.1

 

Список літератури

           1.     Gomes C.P., Selman B. Algorithm portfolios. Artificial Intelligence. 2001. Vol. 126, N 1–2. P. 43–62. https://doi.org/10.1016/S0004-3702(00)00081-3

           2.     Huberman B.A. An economics approach to hard computational problems. Science. 1997. Vol. 275, N 5296. P. 51–54. https://doi.org/10.1126/science.275.5296.51

           3.     Chabrier A., Danna E., Pape C.L., Perron L. Solving a network design problem. Annals of Oper. Res. 2004. Vol. 130, N 1–4. P. 217–239. https://doi.org/10.1023/B:ANOR.0000032577.81139.84

           4.     Шило В.П., Рощин В.А., Шило П.В. Построение портфеля алгоритмов для распараллеливания процесса решения задачи о максимальном взвешенном разрезе графа. Компьютерная математика. Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2014. № 2. C. 163–170.

           5.     Shylo V.P., Glover F., Sergienko I.V. Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel. Кибернетика и системный анализ. 2015. Т. 51, № 1. С. 20–29. https://doi.org/10.1007/s10559-015-9692-2

           6.     Shylo V.P., Shylo O.V. Algorithm Portfolios and Teams in Parallel Optimization. Optimization Methods and Applications. S. Butenko, P.M. Pardalos, V. Shylo (eds.). New York: Springer, 2017. P. 481–493. https://doi.org/10.1007/978-3-319-68640-0_23

           7.     Mostovyi O., Prokopyev O.A., Shylo O.V. On maximum speedup ratio of restart algorithm portfolios. INFORMS J. on Computing. 2013. Vol. 25, N 2. Р. 222–229. https://doi.org/10.1287/ijoc.1120.0497

           8.     Shylo O.V., Prokopyev O.A., Rajgopal J. On algorithm portfolios and restart strategies. Oper. Res. Lett. 2011. Vol. 39, N 1. P. 49–52. https://doi.org/10.1016/j.orl.2010.10.003

           9.     Шило В.П. Метод глобального равновесного поиска. Кибернетика и системный анализ. 1999. Т. 35, № 1. С. 74–81. http://nbuv.gov.ua/UJRN/KSA_2012_48_4_10

       10.     Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения, исследования. Киев: Наукова думка, 2003. 264 с.

       11.     Helmberg C., Rendl F. A spectral bundle method for semidefinite programming. SIAM J. on Optimization. 2000. Vol. 10. P. 673–696. https://doi.org/10.1137/S1052623497328987

       12.     Burer S., Monteiro R.D.C., Zhang Y. Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs. SIAM J. on Optimization. 2002. Vol. 12. P. 503–521. https://doi.org/10.1137/S1052623400382467

       13.     Glover F., Laguna M., Marti R. Fundamentals of scatter search and path relinking. Control and Cybernetics. 2000. Vol. 39. P. 653–684.

       14.     Benlic U., Hao J.K. Breakout local search for the max-cut problem. J. Engineering Applications of Artificial Intelligence. 2013. Vol. 26, N 3. P. 1162–1173 https://doi.org/10.1016/j.engappai.2012.09.001

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  Повний текст  |  Наступна