автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Инструментальные средства для нейросетевого моделирования и управления транспортными потоками на перекрестках

На правах рукописи

ГРИГОРЬЕВ Денис Алексеевич

ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ДЛЯ НЕЙРОСЕТЕВОГО МОДЕЛИРОВАНИЯ И УПРАВЛЕНИЯ ТРАНСПОРТНЫМИ ПОТОКАМИ НА ПЕРЕКРЕСТКАХ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

УФА 2004

Работа выполнена в Уфимском государственном авиационном техническом университете

Научный руководитель - доктор технических наук, профессор

Юсупова Нафиса Исламовна

Официальные оппоненты - доктор технических наук, профессор

Куликов Геннадий Григорьевич

кандидат технических наук, доцент Пестриков Владимир Анатольевич

Ведущее предприятие - Башкирская академия государственной службы

и управления при Президенте РБ

Защита состоится «_»_2004 года в часов на заседании

диссертационного совета_Уфимского государственного авиационного

технического университета по адресу: 450000, Уфа-центр, улХМаркса, 12, УГАТУ.

С диссертацией можно ознакомиться в библиотеке Уфимского государственного авиационного технического университета.

Ученый секретарь диссертационного совета канд. физ.-мат. наук, доцент

Гараев Р.А;

Общая характеристика работы

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

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

В настоящее время накоплен большой опыт применения интеллектуальных методов для различных прикладных проблем как у нас в стране (Васильев В.И., Галушкин А.И., Горбань А.И., Ильясов Б.Г., Куликов Г.Г., Миронов В.В., Поспелов Д.А., Юсупова Н.И. и др.), так и за рубежом (Lotfi A. Zadeh, Anil К. Jain, Narendra K.P. и др.). Выглядит перспективным применение таких методов к задаче распределения потоков транспорта.

В данной работе используется подход к распределению потоков транспорта для произвольного перекрестка и различных условий дорожного дви-

жения с применением нейронных сетей.

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

Для достижения поставленной цели в работе сформулированы и решены следующие задачи:

1. Разработка подхода к моделированию процессов распределения потоков транспорта для сети взаимосвязанных перекрестков на основе нейронной сети;

2. Разработка моделей для.информационной системы распределения потоков транспорта для произвольного перекрестка и моделирующего стенда с использованием структурного и объектно-ориентированного анализа;

3. Разработка алгоритмов распределения потоков транспорта на основе нейросетевого подхода для сети взаимосвязанных перекрестков;

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

Методика исследования. В работе применяются методы системного анализа, системного моделирования, CASE-технологии, нейросетевые методы, методы компьютерного моделирования и анализа данных.

На защиту выносятся

1. Подход к моделированию процессов распределения потоков транспорта для сети взаимосвязанных перекрестков на основе нейронной сети;

2. Модели для информационной системы и моделирующего стенда распределения потоков транспорта для произвольного перекрестка с использованием CASE-технологий;

3. Алгоритмы распределения потоков транспорта для сети взаимосвязанных перекрестков для различных типов нейронных сетей и алгоритмов обучения;

4. Результаты исследования эффективности предложенных методов распределения потоков транспорта на основе разработанных инструментальных средств.

Научная новизна

1. Предложен новый подход к распределению потоков транспорта на основе нейронной сети, позволяющий повысить пропускную способность перекрестков;

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

3. Впервые разработаны модели для реализации моделирующего стенда с целью исследования методики распределения потоков транспорта для произвольного перекрестка на основе нейронной сети;

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

Практическая значимость

В результате выполнения диссертационной работы автором получены следующие результаты:

1. Разработаны инструментальные средства, позволяющие реализовать методику распределения потоков транспорта на перекрестках произвольной конфигурации;

2. Разработано программное обеспечение, реализующее методику распределения потоков транспорта в условиях перекрестка произвольной конфигурации на основе нейронной сети «многослойного персептрона» и алго-

ритма обучения «обратного распространения ошибки», нейронной сети Ко-хонена и алгоритмов обучения Кохонена и Хэбба. Разработаное программное обеспечение зарегистрировано в Реестре программ для ЭВМ (свидетельство о регистрации №2002611009 от 20.06.2002г);

3. Проведены модельные эксперименты, которые показали, что применение нейронных сетей к распределению потоков транспорта на перекрестках является более эффективным по сравнению с традиционным методом и позволяет уменьшить количество транспорта перед светофором на 10-15%.

Работа велась в рамках научной работы по хоздоговорной научно-исследовательской теме "Исследование проблем развития, управления, контроля и моделирования в сложных системах" № ИФ-ТК-14-ОЗ-ОЗ/б. Работа частично поддержана грантом РФФИ 03-07-90242 ."Интернет-комплекс поддержки выполнения проектов фундаментальных исследований сложных систем с применением интеллектуальных технологий на базе экспертных систем" (2003 - 2005 гг.) и федеральной целевой программой "Интеграция науки и высшего образования Российской Федерации на 2002 - 2006 годы", проект П0039 "Фундаментальные исследования и новые, технологии проектирования сложных технических систем1*.

