2023 № 2(59)

выход в свет 30.06.2023

СОДЕРЖАНИЕ

Гурьева Ю. В., Васильев Е. П., Смирнов Л. А. Учет законов сохранения при нейросетевом подходе к численному решению нелинейного уравнения Шредингера
Силенко Д. И., Лебедев И. Г. Алгоритм глобальной оптимизации, использующий деревья решений для выявления локальных экстремумов
Коротышева А. А., Жуков С. Н., Милов В. Р., Егоров Ю. С, Чекушева А. Ю., Дубов М. С. Применение методов машинного обучения для классификации немаркированных элементов питания
Кудрявцев А. А., Малышкин В. Э., Нуштаев Ю. Ю., Перепелкин В. А., Спирин В. А. Эф-фективная фрагментированная реализация краевой задачи фильтрации двухфазной жидкости
Матолыгина Н. А., Громов М. Л., Матолыгин А. К. Применение тензорного подхода к программной реализации клеточно-автоматной модели потока
Микулик И. И., Благовещенская Е. А. Распараллеливание гибридного алгоритма муравьиной колонии с изменяющимися с помощью генетического алгоритма параметрами

Ю. В. Гурьева, Е. П. Васильев, Л. А. Смирнов

Нижегородский государственный университет им. Н. И. Лобачевского,

603022, Нижний Новгород, Россия

УЧЕТ ЗАКОНОВ СОХРАНЕНИЯ ПРИ НЕЙРОСЕТЕВОМ ПОДХОДЕ К ЧИСЛЕННОМУ РЕШЕНИЮ НЕЛИНЕЙНОГО УРАВНЕНИЯ ШРЕДИНГЕРА

УДК 517.957

DOI: 10.24412/2073-0667-2023-2-5-20

EDN: LFBNWY

В работе рассматривается один из возможных вариантов модификации нейросетевого подхода к численному решению нелинейных уравнений в частных производных, у которых благодаря физическим свойствам описываемых явлений имеются интегралы движения. Представленный метод подразумевает учет и непосредственное использование соответствующих законов сохранения при построении и обучении нейронных сетей, аппроксимирующих решения такого класса задач, что позволяет улучшить характеристики и качество получаемых нелинейных регрессионных моделей. Более точное выполнение консервативных свойств физических систем для аппроксиматора обеспечивается регуляризацией функции потерь: добавлением невязки сохраняющейся величины нейросетевого решения. Данная концепция рассмотрена и апробирована на примере нелинейного уравнения Шредингера и двух его интегралов движения, отвечающих законам сохранения числа квантов и энергии. Для вычисления невязки этих сохраняющихся величин и реализации консервативной регуляризации функции потерь был использован метод плоскостей непрерывности (вычисление величин в фиксированные моменты времени). Полученные результаты показывают улучшение консервативных свойств, а также в некоторых случаях точности нейросетевого решения по сравнению с регрессионной моделью, построенной с помощью глубокого обучения без учета предложенной в работе модификации.

Ключевые слова: глубокое обучение, нейронные сети, нелинейное уравнение Шредингера, законы сохранения, солитоны.

Работа проведена при поддержке Проекта № 0729-2021-013, в рамках Государственного задания па выполнение научно-исследовательских работ лабораториями, прошедших конкурсный отбор в ходе реализации национальной программы «Наука и университеты».

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

1. Moxley F., Chuss D., Dai W. A generalized finite-difference time domain scheme for solving nonlinear Schrodinger equations /7 Computer Physics Communications, 2013. N 184 (8). P. 1834¬1841. [El. Res.]: https://doi .org/10.1016/j . cpc .2013.03.006.

2. Васильев Е.П., Болотов Д. И., Болотов М.И., Смирнов Л. А. Нейросетевой подход к реше-нию задачи самовоздействия волновых полей в нелинейных средах / / Проблемы Информатики, 2022. № 1. С. 5-16. [Электрон, рос.]: https://doi.org/10.24412/2073-0667-2022-l-5-16.

3. Karniadakis, G.E., Kevrekidis, EG., Lu, L. et al. Physics-informed machine learning /7 Nature Reviews Physics. 2021. N 3. P. 422-440. [El. Res.]: https://doi.org/10.1038/s42254-021-00314-5.

4. Raissi М., Perdikaris Р., Karniadakis G.E.: Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations / / Journal of Computational Physics. 2019. N 378. P. 686-707. [El. Res.]: https://doi.org/10.1016/ j.jcp.2018.10.045.

