ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ОРГАНИЗАЦИИ РАБОТЫ СВЕТОФОРОВ С ЦЕЛЬЮ ОПТИМИЗАЦИИ ДОРОЖНОГО ТРАФИКА

ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ОРГАНИЗАЦИИ РАБОТЫ СВЕТОФОРОВ С ЦЕЛЬЮ ОПТИМИЗАЦИИ ДОРОЖНОГО ТРАФИКА

Константинов Кирилл Сергеевич

студент Московского автомобильно-дорожного государственного технического университета (МАДИ),

РФ, г. Москва

Волосова Александра Владимировна

научный руководитель, канд. техн. наук, Московский автомобильно-дорожный государственный технический университет (МАДИ),

РФ, г. Москва

АННОТАЦИЯ

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

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

Для симуляции работы светофоров и оценки эффективности различных расписаний переключения сигналов было использовано программное средство Simulation of Urban MObility (SUMO), который является мощным инструментом для моделирования и симуляции дорожного трафика, позволяющим создавать реалистичные городские сценарии и анализировать их производительность.

Для реализации генетического алгоритма и проведения экспериментов был использован язык программирования Python, который предоставляет широкий набор библиотек и инструментов для разработки и исследования в области искусственного интеллекта и оптимизации. Были использованы такие библиотеки, как Traci для работы со средой симуляцти, а также DEAP (Distributed Evolutionary Algorithms in Python) для реализации генетического алгоритма и коэволюции.

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

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

Ключевые слова: Генетический алгоритм, коэволюция, оптимизация дорожного трафика, симуляция реальной дорожной сети, адаптивное управление, эволюционные методы оптимизации, планирование переключения сигналов, Python, SUMO (Simulation of Urban MObility).

Введение

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

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

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

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

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

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

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

1 ОБЗОР РАБОТ ПО ТЕМЕ ИССЛЕДОВАНИЯ

В работе [1] было описано использование генетического алгоритма для оптимизации планов синхронизации светофоров. В качестве объекта применения была выбрана сеть дорожных перекрестков формы октоторпа с четырьмя перекрестками. Каждый перекресток может иметь двухфазный план работы. В этом методе использовались девять переменных решения, включая общее время зеленого сигнала для всех фаз, порядок и деление фаз. Девять переменных решения кодировались 24-битными последовательностями. Целевая функция была обратной величине общего времени ожидания. Для оценки оптимизационного метода использовалась модель симуляции. Результаты показали, что генетический алгоритм является параллельным методом оптимизации по сравнению с традиционными методами поиска.

Для управления и контроля данной проблемы большинство существующих систем управления светофорами используют статические модели потоков на перекрестках, предполагая, что форма и цикл потока в обычные или пиковые часы одинаковы во все время. Некоторые исследования фиксировали длительность цикла и переполнение на каждом перекрестке, изменяя только деление зеленого сигнала [2, 3, 4].

Коэволюция используется для реализации сотрудничества между мультиагентами [5], работающими в сложных средах задач. В настоящее время большинство методов мультиагентной коэволюции основаны на устойчивых и статических средах, в которых агенты взаимодействуют, чтобы получать опыт и постепенно адаптироваться к среде, например, метод ISGE-NCE и метод MPT-NCE на основе некооперативного равновесия [6, 7]. Однако в динамической среде, где условия задачи постоянно меняются, лучшая политика, основанная на текущей информации, перестает быть "лучшей", поскольку меняется среда [8]. Например, рассмотрим ситуацию преследования: количество и положение агентов, препятствий и целей, режим движения препятствий и любое изменение этих факторов приводят к динамической среде. В этом случае оптимальные параметры, полученные агентами на основе предыдущего опыта, могут стать переобученными и представлять набор локально оптимальных решений [9]. В таком случае повторное обучение является прямым способом избежать локального оптимума, но требует много времени. Для быстрой адаптивной коэволюции мультиагента в динамической среде великая важность решения проблемы возможного локального оптимума в процессе обучения и эволюции мультиагента.

2 Модели и методы решения поставленной задачи

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

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

2.1 Моделирование и симуляция:

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

 Все это будет симулировано на платформе SUMO, которая обеспечит возможность проведения экспериментов на всех выбранных сценариях. А для построения модели дорожной сети был использован инструмент OSM Web Viewer, поставляющийся в пакете с платформой SUMO. Готовая симуляция представлена на рисунке 1.

 Рисунок 1. Симуляция двух кварталов на платформе SUMO

2.2 Реализация генетического алгоритма с коэволюцией

Реализация генетического алгоритма с коэволюцией для оптимизации управления светофорами включает следующие этапы и подходы.

• Инициализация начальных популяций.
• Оценка приспособленности индивидуумов популяций.
• Применение генетических операторов: селекции, скрещивания и мутации.
• Создание новой популяции.
• Повторение шагов до достижения критерия остановки.

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