Результаты внедрены в учебный процесс УГАТУ по изучению нейронных сетей и используются в материалах лекций, практических и лабораторных работ дисциплин «Нейрокомпьютерные системы», «Системы искусственного интеллекта», «Теоретические основы информационных процессов» для студентов специальностей 351500 «Математическое обеспечение и администрирование информационных систем», 220400 «Программное обеспечение вычислительной техники и автоматизированных систем», а также магистрантов направления 552800 «Информатика и вычислительная техника», обучающихся по программе 552819 «Компьютерный анализ и интерпретация данных».

Результаты внедрены в учебный процесс БАГСУ и используются в материалах лекций и лабораторных работ дисциплин «Разработка управленческих решений», «Информационные технологии в управлении», «Основы системного анализа» по специальностям 061000 «Государственное и муниципальной управление», 061100 «Менеджмент организации».

Апробация работы. Основные положения, представленные в диссертационной работе, докладывались и обсуждались на различных конференциях, в частности на VIII Всероссийской конференции с международным участием «Нейрокомпьютеры и их применение» (Москва, 2002), на 10-ом Всероссийском студенческом семинаре «Проблемы управления» (Москва, 2002), на юбилейной студенческой научно-теоретической конференции (Уфа, 2002), на международных конференциях «Computer Science and Information Technologies» (CSIT) (Патрас, Греция, 2002; Уфа, 2003).

Результаты работы отражены в 6 публикациях, 3 приняты к публикации в различных изданиях.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе представлены результаты анализа известных подходов к распределению потоков транспорта.

Подход к решению на основе оптимизации перемещения из одного пункта в другой соответствует методам динамического программирования, в частности, классу задач, объединяемых под названием «транспортная задача». В нем не учитываются ряд особенностей: заранее неопределенное направление движения транспорта; постановка транспортной задачи предпола-

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

На основании результатов анализа существующих методов были выделены нерешенные задачи и сформулированы цель и задачи настоящего исследования.

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

ного сигнала. Перед системой распределения потоков транспорта ставится задача минимизации количества транспорта, стоящего перед светофором.

В данном случае нейронная сеть (НС) применяется для решения задачи аппроксимации функции. При этом аргументом функции являются данные о потоке транспорта, а значением функции - сигналы для светофоров.

Возможные варианты включения НС в дорожную сеть представлены на рисунке 1.

Рис. 1 - Возможные варианты включения НС в дорожную сеть а - соседние перекрестки не управляются нейронной сетью; б - соседние перекрестки управляются неГфонной сетью; в - смешанный вариант.

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

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

Для моделирования информационной системы распределения потоков транспорта использовалась методология структурного анализа. Разработанные функциональная (см. рис. 2) и информационная (см. рис. 3) модели информационной системы позволяют автоматизировать процесс разработки ПО и проектирования базы данных информационной системы.

На основе структуры системы перекрестков и потока транспорта осуществляется обработка данных. На основе обработанных данных получаем управляющие сигналы для каждой нейронной сети. Поток транспорта совместно с управляющими сигналами обрабатывается нейронной сетью, в результате чего вырабатываются длительности сигналов светофоров. Разработанная на основе функциональной модели системы информационная модель для рассматриваемой задачи (см. рис. 3) включает в себя следующие сущности -отдельно взятый перекресток в системе связанных перекрестков, поток транспорта на перекрестках, обучающие данные, нейронную сеть, длительность сигналов.

Для проектирования моделирующего стенда было использовано средство фирмы Rational Software Corporation - Rational Rose, которое предназначено для автоматизации этапов анализа и проектирования программного обеспечения, а также для генерации кодов на различных языках и выпуска проектной документации и основано на универсальной нотации для моделирования объектов (UML).

Разработанные на основе методологии объектно-ориентированного анализа UML диаграммы (см. рис. 4) позволили получить основные классы и модули программы модулирующего стенда для исследования эффективности нейросетевого подхода.

В четвертой главе исследуется вопрос выбора нейронных сетей для задачи распределения потоков транспорта на перекрестках.

