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


Скачать 349,28 Kb.
НазваниеКомплекс программ для исследования методов решения задачи о коммивояжере
страница1/4
Ляликов Вадим Николаевич
Дата конвертации14.08.2012
Размер349,28 Kb.
ТипАвтореферат
СпециальностьМатематическое моделирование, численные методы и комплексы программ
Год2008
На соискание ученой степениКандидат технических наук
  1   2   3   4


На правах рукописи


Ляликов Вадим Николаевич


КОМПЛЕКС ПРОГРАММ ДЛЯ ИССЛЕДОВАНИЯ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ О КОММИВОЯЖЕРЕ


05.13.18 – математическое моделирование, численные методы и

комплексы программ


АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук


Ульяновск – 2008

Работа выполнена на кафедре прикладной математики в Государственном образовательном учреждении высшего профессионального образования Ульяновский государственный университет


Научный руководитель: кандидат физико-математических наук,

доцент Воденин Дмитрий Ростиславович


Официальные оппоненты: доктор физико-математических наук,

профессор

Мельников Борис Феликсович

доктор технических наук, профессор

Смагин Алексей Аркадьевич


Ведущая организация: ГОУ ВПО Ульяновский государственный

технический университет


Защита диссертации состоится « 23 » апреля 2008 года в 10 часов на заседании диссертационного совета Д 212.278.02 при Ульяновском государственном университете по адресу: Набережная р. Свияги, 106, корп. 1, ауд. 703.


С диссертацией можно ознакомиться в библиотеке Ульяновского государственного университета, с авторефератом - на сайте вуза http://www.uni.ulsu.ru


Отзывы по данной работе просим направлять по адресу: 432000, г. Ульяновск, ул. Л.Толстого, д. 42, УлГУ, Управление научных исследований


Автореферат разослан «____» марта 2008 года


Ученый секретарь

диссертационного совета Волков М.А.


ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность исследования. Задача о коммивояжёре – traveling salesman problem (TSP, ЗКВ) – является NP-сложной задачей дискретной оптимизации. Для нее не найдено, и возможно, не существует быстрых, полиномиальных алгоритмов. На графах она формулируется следующим образом: требуется найти гамильтонов цикл наименьшей стоимости во взвешенном полном графе. Т.е. выйдя из стартовой вершины, посетить каждую вершину графа ровно один раз и вернуться в начальную по кратчайшему пути.

Поиск точных и приближённых способов решения задачи о коммивояжёре остается актуальным и с теоретической и с практической точек зрения. Результатом теоретических исследований1 являются такие методы как:

  • релаксации линейного программирования, релаксация Лагранжа, метод ветвей и отсечений, метод ветвей и границ (МВГ)

  • распределенный метод ветвей и границ, решатели ЛП (задачи линейного программирования)

  • эвристические: симулированный отжиг, генетические алгоритмы, цепная локальная оптимизация, поиск с запретами.

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

Программные коды, предназначенные для решения на оптимальность задачи о коммивояжёре, за последние 30 лет развились от решения задач размерности 100 до 10 0002.

Среди приложений ЗКВ, встречающихся в литературе3, можно отметить:

  • Оптимизацию в сетях

  • Оптимизацию маршрутов

  • Приложения в кристаллографии

  • Управление роботами

  • Обработку печатных плат

  • Исследование ДНК

«Городами» в различных задачах могут выступать как физические объекты, так и процессы, и другие сущности.

Основными актуальными вопросами, связанными с решением ЗКВ, являются

  • Быстрое точное решение асимметричных и симметричных ЗКВ больших размерностей

  • Быстрое приближённое решение асимметричных и симметричных ЗКВ больших размерностей

  • Разработка быстрых схем аппроксимации ЗКВ высокой точности

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

Цель работы. Целью настоящей работы является

  • создание новых алгоритмов и программ для точного и приближённого решения асимметричной и симметричной задачи о коммивояжёре

  • реализация и получение экспериментальных оценок эффективности схем аппроксимации ЗКВ

  • улучшение качества тура и ускорение существующих программ решения ЗКВ

  • поиск новых способов эффективного использования существующего программного обеспечения (ПО) по решению ЗКВ

Методы исследования. В исследовании использовались методы комбинаторного анализа, теории графов, дискретной оптимизации, линейного программирования, технологий распределённых вычислений.

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

Научная новизна

