Санников М. А.

Студент,

Томский политехнический университет

ПРИМЕНЕНИЕ ТЕХНОЛОГИИ CUDA К РЕАЛИЗАЦИИ ЭВОЛЮЦИОННОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

Аннотация

В статье рассмотрены основные моменты реализация генетического алгоритма для решения задачи коммивояжера с использованием технологии CUDA, выявлены преимущества и недостатки некоторых эвристик, для чего использован профилировщик программной среды Nsight.

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

Sannikov M. A.

Student,

Tomsk polytechnic university

EVOLUTIONARY ALGORITHM IMPLEMENTATION USING CUDA TECHNOLOGY FOR TRAVELLING SALESMAN PROBLEM SOLVING

Abstract

The article contains description of main parts of evolutionary algorithm implementation for travelling salesman problem solving using CUDA grid technology. Advantages and disadvantages of some heuristics are fetched up with the help of built-in Nsight IDE profiler.

Keywords: evolutionary algorithm, travelling salesman problem, CUDA, parallel computing, profiling.

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

Каждая особь популяции содержит хромосому в виде перестановки вершин графа. Это позволяет применить технологии параллельных вычислений, а именно обрабатывать каждую особь, или пары особей в одном потоке. Алгоритм реализован на языке C++ с использованием технологии CUDA.

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

После получения новой популяции необходимо вычислить значение функции приспособленности каждой особи, что можно реализовать для каждой особи в отдельном потоке. Таким образом каждый поток просто выполнит проход по массиву хромосомы за O(n) и получит сумму расстояний между соседними вершинами. Также можно, в случае большого числа вершин, распараллелить проход по массиву, но на практике это только замедляет работу алгоритма.

Далее, после некоторого числа итераций, необходимо найти лучшую особь популяции, хромосому которой и будем считать результатом решения задачи. Для этого можно перебрать всех особей и найти минимум из значений функции приспособленности, но намного быстрее на практике оказалось распараллеливание этого процесса. Для этого будем использовать только потоки первого блока сетки CUDA. Если рассмотреть i-ый поток, то в нем находится минимум из значений функции приспособленности тех особей, которые имеют индекс i в своем блоке. Таким образом каждый поток пройдет ровно столько особей, сколько блоков в сетке CUDA. Далее необходимо каким-то образом найти минимум по всем потокам. Для этого можно воспользоваться массивом в разделяемой памяти. Каждый поток записывает минимум из своих особей в массив. И далее, используя только первый поток, находим минимум в массиве. Несмотря на то, что этот метод показал лучшие результаты, чем простой проход по всем особям в одном потоке, его невозможно применять для эвристики сохранения лучших особей старой популяции в новой. С помощью встроенного в среду разработки Nsight профилировщика выявлено, что даже при вызове функции поиска лучшей особи 10% от размера популяции раз, является самой затратной процедурой по сравнению со скрещиванием и мутацией. Поэтому, несмотря на возможно лучшие показатели сходимости, применение функции лучшей особи для этой эвристики не оправданно. В процессе исследования возможных улучшений, выявлено, что можно реализовать достаточно хорошую сортировку особей популяции, что позволит быстро выделять лучших особей, но для этого необходимо тщательно подобрать параметры алгоритма (например количество блоков и потоков в каждом блоке), для улучшения сходимости.

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