Оптимизация по принципу муравьиной колонии. Обеспечение эффективной работы программы на компьютере с четырьмя процессорами Intel Xeon E7-8890 v4. Проблема поиска оптимального маршрута в транспортной сети. Блок-схема архитектуры реализации алгоритма.
Аннотация к работе
Цель задачи добиться эффективной работы программы на компьютере с четырьмя процессорами Intel Xeon E7-8890 v4. Система оснащена 512 Гб оперативной памяти, на ней установлена Linux 3.10.0-327.el7.x86_64, код компилировался с помощью Intel Parallel Studio XE 2016 U2. Проблема поиска оптимального маршрута в транспортной сети известна как «задача коммивояжера». На практике это, например, нахождение оптимальных путей перевозок товаров. Изначально «эффективность» в задачах такого рода означала выбор наиболее дешевого пути, но за последние несколько десятилетий понятие «стоимость маршрута» расширилось. Теперь сюда включают и воздействие на окружающую среду, и цену энергоресурсов, и время. В дополнение к этому, глобализация бизнеса и цепочек поставок привели к тому, что размеры и сложность транспортных сетей, а значит - и моделей, на которых базируются расчеты, значительно выросли. Теперь типичные задачи оптимизации маршрутов классифицируют как НП-трудные. Обычно для решения таких задач не подходят детерминированные методы. С развитием распределенных и многоядерных вычислительных систем были разработаны и успешно применены эвристические методы решения задач, в частности - так называемый муравьиный алгоритм (Ant Colony Optimization, ACO). Рассмотрим процесс анализа базовой реализации ACO и улучшении кода.Алгоритм в программе основан на поведении колонии муравьев.Вот блок-схема базовой архитектуры параллельной реализации муравьиного алгоритма.Один из самых быстрых способов выяснить, эффективно ли масштабируется приложение при увеличении числа доступных ему вычислительных ядер, заключается в следующем. Сначала получают базовый показатель производительности на одном процессоре . Затем этот показатель сравнивают с результатами измерения производительности при запуске на нескольких процессорах, причем, как с применением технологии Hyper-Threading, так и без нее.Гибридная MPI-OPENMP версия программы показала гораздо лучшие результаты в плане балансировки нагрузки между MPI-процессами и потоками OPENMP.