Распараллеливание алгоритма муравьиной колонии на примере задачи о рюкзаке с использованием Python
М. Р. Вагизов, С. П. Хабаров
Загрузить полный текст
Аннотация: В статье рассмотрен алгоритм муравьиной колонии и описан процесс его распараллеливания с использованием Python и модуля multiprocessing. На примере задачи о рюкзаке показано, что распределение задач между рядом процессов позволяет улучшить производительность алгоритма, сохраняя его эффективность. По сравнению с точными методами типа динамического программирования использование алгоритма муравьиной колонии показало значительное сокращение времени выполнения при приемлемом уровне отклонения от оптимального решения. Преимущество алгоритмов распараллеливания заключается в эффективном использовании вычислительной системы, где используются все доступные ядра процессоров, что приводит к ускорению выполнения большего числа итераций за то же время. Полученные результаты подтверждают потенциал АСО для решения сложных задач с ограниченным временем расчета.
Ключевые слова: алгоритм муравьиной колонии, задача о рюкзаке, параллельные вычисления, программирование на Python
Для цитирования. Вагизов М. Р., Хабаров С. П. Распараллеливание алгоритма муравьиной колонии на примере задачи о рюкзаке с использованием Python // Известия Кабардино-Балкарского научного центра РАН. 2024. Т. 26. № 5. С. 73–83. DOI: 10.35330/1991-6639-2024-26-5-73-83
Список литературы
- Даринцев О. В., Мигранов А. Б. Использование муравьиного алгоритма для поиска стратегии поведения группы мобильных роботов на рабочем поле с препятствиями // Многофазные системы. 2022. Т. 17. № 3−4. С. 177−186. DOI: 10.21662/mfs2022.3.016
- Минин А. А., Немтинов В. А. Применение алгоритма муравьиных колоний для создания технологических процессов обработки резанием // Инженерные технологии. № 3. С. 31−36. EDN: LAMZQA
- Павловская К. А., Червинский В. В. Маршрутизация в сетях MANET на основе муравьиных алгоритмов с учетом энергосбережения // Вестник Донецкого национального университета. Серия Г: Технические науки. 2023. № 1. С. 4−10. EDN: SWIUGB
- Вагизов М. Р., Хабаров С. П. Построение программных траекторий движения на базе решения задачи «Машина Дубинса» // Информация и космос. 2021. № 3. С. 116–125. EDN: DDDWFN
- Коренев А. С., Скрыпка А. С., Хабаров С. П. Автономное судовождение на действующих судах // Морской вестник. 2022. № 1(81). С. 92–95. EDN: MIPIOP
- Хабаров С. П., Шилкина М. Л. Геометрический подход к решению задачи для машин Дубинса при формировании программных траекторий движения // Научно-технический вестник информационных технологий, механики и оптики. 2021. Т. 21. № 5. С. 653–663. DOI: 10.17586/2226-1494-2021-21-5-653-663
- Думов М. И. Моделирование беспроводных сетей в среде OMNеT++ с использованием INET framework // Научно-технический вестник информационных технологий, механики и оптики. 2019. Т. 19. № 6. С. 1151–1161. DOI: 10.17586/2226-1494-2019-19-6-1151-1161
Информация об авторах
Вагизов Марсель Равильевич, канд. тех. наук, заведующий кафедрой информационных систем и технологий, Санкт-Петербургский государственный лесотехнический университет им. С. М. Кирова;
194021, Россия, Санкт-Петербург, Институтский пер., 5;
bars-tatarin@yandex.ru, ORCID: https://orcid.org/0000-0003-4848-1619, SPIN-код: 4811-8943
Хабаров Сергей Петрович, канд. тех. наук, доцент кафедры информационных систем и технологий, Санкт-Петербургский государственный лесотехнический университет им. С. М. Кирова;
194021, Россия, Санкт-Петербург, Институтский пер., 5;
Serg.Habarov@mail.ru, ORCID: https://orcid.org/0000-0003-1337-0150, SPIN-код: 4365-2033