Содержание к диссертации
Введение
Глава 1. Обзор существующих подходов в области постановки и методов решения задач упорядочения потоков 14
1.1. Характеристика задач построения расписаний 14
1.2. Постановка задачи упорядочения транспортных потоков 18
1.3. Анализ основных приемов решения задач построения расписаний 21
1.4. Нейросетевые и генетические алгоритмы, гибридные методы 32
Выводы по главе 1 42
Глава 2. Представление задачи упорядочения потоков в категориях искусственных нейронных сетей 44
2.1. Характеристика задач упорядочения транспортных потоков на железнодорожных линиях 44
2.2. Описание основных элементов графика движения поездов и ограничений в терминах нейронных сетей 48
2.3. Способы задания целевых функций графика движения поездов на языке нейронных сетей 51
Выводы по главе 2 53
Глава 3. Разработка гоижгипиальной архитектуры нейронных сетей, алгоритмов обучения для решения задач упорядочения транспортных потоков 54
3.1. Синтез ключевых архитектур и их исследование 54
3.2. Проектирование и настройка комплекса моделей и архитектуры нейронной сети для работы с двухпутной железнодорожной линией 60
3.3. Проектирование и настройка комплекса моделей и архитектуры нейронной сети для работы с однопутной железнодорожной линией 71
Выводы по главе 3 81
Глава 4. Исследование корректности ИНС, проектирование комплекса программ и его применение для расчета графиков движения поездов 83
4.1. Разработка программы испытаний ИНС для двухпутного участка железнодорожной линии 83
4.2. Разработка программы испытаний ИНС для однопутного участка железнодорожной линии 94
4.3. Оценка поведения многослойных искусственных нейронных сетей с переменной проводимостью сигнала 98
4.4. Проектирование системной архитектуры сети 105
4.5. Разработка интерфейса нейронной сети 110
4.6. Применение нейронной сети для построения и доработки существующего графика 114
Выводы по главе 4 120
Заключение 122
список литературы 126
Приложение 1 140
- Анализ основных приемов решения задач построения расписаний
- Характеристика задач упорядочения транспортных потоков на железнодорожных линиях
- Проектирование и настройка комплекса моделей и архитектуры нейронной сети для работы с двухпутной железнодорожной линией
- Разработка программы испытаний ИНС для двухпутного участка железнодорожной линии
Введение к работе
Актуальность темы. В любой транспортной системе, в том числе на железнодорожном транспорте, принципиально важным является построение эффективного адаптивного расписания (графика движения) для регулирования транспортных потоков.
С математической точки зрения задачу составления графика движения поездов можно рассматривать как задачу составления расписания высокой размерности. Задача усложняется топологической сложностью сети железных дорог, большим числом изменяемых параметров, связанных с эксплуатацией этой сети (многопутность, конфигурация магистральных и станционных путей сообщения, различный характер тяги, определяющий в свою очередь, временные интервалы между поездами одного направления).
Традиционные способы решения этой задачи (последовательный способ с использованием жесткой нормативно-справочной информации; способ по-ниточной прокладки) часто базируются на неэффективных приемах, алгоритмы на их основе опираются на неадаптивные решения, требуют значительных затрат вычислительного времени и постоянной корректировки решений при изменении условий, а также не учитывают неформальные факторы.
До настоящего времени задача построения адаптивного расписания с позиции эффективного использования мощностей инфраструктуры не реализована. Для конкретных случаев построения расписания на заданном участке все алгоритмы сводятся к перебору всех возможных случаев с вкраплениями оптимизаций типа отбрасывания ветви неправильных решений (Р. Кормен, Ч. И. Лейзерсон). Проблема заключается и в том, что большая часть задач построения графика является TVP-трудной, т.е. алгоритмы их решения, используемые для автоматизации процесса, могут требовать неприемлемо большого времени выполнения (В. С. Танаев, В. В. Шкурба, Д. И. Бати-щев).
В то же время известна способность искусственных нейронных сетей к самообучению и решению слабоформализованных задач, что может быть использовано для нейросетевого моделирования и решения задач теории расписаний.
Задачи составления расписаний на основе использования аппарата искусственных нейронных сетей для статических процессов с равной длительностью любого процесса исследовались в работах R. Chen, В. А. Костенко, А. В. Назарова, А. И. Лоскутова, Дж. Хопфилда, Б. М. Калмыкова и др.
Основными проблемами полученных авторами решений являются как невозможность установить соответствие между содержательными аспектами задачи расписания и параметрами функции энергии нейронной сети, так и вопрос вычисления коэффициентов уравнения данной функции.
Данные решения являются многоступенчатыми: для получения базисного решения используется один из эвристических алгоритмов, далее такое
решение подается на вход искусственной нейронной сети Хопфилда, результат работы которой вновь подвергается обработке алгоритмами локальной оптимизации.
Сеть Хопфилда применяется в задачах построения расписаний лишь для тех случаев, когда важно только конечное распределение ресурсов (доступен / не доступен). Данный метод не может применяться тогда, когда важно, каким образом менялось состояние этих ресурсов, а также в том случае, если состояние ресурса в выбранный момент времени должно быть эквивалентно состоянию предшествующего ресурса в прошедший момент времени и если данные последовательности требуется не только запоминать, но и смещать в пространстве «время - расстояние».
Известно, что решения, основанные на использовании искусственных нейронных сетей, часто оказываются субоптимальными, а по соотношению затраченных времени и вычислительной мощности относительно качества полученных решений значительно выигрывают у строгих классических постановок. Процесс построения графика движения традиционными методами требует значительных итерационных перестроений и согласований промежуточных результатов между участками, что требует многократной перестройки графика в процессе его разработки. В отличие от существующих решений, использование нейросетевого подхода позволит создавать график единовременно в процессе расчета, что сократит затраты времени и труда на его разработку. Именно это обусловило выбор данного подхода при написании настоящего исследования.
Объектом исследования являются транспортные потоки на железнодорожных линиях.
Предметом исследования выступает упорядочение потоков с помощью нейросетевого моделирования.
Работа по своей цели и задачам соответствует приоритетам научно-технологического развития РФ в редакции п. 20 пп. «а» Указа Президента РФ от 01.12.2016 № 642 «О стратегии научно-технологического развития Российской Федерации»: «переход к передовым цифровым, интеллектуальным производственным технологиям, роботизированным системам, новым материалам и способам конструирования, создание систем обработки больших объемов данных, машинного обучения и искусственного интеллекта».
Целью работы является разработка нейросетевой модели, алгоритмов обучения специальных искусственных нейронных сетей (ИНС), а также создание комплекса программ на их основе для упорядочения транспортных потоков во времени на заданной железнодорожной инфраструктуре.
В соответствии со сформулированной целью решены следующие основные задачи диссертации:
-
исследование существующих подходов и анализ основных результатов в области постановки и методов решения задач упорядочения транспортных потоков;
-
разработка нейросетевой модели для решения задачи построения расписания транспортных потоков;
-
проведение нейросетевого моделирования процесса упорядочения транспортных потоков (на примере графика движения поездов);
-
разработка численных алгоритмов расчета выходных сигналов сети и ее обучения в процессе построения расписания, а также способа применения ИНС для упорядочения транспортных потоков;
-
разработка комплекса программ на основе специализированной архитектуры ИНС для решения задач упорядочения транспортных потоков с последующей апробацией на тестовом участке.
Методы исследования. При выполнении исследования использовались: теория и методы системного анализа, математическое моделирование, методы и приемы построения искусственных нейронных сетей, методика планирования частичного факторного эксперимента, объектно ориентированное программирование. Для построения комплекса программ использовался объектно ориентированный язык С#, для обработки сигналов нейронных сетей - язык программирования R.
Научная новизна работы заключается в следующем:
-
Разработана нейросетевая модель, в основе которой лежит топология многослойной ИНС с переменной проводимостью сигнала. Ее особенности заключаются в представлении пункта маршрута в расписании как слоя сети, временной шкалы как ряда нейронов в слое, в наличии двух комплектов весов, связей между нейронами как внутри самого слоя, так и с соседними слоями.
-
Разработан алгоритм расчета выходных сигналов многослойной ИНС с переменной проводимостью сигнала для упорядочения транспортных потоков на основе прохождения сигналов внутри ИНС, реализующий специальные виды функции ошибки, учитывающие особенности графиков движения поездов на линиях железных дорог.
-
Разработано семейство алгоритмов обучения ИНС для упорядочения транспортных потоков. В отличие от существующих способов обучения, данные алгоритмы базируются на мягкой конкуренции нейронов, выборе решающей связи и различной скорости и направления изменения весов в зависимости от положения данной связи, а также предусматривают введение переменной скорости обучения, ограниченной сверху.
-
Разработан способ упорядочения транспортных потоков, заключающийся в функционировании двух независимых многослойных нейронных сетей и отличающийся от известных постепенным шаговым изменением параметров, нормирующих график движения поездов.
-
Разработан комплекс программ, реализующий нейросетевую модель упорядочения потоков и алгоритмы обучения нейронных сетей. В отличие от известных программных продуктов для упорядочения транспортных потоков, вариант расписания получается в процессе обучения ИНС для всего рассматриваемого направления (полигона) в целом.
Практическая значимость работы. Работа предлагает способ построения расписания с использованием ИНС, включающий в себя специализированные алгоритмы обучения, учитывающие специфику эксплуатации железных дорог как на двухпутных, так и на однопутных линиях. Разработан и внедрен комплекс программ, который применяется на промышленном и магистральном железнодорожном транспорте для построения графика движения поездов с возможностью разрешения конфликтов. Время разработки одного графика инженером сокращается в среднем на 28 %.
Получен один патент и одно свидетельство о регистрации программного продукта.
Соответствие паспорту научной специальности. Область исследования соответствует паспорту специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ» по пунктам 2, 3, 4, 5, 8: построена модель прохождения сигналов внутри специализированной ИНС, разработаны способы расчета расписания с помощью специализированной ИНС, математическая модель функционирования такой сети, численные алгоритмы обучения для разных задач построения расписаний, способ раздельного построения графика движения, проведены комплексные исследования процесса построения расписания с помощью ИНС и разработан комплекс программ.
На защиту выносятся:
-
Нейросетевая модель, в основе которой лежит использование многослойной ИНС с переменной проводимостью сигнала; результаты ее применения для решения задачи построения расписания для двухпутных и однопутных линий.
-
Алгоритмы вычисления выходных сигналов нейронной сети, расчета величины ошибки, алгоритмы обучения многослойной искусственной нейронной сети с переменной проводимостью сигнала (для различных сценариев).
-
Способ упорядочения транспортных потоков, заключающийся в функционировании двух независимых многослойных нейронных сетей и отличающийся от известных постепенным шаговым изменением параметров, нормирующих график движения поездов.
-
Комплекс программ для упорядочения транспортных потоков на основе разработанной нейронной сети.
Реализация работы и внедрение результатов. Разработан комплекс программ для построения графика движения поездов (свидетельство № 2017613361 от 16.03.2017 о государственной регистрации программы для ЭВМ).
Отдельные положения проведенного исследования внедрены в работу АО НИИАС, г. Москва, используются в учебном процессе ФГБОУ ВО СамГУПС при проведении лекционных и практических занятий по дисциплинам «Производственный менеджмент на железнодорожном транспорте»,
«Основы теории автоматического управления», «Транспортная логистика», а также на занятиях с магистрами по кафедре «Менеджмент и логистика на транспорте».
Апробация работы. Результаты диссертационного исследования были представлены и обсуждены на конференциях: Международной научно-практической конференции «Перспективные информационные технологии ПИТ» в (г. Самара, НИУ Самарский университет, 2015, 2016, 2017 гг.); X Юбилейной Международной научно-практической конференции «Современные информационные технологии и ИТ-образование» (г. Москва, ВМК МГУ, 21-22 ноября 2015 г.); Всероссийской научно-практической конференции «Современные подходы к управлению на транспорте и в логистике» (г. Москва, МГУПС, 10 февраля 2016 г.); Международной научно-практической конференции «Современные методы, принципы и системы автоматизации управления на транспорте» (г. Нижний Новгород, НФ МГУПС, 19-20 апреля 2016 г.); XVII и XVIII Международной научной конференции «Системы компьютерной математики и ее приложения» (г. Смоленск, СмолГУ, май 2016 г., май 2017 г.); X Международной научно-технической конференции молодых специалистов, аспирантов и студентов «Проблемы автоматизации и управления в технических системах» (г. Пенза, ПГУ, 15-18 мая 2016 г.); 3 Международной конференции по информационным технологиям и нанотехнологиям «ИТНТ-2017» (г. Самара, Самарский университет); XXXII Международной научно-технической конференции «Проблемы автоматизации и управления в технических системах - 2017» (г. Пенза, ПГУ, 6-8 июня 2017 г.).
Публикации. По результатам исследования подготовлено 26 публикаций, в том числе четыре в изданиях, рекомендованных ВАК РФ для публикации результатов научных исследований.
Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников и приложений. Материалы диссертации изложены на 144 страницах основного текста, содержат 35 иллюстраций, 5 таблиц, 2 приложения. Библиография включает 107 наименований.
В приложении приведены копии актов о внедрении, копия свидетельства о регистрации программного продукта, а также примеры полученных графиков движения.
Анализ основных приемов решения задач построения расписаний
Перейдем к анализу основных приемов и методов, которые применяются при решении задач составления расписания.
Эвристическими алгоритмами называют алгоритмы, основанные на правдоподобных, но не обоснованных математически предположениях о свойствах оптимального решения задачи [74].
Они отличаются тем, что на основе предположений экспертов о природе и свойствах решаемой задачи или оптимизируемого функционала выдвигается некоторая правдоподобная идея о форме решения и используется некоторая техника для ее реализации. Эти методы направлены на сокращение комбинаторных альтернатив возможных решений. Сидорин, Ликучева, Дворянкин [74] отмечают еще и такой самый важный недостаток эвристических приемов, как возможность недостижения глобального экстремума и остановки алгоритма в локальном минимуме при использовании некоторого критерия оптимальности.
Один из самых известных эвристических приемов - метод жадных стратегий, который рассматривают в классическом труде Кормен и Штайн [48]. Он заключается в выборе на каждом шаге локально оптимального выбора.
Он может быть использован для решения задачи составления расписания транспортных процессов, но его сложно использовать для многокритериальных задач составления расписания в силу невозможности учесть все взаимодействующие условия. Кроме того, строго доказать оптимальность решения, полученного с помощью такого подхода, невозможно. Этот алгоритм не ориентирован на учет изменяющихся особенностей работы линии.
Не считая предварительной сортировки, этот алгоритм требует 0(п) шагов. С учетом подготовки заявок сложность работы этого алгоритма составит Oinlogri).
Для некоторых задач этот способ может дать оптимальное решение, но для отдельных случаев ответ будет иметь сколь угодно большое отклонение от оптимума [48].
Другим подходом, требующим значительных вычислительных мощностей и учета значительного количества ограничений, является применение метода Монте-Карло к задачам составления расписаний, который позволяет получить серию приближенных решений, из которых необходимо выбрать наилучшее по пользовательским критериям [43]. Очевидно, что любое подтвержденное изменение в режиме работы железнодорожной линии приведет к необходимости изменения основных параметров алгоритма, таких как вид функции распределения случайной величины, дисперсии, математического ожидания и пр.
Необходимо отметить, что для получения оптимального решения требуется большое количество испытаний, и это увеличивает затраты на время, причем не гарантируется, что полученное решение будет близким к оптимальному.
Кроме вышеупомянутых, существуют методы динамического программирования, основанные на уравнении Беллмана [64]. При этом применяется последовательное конструирование расписания с использованием принципа оптимальности любой части расписания, когда оно оптимально в целом.
Таким образом, оптимальное расписание следует составлять, руководствуясь правилом (1.4), т.е. в порядке неубывания отношения длительности штрафа к штрафу за единицу времени ожидания. В случае равенства штрафов за ожидание расписание составляется по неубыванию значений Т{. Можно доказать, что при соблюдении такого правила будет минимальным среднее число заявок в системе и средняя длительность ожидания до начала реализации заявок [77].
Аналогично с применением уравнения Беллмана может быть получено решающее правило для расписаний для критерия нарушения директивных сроков. Для оптимизации последовательности решения задач минимальное и максимальное отклонения должны выполняться и для двух последних процессов. Если изменить порядок выполнения двух последних процессов, то общее значение функционала не станет меньше, так как полученный порядок является по построению оптимальным.
Если при одновременном поступлении всех заявок существует такое расписание, которое обеспечивает полное отсутствие нарушения директивных сроков, то по правилу (1.4) заявки могут быть упорядочены так, чтобы значение средней длительности ожидания до завершения обслуживания и получения результатов было минимальным. Отсюда следует, что последней реализуемой заявкой будет та, которая не нарушает директивного срока и характеризуется максимальной длительностью выполнения среди всех прочих заявок, выполнение которых в последнюю очередь не приводит к нарушению директивных сроков.
Построение оптимального расписания в этом случае можно производить рекуррентно, начиная с последней заявки. Из всех совокупностей заявок выбираются те, для которых директивные сроки превышают суммарную длительность выполнения всех процессов V7]. Из заявок, удовлетворяющих этому условию, отбирается одна с наибольшей длительностью использования и фиксируется на последнем месте. Затем рассчитывается общее время выполнения предпоследней заявки, с которым сравниваются директивные сроки оставшихся заявок, и повторяется выбор предпоследней заявки и т.д.
В общем случае, когда не существует расписания, при котором выполняются все директивные сроки либо заявки поступают неодновременно, необходимо применять эвристические или гибридные алгоритмы, а также методы статистического моделирования.
Рассмотрим также работу [53], в которой описывается задача Беллмана -Джонсона для конвейерных систем с переменным порядком работ. Предлагаемые допущения в большей степени соответствуют пропуску поездов по участку (единый порядок операций с работами), однако существует ряд отличий, связанных со спецификой работы на железной дороге. Если под работой подразумевать поезд, то в зависимости от категорий поездов существенно усложняется порядок его обработки на станциях (транзитный проход скорого поезда по станции отличается от работы с пригородным, грузовые поезда часть станций проходят без переработки), кроме того, на транспорте времена хода поездов в силу множества факторов могут быть сильно изменяющимися, что потребует дополнительных пересчетов, если действовать в рамках предлагаемой математической модели. Можно отметить, что для пассажирского движения сам принцип максимального быстродействия, ставящий цель минимизировать загрузку оборудования (сети дорог) при сложившихся требованиях к графику движения поездов, не является всегда выполнимым. Часто требуется обеспечить необходимое заданное время прибытия поездов, в этом случае применяется их замедление.
Кроме того, вызывает сомнения допущение о независимости подсистем, в которых происходит перестановка порядка работ. В рассматриваемом случае железнодорожная линия - это система, в которой существует зависимость между событиями.
Допущение автора [53] о том, что если порядок с перестановками работ имеет меньшие затраты времени, чем порядок без таковых, то новый порядок является оптимальным, справедливо и в случае железнодорожных графиков, так как одним из критериев разработки графиков является более высокая участковая скорость. Уравнение Беллмана является комплексным междисциплинарным научным приемом, часто применяемым в теории автоматического управления [7].
Сделаем еще одно замечание о взаимосвязи теории управления и задач расписания. Если наша система описывается такими уравнениями, при которых часть системы функционирует дискретно, а часть - непрерывно, то мы ищем управление обеими частями системы. Такими могут быть многозадачные процессы, в которых дискретная часть отвечает, например, за начало того или иного процесса в заданный момент времени, а непрерывная - за качество такого процесса. Нечто подобное можно увидеть в задаче организации движения, когда процесс движения описывается некоторым уравнением, например, как в [60], а момент отправления поездов выбирается в интервале 1440 минут (сутки).
Характеристика задач упорядочения транспортных потоков на железнодорожных линиях
В настоящем исследовании будет рассмотрено упорядочение транспортных потоков на заданном полигоне на примере движения поездов. Фактически задачей проектируемой нейронной сети будет являться построение графика движения поездов.
Для целей нейросетевого моделирования график движения лучше определить как систему событий и процессов между ними, выбранную и заданную на многомерном графе путей и станций, включая необходимые условия и ограничения на отношения между элементами графа и категорией процесса.
Он включает следующие элементы:
- точность графика (1 мин для общего графика, 0,5 мин для графика с наличием скоростных и высокоскоростных поездов);
- множество раздельных пунктов сети (N станций);
- набор данных о соединении пунктов сети - матрица N N, а также матрица корреспонденций всех поездов, необходимых в графике (также размерностью N N);
- топологию путей {RN} и набор к свойств каждого пути (длина, специализация работы, запреты на отдельные операции и пр.);
- моменты отправлений поездов {аа\44о) по всем раздельным пунктам;
- моменты прибытий поездов (b\y...,b\44o) по всем раздельным пунктам;
- путность соединений между станциями (матрица размерности N N), значения путности 1, 2, 3, 4;
- набор ограничений по прибытию и отправлению поездов (выраженный через условия допустимых неодновременных / одновременных прибытий и отправлений, попутных следований, с помощью задаваемых величин межпоездного интервала и пр.), который будет выписан отдельно и неоднократно рассматривался в существующей эксплуатационной литературе [12, 104];
- пропускная способность станций и перегонов, определяемая расчетом;
- емкости станций (их парков), в поездах;
- сведения о лимитирующих перегонах;
- информация о минимальных перегонных временах хода между раздельными пунктами.
Такое определение графика движения поездов является новым с позиций практики и теории управления эксплуатацией железных дорог [24].
Рассмотрим, каким образом перечисленные в определении аспекты будут влиять на специфику разработки ИНС.
1. Двухпутный участок
Двухпутный участок не предполагает конфликтов между встречными поездами на графике. Он характеризуется только позиционным расположением поездов во времени: использование пропускной способности зависит от величины межпоездного интервала. В этих условиях наиболее распространенный вид конфликта - возможность конкуренции двух попутных поездов за один и тот же путь станции. Времена стоянок поездов на двухпутных участках, как правило, определяются длительностью интервалов времени для различных операций или необходимостью провести обгон одного поезда другим.
Для расчета графика по каждой категории поездов или по каждому поезду времена стоянки могут считаться заданными или определяться нейронной сетью по заданным правилам в пределах некоторого интервала.
Двухпутный параллельный график движения поездов обеспечивает максимальное использование пропускной способности линии и наиболее прост для построения за счет полного отсутствия съема поездов одной категории другими.
Непараллельность графика может быть выражена через массив времен хода, отличающихся друг от друга по перегонам, или через искусственное сведение двухпутного участка к однопутному (в нейросетевом базисе), при котором конфликты разрешаются только на станциях.
2. Однопутный участок
В свою очередь, для однопутного участка пропускная способность определяется периодом графика - временем, которое затрачивается на прохождение одной пары встречных поездов по самому трудному для движения перегону. В случае ручной прокладки его построение начинается по ограничивающему перегону. Для нейронной сети, которая не оперирует пропускной способностью как входным параметром, а использует его как ориентир, необходимость учета ограничивающего перегона отсутствует. Одним из представляющих интерес подходов для однопутного участка становится такой, при котором движение поездов между перегонами осуществляется с максимально допустимой скоростью, а изменение порядка движения возможно за счет стоянок на станциях.
В отдельных случаях поезда одного направления пропускаются пакетами -группами ниток, следующими через одинаковый небольшой интервал времени. Необходимость пакетного пропуска возникает тогда, когда степень использования пропускной способности приближается к 100 %.
Требуется обеспечить возможность самоорганизации ИНС на однопутном участке, когда возникает вопрос выбора режима пропуска между пакетным режимом или режимом с измененными временами стоянок.
Многие интервалы, используемые для построения графика движения поездов, являются переменными величинами, но нормативными документами они задаются как постоянные [40]. Нейросетевой способ прокладки поездов не содержит четкого указания на величину межпоездного интервала, ограничиваясь лишь минимальным значением.
При построении графика существуют периоды суток, которые желательно использовать чаще или, наоборот, оставлять свободными. Эту особенность необходимо реализовать в нейронной сети.
Инфраструктурная емкость станций, которая используется для ручного построения графика движения поездов, представляет собой набор путей и стрелочных переводов, каждый из которых на некоторое время занимается поездом. Маршрут приема и отправления поезда со станции представляет собой сочетание путей.
Специфика метода нейросетевого моделирования такова, что при использовании ИНС необходимо применять как можно меньше условных переходов. Между тем именно проверка условий на свободность пути [46] часто используется в современном программном обеспечении, строящем графики движения (система AC «PlanGraph», «ГДП ИСУЖТ» и др.). Если каждый из элементов станционной инфраструктуры рассмотреть как некий «фиктивный» перегон с заданием соответствующих длин и времени «хода» по нему, то участок для построения графика просто расширяется за счет включения новых перегонов.
Топология парков (в сложных случаях) может быть выражена в виде таблиц смежности раздельных пунктов и введении переключателя для нейронной сети, который будет перенаправлять сигнал на тот или иной участок.
При построении графика движения поездов вручную используется, как правило, один набор нормативной информации. Любое изменение графиков движения поездов требует создания нового варианта. Это требует значительных ресурсов для хранения промежуточных вариантов. Желаемая нейросетевая конструкция должна адаптивно менять используемые нормативы в процессе совершения попыток построения графика. В связи с этим требуется обеспечить упорядочение транспортных потоков в процессе самообучения сети.
Проектирование и настройка комплекса моделей и архитектуры нейронной сети для работы с двухпутной железнодорожной линией
Для двухпутного железнодорожного участка, состоящего из нескольких перегонов с заданными временами хода поездов в четном и нечетном направлении, задан входной векторX = {xQ,xlt .,х1439}, состоящий из нулей и единиц, характеризующих моменты отправления поезда с заданных крайних станций участка. Задан желаемый вектор выхода данных поездов с конечной станции участка, в качестве которого принимается желаемое значение выхода нулевого слоя X искомой сети.
Указанные векторы задаются как для четного, так и для нечетного движения поездов. Требуется разработать архитектуру нейронной сети и алгоритм обучения данной сети, обеспечивающий построение расписания с суммарной ошибкой не более заданной величины.
Для работы с движением поездов в четном и нечетном направлении каждый слой нейронов имеет связи со слоями как в сторону возрастания номеров слоев, так и в сторону убывания. Ниже мы будем описывать прохождение сигнала в сети от слоя с наибольшим номером в сторону слоя с нулевым номером. Обучение же будет строиться в противоположном направлении - от нулевого слоя. Таким образом будет имитироваться прохождение сигнала в сети в направлении, противоположном движению поезда в реальном времени, о чем говорилось в п. 3.1.
Каждая строка представляет собой набор весов нейрона с фиксированным индексом. Номер столбца - номер нейрона предыдущего слоя, который связан с нейроном данного слоя.
Нейрон с номером j, как это было указано выше, связан со всеми нейронами предыдущего слоя. Принимая во внимание тот факт, что при перемещении поезда между двумя станциями должно соблюдаться минимальное время хода t, представляющее собой целое число и являющееся характеристикой железнодорожного перегона, начиная с нейрона с номером (/ 0 все веса вплоть до нейрона с номером 1439 принимают значение достаточно большого по модулю отрицательного числа (-U). Веса связей определяют уровень конкуренции между нейронами за право принять сигнал (поезд) на следующем слое (станции) в минуту, номер которой является номером столбца с положительным весом. Таким образом, передаваемый сигнал от одного слоя нейронной сети до другого не может нарушить правило минимального времени хода.
На участке области определения функции (0, +оо) функция активации (3.3) является дифференцируемой по аргументу. [83].
3. Выходным сигналом Y сети является вектор значений нейронов нулевого слоя Существует желаемый выходной вектор сети 7ц, который представляет собой последовательность нулей и единиц, смысл которой идентичен смыслу входного вектора X.
Введем свойство нейрона «номер поезда», который обозначим как г. Зададим следующее ограничение: на каждом слое сети только один нейрон может иметь номер г, т.е. все поезда проходят по каждой станции ровно в одной точке-минуте. По номерам поездов производится отслеживание прохождения поездов по всем станциям. Значения номеров поездов присваиваются на основании задания на разработку графика и действующей классификации поездов [41].
Расчет сети приведен на укрупненной блок-схеме (рисунок 3.2), на которой отражены все этапы работы ИНС.
Для обработки такого рода конфликта создается объект класса TrainCrossing, который описывается следующими нейронами: SlowTrainDepNeuron нейрон, из которого выходит медленный поезд и CrossedNeuron самый правый нейрон предыдущего слоя, поезд которого пересекает медленный поезд. Указанный объект получается по следующему алгоритму: каждому нейрону первого слоя, который характеризуется прибытием поезда, сопоставляется нейрон второго слоя, из которого этот поезд отправился.
Далее мы перебираем все нейроны второго слоя, из которых отправляется поезд, начиная нейрона с номером SlowTrainDepNeuron и заканчивая номером соответствующего нейрона прибытия того же поезда. В случае возникновения конфликта мы запоминаем получившуюся пару поездов. Она будет использована при обучении нейронной сети.
Обучение сети происходит согласно алгоритму, представленному на рисунке 3.4, где countLayers - число слоев сети; countMinutes - число минут в рассматриваемом периоде; trainspeed - текущая скорость обучения сети; iLayers -номер рассматриваемого слоя; iNeuron - номер рассматриваемого нейрона; errorChet; errorNechet - четная и нечетная ошибки сети; Е - общая ошибка сети; а - параметр неравнозначности раннего прибытия поездов; Delta -ожидаемая точность расчета сети; epochs - номер эпохи; maxEpochs -максимальное число эпох обучения; sostoyanie = sleep - условие состояния нейрона; maxLink - связь нейрона, имеющая максимальный вес; weight - вес связи нейрона; Power - значение потенциала нейрона; G - коэффициент ускоренного роста; / (x) - производная функции активации.
Ошибки сети вычисляются по формулам (2.1) и (2.2).
Обозначим через errorChet и errorNechet ошибки, вычисляемые для соответственно четных и нечетных поездов по формуле (2.1), и posErrorChet, posErrorNechet - ошибки, вычисляемые по формуле (2.2). Суть первой пары -накопленное время поездов, прибывших позже ожидаемого времени, второй -суммарное время отклонения по прибытиям поездов раньше требуемого времени.
Выше были рассмотрены принципы построения, функционирования и организации сети. Однако существует ряд дополнительных задач и свойств, вытекающих из особенностей сети и требующих дальнейшего исследования.
1.Ярко выраженной особенностью строения сети является наличие двойного набора весов, служащих для прокладки четных и нечетных поездов.
2. Спецификой предложенной конструкции является использование функции ошибки, которая в явном виде не связана со значением весов, так как вычисление наиболее вероятного пути прохождения поезда осуществляется по принципу мягкой конкуренции нейронов (выигрывает наиболее «тяжелая» связь из всех ненулевых весов выбранного нейрона, но веса остальных связей при этом не становятся нулевыми). В то же время величина ошибки влияет на ширину пучка связей, которые будут подвергнуты обучению.
3. Использование связей в качестве носителей «знаний» о состоянии сети является распространенной практикой, однако в предлагаемой сети происходит разнонаправленное обучение связей (по разные стороны от наиболее тяжелой связи). При этом скорость обучения связей, которые подлежат уменьшению, и скорость связей, подлежащих увеличению, меняется со скоростью, отличающейся на 1-2 порядка, что выражается коэффициентом ускоренного роста.
Разработка программы испытаний ИНС для двухпутного участка железнодорожной линии
В предыдущих главах разработана искусственная нейронная сеть для упорядочения транспортных потоков. Возникает необходимость провести испытания с целью оценки ее пригодности для решения целевой задачи. Кроме того, требуется обосновать участвующие в процессе расчета и обучения сети параметры в части влияния их на поведения сети, а именно: проанализировать зависимость времени обучения сети от таких параметров, как скорость обучения, начальные значения весов межнейронных связей, желаемая точность работы сети, а также коэффициент ускоренного роста из формулы (3.7).
К решению указанных задач существует три основных подхода:
1. Планирование и постановка полного факторного эксперимента, осуществление серии опытов с построенной ИНС и получение табулированных значений функции ошибки сети в зависимости от влияющих факторов.
2. Рассмотреть поведение весов сети и ошибки сети, а также обучение сети как некоторый процесс, описываемый стохастическими (в общем случае) дифференциальными уравнениями. Этот процесс может быть формализован как некоторая задача оптимального управления поведением нейронной сети [94] с учетом специфики функционирования и обучения рассмотренной сети. Преимущества данного подхода - это получение выводов, основывающихся на применении положений теории автоматического управления, которая является строгой доказательной научной дисциплиной. Трудности - возможные сложности в формулировке дифференциальных уравнений и в нахождении оптимальных решений при решении стохастических задач оптимального управления с обратной связью при значительной размерности системы. Кроме того, необходимо исследовать вопрос управляемости созданной сети как динамической системы с учетом аспектов, изложенных в [73].
3. Построить дополнительную нейронную сеть, которак бы выполняла функции аппроксимации зависимостей, указанных в п. 1, и использовать реакции данной сети как эталонные. Данный подход, как и первый, не полностью удовлетворяет требованиям строгой доказательности, но может быть использован на практике как вспомогательный при обучении и доводке рассматриваемой нейронной сети.
Экспериментальные исследования велись по мере создания сети. На основе оценки времен хода поездов по сети железных дорог России за 2012-2014 гг. были разработаны обучающие выборки времен начала и окончания движения поездов на двухпутном участке, состоящим из 7 станций. Всего сформирована 21 выборка для восьми пар поездов. Горизонт планирования выбран состоящим из 300 мин. В дальнейшем он был расширен до полных суток.
Для испытаний были выбраны следующие факторы:
1) начальная скорость обучения;
2) желаемая точность выхода сети;
3) величина коэффициента ускоренного роста.
Были проанализированы следующие зависимости от этих факторов при фиксированном значении коэффициента ускоренного роста весов:
1) сходимость сети;
2) величина итоговой ошибки;
3) число потребовавшихся эпох.
Еще на первоначальной стадии написания программы опытным путем было установлено, что при инициализации сети наилучший эффект достигается при присвоении весам связей случайных чисел из диапазона (0; 0,1). В дальнейшем это решение также было подтверждено [75].
Наилучшие результаты работы сети достигались при установлении коэффициента ускоренного роста весов, равного 120. При фиксированном значении этого коэффициента рассматривалась зависимость величины итоговой ошибки от начальной скорости обучения и желаемой точности выхода сети.
Первая серия экспериментов была проведена для прототипа нейронной сети, в которой рассматривалась только ошибка выхода, заданная по формуле (2.1). Зависимость функции ошибки нейронной сети устанавливалась от числа эпох и скорости обучения. Границы исследования: скорость обучения менялась от 0,0005 до 0,0999 с шагом 0,0001 (в ходе каждого запуска она также менялась согласно алгоритму обучения), желаемая точность менялась от 300 до 590 с шагом 10. После 5000 эпох обучение прекращалось.
После 200781 эксперимента были выбраны те результаты, в ходе получения которых обучение прекратилось до 5000 эпох более чем в половине случаев для заданной скорости обучения и заданной точности. Полученные данные сведены в таблице 4.1. Для каждой скорости обучения приведены средняя величина ошибки и среднее число потребовавшихся эпох.
В таблице 4.1 полужирным курсивом выделено начальное значение скорости обучения, равное 0,0096, - ему соответствует минимальное значение ошибки выхода сети в данных условиях.
На основании проведенной серии экспериментов можно сделать вывод о принципиальной применимости рассматриваемой ИНС для построения графиков движения поездов. В дальнейшем было произведено развитие конструкции и улучшение функционала сети.
Перед второй серией экспериментов в конструкцию сети были внесены следующие изменения. Добавлены наборы весов для прокладки четных поездов. Введено такое свойство нейрона, как технологическая операция (см. п. 2.2). Коэффициент ускоренного роста стал зависеть от номера слоя - на слоях сети с большим номером он должен быть меньше, так как одни и те же нейроны будут использоваться чаще во время обучения.
Во время второго эксперимента, в ходе которого обучение также производилось на 11 выборках, было проведено 9898 прогонов сети. Начальная скорость обучения менялась от 0,0041 до 0,0141. Ожидаемая ошибка менялась от 2 до 100. По результатам полученных результатов динамика сети характеризуется следующими данными (рисунок 4.5).
Следует заметить, что по сравнению с первой серией экспериментов величина ошибки снизилась более чем в 10 раз (в среднем), минимальные значения ошибки достигали 2 мин на весь период построения графика.
Для демонстрации эффективности работы рассматриваемой нейронной сети приведем построение графика движения поездов, который получается до начала обучения сети на начальных значениях весов связей (рисунок 4.7). Здесь красным цветом обозначены желаемые входы и выходы нечетных поездов, фиолетовым-четных.