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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проект «Защита данных»

Доступна к просмотру полнотекстовая версия работы

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

Проект «Компьютерные вирусы»

Доступна к просмотру полнотекстовая версия работы

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

Исследовательский проект «Разработка веб-сервиса для оптимизации составления расписания, основанное на искусственном интеллекте»

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

Информационный проект «Шифрование информации»

Доступна к просмотру полнотекстовая версия работы

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

Индивидуальный проект «Универсальная среда разработки программного обеспечения»

Доступна к просмотру полнотекстовая версия работы

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

Проект «Иностранные слова как основа для образования русского сленга»

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

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

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

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

Направление

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

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

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

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

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

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

14.05.2023