5. Pu J.C., Li J., Chen Y. Soliton, breather, and rogue wave solutions for solving the nonlinear Schrodinger equation using a deep learning method with physical constraints // Chinese Physics B, 2021. N 30 (6), 060202. [El. Res.]: https://dx.doi.org/10.1088/1674-1056/abd7e3.

6. Wu G. Z., Fang Y., Wang Y. Y., Wu G. C., Dai C. Q. Predicting the dynamic process and model parameters of the vector optical solitons in birefringent fibers via the modified PINN // Chaos, Solitons and Fractals. 2021. N 152, 111393. [El. Res.]: https://doi.Org/10.1016/j.chaos.2021.111393.

7. Wang L., Yan. Z. Data-driven rogue waves and parameter discovery in the defocusing nonlinear Schrodinger equation with a potential using the PINN deep learning // Physics Letters A. 2021. V. 404. P. 127408. [El. Res.]: https://doi.Org/10.1016/j.physleta.2021.127408.

8. Jagtap, A., Kharazmi, E., Karniadakis. G.E. Conservative physics-informed neural networks on discrete domains for conservation laws: Applications to forward and inverse problems // Computer Methods in Applied Mechanics and Engineering. 2020. N 365, 113028. [El. Res.]: https://doi.org/ 10.1016/j. cma.2020.113028.

9. Wu G.Z., Fang Y., Kudryashov N., Wang Y. Y., Dai C.Q. Prediction of optical solitons using an improved physics-informed neural network method with the conservation law constraint // Chaos, Solitons and Fractals, 2022. 159(C), 112143. [El. Res.]: https://doi.Org/10.1016/j.chaos.2022. 112143.

10. Lin S., Chen Y. A two-stage physics-informed neural network method based on conserved quantities and applications in localized wave solutions // Journal of Computational Physics, 2022. 457(C), 111053. [EL Res.]: https://doi.Org/10.1016/j.jcp.2022.111053.

11. [El. Res.]: https://docs.nvidia.com/deeplearning/modulus/user_guide/theory/ recommended_practices.html.

12. Zakharov V., Manakov S. On the complete integrability of a nonlinear Schrodinger equation // Theoretical and Mathematical Physics. 1974. N 19 (3). P. 551-559. [El. Res.]: https://doi.org/10. 1007/BF01035568.

13. [El. Res.]: https://docs.nvidia.com/deeplearning/modulus/user_guide/foundational/ scalar_transport.html.

14. Stein M. Large sample properties of simulations using Latin hypercube sampling, Technometrics. 1987. N 29. P. 143-151. [El. Res.]: https://www.jstor.org/stable/1269769.

15. Schraudolph N. N., Yu J., Gunter S. A Stochastic Quasi-Newton Method for Online Convex Optimization // International Conference on Artificial Intelligence and Statistics, 2007. P. 436-443. [El. Res.]: http://proceedings.mlr.press/v2/schraudolph07a/schraudolph07a.pdf.

статья

Библиографическая ссылка: Гурьева Ю. В., Васильев Е. П., Смирнов Л. А. Учет законов сохранения при нейросетевом подходе к численному решению нелинейного уравнения Шредингера // Проблемы информатики. 2023. № 2. С. 5-20. DOI: 10.24412/2073-0667-2023-2-5-20

Д. И. Силенко, И. Г. Лебедев

Нижегородский государственный университет им. Н. И. Лобачевского,

603022, Нижний Новгород, Россия

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

УДК 519.853.4

DOI: 10.24412/2073-0667-2023-2-21-33

EDN: MLGKOX

В работе рассматривается решение задач многомерной глобальной оптимизации с применением деревьев решений для выявления областей притяжения локальных минимумов. Предполагается, что целевая функция задачи задана как «черный ящик» и удовлетворяет условию Липшица с априори неизвестной константой. Мы предлагаем способ выделения окрестностей локальных экстремумов целевой функции на основе анализа накопленной поисковой информации средствами машинного обучения. Это позволяет принять решение о запуске локального метода для уточнения значения функции в локальном минимуме, что может ускорить сходимость алгоритма. Выдвинутое предположение подтверждается результатами вычислительных экспериментов, демонстрирующих ускорение при решении серии тестовых задач.

Ключевые слова: деревья решений, глобальная оптимизация, многоэкстремальные функции, локальная оптимизация.

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

