Нейросетевые модели пошаговой оптимизации, маршрутизации и тактических игр

14.1. Логическая нейронная сеть - средство пошагового принятия решений

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

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

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

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

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

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

Такая схема соответствует и идее ситуационного управления, и рассмотренной ранее схеме нейросетевой реализации управления.

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

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

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

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

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

14.2. Нейросетевая транспортная модель динамической маршрутизации

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

Случайным образом или по некоторому закону (например, по расписанию) в сети возникают заявки на транспортное перемещение, на передачу сообщений или, в общем случае, - на движение объекта из пункта отправления к пункту назначения. Такими пунктами может быть любая пара пунктов сети. Заявки требуют прокладки маршрутов следования. Маршрут может предполагать как непосредственное перемещение из пункта отправления в пункт назначения (если существует связь), так и транзитное перемещение через промежуточные пункты.

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

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

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

Пусть $$\Delta х$$ - разность координаты х пункта назначения и пункта нахождения (отправления или промежуточного пункта), из которого следует произвести шаг перемещения - смещение; $$\Delta у$$ - аналогичная разность координаты у.

Для полной реализации модели достаточна однослойная логическая нейронная сеть (рис. 14.1).

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

Весь интервал возможного изменения $$\Delta у$$ также разобьем на отрезки b1, ..., bn. За каждым отрезком закрепим нейрон-рецептор. Его возбуждение определяется достоверностью того, что текущее значение $$\Delta у$$ принадлежит соответствующему отрезку.

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

Выходной слой состоит из N нейронов. Их возбуждение определяет пункты, в которые необходимо или возможно произвести смещение.

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

Синапсические связи вводятся так, чтобы каждое единичное возбуждение рецепторов всех элементов тройки {ai, bj, <k-й пункт нахождения>} приводил к максимальному возбуждению нейрона выходного слоя, называющего пункт дальнейшего смещения.

Передаточную функцию целесообразно выбрать как

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

Координаты каждого полученного пункта смещения сравниваются с координатами пункта назначения, т.к. в случае их совпадения маршрут следования реализован.

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

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

Продвижение по сети с каждого пункта должно уменьшать значение соответствующего ему порога (на выходном слое) в зависимости от "физического смысла" задачи.

Регулировка синапсических весов нейрона выходного слоя может быть связана с загруженностью пути, линии передачи данных и других средств перемещения в транспортной сети. Такая регулировка требует введения дополнительного контроля состояния связи, соединяющей пункты. Синапсический вес такой связи должен снижаться при имитации движения. С этим снижением должен быть связан счетчик времени, в течение которого связь невозможна. Например, интервал следования поездов по одному пути обусловлен, в частности, необходимым расстоянием между поездами. В общем случае необходимо учитывать пропускную способность линий связи. По истечении определенного времени (когда счетчик "обнуляется") вес связи увеличивается до максимального (скорее всего, до единицы). Таким образом, даже если величина возбуждения нейрона, указывающего на пункт смещения, высока и позволяет принять движущийся объект, учитывается состояние средства связи.

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

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

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

14.3. Пример модели транспортного маршрутизатора из центрального пункта отправления

Рассмотрим пример транспортного маршрутизатора, планирующего движение из одного, центрального пункта к периферийным пунктам со специальной топологией связей. Транспортная сеть представлена на рис. 14.2, где все пункты заданы своими координатами (х, у) в системе координат, связанной с центром.

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

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

Если координаты найденного пункта смещения совпадают с координатами пункта назначения, маршрут реализован.

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

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

Например, при движении из пункта 0 по адресу пункта 6 с координатами (-50, 150) оказывается, что $$\Delta x < 0$$, $$\Delta y \ge 0$$. Тогда нейрону 1 сообщается значение возбуждения, равное 1. Такое же значение сообщается нейрону 4, а также нейрону 5, соответствующему центральному пункту. Тогда V27 = 1, V28 = ... V46 = 0. То есть найден промежуточный пункт 1. Тогда возбуждение нейрона 6 полагается равным единице и устанавливается, что относительно пункта 1 координаты пункта назначения определяют неравенства $$\Delta х \ge 0, \Delta у \ge 0$$. Значит, следует сообщить единичное возбуждение нейронам 2 и 4. Возбуждение всех других рецепторов полагается нулевым. При расчете передаточной функции для всех нейронов выходного слоя выдается рекомендация следования в пункт 6, т.к. единичное возбуждение приобретает нейрон 32. Маршрут составлен: 0 -> 1 -> 6.

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

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

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

Проектируемая модель строится на основе логической нейронной сети, представленной на рис. 14.3, и должна удовлетворять следующим требованиям:

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

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

Блок-схема проектируемой модели представлена на рис. 14.5.

Блок 1 реализует функции управления, связи с пользователем и формирования транспортного потока. Каждая заявка на выполнение маршрута предполагает задание координат пункта отправления и пункта назначения, время начала движения, приоритет маршрута (литер).

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

Блок 3 управляет циклом обработки всех выполняющихся маршрутов. Если все маршруты в такте обработаны, допускается возможность генерации (в блоке 1) новых маршрутов. Исследование маршрутов в порядке их приоритета обеспечивает преимущественное, первоочередное использование ресурсов – узлов и магистралей.

В блоке 4 проверяется, движется ли объект по магистрали, или находится на станции.

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

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

В блоке 7 проверяется, достиг ли указанный счетчик нулевого значения? Это означает прибытие поезда на станцию.

Если достиг (блок 8), проверяется, конечный ли это пункт следования. Если да, маршрут полностью выполнен и осталось обработать информацию о его следовании (блок 19).

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

Блок 11 выполняется в случае нахождения объекта движения на станции. В нем проверяется, исчерпан ли счетчик "остановки".

Если этот счетчик не равен нулю, в блоке 12 производится его уменьшение на единицу и осуществляется переход к анализу следующего маршрута (блок 3).

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

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

Если нейросеть указала пункт смещения, в блоке 15 проверяется: позволяет ли загрузка магистрали (вес соответствующей связи) начать движение?

Если нет, в блоке 16 увеличивается значение счетчика тактов времени пребывания на станции.

При положительном результате анализа в блоке 17 рассчитывается и "взводится" счетчик движения объекта по данной магистрали.

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

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

Таким образом:

14.5. Нейросетевой "подсказчик" в тактической игре

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

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

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

То есть каждая клетка i может принимать значение из множества $$\{ \varnothing , пешка \ белая, ладья \ белая, конь \ белый, слон \ белый, ферзь \ белый, король \ белый, пешка \ черная, ладья \ черная, конь \ черный, слон \ черный, ферзь \ черный, король \ черный\}$$. При этом позиции являются симметричными относительно цвета фигур. Игроку, прибегающему к услугам "подсказчика", главное - указать: "фигуры мои - фигуры противника". Играть можно "самому с собой", как бы поворачивая доску после очередного хода. (Если "подсказчик" играет сам с собой, логично предположить, что такая игра всегда будет сводиться к ничьей?)

Тогда рецепторный слой однослойной логической нейронной сети должен состоять (рис. 14.6) из 64 групп нейронов. Каждая группа закреплена за одной клеткой и, в свою очередь, состоит из 13 нейронов-рецепторов. Каждый рецептор закреплен за одним из возможных значений клетки.

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

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

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

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

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

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

На этом пути может производиться совершенствование "подсказчика", что повышает интерес именно игры человека с машиной.