Подсистема распределенного решения оптимизационных задач

  • Д.Ю. Запорожец ЮФУ
  • Д.В. Заруба
  • Ю.Ю. Запорожец
Ключевые слова: Биоинспирированыне алгоритмы, Распределенные вычисления, задача Коммивояжера

Аннотация

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

Литература

1. Запорожец, Д.Ю. Генерация биоинспирированных поисковых процедур для решения оптимизационных задач / Заруба Д.В., Запорожец Д.Ю.// Известия ЮФУ. Технические науки, 2016. – № 6 (179). – С. 13-24.
2. Кравченко, Ю.А. Метод интеллектуального принятия эффективных решений на основе биоинспирированного подхода / Кулиев Э.В., Кравченко Ю.А., Логинов О.А., Запорожец Д.Ю. // Известия Кабардино-Балкарского научного центра РАН. 2017. – № 6-2 (80). – С. 162-169.
3. Родзин, С.И. Состояние, проблемы и перспективы развития биоэвристик / Родзин С.И., Курейчик В.В. // Программные системы и вычислительные методы. 2016. – № 2. – С. 158-172.
4. Кравченко, Ю.А. Разработка вычислительно-независимых моделей (cim) на основе многоагентных систем // Известия Кабардино-Балкарского научного центра РАН, 2017. – № 6-2 (80). – С. 149-155.
5. Запорожец, Д.Ю. Модифицированный гибридный алгоритм на основе алгоритмов волчьей стаи и дифференциальной эволюции / Пантелюк Е.А., Запорожец Д.Ю., Курейчик В.В., Заруба Д.В. // Информатизация и связь, 2018. – № 4. – С. 61-66.
6. Zaporozhets, D. Parallel approach for bioinspired algorithms / Zaporozhets D., Zaruba D., Kulieva N. // Journal of Physics: Conference Series Сер. "International Conference Information Technologies in Business and Industry 2018 - Enterprise Information Systems", – 2018. – С. 042065.
7. Kureichik, V. M., and V. V. Kureichik. "Genetic algorithm for the graph placement." Journal of Computer and Systems Sciences International 39.5 (2000): 733-740.
8. Курейчик, В.М. Обзор состояния проблемной области по теме решение задачи коммивояжёра / Курейчик В.М., Логунова Ю.А., Игнатьева А.С. // Информатика, вычислительная техника и инженерное образование, 2017. – № 3 (31). – С. 39-59.
9. Курейчик, В.М. Прогнозирование состояния технических систем при помощи генетических алгоритмов / Курейчик В.М., Синютин Е.С., Каплунов Т.Г. // Вестник Рязанского государственного радиотехнического университета, 2018. – № 65. – С. 107-112.
10. Kureichik, V. Hybrid approach for graph partitioning / Kureichik V., Zaruba D., Kureichik V.V. // Advances in Intelligent Systems and Computing, 2017. – Т. 573. – С. 64-73.
11. Курейчик В.В., Интегрированная инструментальная подсистема генетического поиска / Курейчик Л.В., Курейчик В.В., Курейчик В.В. // Программная инженерия: методы и технологии разработки информационно-вычислительных систем (ПИИВС-2016) Сборник научных трудов I научно-практической конференции (студенческая секция). ГОУ ВПО "Донецкий национальный технический университет", 2016. – С. 93-96.
12. Литвиненко, В. А. Организация и защита распределенных вычислений на базе многоагентной системы в компьютерной сети с целью сокращения времени решения масштабных задач / Ховансков С. А., Литвиненко В. А., Хованскова В. С. // Известия ЮФУ. Технические науки, 2018. – №4 (198). – С. 198-210
13. Полковникова Н.А., Многокритериальная оптимизация на основе эволюционных алгоритмов / Полковникова Н.А., Курейчик В.М. // Известия ЮФУ. Технические науки, 2015. – № 2 (163). – С. 149-162.
14. Кравченко, Ю.А. Комбинированный подход к решению задачи распределения ресурсоВ / Кравченко Ю.А., Курситыс И.О. // Известия ЮФУ. Технические науки, 2017. – № 7 (192). – С. 111-122.
15. Кравченко, Ю.А. Применение имитационного моделирования и временных сетей петри для задачи распределения вычислительных ресурсов / Курситыс И.О., Кравченко Ю.А. // Фундаментальные и прикладные аспекты компьютерных технологий и информационной безопасности Сборник статей II Всероссийской научно-технической конференции молодых ученых, аспирантов и студентов, 2016. – С. 254-258.
16. Roy G. M. RabbitMQ in Depth. – Manning Publications, 2018.
17. Batyuk A. et al. Software architecture design of the real-time processes monitoring platform //2018 IEEE Second International Conference on Data Stream Mining & Processing (DSMP). – IEEE, 2018. – С. 98-101.
18. Das N. et al. NoSQL Overview and Performance Testing of HBase Over Multiple Nodes with MySQL //Emerging Technologies in Data Mining and Information Security. – Springer, Singapore, 2019. – С. 269-279.
19. Bell C. Introducing InnoDB Cluster: Learning the MySQL High Availability Stack. – Apress, 2018.
Опубликован
2019-07-13
Выпуск
Раздел
РАЗДЕЛ I. АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