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

Abstract

Целью выпускной квалификационной работы является сравнительный анализ муравьиного и генетического алгоритмов для поиска приближенного решения задачи коммивояжёра, а также экспериментальная оценка их эффективности. В рамках исследования разработана информационно-логическая модель системы с использованием нотации UML, разработаны логическая и физическая модели данных системы и программная реализация обоих алгоритмов, выполнено тестирование на различных конфигурациях графов, определены оптимальные параметры для каждого метода. Для муравьиного алгоритма реализован механизм обновления феромонов с учетом длины маршрута, а в генетическом алгоритме применены методы турнирной селекции, order crossover и мутации с применением алгоритма 2-Opt. Проведено сравнение алгоритмов по критериям времени выполнения, точности решения и устойчивости к локальным оптимумам. Программная реализация выполнена на языке Java с использованием JavaFX для визуализации результатов. Среда разработки – Intellij IDEA. Тестирование проводилось на