Для реализации системы распределения потоков транспорта выделены «многослойный персептрон» и сеть Кохонена, а в качестве алгоритмов обучения нейронных сетей — метод обратного распространения ошибки, алгоритм обучения Кохонена и обучение по правилу Хебба. При использовании сети типа «многослойный персептрон» на вход нейронной сети поступает информация о состоянии дорожного движения, куда входит информация о входящих потоках транспорта, о пропускной способности выходных дуг, а также о потоках транспорта, движущихся с соседних перекрестков. На выходах нейронной сети - интервалы работы сигналов светофора. В качестве функции активации предлагается использовать сигмоидную функцию. Это связано с тем, что на выходе необходимо получать сигнал от 0 до I, соответствующий доле зеленого сигнала в полном цикле работы светофора. При использовании сети Кохонена диапазон изменения длительности сигналов светофора разбивается на несколько интервалов в зависимости от количества выходных нейронов, при этом активный нейрон на выходе будет соответствовать одному из интервалов длительности сигнала светофора. Число скрытых слоев и число нейронов в каждом слое выбираются исходя из скорости обучения НС и качества управления транспортом обученной НС. Число слоев НС определяется порядком числа обучающих данных. При использовании около 10-20 обучающих пар достаточно двух скрытых слоев по 8-10 нейронов, при увеличении объема обучающей выборки число слоев увеличивается, когда результаты обучения сети становятся неудовлетворительными.

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

Для реализации нейросетевого подхода к распределению потоков транспорта на перекрестках произвольной конфигурации была разработана программа "NEURO" в среде Delphi 5 Enterprise Edition. Программа состоит из следующих модулей: настройки параметров, настройки структуры НС, статистических данных, загруженности дорога, протоколирования входной информации, обучения НС, моделирования процесса.

Для реализации компьютерного моделирования на основе предложенного подхода предлагается следующая методика:

- на основе параметров перекрестка формируются тестовые данные, включающие в себя характеристики самого перекрестка (число дорог, их пересечения) и параметры дорожного движения в различное время суток;

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

- выполняется сравнение полученных результатов.

а б в

Рис. 5 - Тестовые конфигурации перекрестков: а - стык трех дорог, б - простое пересечение; в - сложный перекресток

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

В качестве первичных характеристик эффективности предлагается использовать два параметра: число машин перед светофором X, время ожидания перед светофором Длина пробки Ь определяется числом машин. Среднее время ожидания ^ можно оценить с помощью количества циклов работы светофора, в течение которых машина стоит в пробке.

я щ т т.шм^.мв м« гае

Рис. 6 - Количество машин перёд светофором при применении нейро-сетевого подхода а) обратное распространение ошибки б) обучение по правилу Хебба в) алгоритм Кохонена.

Обучающие данные выбирались в соответствии с распределением Пуассона и предъявлялись нейронной сети. В качестве промежутка времени эксперимента было выбрано 200 циклов работы светофоров на перекрестке. Поведено 100 эспериментов для каждого перекрестка и нейросетевого алгоритма. На рисунке 6 (см. рис 6) показан процесс моделирования распределения потоков транспорта, используя различные алгоритмы обучения (обратное распространение ошибки, обучение по правилу Хебба и алгоритм Кохонена).

Среднее количество машин перед светофором для рассмотренных конфигураций перекрестков представлено на рисунке 7.

Рис. 7 - Среднее количество машин перед светофором а) Т-образцый перекресток б) простое пересечение двух дорог в) сложный перекресток (пять дорог)

При сравнении распределения потока транспорта для трех типов перекрестков и при одинаковых исходных данных, но разных алгоритмах обуче-

ния были получены следующие результаты: все нейросетевые алгоритмы показали достаточную эффективность по сравнению с традиционным методом - количество машин перед перекрестком уменьшилось примерно на 10-15%, при увеличении количества дорог на перекрестке эффективность нейросете-вых методов относительно традиционного метода уменьшилось незначительно и примерно одинаково для всех видов алгоритмов - порядка 1-2% при расширении перекрестка на одну дорогу (Алгоритм обратного распространения ошибки для 3 дорог - 16,3%, для 4 - 15,7%, для 5 - 14,0%, Алгоритм Хебба для 3 дорог - 13,6%, для 4 - 11,1%, для 5 -9,5%, Алгоритм Кохонена для 3 дорог -9,8%, для 4 -8,3%, для 5 -6,2%). Алгоритм обратного распространения ошибки обеспечил наибольшую эффективность распределения потока транспорта на рассматриваемых перекрестках по сравнению с другими алгоритмами обучения, но показал намного меньшую скорость обучения нейронных сетей, чем алгоритмы Кохонена и Хэбба.

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

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

1. Разработанный подход к распределению потоков транспорта для сети взаимосвязанных перекрестков позволяет создать распределенную информационную систему с использованием нейронной сети и позволяет улучшить пропускную способность перекрестков по сравнению с традиционным методом;

2. Разработанные модели информационной системы для распределения потоков транспорта на основе нейронной сети с использованием CASE-средств методологии структурного анализа позволяют автоматизировать

процесс разработки ПО и проектирования базы данных информационной системы;

3. Разработанные диаграммы деятельности, основных классов и модулей распределения потоков транспорта с использованием нейросетевого подхода на основе методологии объектно-ориентированного анализа позволяют разработать компоненты программного обеспечения моделирующего стенда;