Для достижения поставленных целей решены следующие задачи:

  1. Разработан алгоритм решения асимметричной задачи о коммивояжёре (АЗКВ, ATSP) с помощью неэквивалентного преобразования к симметричной задаче о коммивояжёре (СЗКВ, STSP). Выработаны рекомендации по применению.

  2. Реализованы и исследованы на эффективность алгоритмы распределенного метода ветвей и границ (МВГ) и полиномиальной аппроксимации СЗКВ PMCA4.

  3. Реализован алгоритм усеченного МВГ ZHANG15 с задачей о назначениях для АЗКВ. Получены оценки времени работы и качества тура. Выработаны рекомендации по применению.

  4. Разработаны схемы экспериментов для исследования эффективности локальных отсечений в методах ветвей и отсечений (МВО, Branch and Cut)6 и эквивалентных преобразований в приближённых k-opt алгоритмах для АЗКВ. По результатам выработаны рекомендации по оптимизации времени и качества тура.

  5. Экспериментально исследована эффективность отсечений ЗКВ для решения задачи маршрутизации (Vehicle Routing Problem – VRP). Подтверждена эффективность подхода.

Практическая значимость исследования. Все рассмотренные в работе алгоритмы и методы оптимизации обладают практической значимостью. Наиболее интересными с теоретической точки зрения являются алгоритмы решения асимметричной задачи о коммивояжёре путем неэквивалентного преобразования к симметричной задаче о коммивояжёре и методы повышения эффективности локальной оптимизации асимметричной задачи о коммивояжёре с использованием различных типов эквивалентных преобразований. Практически полезными эффектами являются улучшение качества получаемого решения (длина тура ЗКВ) и уменьшение времени решения (увеличение скорости решения).

Основные положения, выносимые на защиту:

  1. Новый алгоритм решения асимметричной задачи о коммивояжёре путем неэквивалентного преобразования к симметричной задаче о коммивояжёре.

  2. Программная реализация и экспериментальная оценка эффективности схемы полиномиальной аппроксимации симметричной задачи о коммивояжёре и распределенного метода ветвей и границ для симметричной задачи о коммивояжёре.

  3. Методика повышения эффективности программ метода ветвей и отсечений, метода ветвей и границ с задачей о назначениях, и локальной оптимизации для асимметричной задачи о коммивояжёре.

Апробация работы.

Основные научные и практические результаты исследований по теме диссертации докладывались на

  • VI Международной конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов» (г. Ульяновск, 2005)

  • «XIII Всероссийской школе-коллоквиуме по стохастическим методам и VII Всероссийском симпозиуме по прикладной математике» (г. Йошкар-Ола, 2006)

  • девятом международном семинаре «Дискретная математика и ее приложения» (г. Москва, 2007)

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

Публикации. По теме диссертации опубликовано 10 работ, в том числе 4 в ведущих рецензируемых журналах, рекомендованных ВАК.

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


СОДЕРЖАНИЕ РАБОТЫ

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

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

В главах 2 и 3 изложен основной материал диссертационной работы. Глава 2 посвящена алгоритмам приближённого решения ЗКВ, а глава 3 – алгоритмам точного решения. Обе главы разбиты на параграфы, в каждом из которых рассматривается один из алгоритмов или аспектов решения ЗКВ. В конце каждого параграфа имеется заключение.

В §2.1 «Стабильная аппроксимация -ЗКВ» реализована одна из схем полиномиальной аппроксимации ЗКВ - PMCA. Новыми являются экспериментальные оценки качества тура, не встречавшиеся авторам в литературе.

Для ЗКВ в общем случае не существует полиномиальной схемы аппроксимации. Они созданы лишь для некоторых частных случаев, например, алгоритм Кристофидеса (Christofides) для симметричной ЗКВ с неравенством треугольника. Одним из возможных развитий подхода является разделение задачи в общей постановке на подклассы, и создание алгоритмов, эффективных, но возможно, не на всех подклассах. Громковичем (Hromkovic) и соавторами был предложен алгоритм стабильной аппроксимации для симметричной ЗКВ.

Основное утверждение, доказанное Громковичем, состоит в том, что для любого существует - аппроксимирующий алгоритм для -TSP, работающий за время

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

Целью данной части диссертационной работы было получение экспериментальных оценок эффективности алгоритма PMCA. Программная реализация алгоритма PMCA была произведена с использованием библиотеки оптимизации на графах и сетях GOBLIN, разработанной в Университете Аугсбурга.

