Главная Работы на конкурс Предметное образование Физико-математические дисциплины
Исследовательская работа «Генетические алгоритмы и их компьютерная реализация для планирования туристических маршрутов»
Автор: Иванченко Глеб Вильяминович, Мунтян Ольга Александровна
Место работы/учебы (аффилиация): МОУ «Бендерский теоретический лицей», Приднестровская Молдавская Республика, 11 класс
Научный руководитель: Сокольская Елена Владимировна
Актуальность выбора темы. Задача оптимизации в математике и информатике заключается в нахождении наилучшего решения – минимума или максимума целевой функции. Данная задача решается методом математического моделирования. В частности, большой интерес представляют эволюционные методы, к которым относятся генетические алгоритмы и его реализация для задачи коммивояжера.
Для выбора объекта исследования нами было рассмотрено множество задач в области экономики, логистики транспортных перевозок. Но, в итоге, решили заняться проблемой планирования оптимальных туристических маршрутов в нашем регионе с использованием генетических алгоритмов из-за актуальности этих задач и значительной сложности их решения обычными математическими методами.
Цель исследования заключается в разработке компьютерной программы на основе генетических алгоритмов для оптимального планирования туристических маршрутов.
Задачи исследования:
- Описать схему генетического алгоритма, используя модель «эволюционного процесса».
- Проанализировать особенности применения теории графов в качестве математического инструмента для описания туристических маршрутов.
- Разработать компьютерную программу, реализующую схему генетического алгоритма, для оптимального планирования маршрутов с учетом различных ограничений и критериев оптимизации.
- Применить разработанную компьютерную программу для нахождения оптимальных туристических маршрутов в нашей республике.
Гипотезы исследования:
- Генетический алгоритм позволяет находить наилучшие туристические маршруты исходя из различных критериев оптимальности.
- Генетический алгоритм может быть применен для коротких и длинных туров, причем на коротких турах используется его укороченная версия.
Объект исследования ̶ генетический алгоритм как метод нахождения наилучших решений. Предмет исследования – генетический алгоритм для нахождения
оптимальных туристических маршрутов.
Методы исследования: В процессе выполнения исследовательской работы мы изучили литературные источники по данной теме, проанализировали информацию об использовании теории графов и генетических алгоритмов для нахождения наилучших решений, применили метод математического и компьютерного моделирования для планирования туристических маршрутов.
Результаты и выводы:
- В нашем исследовании мы применили генетические алгоритмы для нахождения оптимальных туристических маршрутов. Для этого разработали компьютерную программу, реализующую «эволюционный процесс» на основе селекции, скрещивания и мутации множества решений данной задачи.
- В качестве математического инструмента для планирования туристических маршрутов выбрали теорию графов. Мы решили задачу коммивояжёра (задачу о путешественнике), заключающуюся в поиске самого выгодного маршрута.
- В компьютерной программе использовали следующие критерии оптимальности маршрута: кратчайший путь, самый дешёвый по стоимости, совокупный критерий и соответствующие матрицы расстояний и иные характеристики. Применили разработанную компьютерную программу для нахождения оптимальных туристических маршрутов в городах Российской Федерации.
- Генетический алгоритм реализован для коротких (10 пунктов) и длинных туров (20 пунктов). Для коротких туристических маршрутов была реализована укороченная версия генетического алгоритма (использована только мутация туров, скрещение и селекция не применялось).
- Проведено тестирование этапов генетического алгоритма в разных вариантах его реализации, на основе чего были разработаны рекомендации по использованию мутации, селекции и скрещивания в задаче оптимального планирования туристических маршрутов.
- Пришли к выводу, что генетический алгоритм достаточно хорошо адаптируется для широкого круга научно-технических задач. Для этого необходимо выбрать математическую модель и множество решений исходной задачи, определить функцию скрещивания и мутации, а также условия отбора наилучших решений.
Смотреть похожие работы
Проектная работа «Веб-сайт «Bestol»
Доступна к просмотру полнотекстовая версия работы
Проектная работа «Создание приложения в Python»
Доступна к просмотру полнотекстовая версия работы
Исследовательский проект «Создание онлайн платформы «Крылатские фарватеры»
Проектная работа «Разработка и внедрение искусственного интеллекта»
Доступна к просмотру полнотекстовая версия работы
Проект «Устройство для поиска вещей в быту на основе технологии RFID»
Доступна к просмотру полнотекстовая версия работы
Презентация «Компьютерная графика в разработке игр и создание образа персонажа в стиле игры Genshin Impact»
Мероприятие завершено
Добавить комментарий