4. Разработанные нейросетевые алгоритмы для задачи распределения потоков транспорта на основе сетей «многослойного персептрона» и Кохо-нена, с использованием алгоритмов обучения обратного распространения ошибки, Кохонена и Хебба, составляют основу для программной реализации соответствующего компонента информационной системы для распределения потоков транспорта и моделирующего стенда для: проведения экспериментальных исследований;

5. Разработанное программное обеспечение и методика исследования работоспособности и эффективности предложенных методов и алгоритмов позволили получить результаты модельного эксперимента, которые показали, что при использовании нейросетевых алгоритмов количество транспорта перед светофором уменьшилось в среднем на 10-15% по сравнению с традиционным методом, при этом при увеличении количества дорог на перекрестке эффективность нейросетевых методов относительно традиционного метода уменьшилось на 1-2% при расширении перекрестка на одну дорогу.

Публикации

1. Юсупова Н.И., Бажин Д.Н., Григорьев Д.А., Шаймарданова СИ. Нейросетевой инструментарий для распределения потоков транспорта на перекрестках произвольной конфигурации // «Нейрокомпьютеры и их применение»: Труды VIII Всероссийской конференции (НКП-2002). Статья на CD-ROM

2. Юсупова Н.И., Бажин Д.Н., Григорьев Д.А., Шаймарданова СИ. Нейросетевой инструментарий для распределения потоков транспорта на перекрестках произвольной конфигурации // «Нейрокомпьютеры и их применение»: Труды VIII Всероссийской конференции (НКП-2002). Материалы научной конференции. - М.: Век книги, 2002. - с.67.

3. Yussupova N.I., Grigoriev D.A., Shaimardanova S.I., Balyklov T.S. Neural Network Simulation and Software for Traffic Flow Control at Crossroads of Arbitrary Configuration // Proceedings of the Workshop on Computer Science and Information Technologies (CSIT'2002) / Information Scientific Issue, Patras, Greece, 2002. Статья на CD-ROM

4. Григорьев Д.А., Бажин Д.Н., Шаймарданова СИ., Балыклов Т.С О программной реализации нейросетевого подхода к распределению потоков транспорта на перекрестках произвольной конфигурации // Материалы научной студенческой конференции. - Уфа: УГАТУ, 2002 - с. 24-26.

5. Григорьев Д.А., Шаймарданова СИ., Балыклов Т.С Свидетельство об официальной регистрации программы для ЭВМ «Нейросетевая система-управления потоками транспорта на перекрестках произвольной конфигурации» №2002611009 от 20.06.2002г. Роспатент, Москва, 2002.

6. Григорьев Д.А., Шаймарданова СИ., Балыклов Т.С. Построение UML диаграмм для задачи распределения потоков транспорта на перекрестках произвольной конфигурации // Принятие решений в условиях неопределенности: Межвуз. науч. сб. - Уфа: УГАТУ, 2003, с.31-36

7. Yussupova N.I., Bajin D.N., Grigoriev D.A., Shaimardanova S.I. UML Diagrams for Traffic Flow Control at Crossroads of Arbitrary Configuration // Proceeding of the Workshop on Computer Science and Information Technologies (CSIT'2003) / Information Scientific Issue, Ufa, Russia, 2003. P. 205-208

Григорьев Денис Алексеевич

ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ДЛЯ НЕЙРОСЕТЕВОГО МОДЕЛИРОВАНИЯ И УПРАВЛЕНИЯ ТРАНСПОРТНЫМИ ПОТОКАМИ НА ПЕРЕКРЕСТКАХ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных систем, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 19.05.04. Формат 60х 84 1/16 Бумага офсетная. Печать плоская. Гарнитура Таймс. Усл. печ. л. 1,0. Усл. кр.-отт. 1,0. Уч-изд.л. 0,9 Тираж 100 экз. Заказ № 337

Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа - центр, ул. К.Маркса, 12

143 924

Введение

Глава 1. Анализ предметной области

1.1 Анализ ситуации на перекрестках и методов распределения 9 потоков транспорта

1.2 Анализ классических подходов к распределению потоков 12 транспорта

1.2.1 Метод распределения потоков транспорта на основе 13 , f транспортной задачи

1.2.2 Метод распределения потоков транспорта на основе 14 дифференциальных уравнений

1.2.3 Методы систем массового обслуживания

1.3 Анализ подходов к распределению потоков транспорта на основе 19 искусственного интеллекта

1.3.1 Подход с применением алгоритмов нечеткой логики

1.3.2 Подход с применением нейронных сетей

1.4 Цели и задачи исследования

1.5 Выводы 25 ^

Глава 2. Разработка подхода к построению информационной системы для моделирования потоков транспорта на перекрестке

2.1 Разработка требований к системе

2.2 Разработка структуры системы

2.3 Выбор и обоснование вычислительной сети для распределяемой 36 информационной системы

2.4 Выводы

Глава 3. Моделирование распределения потоков транспорта на основе 46 структурного и объектно-ориентированного анализа

