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

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

Автор: Иванченко Глеб Вильяминович, Мунтян Ольга Александровна

Место работы/учебы (аффилиация): МОУ «Бендерский теоретический лицей», Приднестровская Молдавская Республика, 11 класс

Научный руководитель: Сокольская Елена Владимировна

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

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

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

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

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

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

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

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

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Смотреть похожие работы

Выпускная квалификационная работа «Разработка программного модуля для определения зон роста биологического объекта с применением машинного обучения»

Автоматизация научных исследований играет ключевую роль в современном мире, ускоряя процесс получения и анализа данных, повышая точность и качество результатов, а также обеспечивая возможность более глубокого анализа и предсказаний. С развитием техно…
Посмотреть работу

Проект «Легенды и мифы уникальных гор Якутии»

Большую часть Республики Саха (Якутия) занимают горы и плоскогорья, которые являются главными природными богатствами. Они поражают не только своими размерами, но красотой и разнообразием: это альпийские поля предгорий, горные тундры, безлесные гольцы…
Посмотреть работу

Проект «Создание бота для программы Discord на языке Python»

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

Проект «Сборка робота-автомобиля с дистанционным управлением на базе программы Arduino»

В нашей повседневной жизни автоматика и робототехника применяется во многих областях. Видим такие устройства, например дома (роботы-пылесосы), на заводах и фабриках (автоматические станки с ЧПУ), на транспорте (турникеты в метро, беспилотные автомоби…
Посмотреть работу

Проект «Открытие школы робототехники и программирования»

В рамках подготовки проекта открытия школы робототехники и программирования проведено комплексное маркетинговое исследование услуг такого рода г. Курска, произведен расчет предполагаемых инвестиционных и текущих расходов, а также разработаны организа…
Посмотреть работу

Проект «Программно-аппаратный комплекс предпрофильного отбора и реабилитации операторов дронов»

Проект посвящён созданию мобильного программно-аппаратного комплекса пред-профильного отбора и реабилитации операторов дронов. Решаемые проблемы: предпрофильный отбор кандидатов способных эффективно дистанционно управлять дронами; контроль степени ут…
Посмотреть работу

Мероприятие завершено

Конкурс, в котором работа участвует

V Международный конкурс исследовательских работ школьников «Research start 2022/2023»

Направление

Физико-математические дисциплины

Форма представления работы

Исследовательская работа

Ключевые слова

Проект по программированию (Pascal, Python, Java, С, С++, C# и др.)

Дата публикации работы

14.05.2023