Тема: Муравьиный алгоритм в решении задачи коммивояжера

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

В рамках бакалаврской работы все цели и задачи выполнены. Было рассмотрены муравьиные алгоритме в задаче коммивояжера, был выделен объект исследования, проанализирована предметная область, определены цели и задачи работы. Проведен анализ существующих алгоритмов для решения задачи коммивояжера и выявлен наиболее подходящий для реализации цели выпускной квалификационной работы.
При анализе задачи коммивояжера было выявлено, что для решения задач бакалаврской работы потребуется написать свою программную реализацию муравьиного алгоритма, а не использовать существующие, так как существующие разработки были сделаны для других конкретных целей, поэтому и наша разработка будет носить такой же характер.
Был спроектирован интерфейс пользователя и использован муравьиный алгоритм.
Алгоритм и интерфейс были реализованы в среде разработки IntelliJ IDEA с использованием языка программирования Java. В ходе выполнения работы реализованы следующие функции:
• ввод пользователем параметров для алгоритма;
• отображение результатов на каждой итерации;
• реализована визуализация муравьиного алгоритма.
Затем, муравьиный алгоритм был применен к задаче коммивояжера, для того что бы найти оптимальный путь прохождения в той или иной задаче.
Итогом бакалаврской работы является разработанный алгоритм и приложение которое решает задачу коммивояжера с помощью муравьиного алгоритма, позволяющая, вручную вводить график, проходить по каждой итерации в задаче. Работа соответствует целям и задачам, которые были поставлены.
Купить