3.1 Выбор методологии моделирования

3.2 Построение моделей информационной системы с помощью 48 структурного анализа

3.3 Построение моделей для моделирующего стенда распределения 51 потоков транспорта с помощью объектно-ориентированного анализа

3.4 Выводы

Глава 4. Разработка нейросетевых моделей

4.1 Анализ возможностей нейросетевых моделей и методов обучения

4.2 Анализ выбранных для исследования нейронных сетей и методов 64 их реализации 4.2.1 Многослойный персептрон и метод обратного 64 ч распространения ошибки

4.2.2 Алгоритмы обучения Хебба и Кохонена

4.3 Разработка правил выбора

4.4 Выводы

Глава 5. Анализ эффективности предлагаемого подхода

5.1 Методика исследования эффективности

5.2 Разработка программного обеспечения для моделирующего стенда 79 5.2.1 Разработка структуры моделирующего стенда

Jr^ 5.2.2 Метрическая оценка качества

5.2.3 Тестирование программного продукта

5.3 Анализ результатов экспериментальных исследований

5.4 Выводы 99 Заключение 101 Список литературы 103 Приложение!

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

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

В настоящее время накоплен большой опыт применения: интеллектуальных методов для различных прикладных проблем! как у нас в стране (Васильев В.И., Галушкин А.И., Горбань А.И., Ильясов Б.Г., Куликов? Г.Г., Миронов В.В., Поспелов Д.А., Юсупова Н.И. и др.), так и за рубежом (Lotfi A. Zadeh, Anil К. Jain, Narendra К.Р. и др.). Выглядит перспективным применение таких методов к задаче распределения потоков транспорта.

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

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

Для достижения поставленной цели в работе сформулированы и решены следующие задачи:

1. Разработка подхода к моделированию процессов распределения ' потоков транспорта для сети взаимосвязанных перекрестков на основе нейронной сети;

2. Разработка моделей для информационной системы распределения потоков транспорта для произвольного перекрестка и моделирующего стенда с использованием структурного и объектно-ориентированного анализа;

3. Разработка алгоритмов распределения потоков транспорта на основе нейросетевого подхода для сети взаимосвязанных перекрестков;

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

Методика^ исследования. В работе применяются методы системного анализа, системного моделирования, CASE-технологии, нейросетевые методы, методы компьютерного моделирования и анализа данных.

На защиту выносятся

1. Подход к моделированию процессов распределения потоков транспорта для сети взаимосвязанных перекрестков на основе нейронной сети;

2. Модели для информационной системы и моделирующего стенда распределения потоков транспорта для произвольного/ перекрестка с. использованием CASE-технологий;

3; Алгоритмы; распределения г потоков транспорта длят сети; взаимосвязанных перекрестков для: различных типов; нейронных сетей? и алгоритмов обучения;

4. Результаты исследованиям эффективности предложенных методов распределения потоков; транспорта на основе; разработанных инструментальных средств.

Научная новизна

1. Предложен новый' подход к распределению (потоков транспорта; на основе; нейронной; сети, позволяющий повысить пропускную способность перекрестков;

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

3". Впервые разработаны модели для реализации моделирующего стенда с целью исследования методики распределения; потоков; транспорта для; произвольного перекрестка на основе нейронной сети;

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

Практическая значимость.

В результате выполнения > диссертационной ii работы > автором получены следующие результаты:

1L Разработаны инструментальные средства, позволяющие реализовать методику распределения потоков транспорта; на перекрестках произвольной конфигурации;

2. Разработано программное обеспечение, реализующее методику распределения? потоков; транспорта; в условиях перекрестка произвольной конфигурации» на основе нейронной сети «многослойного персептрона» и алгоритма обучения «обратного распространения ошибки», нейронной сети Кохонена и; алгоритмов обучения Кохонена и» Хэбба. Разработаное программное обеспечение зарегистрировано в Реестре программ для ЭВМ; (свидетельство о регистрации №2002611009 от 20.06.2002г);

3. Проведены модельные эксперименты, которые показали, что применение нейронных сетей к распределению потоков транспорта на перекрестках является более эффективным по ? сравнению / с традиционным методом и позволяет уменьшить количество транспорта перед светофором на 10-15%.

Работа велась в рамках научной работы по хоздоговорной научно-исследовательской- теме "Исследование проблем развития^ управления, (, контроля и моделирования; в сложных системах!' № ИФ-ТК-14-03-03/6.

Работа частично, поддержана; грантом РФФИ 03-07-90242 "Интернет-комплекс поддержки выполнения проектов фундаментальных исследований сложных систем? с применением х интеллектуальных технологий Has базе экспертных систем!' (2003 - 2005 гг.) ^федеральной целевой программой > "Интеграция науки и высшего образования Российской Федерации на 2002 -2006 годы!', проект П0039 "Фундаментальные исследованиям и новые, технологии проектирования сложных технических систем!'.