1. Ferreiro М. , Garcia J. А. , Lopez-Salas J. G., Vazquez С. An efficient implementation of parallel simulated annealing algorithm in GPUs // Journal of global optimization, 2013. V. 57. N 3. P. 863-890.

2. Garcia-Martinez J.M., Garzon E. M., Ortigosa P. M. A GPU implementation of a hybrid evolutionary algorithm: Gpuego // Journal of super-computing, 2014. V. 70. N 2. P. 684-695.

3. Langdon W.B. Graphics processing units and genetic programming: an overview // Soft Computing, 2011. V. 15. N 8, P. 1657-1669.

4. Евтушенко Ю.Г., Малкова В. У., Станевичюс А. А. Параллельный поиск глобального экс-тремума функций многих переменных // Ж. вычисл. матем. и матем. физ, 2009. Т. 49. № 2. С. 246-260.

5. Не J., Verstak A., Watson L. Т., Sosonkina М. Design and implementation of a massively parallel version of direct // Computational optimization and applications, 2008. V. 40. N 2. P. 217-245.

6. Paulavicius R., Zilinskas J., Grothey A. Parallel branch and bound for global optimization with combination of Lipschitz bounds // Optimization methods and software, 2011. V. 26. N 3. P. 487-498.

7. Стронгин P. Г., Гергель В.П., Гришагин В. А., Баркалов К. А. Параллельные вычисления в задачах глобальной оптимизации. Издательство Московского университета, 2013.

8. Gergel V. Р. A global optimization algorithm for multivariate functions with lipschitzian first derivatives // Journal of Global Optimization, 1997. V. 10. N 3. P. 257-281.

9. Химмельблау Д. Прикладное нелинейное программирование. МИР, 1975.

10. Nelder J., Mead R. A simplex method for function minimization // Computer Journal, 1965. V. 7. N 4. P. 308-313.

11. Brahmbhatt S. Practical OpenCV (Technology in Action). New York: Apress, 2013.

12. ОpenCV (open source computer vision) documentation, (accessed: 10 July 2022). [El. Res.]: https://docs.opencv.org/4.x/de/dd6/ml\_intro.html.

13. Sysoyev, Barkalov K., Sovrasov V., Lebedev L, Gergel V. Globalizer — a parallel software system for solving global optimization problems // Lecture Notes in Computer Science, 2017. V. 10421. N LNCS. P. 492-499.

14. Gaviano M., Lera D., Kvasov D.E., Sergeyev Y. D. Software for generation of classes of test functions with known local and global minima for global optimization // ACM Transactions on Mathematical Software, 2003. V. 29. P. 469-480.

15. Сергеев Я.Д., Квасов Д. Е. Диагональные методы глобальной оптимизации. Физматлит, 2008.

16. Sergeyev Y. D., Kvasov D.E. Global search based on efficient diagonal partitions and a set of Lipschitz constants // SIAM Journal on Optimization, 2006. V. 16. N 3. P. 910-937.

статья

Библиографическая ссылка: Силенко Д. И., Лебедев И. Г. Алгоритм глобальной оптимизации, использующий деревья решений для выявления локальных экстремумов // Проблемы информатики. 2023. № 2. С. 21-33. DOI: 10.24412/2073-0667-2023-2-21-33

А. А. Коротышева*, С.Н. Жуков*, В.Р. Милов**, К. С. Егоров**, А. К. Чекушева**, М.С. Дубов***

* Нижегородский государственный университет им. Н. И. Лобачевского, 603022, Нижний Новгород, Россия

**Нижегородский государственный технический университет им. Р. Е. Алексеева, 603950, Нижний Новгород, Россия

***ООО «Мабекс», 603122, Нижний Новгород, Россия

ПРИМЕНЕНИЕ МЕТОДОВ МАШИННОГО ОБУЧЕНИЯ ДЛЯ КЛАССИФИКАЦИИ НЕМАРКИРОВАННЫХ ЭЛЕМЕНТОВ ПИТАНИЯ

УДК 004.93

DOI: 10.24412/2073-0667-2023-2-34-44

EDN: ACWWCK

