Инструментальные средства для нейросетевого моделирования и управления транспортными потоками на перекрестках тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Григорьев, Денис Алексеевич

• Григорьев, Денис Алексеевич
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Григорьев, Денис Алексеевич

Введение

Глава 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

Список литературы диссертационного исследования кандидат технических наук Григорьев, Денис Алексеевич, 2004 год

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.