Результаты внедрены в учебный процесс УГАТУ по? изучению нейронных сетей; и; используются в материалах лекций, практических и ^ лабораторных работ дисциплин >. «Нейрокомпьютерные системы», «Системы искусственного интеллекта», «Теоретические основы информационных процессов» для; студентов; специальностей 351500- «Математическое обеспечение и администрирование информационных систем», 220400 «Программное обеспечение вычислительной техники и автоматизированных систем», а также магистрантов направления 552800? «Информатика и; вычислительная техника», обучающихся по программе 552819 «Компьютерный анализ и интерпретация данных». ч ■

Результаты внедрены в учебный процесс БАГСУ и используются В: материалах лекций и лабораторных работ дисциплин; «Разработка управленческих решений», «Информационные технологии в управлении»,

Основы системного анализа» по специальностям 061000 «Государственное и муниципальной управление», 061100 «Менеджмент организации».

Апробация работы. Основные положения, представленные в диссертационной работе, докладывались и обсуждались на различных конференциях, в частности на VIII Всероссийской конференции с международным участием «Нейрокомпьютеры и их применение» (Москва, 2002), на 10-ом Всероссийском студенческом семинаре «Проблемы управления» (Москва, 2002), на юбилейной студенческой научно-теоретической конференции (Уфа, 2002), на международных конференциях «Computer Science and Information Technologies» (CSIT) (Патрас, Греция, 2002; Уфа, 2003).

Результаты работы отражены в 6 публикациях, 3 приняты к публикации в различных изданиях.

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

5.4 Выводы

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

Разработана структура» моделирующего стенда для исследования! эффективности * предложенных методов * распределения ? потоков ?■ транспорта. Обоснован выбор языка* программирования. Осуществлена метрическая оценка качества разработанной; программы; в результате которой' было выявлено, что для улучшения качества программы необходимо разбить, отдельные модули на более мелкие: Произведено- тестирования; программного продукта. На все тестирующие данные программа реагировала корректно.

Произведено исследование эффективности распределения потоков транспорта в условиях перекрестков различных конфигураций для различных типов нейронных сетей. При сравнении распределения потока транспорта для трех типов перекрестков и при одинаковых исходных данных, но разных алгоритмов обучения были получены следующие результаты: все нейросетевые алгоритмы показали достаточную эффективность по сравнению с традиционным методом - примерно 10-15%, при увеличении количества дорог на перекрестке эффективность нейросетевых методов относительно традиционного метода уменьшилось незначительно и примерно одинаково для всех видов алгоритмов - порядка 1-2% при расширении перекрестка на одну дорогу (Алгоритм обратного распространения для 3 дорог — 16,3%, для 4 — 15,7%, для 5 — 14,0%, Алгоритм Хебба для 3 дорог - 13,6%, для 4 - 11-1%, для 5 -9,5%, Алгоритм Кохонена для 3 дорог -9,8%, для 4 -8,3%, для 5 -6,2%). Исследование показало, что наиболее эффективным нейросетевым алгоритмом является алгоритм обратного распространения ошибки, по сравнению с алгоритмами Хебба и Кохонена, однако алгоритм обратного распространения ошибки имеет намного меньшую скорость обучения нейронных сетей, чем алгоритмы Кохонена и Хэбба.

Заключение

В диссертационной работе предложен и разработан подход к распределения потоков; транспорта' на перекрестках произвольной конфигурации на основе нейронных сетей; Выполненные исследования? и; разработки позволили получить следующие выводы:

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

2. разработанные модели информационной системы для распределения потоков транспорта на основе нейронной сети с использованием. CASE-средств методологии; структурного анализа позволяют автоматизировать процесс; разработки ПО и проектирования базы; данных информационной системы;

3: разработаные диаграммы деятельности, основных классов и модулей распределения потоков транспорта;; с использованием нейросетевого подхода на основе методологии» объектно-ориентированного анализа позволяют разработать компоненты программного обеспечения моделирующего стенда;

4. разработанные нейросетевые алгоритмы для задачи распределения-потоков транспорта на основе сетей «многослойного персептрона» и Кохонена, с использованием; алгоритмов обучения обратного распространения ошибки, Кохонена и Хебба, составляют основу для программной реализации соответствующего компонента информационной; системы для распределения потоков транспорта и моделирующего стенда для проведения экспериментальных исследований;

5. разработанное программное обеспечение и методика исследования работоспособности и эффективности предложенных методов и; алгоритмов позволили; получить результаты модельного эксперимента, которые показали, что при использовании нейросетевых алгоритмов количество транспорта перед светофором уменьшилось 10-15% по сравнению с традиционным методом, при этом при увеличении количества дорог на перекрестке эффективность нейросетевых методов относительно традиционного метода уменьшилось на 1-2% при расширении перекрестка на одну дорогу. Наиболее эффективным нейросетевым алгоритмом является алгоритм обратного распространения ошибки, по сравнению с алгоритмами Хебба и Кохонена, но алгоритм обратного распространения ошибки имеет намного меньшую скорость обучения нейронных сетей, чем алгоритмы Кохонена и Хэбба.