Актуальность исследования предопределяется необходимостью сортировки опасных и ценных объектов в составе твердых коммунальных отходов (ТКО), в частности немаркированных элементов питания, с целью их дальнейшей утилизации или переработки, что приобретает особую важность в условиях изменения мировой экологической политики. Предложен подход к идентификации немаркированных цилиндрических элементов питания стандартных типоразмеров на основе компьютерного зрения. Источником анализируемых изображений являются видеокамера и рентгеновская установка. Идентификация выполняется на основе последовательно применяемых процедур, позволяющих обнаруживать и распознавать элементы питания в потоке ТКО на конвейерной ленте. При наличии неповрежденной маркировки на корпусе элементов питания обработка изображений, распознавание надписей и анализ идентификаторов обеспечивают достаточно достоверную классификацию. При существенном повреждении маркировки распознавание затруднено, поэтому предложен дополнительный этап обработки изображений в рентгеновском диапазоне. Нейронные сети, составляющие основу системы идентификации элементов питания, обучаются на подготовленных наборах данных, содержащих множество рентгеновских снимков элементов питания разных типов, которым сопоставлены искомые классы. Обученная модель позволяет классифицировать тип элементов питания для последующей сортировки. Предложенный способ нейросетевой классификации элементов питания на основе обработки оптических изображений и рентгеновских снимков составляет основу программно-аппаратного комплекса, предназначенного для автоматизированных линий сортировки ТКО.

Ключевые слова: машинное обучение, рентгеновские снимки, нейронная сеть, элементы питания, классификация изображений.

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

1. Блохин М. А. Рентгеновское излучение // Физическая энциклопедия: [в 5 т.] / Гл. ред. А. М. Прохоров. М.: Большая российская энциклопедия, 1994. Т. 4: Пойнтинга-Робертсона-Стримеры. С. 375-377.

2. Принципы построения досмотровой рентгеновской техники. [Электрон, pec.]: http://tstk. narod.ru/tsiotk/ppdrt.html (дата обращения: 14.01.2023).

3. Лещенко В. Г., Ильич Г. К. Медицинская и биологическая физика / М.: ИНФРА-М, 2012.

4. Kaggle: Your Home for Data Science. [Электрон, pec.]: https://www.kaggle.com/ (дата обра-щения: 16.01.2023).

5. Махсотова Ц. В. Исследование методов классификации при несбалансированности классов // Научный журнал. 2017. № 5(18). С. 35-36.

6. Sandler М., Howard A. G., Zhu М., Zhmoginov A., Chen L.-C. MobileNetV2: Inverted Residuals and Linear Bottlenecks // Computer Vision and Pattern Recognition. 2018. P. 4510-4520.

7. Блатов P. И., Вострякова E.A., Москвин А. С., Чупров Д. А., Егоров Ю.С., Коротышева А. А., Милов В.Р., Дубов М.С., Кербенева А.Ю. Свидетельство о регистрации программы для ЭВМ RUS 2022663863. Заявка № 2022662975 от 11.07.2022.

статья

Библиографическая ссылка: Коротышева А. А., Жуков С. Н., Милов В. Р., Егоров Ю. С, Чекушева А. Ю., Дубов М. С. Применение методов машинного обучения для классификации немаркированных элементов питания // Проблемы информатики. 2023. № 2. С. 34-44. DOI: 10.24412/2073-0667-2023-2-34-44

A.А. Кудрявцев*, В. Э. Малышкин*,**,*** Ю.Ю. Нуштаев*, B.А. Перепелкин*,**,*** В. А. Спирин*

* Новосибирский национальный исследовательский государственный университет, 630090, Новосибирск, Россия,

**Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия,

***Новосибирский государственный технический университет, 630073, Новосибирск, Россия

ЭФФЕКТИВНАЯ ФРАГМЕНТИРОВАННАЯ РЕАЛИЗАЦИЯ КРАЕВОЙ ЗАДАЧИ ФИЛЬТРАЦИИ ДВУХФАЗНОЙ ЖИДКОСТИ

УДК 004.4’242

DOI: 10.24412/2073-0667-2023-2-45-73

EDN: IWCDKX

