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



Скачать 61.63 Kb.
Дата01.01.2013
Размер61.63 Kb.
ТипДокументы

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


А.Л. Игнатьев
Вычислительный центр РАН
ignatyev.alexander@gmail.com

1. Введение

В работе рассматриваются различные реализации методов решения аcимметричной задачи коммивояжера[1] для многопроцессорных вычислительных систем. Задача коммивояжера формулируется следующим образом: пусть имеется n+1 город 0, 1, …, n; для каждой пары городов i и j задано «расстояние» cij ≥ 0 между ними. Коммивояжер должен, выехав из начального города 0, объехать все города, посетив каждый из них ровно один раз, и вернуться в город 0. Необходимо найти такую последовательность посещения городов, при которой суммарная длина пути минимальна. Асимметричной называется такая задача коммивояжера, где условие cij = cji в общем случае не выполняется.

2. Алгоритмы решения задачи коммивояжера

Для решения задачи коммивояжера были выбраны метод ветвей и границ и алгоритм муравьиной колонии. Метод ветвей и границ (МВГ) позволяет получить точное решение, но, при этом, имеет сложную древовидную структуру алгоритма. Это делает время работы МВГ непредсказуемым и усложняет параллельную реализацию. Муравьиный алгоритм позволяет получить приближенное решение за полиномиальное время и легко распараллеливается.

2.1 Метод ветвей и границ

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

Различные варианты метода ветвей и границ характеризуются в первую очередь применяемыми процедурами ветвления и оценки нижней границы. В данной работе рассмотрен алгоритм, в котором используется дихотомическое ветвление — т.е. множество решений разбивается на два подмножества, в одном из которых делается предположение, что оптимальный маршрут содержит некоторый переход (k, l), в другом подмножестве переход (k, l) запрещается. Последовательно применяя данную процедуру, мы получаем допустимое решение, состоящее из разрешенных переходов. В качестве процедуры оценки используется операция приведения [5]. Более подробно с данным алгоритмом можно ознакомиться в работе [1, 5].

2.2 Алгоритм муравьиной колонии

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

3. Системы параллельных вычислений

Вычислительный эксперимент был проведен на двух типах параллельных систем: с распределенной и общей памятью. В качестве системы с распределенной памятью использовался суперкомпьютер МВС 100K, оснащенный 1564 4-ядерных процессорами Intel Xeon 5365 3 ГГц. В качестве системы с общей памятью была выбрана рабочая станция с 4-ядерным процессором Intel Core 2 Quad 9550 2.83 ГГц, 4 Гб оперативной памяти и графическим ускорителем NVIDIA GTX 280. Для проведения вычислительного эксперименты были взяты тестовые задачи из библиотеки TSPLIB [3].

3.1 Системы с распределенной памятью и библиотека BNB-Solver

Для распараллеливания метода ветвей и границ была использована библиотека BNB-Solver [2], реализованная с помощью технологии MPI для систем с распределенной памятью. Данная библиотека имеет гибкую программную инфраструктуру, основанную на шаблонах C++, обеспечивающую удобное подключение новых задач оптимизации. При этом требуется реализовать только проблемно-зависимые компоненты.

Для параллельного выполнения алгоритмов BNB-Solver использует схему «управляющий-рабочий». На начальном этапе генерируется некоторое количество подмножеств, которые затем пересылаются рабочим процессам для дальнейшей обработки. Для равномерной нагрузки процессоров используются централизованные алгоритмы балансировки.

Результаты вычислительного эксперимента для задачи с 56 городами приведены на рис. 1. Как легко видеть, увеличение числа процессоров приводит к значительному снижению времени решения. Эффективность в то же время не снижается ниже 0.8, что является хорошим показателем. Результаты эксперимента для других задач из библиотеки TSPLIB и других вариантов метода ветвей и границ приведены в работе [4].

3.2 Системы с общей памятью и OpenMP

Библиотека BNB-Solver подходит для проведения вычислений и на системах с общей памятью. Однако, лежащая в ее основе технология MPI, не позволяет использовать все преимущества таких систем. Для эксперимента на системах с общей памятью была использована технология OpenMP, позволяющая эффективно распараллеливать SIMD-задачи. Для проведения численного эксперимента был реализован параллельный вариант алгоритма муравьиной колонии. Полученные результаты сведены в таб. 1. Эффективность использования 4-х ядер колеблется от 0.8 до 0.9.

Таблица 1. Результаты эксперимента для OpenMP и CUDA

Задача

1 ядро

4 ядра

Уско-рение

Эффек-тивность

CUDA

4 ядра/ CUDA

Ftv44

14.42

4.31

3.35

0.84

0.72

5.99

Ftv47

16.63

4.86

3.42

0.86

0.79

6.15