Где продолжительность разрешающий фазы светофора,

продолжительность запрещенной фазы светофора,

количество периодов из сигналов светофора

Начальные популяции для каждого светофора были инициализированы с помощью генерации случайных вещественных значений в диапазоне от 0 до 120. Эти значения представляют длительность фаз светофоров. Количество популяций было получено из конфигурации симуляции.

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

Функция приспособленности была определена формулой, в которой минимум будет являться наилучшими показателями по трем параметрам. Для наглядности неоптимальное решение было принято равным единице. Таким образом, функция приспособленности имеет следующий вид:

                              (1)

Где: значение функции приспособленности;

текущий показатель средней скорости;

 неоптимальный показатель средней скорости;

 текущий показатель общего времени остановок;

значение функции приспособленности;

 неоптимальный показатель общего времени остановок;

 неоптимальный показатель общих затрат топлива.

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

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

Таким образом для экспериментов будет использован вышеописанный вариант генетического алгоритма с коэволюцией. А для симуляции работы дорожной сети будет использована среда симуляции SUMO.

3 результаты решения поставленной задачи

Для более объективного сравнения методов необходимо определить набор сценариев, которые будут использоваться при проведении экспериментов. В данной работе будут использоваться конфигурации, в которых постепенно в симуляцию будут загружены 900, 2700 и 5400 автомобилей.

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

Среднее время ожидания одного автомобиля возьмем, как время, в течение которого скорость транспортного средства была ниже или равна 0,1 м/с (плановые остановки не учитываются). Такой показатель можно получить из симуляции.

Количество потраченного топлива - полный объем топлива, израсходованного транспортным средством за время поездки. Такой показатель уже представлен в симуляции.

В качестве неоптимизированный системы возьмем данные полученные при симуляции трафика с светофорами с фиксированным расписанием. Значение метрик приведено в таблице 3.1.

Таблица 3.1.

Значение метрик при фиксированном расписании

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

Зависимость значения приспособленности от продолжительности поиска решений для 900 автомобилей приведен на рисунке 3.1.

Зависимость значения приспособленности от продолжительности поиска решений для 1800 автомобилей приведен на рисунке 3.2.

Зависимость значения приспособленности от продолжительности поиска решений для 2700 автомобилей приведен на рисунке 3.3.

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

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

Таблица 3.2.

Значение метрик самых приспособленных индивидуумов

Таким образом генетический алгоритм показал оптимизацию дорожного трафика по всем метрикам для 900, 1800 и 2700 автомобилей на примерно 48%, 39% и 19% соответственно.

Заключение

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

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

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

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

Список литературы:

1. Foy, M. D. et al., Signal Timing Determination Using Genetic Algorithms. Transportation Research. Record 1365, National Research Council, Washington, D.C., 1992, pp. 108~115.
2. Kwasnicka, H. and Stanek M.: Genetic approach to optimize traffic flow by timing plan manipulation. Intelligent Systems Design and Applications, ISDA’06. Sixth International Conference on, IEEE (2006).
3. Purohit, G., Sherry, M. and Saraswat, M.: Time optimization for real time traffic signal control system using Genetic Algorithm. Global Journal of Enterprise Information System, Volume 3, Issue 4, (2011).
4. Zang, L., Hu, P. and Zhu, W.: Study on dynamic coordinated control of traffic signals for oversaturated arterials. Journal of Information and Computational Science, Volume 9, Issue 12, pp. 3625-3632, (2012)
5. Xue, H.T.; Lincheng, S.C. Multi-agent system based on co-evolution method and its’ symbol deduction theory model. In Proceedings of the 26th Chinese Control Conference, Zhangjiajie, China, 26–31 July 2007; p. 736.
6. Li, Y.; Zhao, M.Y.; Zhang, H.Z.; Yang, F.L.; Wang, S.Y. An Interactive Self-Learning Game and Evolutionary Approach Based on Non-Cooperative Equilibrium. Electronics 2021, 10, 2977.
7. Li, Y.; Zhao, M.Y.; Zhang, H.Z.; Qu, Y.Y.; Wang, S.Y. A Multi-Agent Motion Prediction and Tracking Method Based on NonCooperative Equilibrium. Mathematics 2022, 10, 164.
8. Wang, Z.; Chen, C.L.; Li, H.X.; Dong, D.Y.; Tarn, T.J. Incremental Reinforcement Learning with Prioritized Sweeping for Dynamic Environments. IEEE/ASME Trans. Mechatron. 2019, 24, 621–632. [CrossRef]
9. Wang, Z.; Li, H.X.; Chen, C.L. Incremental Reinforcement Learning in Continuous Spaces via