Автоматизация конструирования параллельных программ численного моделирования являет-ся актуальной темой в области системного параллельного программирования. В общей по-становке задача автоматического конструирования эффективной (по времени выполнения, расходу памяти, нагрузке на сеть и т.п.) параллельной программы по ее высокоуровневой спецификации является алгоритмически труднорешаемой. Развитие языков и систем автоматического конструирования параллельных программ осуществляется за счет накопления в системах частных решений и эвристик, обеспечивающих приемлемую эффективность конструируемых программ для классов приложений. Важную роль в этой связи имеет исследование эффективных параллельных реализаций конкретных задач численного моделирования на предмет возможности создания на основе этого опыта новых методов и алгоритмов конструирования эффективных параллельных программ для аналогичных случаев. Технология фрагментированного программирования является подходом, позволяющим автоматизировать конструирование эффективных параллельных программ численного моделирования. Система LuNA, разрабатываемая в ИВМиМГ СО РАН, инструментально поддерживает этот подход. В статье рассматривается эффективная фрагментированная реализация на мультикомпьютерах решателя краевой задачи фильтрации двухфазной жидкости в трехмерной области в присутствии скважин. Разработаны и оптимизированы две версии программы — одна на основе традиционных средств параллельного программирования (MPI+OpcnMP), вторая — полученная с помощью системы LuNA. Обе реализации основаны на анализе численного алгоритма с точки зрения возможностей его эффективной параллельной реализации. Экспериментальное исследование реализаций показало, что программа, разработанная вручную, обладает удовлетворительной эффективностью, а автоматически сконструированная программа с помощью системы LuNA уступает в производительности ручной реализации около трех раз, что является хорошим показателем для систем такого типа.

Исследование выполнено в рамках государственного задания ИВМиМГ СО РАН 0251-2021-0005.

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

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

1. Ivanov М. L, Kremer I. A., Laevsky Yu. М. On the streamline upwind scheme of solution to the filtration problem // Siberian Electronic Mathematical Reports. 2019. V. 16. P. 757-776.

2. Ivanov M. L, Kremer I. A., Laevsky Yu. M. On wells modeling in filtration problems // Siberian Electronic Mathematical Reports. 2019. V. 16. P. 1868-1884.

3. Malyshkin V. E., Perepelkin V. A. LuNA Fragmented Programming System, Main Functions and Peculiarities of Run-Time Subsystem // Malyshkin, V. (eds) Parallel Computing Technologies. PaCT 2011. Lecture Notes in Computer Science. V. 6873. Springer, Berlin, Heidelberg, https://doi.org/ 10.1007/978-3-642-23178-0\_5.

4. Синтез параллельных программ и систем на вычислительных моделях / В. А. Вальковский, В.Э. Малышкин; Отв. ред. В.Е. Котов; АН СССР, Сиб. отд-ние, ВЦ. Новосибирск: Наука. Сиб. отд-ние, 1988. 126 с.

5. Малышкин В.Э. Технология фрагментированного программирования // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2012. № 46 (305).

6. Перепелкин В. А., Иванов М. И. Повышение производительности LuNA-программ на основе воспроизведения трасс // Десятая Сибирская конференция по параллельным и высокопроизводительным вычислениям. Сборник статей. Под редакцией А. В. Старченко. Томск, 2021. С. 29-36.

7. Информационно-вычислительный центр Новосибирского государственного университета [Электронный ресурс]: http: //nusc. nsu.ru/wiki/doku. php/doc/index.

8. Межведомственный Суперкомпьютерный Центр Российской Академии Наук [Электронный ресурс]: http://www.jscc.ru/.

статья

Библиографическая ссылка: Кудрявцев А. А., Малышкин В. Э., Нуштаев Ю. Ю., Перепелкин В. А., Спирин В. А. Эф-фективная фрагментированная реализация краевой задачи фильтрации двухфазной жидкости // Проблемы информатики. 2023. № 2. С. 45-73. DOI: 10.24412/2073-0667-2023-2-45-73

Н.А. Матолыгина, М.Л. Громов, А. К. Матолыгин

Национальный исследовательский Томский государственный университет, 634050, Томск, Россия

ПРИМЕНЕНИЕ ТЕНЗОРНОГО ПОДХОДА К ПРОГРАММНОЙ РЕАЛИЗАЦИИ КЛЕТОЧНО-АВТОМАТНОЙ МОДЕЛИ ПОТОКА

УДК 004.4‘2

DOI: 10.24412/2073-0667-2023-2-74-85

EDX: ЛРСШ

В работе описывается опыт применения тензорного подхода к программной реализации клеточно-автоматной модели потока FHP. Данный подход ориентирован на применение мно-гоядерных видеокарт и специальной рабочей среды, которая автоматически распределяет вы-числения по ядрам видеокарты без вмешательства исследователя. Продемонстрирована воз-можность внедрения пользовательских операций в рабочую среду и проведены компьютерные эксперименты.

