Аннотация 2
ВВЕДЕНИЕ 5
ГЛАВА 1 ОБЗОР СУЩЕСТВУЮЩИХ СПОСОБОВ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА 7
1.1 Транспортные задачи 7
1.2 Общая характеристика задачи коммивояжера 8
1.2.1 Постановка задачи коммивояжера 8
1.2.2 Математическая модель задачи коммивояжера 9
1.3 Современные алгоритмы с помощью которых решается задача коммивояжера 9
1.3.1 Точные алгоритмы 9
1.3.2 Эвристические алгоритмы 10
1.3.3 Поисковые алгоритмы 11
1.4 Положения муравьиного алгоритма для задачи коммивояжера и ее решения 12
ГЛАВА 2 РАЗРАБОТКА ПРИЛОЖЕНИЯ РЕШЕНИЯ ЗАДАЧ КОММИВОЯЖЁРА С ПОМОЩЬЮ МУРАВЬИНОГО АЛГОРИТМА 16
2.1 Постановка требований к приложению 16
2.2 Обоснование выбора технических средств 17
2.3 Разработка архитектуры ПО 21
2.4 Реализация алгоритма 25
2.5 Разработка приложения 27
2.6 Интерфейс приложения 29
2.7 Описание работы приложения 29
2.7.1 Создание графа 29
2.7.2 Работа приложения 31
2.7.3 Получение результатов 34
2.8 Проведение вычислительного эксперимента 34
2.9 Динамика нахождения решений 37
ЗАКЛЮЧЕНИЕ 39
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 40
Приложение А. Relationships-Class Diagram 42
Купить

С помощью наглядной демонстрации работы алгоритмов можно обеспечить более высокий уровень методов решения задач оптимизации, чтобы при прохождении вычислительных экспериментов была такая возможность, как не только продемонстрировать работу алгоритма на примере, но и модифицировать алгоритм, позволяя увидеть разницу в решении задачи при использовании различных подходов, а также возможность изменения исходных данных для демонстрации работы одного алгоритма в различных условиях.
Задача коммивояжёра дает возможность получить решение с использованием различных алгоритмов. Одним из наиболее результативных алгоритмов считается алгоритм оптимизации подражанием муравьиной колонии (ant colony optimization) [6].
Задача коммивояжёра считается довольно значимой транспортной задачей, которая занимается планированием транспортных перевозок. Для решения данной задачи требуется определить наиболее лучший маршрут объезда всех городов. Задача коммивояжера может решать проблемы распределения общественного транспорта города, выбор наилучшего пути для проезда курьера и т.п.
Известна одна из программных реализаций муравьиного алгоритма, написанная на языке Java, обеспечивающая наглядное представление о механизме работы алгоритма с возможностью его модификации. Однако это решение не позволяет вносить изменения в исходные данные, а также не обеспечивает достаточного функционала для визуального проектирования графов.
Таким образом, актуальность темы бакалаврской работы обусловлена тем, что даже при наличии большого количества уже реализованных муравьиных алгоритмов необходимо и дальше реализовывать, и улучшать данные алгоритмы для поиска наилучшего результата, т.к. применение автоматизированных систем в области транспортной логистики - один из способов экономии ресурсов.
Данная бакалаврская работа отличается высокой практической значимостью. В ходе его создания была разработана программа, решающая задачу коммивояжера с помощью муравьиного алгоритма, позволяющая сделать процесс выбора оптимального пути наиболее результативным.
Программная реализация и визуализация данного алгоритма позволят проектировать графы и наглядно демонстрировать механизм действия муравьиного алгоритма решения задачи коммивояжёра.
Объект исследования ВКР - задача коммивояжера.
Предмет исследования ВКР - применимость муравьиного алгоритма для решения задачи коммивояжера.
Цель работы - исследование применимости муравьиного алгоритма для решения задачи коммивояжера.
Задачами работы являются:
• реализация алгоритма оптимизации с помощью муравьиного алгоритма;
• разработка муравьиного алгоритма для приложения.
Обзор по главам:
1) Первая глава описывает задачу коммивояжера, ее историю, алгоритмы решения данной задачи, муравьиные алгоритмы, решение задач коммивояжера с помощью муравьиных алгоритмов;
2) Вторая глава - разработка приложения, с помощью которого решается задача коммивояжера с помощью муравьиного алгоритма, описание классов, реализация алгоритма, интерфейс приложения, проведение вычислительного эксперимента.
Купить