В таблице 1 приведены результаты вычислительных экспериментов. В первом столбце указаны имена файлов с тестовыми матрицами. Во втором и третьих столбцах – качество полученного с помощью алгоритмов Christofides и PMCA тура в процентах относительно длины оптимального тура.


Таблица 1. Длина тура в процентах от оптимальной.

Название задачи

Christofides

PMCA

E1k.0-E1k.3

112%

113%

M1k.0-M1k.3

5468%

6952%


Эксперименты с разработанной реализацией PMCA показали, что

  • Качество получаемого тура близко к качеству тура алгоритма Кристофидеса (менее чем на один процент хуже на евклидовых матрицах размера 1000 городов из набора DIMACS)

  • Соответственно алгоритм представляет в основном теоретический интерес, а для приближённых решений лучше использовать алгоритмы локальной оптимизации


В §2.2 «Задача о назначениях для решения ЗКВ» реализован и экспериментально исследован усечённый метод ветвей и границ для асимметричной ЗКВ.

Одной из наиболее удачных для асимметричной ЗКВ релаксаций является задача о назначениях (ЗН), решением которой, в отличие от ЗКВ, может быть не один, а множество непересекающихся туров. В некоторых публикациях высказывалось предположение о зависимости качества ЗН-релаксации от разности границ Хелда-Карпа (ХК, HK) и задачи о назначениях (ЗН) для выбранного класса матриц. Что приводит к тому, что ЗН-релаксация оказывается стабильной, но с разными нижними границами: на некоторых классах дает очень хорошие приближения за малое время, а на некоторых даже с расширением пространства и времени поиска показывает слабые результаты.

Открытых кодов подобных реализаций авторами найдено не было. Целью данной части работы было создать программу, реализующую усечённый МВГ для АЗКВ в варианте, предложенном Жангом, исследовать временные характеристики и качество тура. Для выбора элемента ветвления и узла ветвления использовались правила Карпането-Тота, ветвление проводилось поиском в глубину, в памяти сохранялись вершины от корня до текущей, плюс все потомки ближайшей родительской вершины. Для решения ЗН использовался интерфейс библиотеки libhungarian без дополнительной оптимизации.

В таблице 2 приведены результаты вычислительных экспериментов на асимметричных матрицах классов coin, rtilt, disk, shop, super и amat размерности 316 и 1000 городов.

Эксперименты с использованием алгоритма ZHANG1 для решения задач АЗКВ шести разных классов из тестового набора ATSP Challenge, подтвердило наличие чёткой границы ZHANG1 для некоторых классов (тем больше, чем больше разница ХК-ЗН). Она изменяется с изменением размера задачи, но порядок остаётся постоянным. Так для трёх классов разность ХК-ZHANG1 составляла около десятой доли процента и менее, для оного класса – несколько десятых долей, а для двух оставшихся – более десяти процентов. Причём в первом случае разность с увеличением размера задачи уменьшалась, а в последнем (худшем) наоборот увеличивалась.

Простая оценка временной сложности алгоритма показала, что простой неоптимизированный вариант с использованием внешней библиотеки венгерского алгоритма с решением полной ЗН в каждом узле дерева МВГ получается со сложностью - , которую при использовании описанных в литературе оптимизаций можно снизить до .


Таблица 2. Качество тура и время работы ZHANG1

Класс

Задач

Средняя разность

ХК-ZHANG1

для задач в 316

городов, %

Средняя разность

ХК-ZHANG1

для задач в

1000 городов, %

Среднее время

, с

Среднее время

, с

Оценка временной

сложности



coin

10.62

12.34

54.83

3615.85

3.64

rtilt

10.78

12.81

109.82

8960.02

3.82

disk

0.21

0.03

10.14

364.34

3.11

shop

0.07

0.04

191.17

15642.32

3.82

super

0.24

0.22

26.65

1761.75

3.64

amat

0.16

0.04

6.34

372.16

3.54


В заключение можно сказать, что для классов АЗКВ с малой разницей границ ХК-ЗН релаксация к задаче о назначениях, например, варианты алгоритма Жанга, может быть очень успешной и находить туры высокого качества за время, сравнимое с алгоритмами локальной оптимизации.


В
  1   2   3   4

Разместите кнопку на своём сайте:
поделись


База данных защищена авторским правом ©dis.podelise.ru 2012
обратиться к администрации
АвтоРефераты
Главная страница