103

1. Алгоритмы обучения http://archer.newmail.ru/contents/neuro/teach.htrnl

2. Андрейчиков А.В., Андрейчикова О.Н. Интеллектуальные информационные системы М.: Финансы и статистика, 2003. 368с.

3. Бажин Д.Н. Об одном подходе к управлению дорожным движением на основе нечеткой логики // Математическое моделирование в решении научных и технических задач. Вып.2. Уфа, Издательство «Технология», 2001. - С.80-84

4. Бройдо В. Вычислительные системы, сети и телекоммуникации. Издательство "Питер", 2002 г. 688 стр.

5. Буч Г., Рамбо Дж., Якобсон А. Язык UML руководство пользователя. Издательство "Питер", 2003 г. 432 стр.

6. Васильев В.И., Ильясов Б.Г. Интеллектуальные системы управления с использованием нечеткой логики: Учеб. пособие. Уфа: УГАТУ, 1995 - 80с.

7. Васильева Е.М. Нелинейные транспортные задачи на сетях. М.: Финансы и Статистика, 1981.

8. Галушкин А.И; Теория нейронных сетей. КнЛ: Учеб. пособие для вузов / Общая ред. А.И.Галушкина. М.: ИПРЖ, 2000

9. Горбань А.Н. Обучение нейронных сетей. М.: СП ПараГраф, 1990

10. Горбань А.Н., Россиев Д.А. Нейронные сети на персональном компьютере. Новосибирск: Наука. Сиб. изд. фирма РАН, 1996

11. Григорьев Д.А., Бажин Д.Н., Шаймарданова С.И., Балыклов Т.С. О программной реализации нейросетевого подхода к распределению потоковтранспорта на перекрестках произвольной конфигурации // Материалы научной студенческой конференции. УГАТУ, 2002.

12. Гусева А.И. Работа в локальных сетях NetWare 3.12-4.1.- Учебник. -М.:Диалог МИФИ, 1996 г.

13. Дуглас Б. Ленат. Искусственный интеллект, http://www.hamovniki.net/ ~alchemist/NN/ii/ii9.htm

14. Джон Д.Рули, Дэвид Мэсвин, Томас Хендерсон, Мартин Хеллер. Сети Windows NT 4.0. BHV - Киев, 1997 г.

15. Жуков А.В: Изучаем Delphi. СПб: Издательский дом «Питер», 2001г. -352с.

16. Иванов В.Б. Компьютерные коммуникации. Учебный курс. Питер, 2002-224с.

17. Ильясов БЛ7. Управление динамическими системами в условиях неопределенности. Под ред. С.Т.Кусимова. Уфа: УГАТУ, 1998 -426с.

18. Интеллектуальные системы управления с использованием нейронных сетей: Учебное пособие. /В.И.Васильев, Б.Г.Ильясов, С.С.Валеев, С.В.Жернаков. Уфа: УГАТУ, 1997-92с.

19. Канер С., Фолк Д., Нгуен Е.К. Тестирование программного обеспечения. М:: ДиаСофт, 2000. 544с.

20. Карл И. Вигерс Разработка требований к программному обеспечению. Русская Редакция, 2004. — 576с.

21. Карпов Б.И., Карпов Б.И. Delphi: Специальный; справочник. СПб: Издательский дом «Питер», 2001. 688с.25; Комашинский В., Смирнов Д. Нейронные сети и их применение в системах управления и связи. Горячая Линия — Телеком, 2002; 94с.

22. Компания» «Нейропроект», нейросетевая динамическая библиотека. http://www.neuroproiect.ru/nwindows.htm;

23. Короткий С. Нейронные сети: алгоритм обратного распространения

24. Мартин Фаулер, Кендалл Скотт UML. Основы. Краткое руководство по унифицированному языку моделирования: Мартин: Фаулер: и Кендалл Скотт. Издательство Символ Плюс. 2002. - 192с.

25. Нейронные сети. http://www.neuroproiect.rU/neuro.htm#whatneuro38. Нейронные сетиhttp://support.vologda.ru/Book/SCIENGE/BOOKl /context.htm

26. Нейросетевые методы обработки информации и средства их программно-аппаратной поддержки.http://\^дvw.hamovniki.net/~alchemist/NN/DATA/nnl 6.htm.

27. Орлов С. Технологии разработки программного обеспечения. 2-е изд. Издательство "Питер", 2003 г. 480 стр.

28. Поляк-Брагинский А. Сеть своими руками. Самоучитель. Издательство: BHV. 2002г. 320 стр:

29. Правила дорожного движения Российской Федерации. 43 • Приложения сетевых технологий http://alice.stup.ac.ru/~dvn/complex/applic.htm

