Исследовательская работа «Генетические алгоритмы и их компьютерная реализация для планирования туристических маршрутов»

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

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

Задачи исследования:

1. Описать схему генетического алгоритма, используя модель «эволюционного процесса».
2. Проанализировать особенности применения теории графов в качестве математического инструмента для описания туристических маршрутов.
3. Разработать компьютерную программу, реализующую схему генетического алгоритма, для оптимального планирования маршрутов с учетом различных ограничений и критериев оптимизации.
4. Применить разработанную компьютерную программу для нахождения оптимальных туристических маршрутов в нашей республике.

Гипотезы исследования:

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

Объект исследования ̶ генетический алгоритм как метод нахождения наилучших решений. Предмет исследования – генетический алгоритм для нахождения
оптимальных туристических маршрутов.

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

Результаты и выводы:

1. В нашем исследовании мы применили генетические алгоритмы для нахождения оптимальных туристических маршрутов. Для этого разработали компьютерную программу, реализующую «эволюционный процесс» на основе селекции, скрещивания и мутации множества решений данной задачи.
2. В качестве математического инструмента для планирования туристических маршрутов выбрали теорию графов. Мы решили задачу коммивояжёра (задачу о путешественнике), заключающуюся в поиске самого выгодного маршрута.
3. В компьютерной программе использовали следующие критерии оптимальности маршрута: кратчайший путь, самый дешёвый по стоимости, совокупный критерий и соответствующие матрицы расстояний и иные характеристики. Применили разработанную компьютерную программу для нахождения оптимальных туристических маршрутов в городах Российской Федерации.
4. Генетический алгоритм реализован для коротких (10 пунктов) и длинных туров (20 пунктов). Для коротких туристических маршрутов была реализована укороченная версия генетического алгоритма (использована только мутация туров, скрещение и селекция не применялось).
5. Проведено тестирование этапов генетического алгоритма в разных вариантах его реализации, на основе чего были разработаны рекомендации по использованию мутации, селекции и скрещивания в задаче оптимального планирования туристических маршрутов.
6. Пришли к выводу, что генетический алгоритм достаточно хорошо адаптируется для широкого круга научно-технических задач. Для этого необходимо выбрать математическую модель и множество решений исходной задачи, определить функцию скрещивания и мутации, а также условия отбора наилучших решений.