Ключевые слова: клеточный автомат, тензорный подход, газовый поток.

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

1. Калгин К. В. Клеточно-автоматное моделирование физико-химических процессов на вы-числителях с параллельной архитектурой: дис. ... канд. техн. наук. Новосибирск: 2012. 82 с.

2. Субботина А. Ю., Хохлов Н. И. Реализация клеточных автоматов «Игра “Жизнь”» и клеточного автомата Кохомото-Ооно с применением технологии MPI // Компьютерные исследования и моделирование. 2010 Т. 2. № 3 С. 319-322.

3. Шарифулина А.Е. Параллельная реализация каталитической реакции (СО+О2>СО2) // Вестник ЮУрГУ. 2012. № 47(306). С. 112-126.

4. Szkoda S., Koza Z., Tykierko M. Accelerating cellular automata simulations using AVX and CUDA // arXiv preprint. 2012. arXiv:1208.2428vl.

5. Калгин К. В. Реализация алгоритмов с мелкозернистым параллелизмом на графических ускорителях // Сиб. журн. вычисл. матем. 2011. Т. 14. № 1. С. 46-55.

6. TensorFlow. [Электрон, ресф https://www.tensorflow.org.

7. Shalyapina N. A., Gromov М. L. «Life» in Tensor: Implementing Cellular Automata on Graphics Adapters // Proceedings of the Institute for System Programming of the RAS. 2019. T. 31. № 3. S. 217-228. DOI: https://doi.org/10.15514/ISPRAS-2019-31(3)-17.

8. Frisch U., Hasslacher B., Pomeau Y. Lattice-Gas automata for Navier-Stokes equations // Phys. Rev. Lett. 1986. N 56. P. 1505.

9. Тумаков Д. H. Технология программирования CUDA: учебное пособие / Казанский госу-дарственный университет. Казань, 2017. 112 с.

10. Szkoda S., Koza Z., Tykierko M. Multi-GPGPU Cellular Automata Simulations using OpenACC // Zenodo. 2014. P. 1-6. DOL 10.5281/zenodo.822901

статья

Библиографическая ссылка: Матолыгина Н. А., Громов М. Л., Матолыгин А. К. Применение тензорного подхода к программной реализации клеточно-автоматной модели потока // Проблемы информатики. 2023. № 2. С. 74-85. DOI: 10.24412/2073-0667-2023-2-74-85

И. И. Микулик, Е.А. Благовещенская

Петербургский государственный университет путей сообщения Императора Александра I, 190031, Санкт-Петербург, Россия

РАСПАРАЛЛЕЛИВАНИЕ ГИБРИДНОГО АЛГОРИТМА МУРАВЬИНОЙ КОЛОНИИ С ИЗМЕНЯЮЩИМИСЯ С ПОМОЩЬЮ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ПАРАМЕТРАМИ

УДК 519.854.2

DOI: 10.24412/2073-0667-2023-2-86-97

EDN: HBTPLC

В работе рассмотрена возможность использования параллельной реализации гибридного метода оптимизации, использующего муравьиный и генетический алгоритмы, для решения задачи коммивояжера. Известно, что алгоритм муравьиной колонии чувствителен к изменению параметров, поэтому поиск подходящих параметров муравьиного алгоритма рассматривается в качестве задачи оптимизации, решение которой предоставляется генетическому алгоритму. Целью распараллеливания вычислений является сокращение временных затрат, но не все алгоритмы имеют эффективную параллельную реализацию. Известно, что генетический алгоритм и алгоритм муравьиной колонии распараллеливаются. В работе изучается возможность построения параллельных вычислений и для представленного гибридного метода. Задача коммивояжера, на которой проводится исследование, является NP-полной задачей и часто применяется для тестирования алгоритмов комбинаторной оптимизации. Показано, что распараллеливание используемого метода приводит к увеличению скорости выполнения работы алгоритма.

Ключевые слова: распараллеливание, задача коммивояжера, методы оптимизации, му-равьиные алгоритмы, генетический алгоритм, параллельные вычисления.

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

1. Zhang N. Moore’s law is dead, long live moore’s law! // arXiv preprint arXiv:2205.15011, 2022.

2. Pujol R., Jorba J., Tabani H., Kosmidis L., Mezzetti E., Abella J., Cazorla F. Vector extensions in cots processors to increase guaranteed performance in real-time systems, 2022. ACM Transactions on Embedded Computing Systems (TECS).

3. Zhou K. Feng X. A collaborative grouping aggregation query scheme on heterogeneous computing systems //in 2022 7th International Conference on Cloud Computing and Big Data Analytics (ICCCBDA), 2022. P. 53-61.

4. Regassa D., Yeom H., Son Y. Harvesting the aggregate computing power of commodity computers for supercomputing applications // Applied Sciences, 2022. V. 12, N 10, P. 5113.

5. Ong B. W., Schroder J. B. Applications of time parallelization // Computing and Visualization in Science, 2020. V. 23, N 1. P. 1-15.

6. Blagoveshchenskaya E., Zuev D., Kuznecova I., Tihomirov S. Prilozheniya algoritmov prvamvh razlozhenii abelevvh grupp bez krucheniva k zadacham rasparallelivaniva vvchislitel’nvh i konstruktivnyh processov //in Mezhdunarodnye Kolmogorovskie chteniya-XIV, posvyashchennye 100- letiyu professora Z. A. Skopeca, 2017. P. 38-40.

7. Stutzle T. Parallelization strategies for ant colony optimization //in International Conference on Parallel Problem Solving from Nature. Springer, 1998. P. 722-731.

8. Hassan M., Hasan M., Hashem M. et al. An improved acs algorithm for the solutions of larger tsp problems. arXiv preprint arXiv:1304.3763, 2013.

9. Liang D., Zhan Z.-H., Zhang Y., Zhang J. An efficient ant colony system approach for new energy vehicle dispatch problem // IEEE Transactions on Intelligent Transportation Systems, 2019. V. 21. N 11. P. 4784-4797.

10. Zhou X., Ma H., Gu J., Chen H., Deng W. Parameter adaptation-based ant colony optimization with dynamic hybrid mechanism // Engineering Applications of Artificial Intelligence, 2022. V. 114. P. 105139.

11. Olivas F., Valdez F., Castillo O., Gonzalez С. L, Martinez G., Melin P. Ant colony optimization with dynamic parameter adaptation based on interval type-2 fuzzy logic systems // Applied Soft Computing, 2017. V. 53. P. 74-87.

12. Blagoveshchenskaya E. A., Mikulik I. I., Strbungmann L. H. Ant colony optimization with parameter update using a genetic algorithm for travelling salesman problem // Models and Methods for Researching Information Systems in Transport 2020 (MMRIST 2020), 2020. N 1. P. 20-25.

13. Baydogmus G. К. A parallelization based ant colony optimization for travelling salesman problem //in 2022 1st International Conference on Information System & Information Technology (ICISIT). IEEE, 2022. P. 166-169.

14. Liu G., Xu X., Wang F., Tang Y. Solving traveling salesman problems based on artificial cooperative search algorithm // Computational Intelligence and Neuroscience, 2022. V. 2022.

15. El-Khatib S. , Skobtsov Y. , Rodzin S. , Zakharov V. Comparison of modified object detected graph cut and hybrid ant colony optimization-k-means for mri images segmentation //in Computer Science On-line Conference. Springer, 2021. P. 701-708.

16. Brand M., Masuda M., Wehner N., Yu X.-H. Ant colony optimization algorithm for robot path planning //in 2010 international conference on computer design and applications, V. 3. IEEE, 2010. P. V3-436.

17. Whitley D. Next generation genetic algorithms: a user’s guide and tutorial //in Handbook of metaheuristics. Springer, 2019. P. 245-274.

18. Katoch S., Chauhan S. S., Kumar V. A review on genetic algorithm: past, present, and future // Multimedia Tools and Applications, 2021. V. 80, N 5. P. 8091-8126.

19. Singh G., Gupta N. A study of crossover operators in genetic algorithms //in Frontiers in Nature-Inspired Industrial Optimization. Springer, 2022. P. 17-32.

20. Lambora A., Gupta K., Chopra K. Genetic algorithm-a literature review //in 2019 international conference on machine learning, big data, cloud and parallel computing (COMITCon). IEEE, 2019. P. 380-384.

статья

Библиографическая ссылка: Микулик И. И., Благовещенская Е. А. Распараллеливание гибридного алгоритма муравьиной колонии с изменяющимися с помощью генетического алгоритма параметрами // Проблемы информатики. 2023. № 2. С. 86-97. DOI: 10.24412/2073-0667-2023-2-86-97

Main menu

2023 № 2(59)

Languages

Main menu

You are here

2023 № 2(59)

Languages