Ftv55

22.49

6.55

3.43

0.86

1.06

6.18

Ftv64

29.25

8.3

3.52

0.88

1.42

5.84

Ftv70

35.24

9.54

3.69

0.92

1.68

5.76

Рис. 1. Результаты эксперимента для BNB-Solver
3.3 Графические сопроцессоры и CUDA

Современные графические сопроцессоры NVIDIA состоят из нескольких мультипроцессоров, каждый из которых состоит из 8 потоковых процессоров и одного управляющего устройства. Наличие всего одного управляющего устройства на 8 потоковых процессоров накладывает определенное ограничение на алгоритмы, состоящее в том, что код должен выполняться синхронно — в каждый момент времени одна и та же инструкция на каждом процессоре. Это типичная ситуация параллелизма задач (SIMD). Так как метод ветвей и границ MIMD-алгоритм, распараллеливание его на графических сопроцессорах не выглядит целесообразным. С некоторыми оговорками муравьиный алгоритм является SIMD-алгоритмом. Исходя из этих соображений, для эксперимента на графических сопроцессорах был выбран именно муравьиный алгоритм.

Результаты эксперимента приведены в таб. 1. Время решения задачи на графическом сопроцессоре в 5-6 раз меньше, чем на 4-ядерном процессоре.

4. Заключение

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

Литература

[1] Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособ. – 2-е изд., испр. и доп. – М.: ФИЗМАТЛИТ, 2007.

[2] Посыпкин М.А. Архитектура и программная реализация библиотеки для решения задач оптимизации методом ветвей и границ на многопроцессорных вычислительных комплексах // Проблемы вычислений в распределенной среде: распределенные приложения, коммуникационные системы, математические методы и оптимизация. ИСА РАН. М.: КомКнига, 2006. С. 18-25.

[3] Reinelt G. TSPLIB - A Traveling Salesman Problem Library // ORSA Journal on Computing. – 1991. – N. 3. – P. 376-384.

[4] Игнатьев А.Л., Параллельные методы решения задачи коммивояжера//Труды 51-й научной конференции МФТИ (в печати).

[5] Литл. Дж., Мурти К., Суини Л., Кэрел К. Алгоритм для решения задачи коммивояжера // Экономика и математические методы. – 1965. – Т.1, В. 1. – С. 94-107.

Похожие:

Сравнение различных методов решения задачи коммивояжера на многопроцессорных системах iconПрименение нейросетевых методов для решения задачи коммивояжера
В настоящем сообщении излагаются результаты исследования возникающих при этом проблем и возможностей для модельной ситуации в случае...
Сравнение различных методов решения задачи коммивояжера на многопроцессорных системах iconЗадача коммивояжера Общее описани Методы решения задачи коммивояжера
Комбинаторика раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества...
Сравнение различных методов решения задачи коммивояжера на многопроцессорных системах iconРешение задач глобальной оптимизации большой размерности на многопроцессорных комплексах и грид-системах1
...
Сравнение различных методов решения задачи коммивояжера на многопроцессорных системах iconМетоды и программное обеспечение для решения задач исследования операций на многопроцессорных системах
Методы и программное обеспечение для решения задач исследования операций на многопроцессорных системах1
Сравнение различных методов решения задачи коммивояжера на многопроцессорных системах iconЗадача и примеры численных методов ее решения. Постановка исходной задачи
Численный методы решения задачи Коши для обыкновенных дифференциальных уравнений
Сравнение различных методов решения задачи коммивояжера на многопроцессорных системах iconЦель работы: Сделать оценку и сравнение различных методов определения количества аскорбиновой кислоты в апельсиновом соке. Задачи
Здоровье современного человека часто подвергается внешним и внутренним угрозам. Справляться с ними нам помогает один из самых важных...
Сравнение различных методов решения задачи коммивояжера на многопроцессорных системах iconДинамическая структурная оптимизация распределенных систем обслуживания на многопроцессорных системах

Сравнение различных методов решения задачи коммивояжера на многопроцессорных системах iconРешение задач математического программирования на многопроцессорных вычислительных системах
Решение задач математического программирования на многопроцессорных вычислительных системах1
Сравнение различных методов решения задачи коммивояжера на многопроцессорных системах iconОценка масштабируемости параллельных вычислений для одношаговых многоточечных методов решения задачи коши
Ллюстрировано на примере решения задачи Коши на основе одношаговых разностных схем с контролем погрешности на шаге. В качестве параллельных...
Сравнение различных методов решения задачи коммивояжера на многопроцессорных системах iconТринадцать примеров и тринадцать различных методов их решения Экелекян Варужан Левонович
Поэтому целесообразно через журнал, например математика (1 сентября) последовательно рассмотреть различные методы решения уравнений...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org