СРАВНЕНИЕ ПАРАЛЛЕЛЬНЫХ РЕАЛИЗАЦИЙ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ СИСТЕМ С ОБЩЕЙ ПАМЯТЬЮ

Обложка

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Рассматривается четыре параллельных алгоритма, реализующих метод ветвей и границ для решения задач поиска глобального минимума. Алгоритмы предназначены для вычислительных систем с общей памятью. Метод ветвей и границ базируется на двух основных операциях – ветвление и отсев. Для реализации операции отсева используется интервальная арифметика, которая для вещественных интервалов определяет операции, аналогичные обычным арифметическим. Основное отличие алгоритмов заключается в различной реализации хранения списка подзадач. В процессе тестирования на представительном наборе тестовых задач исследованы быстродействие алгоритмов, масштабируемость и устойчивость к аномалиям поиска.

Об авторах

А. Ю. Горчаков

ФИЦ ИУ РАН

Email: agorchakov@frccsc.ru
Россия, Москва

М. А. Посыпкин

ФИЦ ИУ РАН

Автор, ответственный за переписку.
Email: mposypkin@frccsc.ru
Россия, Москва

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

  1. Евтушенко Ю.Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) // ЖВМ и МФ. 1971. Т. 11. № 6. С. 1390–1403.
  2. Lawler E.L., Wood D.E. Branch-and-Bound Methods: A survey // Operations research. 1966. V. 14. № 4. P. 699–719.
  3. Евтушенко Ю.Г., Посыпкин М.А. Применение метода неравномерных покрытий для глобальной оптимизации частично целочисленных нелинейных задач // ЖВМ и МФ. 2011. Т. 51. № 8. С. 1376–1389.
  4. Karnopp D.C. Random Search Techniques for Optimization Problems // Automatica. 1963. V. 1. № 2–3. P. 111–121.
  5. Solis F.J., Wets R.J.B. Minimization by Random Search Techniques // Mathematics of Operations Research. 1981. V. 6. № 1. P. 19–30.
  6. Marte R., Lozano J.A., Mendiburu A. et al. Multi-start Methods // Handbook of Heuristics. Cham: Springer, 2018. P. 155–175.
  7. Marte R., Aceves R., LeГin M.T at al. Intelligent Multi-start Methods // Handbook of Heuristics. Cham: Springer, 2019. P. 221–243.
  8. Амирханова Г.А., Горчаков А.Ю., Дуйсенбаева А.Ж., Посыпкин М.А. Метод мультистарта с детерминированным механизмом рестарта // Вестн. С.-Петербургского ун-та. Прикладная математика. Информатика. Процессы управления. 2020. Т. 16. № 2. С. 100–111.
  9. Зайцев А.А., Курейчик В.В., Полупанов А.А. Обзор эволюционных методов оптимизации на основе роевого интеллекта // Изв. Южного федерального ун-та. Технические науки. 2010. Т 113. № 12. С. 7–12.
  10. 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.
  11. 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.
  12. Posypkin M., Usov A. Implementation and Verification of Global Optimization Benchmark Problems // Open Engineering. 2017. V 7. № 1. P. 470–478.
  13. Land A.H., Doig A.G. An Automatic Method of Solving Discrete Programming Problems // Econometrica. 1960. V. 28. № 3. C. 497–520.
  14. Van Der Pas R., Stotzer E., Terboven C. Using OpenMP-The Next Step: Affinity, Accelerators, Tasking, and SIMD. London: MIT Press, 2017.
  15. Rabinovich S.G., Rabinovich M. Evaluating Measurement Accuracy. N.Y.: Springer, 2010.
  16. Dekking F.M., Kraaikamp C., Lopuhaí H.P. et al. A Modern Introduction to Probability and Statistics: Understanding why and how. London: Springer, 2005.
  17. Efron B., Tibshirani R. J. A An Introduction to the Bootstrap. Boca Raton: CRC press, 1994.
  18. Helwig N.E. Bootstrap Confidence Intervals // Twin:University of Minnesota, 2017.
  19. 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.
  20. Положение о ЦКП “Информатика”. 2020. URL: http://www.frccsc.ru/ ckp (onlineНѕ accessed: 2020-07-23).

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
2.

Скачать (61KB)
3.

Скачать (68KB)
4.

Скачать (88KB)
5.

Скачать (89KB)

© А.Ю. Горчаков, М.А. Посыпкин, 2023