Регистрация / Вход
Прислать материал

ПОИСК РЕШЕНИЙ ТРАНСПОРТНОЙ ЗАДАЧИ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

Сведения об участнике
ФИО
Подъячев Артем Алексеевич
Вуз
Федеральное государственное бюджетное образовательное учреждение высшего образования «Сибирский государственный университет водного транспорта»
Тезисы (информация о проекте)
Область наук
Информационные технологии и вычислительные системы
Раздел области наук
Информационные технологии
Тема
ПОИСК РЕШЕНИЙ ТРАНСПОРТНОЙ ЗАДАЧИ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ГЕНЕТИЧЕСКОГО АЛГОРИТМА
Резюме
Основной идеей проекта является разработка программной среды, предназначенной для работы с генетическими алгоритмами, а именно для решения транспортной задачи при помощи генетических алгоритмов. Основными компонентами среды являются: web-ориентированная архитектура, гипертекстовое оформление программы и скриптовый обработчик всех необходимых вычислений, написанный на языке JavaScript
Ключевые слова
Генетический алгоритм,транспортная задача, web-ориентированная архитектура,преобразование Хафа
Цели и задачи
Цель проекта
Основной целью проекта решение транспортного вопроса для участка дороги с помощью методов генетического алгоритма.
Задачи проекта
Основными задачи проекта являются:
1.Анализ транспортного вопроса
2.Составление генетического алгоритма.
3.Возможность загрузки и сохранения результатов
4. Разработка взаимодействия с пользователем.
5. Программная реализация среды
Введение

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

Методы и материалы

Генетический алгоритм (далее ГА) – это процедуры поиска, основанные на механизмах естественного отбора и наследования, нацеленные главным образом, на решение задач оптимизации.

Алгоритм делится на три этапа:

·        Скрещивание

·        Селекция (отбор)

·        Формирования нового поколения

Если результат нас не устраивает, эти шаги повторяются до тех пор, пока результат нас не начнет удовлетворять или произойдет одно из ниже перечисленных условий:

·        Количество поколений (циклов) достигнет заранее выбранного максимума

·        Исчерпано время на мутацию

Преобразование Хафа — это метод обнаружения прямых и кривых линий на полутоновых или цветных изображениях. Метод позволяет указать параметры семейства кривых и обеспечивает поиск на изображении множества кривых заданного семейства. Назначение преобразования Хафа — разрешить проблему группировки граничных точек путём применения определённой процедуры голосования к набору параметризованных объектов изображения.

Описание и обсуждение результатов

Основные научные результаты

Перед тем как приступить к реализации проекта понадобилось тщательное изучение проблемы генетических алгоритмов и детальное рассмотрение предметной области.

Результатом данной исследовательской работы явилось следующее:

  1. Был проведен сравнительный анализ существующих программных сред, для работы с ГА, и сделан вывод о том что, для решения поставленных задач, необходимо разрабатывать собственную программную среду.
  2. Был проведен анализ инструментальных средств создания различных программным сред, и для разработки программы выбрана web-ориентированная архитектура и язык программирования JavaScript.

Ожидаемые результаты

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

Так же необходима реализация всех видов генетического алгоритма, и выбора, наиболее подходящего для выполнения поставленной задачи

Помимо этого, есть необходимость в наглядном отображении результатов оптимизации в виде графиков функции.

Используемые источники
Литература
1. Панченко, Т. В. Генетические алгоритмы [Текст]: учебно-методическое пособие / под ред. Ю. Ю. Тарасевича. — Астрахань: Издательский дом «Астраханский университет», 2007. — 87 с.
2. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы [Текст]: учеб. пособие - 2-е изд. - М: Физматлит, 2006. — 320 с.
3. Генетические алгоритмы в методах оптимизации [Электронный ресурс]. – Режим доступа: http://www.lib.tpu.ru/fulltext/v/Conferences/2012/ C2/V2/v2_129.pdf, свободный.
4. Преобразование Хафа [Электронный ресурс]. – Режим доступа
http://robocraft.ru/blog/computervision/502.html свободный.
Information about the project
Surname Name
Podyachev Artem
Project title
FINDING OF SOLUTIONS TRANSPORT PROBLEMS WITH THE USE OF METHODS OF GENETIC ALGORITHM
Summary of the project
Currently, the problem of traffic congestion is very is very important. To solve this problem, you must apply different analytical method of optimization. For example the genetic algorithm . If to use the genetic algorithm’s, to solve the transport problem you can reduce the time spent required for the analysis. Additionally, the algorithms can be useful when you are implementing the optimization computations in different information systems with artificial intelligence.
Keywords
genetic algorithm, traffic congestion, transport problem