Отправить статью по E-mail 
СРАВНЕНИЕ ПАРАЛЛЕЛЬНЫХ РЕАЛИЗАЦИЙ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ СИСТЕМ С ОБЩЕЙ ПАМЯТЬЮ
- Авторы: Горчаков А.Ю.1, Посыпкин М.А.1
-
Учреждения:
- ФИЦ ИУ РАН
- Выпуск: № 2 (2023)
- Страницы: 108-122
- Раздел: УПРАВЛЕНИЕ В СТОХАСТИЧЕСКИХ СИСТЕМАХ И В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ
- URL: https://kld-journal.fedlab.ru/0002-3388/article/view/676502
- DOI: https://doi.org/10.31857/S0002338823020099
- EDN: https://elibrary.ru/JDULMW
- ID: 676502
Цитировать
Полный текст
Открытый доступ
Доступ предоставлен
Доступ платный или только для подписчиков
Аннотация
Рассматривается четыре параллельных алгоритма, реализующих метод ветвей и границ для решения задач поиска глобального минимума. Алгоритмы предназначены для вычислительных систем с общей памятью. Метод ветвей и границ базируется на двух основных операциях – ветвление и отсев. Для реализации операции отсева используется интервальная арифметика, которая для вещественных интервалов определяет операции, аналогичные обычным арифметическим. Основное отличие алгоритмов заключается в различной реализации хранения списка подзадач. В процессе тестирования на представительном наборе тестовых задач исследованы быстродействие алгоритмов, масштабируемость и устойчивость к аномалиям поиска.
Об авторах
А. Ю. Горчаков
ФИЦ ИУ РАН
Email: agorchakov@frccsc.ru
Россия, Москва
М. А. Посыпкин
ФИЦ ИУ РАН
Автор, ответственный за переписку.
Email: mposypkin@frccsc.ru
Россия, Москва
Список литературы
- Евтушенко Ю.Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) // ЖВМ и МФ. 1971. Т. 11. № 6. С. 1390–1403.
- Lawler E.L., Wood D.E. Branch-and-Bound Methods: A survey // Operations research. 1966. V. 14. № 4. P. 699–719.
- Евтушенко Ю.Г., Посыпкин М.А. Применение метода неравномерных покрытий для глобальной оптимизации частично целочисленных нелинейных задач // ЖВМ и МФ. 2011. Т. 51. № 8. С. 1376–1389.
- Karnopp D.C. Random Search Techniques for Optimization Problems // Automatica. 1963. V. 1. № 2–3. P. 111–121.
- Solis F.J., Wets R.J.B. Minimization by Random Search Techniques // Mathematics of Operations Research. 1981. V. 6. № 1. P. 19–30.
- Marte R., Lozano J.A., Mendiburu A. et al. Multi-start Methods // Handbook of Heuristics. Cham: Springer, 2018. P. 155–175.
- Marte R., Aceves R., LeГin M.T at al. Intelligent Multi-start Methods // Handbook of Heuristics. Cham: Springer, 2019. P. 221–243.
- Амирханова Г.А., Горчаков А.Ю., Дуйсенбаева А.Ж., Посыпкин М.А. Метод мультистарта с детерминированным механизмом рестарта // Вестн. С.-Петербургского ун-та. Прикладная математика. Информатика. Процессы управления. 2020. Т. 16. № 2. С. 100–111.
- Зайцев А.А., Курейчик В.В., Полупанов А.А. Обзор эволюционных методов оптимизации на основе роевого интеллекта // Изв. Южного федерального ун-та. Технические науки. 2010. Т 113. № 12. С. 7–12.
- Crainic T.G., Le Cun B., Roucairol C. Parallel Branch-and-bound Algorithms // Parallel Combinatorial Optimization. New Jersey: John Wiley & Sons, Inc., 2006. P. 1–28.
- Casado L.G., Martinez J.A., García I. et al. Branch-and-bound Interval Global Optimization on Shared Memory Multiprocessors // Optimization Methods & Software. 2008. V. 23. № 5. P. 689–701.
- Posypkin M., Usov A. Implementation and Verification of Global Optimization Benchmark Problems // Open Engineering. 2017. V 7. № 1. P. 470–478.
- Land A.H., Doig A.G. An Automatic Method of Solving Discrete Programming Problems // Econometrica. 1960. V. 28. № 3. C. 497–520.
- Van Der Pas R., Stotzer E., Terboven C. Using OpenMP-The Next Step: Affinity, Accelerators, Tasking, and SIMD. London: MIT Press, 2017.
- Rabinovich S.G., Rabinovich M. Evaluating Measurement Accuracy. N.Y.: Springer, 2010.
- Dekking F.M., Kraaikamp C., Lopuhaí H.P. et al. A Modern Introduction to Probability and Statistics: Understanding why and how. London: Springer, 2005.
- Efron B., Tibshirani R. J. A An Introduction to the Bootstrap. Boca Raton: CRC press, 1994.
- Helwig N.E. Bootstrap Confidence Intervals // Twin:University of Minnesota, 2017.
- Virtanen P.,Gommers R., Oliphant T.E. et al. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python // Nature methods. 2020. V. 17. № 3. C. 261–272.
- Положение о ЦКП “Информатика”. 2020. URL: http://www.frccsc.ru/ ckp (onlineНѕ accessed: 2020-07-23).
Дополнительные файлы