30. Пятибратов А.П. Вычислительные системы, сети; и телекоммуникации. Финансы и статистика, 2001. 400с.,

31. Сравнительный > анализ алгоритмов обучения нейронных сетей. http://www.91. in/Education/Books/NeuralNet/NeuralTeory/compare2.htm;

32. Стандарт СММ путь к качеству ПО http://www.ivn.newmail.ru/CMM.html

33. Стандарты моделирования IDEF и ABC http://citforum.muravlenko.ru/cfin/idef/

34. Теория построения; Нейрокомпьютерных сетей http.7/infocitv.kiev.ua/prog/other/content/progother029.phtml?id=1441

35. Терехов В. А. Динамические алгоритмы обучения многослойных нейронных сетей в системах управления.//Теория и системы управления. М.: Наука, 1996. №3. - С. 70-79.

36. Технологии! оценки качества программных продуктов http://vvvvw.rol .ru/ne ws/i t/press/c wm/2 596/teh.htm

37. Трофимов С. A. CASE-технологии. Практическая работа в Rational Rose. Бином-Пресс, 2002 288с.

38. Тютерев В.В. Определение эффективного* размера нейронной! сети в процессе обучения методом динамического наращивания узлов.55; Уэйн Дж. Линейные и нелинейные волны. М.: 1979.

39. Федотова Д.Э., Семенов! Ю.Д., Чижик К.Н. CASE-технологии: Практикум. "Горячая линия-Телеком, Радио и связь", 20031 160с.

40. Фигурнов В.Э; IBM!PC для пользователя!краткийгкурс. М. Инфра М, 1998 г.

41. Хант К. Серия «Для- специалиста»: Персональные компьютеры в сетях TCP/IP. BHV - Киев, 1997 г.

42. Черемных С.В:, Семенов; И.О., Ручкиш В1С. Моделирование» ш анализ систем. IDEF-технологии: практикум. М.: Финансы, и статистика, 20021 192 с.

43. Черемных С.В., Семенов И.О., Ручкин B.C. Структурный анализ систем: IDEF-технологии. Ml: Финансы и статистика, 2001. 208 с.

44. Экстремальное тестирование:http ://www.xprogrammin g.ru/ Artie 1 es/ExtremeTesting.html

45. Юсупова Н.И., Бажин Д.Н. Нейросетевые методы управления движением транспорта на перекрестках // Вестник УГАТУ 2002. Т.З, №1- УГАТУ, 2002. с. 126-134

46. Язык UML. руководство пользователя http://citforum.ai.kharkov.corn/book/urnlbooch/umlboochc.shtml

47. Язык UML. http://programming.com.ua/doc/11/

48. Якубайтис Э.А. "Информационные сети г и системы". Справочная книга. М.: Финансы и статистика, 2002. 192с.

49. Якушев; Д.Ж. Нейронные сети в задачах управления движением. Зарубежная радиоэлектроника, №1, 1999г. С.58-64.

50. Visual: С++ 6.0 в составе Microsoft Visual; Studio http://cpp.hotmail.ru/artic1es/vc03 05.html

51. Bazhin D.N., Shakhmametova G.R. Using a.Neural Network for Traffic Flow Control // Proceeding of the 3rd International Workshop on Computer Science and Information Technologies. Ufa, Russia, Sept.21-26 2001;

52. Classic Testing Mistakes http://www.testing.com/writings/classic/mistakes.pdf

53. Delphi 5 Component's Guide. Inprise Corporation, 1999

54. Delphi 5 Developer's Guide. Inprise Corporation, 1999

55. Findler N.V., Surender S., Ziya Ma. Catrava, Distributed Intelligent Control of Street and Highway Ramp Traffic Signals, Elsevier Science, 1997.

56. Gilmore J., Abe N. A Neural Networks System for Traffic Congestion Forecasting.

57. Goldstonet J.S., Myers C.E. Traffic Monitoring with Wisard and Probabilistic Logic Nodes. Elsevier Science, 1991r.

58. Montana D.J. and Davis L. Training feedforward neural networks using genetic algorithms. Preprint, BBN Systems and Technologies, Cambridge, Mass., 1989.

59. Neural Innovation, http://www.neural.co.uk/

60. Neural Network FAQ. ftp://flp.sas.com/pub/neural/FAQ.html• 84. Syal M.Y., Fathy M., Dorry F. Neural-Vision Based Approach for Real-Time Road Traffic Applications. EL, 1997, No.ll.

61. Testing Component-Based Softwarehttp://www.stickvminds.com/docs index/XDD2044filelistfilenamel .doc

62. Ulbricht C. Multi-Recurrent Networks for Traffic Forecasting, Neural Networks, 1996.

63. Wynne-Jones M. Node splitting: A constructive algorithm for feed-forward; neural networks // Neural Computing and Applications, v.l , No. 1, 1993, p. 17-22.