Разработка искусственной нейронной сети для решения задачи маршрутизации

Потапкин Кирилл Олегович

Разработка искусственной нейронной сети для решения задачи маршрутизации

Бакалаврская работа

Автоматика. Вычислительная техника

Дипломы

Вуз: Мордовский государственный университет имени Н.П. Огарева

ID: 5bbb11c77966e104f1dd9ed3

UUID: 08863280-ad00-0136-cd97-525400005860

Язык: Русский

Опубликовано: около 6 лет назад

Просмотры: 61

Потапкин Кирилл Олегович

Источник: федеральное государственное бюджетное образовательное учреждение высшего образования "Национальный исследовательский Мордовский государственный университет им. Н. П. Огарёва"

Комментировать 0

Рецензировать 0

Скачать - 4,3 МБ

Поделиться работой

СОДЕРЖАНИЕ ВВЕДЕНИЕ .................................................................................................................. 6 1 Описание способов организации потоков информации ...................................... 8 1.1 Современные технологии для обеспечения маршрутизации ....................... 8 1.2 Дистанционно-векторные алгоритмы ........................................................... 10 1.3 Алгоритмы состояния каналов ...................................................................... 13 2 Описание искусственных нейронных сетей ........................................................ 18 2.1 Преимущества нейронных сетей ................................................................... 18 2.2 Область применения нейронных сетей ......................................................... 23 2.3 Общие черты нейронных сетей ..................................................................... 23 2.4 Типы функций активации............................................................................... 26 3 Методы обучения нейронной сети ....................................................................... 29 3.1 Обучение с учителем ...................................................................................... 29 3.2 Обучение без учителя ..................................................................................... 31 4 Разработка и анализ алгоритмов работы сети Хопфилда .................................. 36 4.1 Нейронная сеть Хопфилда ............................................................................. 36 4.2 Методы нахождения кратчайшего пути ....................................................... 38 5 Практическая реализация искусственной нейронной сети................................ 44 5.1 Выбор среды проектирования........................................................................ 44 5.2 Разработка программного кода ...................................................................... 46 5.3 Анализ полученных данных........................................................................... 48 ЗАКЛЮЧЕНИЕ ......................................................................................................... 52 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ ............................................... 54 ПРИЛОЖЕНИЕ А (обязательное) Функциональный код программы ................ 57 Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 5

ВВЕДЕНИЕ Становление сложных электронно-вычислительных комплексов и систем базируется на передаче данных от отправителя к получателю. Задачу подбора оптимального пути, который обеспечивает прохождение информации по маршруту, отвечающему определённым критериям, решают методы маршрутизации. Маршрутизация – это процесс определения пути следования информации в сетях связи. При этом, как правило, на пути встречается, по крайней мере, один узел. Маршрутизация включает в себя две главные составляющие: определение оптимальных путей маршрутизации и передача информационных сообщений. Определение маршрута характеризуется сложностью процесса и основывается на различных показателях или их комбинация. Когда информация передается по пути, заранее не заданном, и определяется на каждом узле по мере продвижения информации, т.е. процесс маршрутизации происходит в динамическом режиме, сложность расчёта маршрута возрастает. В практических задачах появляются такие требования, что передачу информации необходимо осуществить открытом виде, т.е. без использования средств шифрования. В этом случает необходимо построение маршрутов транспортировки данных по каналам связи, обладающих требуемой степенью надёжности и защищённости от вмешательства злоумышленников, в том числе от непосредственного физического подключения к среде передачи. При маршрутизации на основе установленных требований нужно выполнять оценку не только характеристик, которые обеспечивают быструю передачу информации получателю, но и в процессе поиска оптимального пути учитывать критерии безопасности среды передачи. Имеющиеся методы маршрутизации требуют наличия информации о полной структуре сети, в которой будет производиться передача данных. Если топология сети подвергается частым изменениям, появление и удаление новых Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 6

соединений и узлов, изменения в среде передачи, то маршрутизирующие алгоритмы утрачивают способность поддерживать эффективный обмен информации в сети. Для того чтобы телекоммуникационная сеть поддерживала свои функции по обеспечению передачи информационных сообщений, требуется применение современных методов, которые способны решать задачи при неполных, неверных, или противоречивых входных данных. Такой способностью обладают вычислительные методы на основе нейросетевых алгоритмов. Использование интеллектуальных разработок позволит выполнять передачу данных в распределённых сетях связи даже при условии частичного вывода из строя оборудования маршрутизации или линии связи, а также в случаях сбоя, вызванных действиями третьих лиц. Таким образом, задача разработки искусственной нейронной сети для решения задачи маршрутизации является актуальной и практически значимой. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 7

1 Описание способов организации потоков информации 1.1 Современные технологии для обеспечения маршрутизации Телекоммуникационные сети применяются для того, чтобы транспортировать информацию от отправителей к получателям. Обычно информация пересылается от одного узла к другому до момента, пока не достигнет конечного пункта, на который должны быть переданы данные. В большинстве случаев существует несколько путей передачи информации (рисунок 1.1). Рисунок демонстрирует возможность передачи информации от узла А к узлу B по нескольким маршрутам. Рисунок 1.1 – Проблема выбора оптимального маршрута Чтобы выбрать оптимальный путь, соответствующий определенным критериям, применяются алгоритмы маршрутизации. В рамках маршрутизации осуществляются следующие параллельные процессы: – формируется таблица маршрутизации – информационная структура, включающая данные о том, какой пункт информация должна пройти следующим, чтобы маршрут доставки ее на узел назначения был оптимальным; Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 8

– осуществляется процесс управления передачей информации на основе таблицы маршрутизации. Средства программного или аппаратного характера, формирующие таблицы маршрутизации, именуются маршрутизаторами. Маршрутизаторы обеспечивают определение маршрута с использованием набора критериев, которые называют метриками. Метрики отражают степень предпочтительности тех или иных маршрутов. При выборе критериев следует ориентироваться на особенности функционирования сети. Необходимость быстро доставить информацию предопределяет выбор критериев, характеризующих расстояние, которое проходит посылка данных в процессе движения до узла назначения. В алгоритмах маршрутизации учитывается такие характеристики, как пропускная способность и задержка передачи. Также учитываются стоимостные параметры передачи информации, и ряд иных характеристик. Преимущественное значение имеют критерии, отражающие степень физической безопасности каналов связи. Существуют способы, посредством которых обеспечивается возможность анализировать целостность каналов, по которым передается информация, для определения критериев, используемых в процессе прокладки маршрутов. С увеличением числа метрик, которые учитывает маршрутизатор, повышается эффективность генерации маршрутов, соответствующих определенным требованиям. Динамическая (адаптивная) маршрутизация представляет собой систему, в которой любые изменения конфигурации сети в автоматическом режиме учитываются в таблицах маршрутизации. Потребность в формировании подобного рода алгоритмов обусловлена тем, что существующие алгоритмы динамической маршрутизации имеют уязвимости. На сегодня большинство сетей телекоммуникации распределенных алгоритмов и основывается алгоритмов алгоритмов на маршрутизации состояния применении – канала. адаптивных дистанционно-векторных Распределенный подход предполагает, условия, в которых находятся маршрутизаторы сети, идентичны. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 9

Маршрутизаторы производят выявление маршрутов, формируют таблицы маршрутизации, и находятся во взаимодействии друг с другом [1]. Подобный подход является более оптимальным, чем централизованный подход, при котором в сети представлен единственный маршрутизатор, осуществляющий сбор информации о сети от иных маршрутизаторов, и конфигурирующий маршруты, по которым движутся данные. Если центральный маршрутизатор откажет, произойдет выход из строя всей сети. В этой связи данный подход в процессе проектирования сетей практически не используется. 1.2 Дистанционно-векторные алгоритмы Если маршрутизаторы используют дистанционно-векторные алгоритмы (ДВА), они на регулярной основе передают друг другу копии таблиц маршрутизации производится При [2]. обмен регулярных информацией об обновлениях изменении маршрутизаторами топологии сети. Соответственно, все маршрутизаторы получают от соседних информацию о каждом из имеющихся узлов. Основой выявления маршрута, являющегося оптимальным, является вектор расстояния. Данный вектор демонстрирует, сколько переходов потребуется, чтобы информация попала на заданный пункт. Каждая позиция в таблице маршрутизации сопровождается сведениями о суммарном векторе, отражающем расстояние до соответствующей сети или узла (рисунок 1.2). ДВА лежит в основе дистанционно-векторного протокола маршрутизации группового вещания DVMRP (Distance Vector Multicast Routin Protocol). Данный протокол был создан в числе первых протоколов, использовавшихся при определении пути, по которому движется групповой трафик, т.е. производится доставка данных до нескольких получателей из одного источника. Подобный тип передачи информации весьма важен в случае, когда команды управления или данные рассылаются на большое число узлов. В процессе выбора маршрутов Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 10

рассылки актуальной является и вопрос о выборе маршрута с необходимой степенью безопасности, обеспечивающего надежную доставку информации. Рисунок 1.2 – Пример таблицы маршрутизации ДВА Начальным этапом развития протоколов широковещательной рассылки стало создание алгоритма, в соответствии с которым маршрутизатор пересылает информацию на каждый из интерфейсов, за исключением входного. Подобная стратегия обеспечивает генерацию значительного объема трафика в сети, не несущего полезной нагрузки. Модификации алгоритма дают возможность распространять трафик от источника до получателя таким образом, чтобы продвижение пакетов происходило исключительно по путям, которые наиболее оптимально соединяют источник и каждого из получателей. Рисунок 1.3 отображает ситуацию, когда маршруты группового трафика от источника до получателей, которым они не предназначаются, исключены. Таким образом, существует необходимость в формировании дерева, вершина которого будет находиться в источнике информации, запланированной к передаче. Дерево должно обеспечивать соединение всех маршрутизаторов с подключенными к ним локальными сетями, в которых содержатся получатели данной группы, по Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 11

наиболее оптимальным путям [3]. Применяя нейросетевые технологии для модификации алгоритмов данного типа, можно добиться построения маршрута движения групповой информации по пути, который будет наиболее безопасным, и при этом обеспечить учет изменений топологии сети. Рисунок 1.3 – Управление групповой передачей информации Недостатки представленного алгоритма могут быть представлены следующим образом. 1) Алгоритм стабильно функционирует в случае, если масштабы сети являются сравнительно небольшими. Если сеть имеет значительный масштаб, процесс интенсивного обмена таблицами маршрутизации вызывает дополнительную нагрузку на линии связи. 2) Обработка изменений конфигурации сети подобными алгоритмами маршрутизации не всегда может быть корректной, в силу того, что у маршрутизаторов нет сведений о том, какова точная топология сети. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 12

3) Адаптация протоколов, которые используют ДВА маршрутизации (к примеру, RIP – Routing Information Protocol) к утрате маршрута вызывает определенные затруднения, поскольку они передают информацию, которая необходима, чтобы пополнять таблицы маршрутизации. 4) Информация может зацикливаться, т.е. информационные группы могут постоянно передвигаться между маршрутизаторами. Возможна вероятность того, что появятся ложные маршруты, возникающие в случае, когда используется информация о маршрутах, которые не существуют. 1.3 Алгоритмы состояния каналов За счет алгоритмов состояния каналов (АСК) все маршрутизаторы обеспечиваются информацией, которая является достаточной для того, чтобы построить точный граф сети. Если маршрутизаторы работают на базе АСК, они в состоянии поддерживать сложную базу с информацией о том, какова топология соединений в сети. Все маршрутизаторы функционируют на основе одного графа сети. В силу подобной особенности маршрутизация становится устойчивой к изменению конфигурации. В случае, когда осуществляется ДВА-маршрутизация информация об удаленных сетях и маршрутизаторах отсутствует. Процесс формирования таблицы маршрутизатора является двухэтапным. 1) На первом этапе формируется база данных, включающая сведения о состоянии связей в сети. Топология имеет вид графа. В качестве вершин выступают маршрутизаторы, маршрутизаторов. ребра Маршрутизаторы графа представлены осуществляют обмен с связями соседними маршрутизаторами информацией о графе сети, которая имеется у каждого из маршрутизаторов на данный момент. Информация в процессе передачи маршрутизаторами не модифицируется. Каждый из маршрутизаторов в итоге имеет идентичную информацию о том, какова структура сети. Производится Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 13

упорядочение информации, и в итоге формируется логическая топология, которая представляет собой дерево связей. Корень дерева представлен в виде текущего маршрутизатора, ветви – в виде возможных маршрутов к каждой из подсетей. При изменении состояния происходит повторение процесса формирования графа. 2) В рамках второго этапа определяются оптимальные маршруты. Генерируются таблицы маршрутизации. После того, как будет построено дерево связей, начинается трудоемкий процесс поиска оптимального пути в рамках графа. В протоколах маршрутизации, в основе которых – АСК (к примеру, OSPF – Open Shortest Path First), при поиске указанного пути примеряется итеративный алгоритм Дейкстры. Каждым маршрутизатором производится поиск оптимальных путей от собственного интерфейса до каждой из известных подсетей. По каждому из найденных путей осуществляется запоминание только первого шага, который и включается в таблицу маршрутизации. Рисунок 1.4 отображает сеть, включающую шесть маршрутизаторов (R1 – R6) и подсетей (N1 – N6). Проводится оценка состояния каналов, с приписыванием каждому каналу меры стоимости. Рисунок 1.5 отражает дерево наиболее коротких путей применительно к маршрутизатору R3. Соответственно, каждым из маршрутизаторов может осуществляться отслеживание альтернативных путей и осуществляться выбор пути до каждой из конечных точек, который будет оптимальным. На основе АСК осуществляется функционирование и протокола MOSF (Multicast extensions to OSPF), который применяется при групповом вещании. Маршрутизаторами производится добавление к информации о состоянии каналов передачи данных о том, в каких группах состоят различные узлы сети. Это позволяет маршрутизаторам осуществлять формирование не только общего графа сети, но и получать информацию о том, каков состав групп для рассылки сообщений. На основе этих данных маршрутизирующими алгоритмами производится определение дерева наиболее коротких путей применительно к Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 14

каждой группе. Это дает возможность доставки информационных сообщений по наиболее коротким путям от источника до подсетей, в которых имеются члены группы – конечные получатели информации. Рисунок 1.4 – Пример конфигурации сети и состояния каналов Рисунок 1.5 – Кратчайшие маршруты от узла R3 Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 15

На основе АСК осуществляется функционирование и протокола MOSF (Multicast extensions to OSPF), который применяется при групповом вещании. Маршрутизаторами производится добавление к информации о состоянии каналов передачи данных о том, в каких группах состоят различные узлы сети. Это позволяет маршрутизаторам осуществлять формирование не только общего графа сети, но и получать информацию о том, каков состав групп для рассылки сообщений. На основе этих данных маршрутизирующими алгоритмами производится определение дерева наиболее коротких путей применительно к каждой группе. Это дает возможность доставки информационных сообщений по наиболее коротким путям от источника до подсетей, в которых имеются члены группы – конечные получатели информации. Затруднения, возникающие в случае, когда используется алгоритм маршрутизации, основанный на оценке состояния каналов передачи, следующие: 1) для реализации алгоритма необходим значительный объем памяти. Обработка больших потоков информации, поддержка логического дерева и таблиц маршрутизации также вызывает необходимость в существенных вычислительных ресурсах; 2) следствием динамического определения структуры сети является генерация значительных объемов трафика, который требуется, чтобы обеспечивать обмен маршрутизаторов информацией друг с другом; 3) если в сетевой структуре имеется сложная топология, с множественными связями, то при частом изменении характеристик каналов связи, возникновении новых соединении, отключении части каналов связи возможен полный отказ алгоритма. Одна из наиболее важных проблем, выявленная в процессе исследования недостатков представленных маршрутизации, когда алгоритмов, информация состоит является в выполнении недостаточно полной. Маршрутизаторы получают информацию от отдельных элементов сети, однако Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 16

таблицы маршрутизации могут содержать неполную маршрутную информацию. Если маршрутизирующая система начинает выполнять свои функции с нарушениями, отдельные каналы связи или сами маршрутизаторы могут отказать. Если у маршрутизаторов отсутствует информация, которая требуется, чтобы выбрать оптимальный путь до узла назначения, пересылка данных осуществляется в соответствии со стандартными, заранее определенными маршрутами. Маршрутизирующей системой данные могут быть отправлены за пределы локальной автономной системы. Вследствие этого указанные данные могут вернуться обратно, и трафик может зациклиться. При отказе каланов связи, за счет которых обеспечиваются статические резервные маршруты передачи информации, Использование происходит полная аппроксимирующих остановка функционирования способностей нейронных сети. сетей обеспечивает поддержание функционирование сети в моменты, когда стандартные протоколы маршрутизации работают нестабильно. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 17

2 Описание искусственных нейронных сетей Нейронные сети представляют собой гигантские распределенные параллельные процессоры, состоящие из базовых устройств обработки информации для сбора экспериментальных знаний и обеспечения их дальнейшего использования. Нейронная сеть похожа на человеческий мозг по двум соображениям: – знания в нейронную сеть принимаются из окружающей среды и продолжают использоваться в процессе обучения; – связи между нейронами, называемые синаптическими весами, используются для накопления знаний. 2.1 Преимущества нейронных сетей Совершенно очевидно, что нейронные сети наиболее перспективны и мощны, во-первых, из-за параллелизма в обрабатывании информации, вовторых, из-за способности к самообучению, т.е. создавать обобщения. Обобщение термин, означающий способность получать достоверные результаты на основе данных, которые были получены в учебном процессе. Благодаря этим свойствам нейронным сетям не составляется труда принимать решения по сложным (масштабным) задачам, считающимся трудноразрешимыми в настоящее время. Однако, как показывает практика, нейронные сети не способны автономно обеспечить нас готовыми решениями. Для этого необходима интеграция в сложные системные комплексы. В частности, сложные задачи можно поделить на некоторую последовательность сравнительно простых, решаемость которых обеспечивается нейронными сетями. Для создания компьютерной архитектуры, которая будет способна имитировать человеческий мозг (если такое окажется возможным вообще), придется пройти долгий и Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 18

трудный путь [3]. Обоснованность использования нейронных сетей показывают следующие положительные свойства систем. Нелинейность Искусственные нейронные сети существуют в линейных и нелинейных формах. Нейронные сети, состоящие из нелинейных нейронных соединений, сами являются нелинейными. Кроме того, поскольку нелинейность распределена по сети, – она особого сорта. Нелинейность является особенно важным свойством, в тех случаях, когда сам природный механизм, который отвечает за образование входного сигнала, также является нелинейным, например, человеческая речь. Отображение входной информации в выходную Одна из распространённых парадигм обучения состоит в том, что обучение с учителем, который может изменить синаптические веса на основе набора маркированных учебных образцов. В каждом примере они состоят из входногоo сигнала и соответствующего ему желаемого ответа. Произвольно выбирая множества из этого наборы, нейронная сеть изменяет синаптические веса, чтобы минимизировать несоответствия между требуемым выходным сигналом и генерируемым сетью согласно взятым статистическим критериям. При этом как раз модифицируются свободные параметры сети. Пример, который был показан ранее, может быть применен и впоследствии, но уже в ином порядке. Такое обучение производится до тех пор, пока состояние синаптических весов не станет стабилизированным. Таким образом, искусственная нейронная сеть обучается на примерах, создавая таблицу входов и соответствующих им выходов для определенной задачи. Такой метод может напомнить о непараметрическом статистическом обучении. Это направление статистики имеет дело с оценками, не связанными с какой-либо конкретной моделью, или, с биологической точки зрения, с обучением с нуля. Здесь термин непараметрический используется для Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 19

акцентирования того, что изначально не существует никакой предопределенной статистической модели входных данных [3]. Например, рассмотрим задачу определения изображений. В ней требуется сопоставить входной сигнал, указывающий на материальный объект, или событие, с какой-либо заданной категорией (классом). В таком подходе к этой проблеме необходимо оценить рамки принятия решений в множестве входного сигнала на основе серии выборок. При этом никакая модель распределения вероятностей не используется. Аналогичный подход применяется и в парадигме обучения с учителем. Это вновь подчеркивает параллельную взаимосвязь между отражением входных сигналов во выходные, которые осуществляются нейронной сетью, и непараметрическим статистическим обучением. Адаптивность Способностью нейронные сети подстраивать свои синаптические веса к изменениям в окружающей среде считается адаптивностью. В частности, обученные нейронные сети, которые действуют в определенной среде, могут быть легко использованы после переобучения в работе, когда условия параметров среды находятся в незначительные колебания. Также, при работе в нестационарной среде создаются нейронные сети, которые изменяют синаптические веса в реальном времени. Архитектура нейронных сетей, естественная для определения изображений, обработки сигналов и задач управления, может быть скомбинирована с их способностью к адаптированию, что приводит к созданию моделей адаптивного определения изображений, адаптивной обработки сигналов и адаптивного управления. Установлено, что чем выше способность системы адаптироваться, тем более стабильной будет ее работа в нестационарной среде. В тоже время хотелось бы отметить, что адаптивность не всегда ведет к стабильности; иногда она приводит к результатам совершенно противоречивым. Например, адаптивная система, параметры которой очень быстро изменяются во времени, может также очень быстро Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 20

реагировать на незнакомые производительности. преимуществами Чтобы раздражители, в адаптивности, полной основные мере что вызывает воспользоваться параметры системы потерю всеми должны оставаться достаточно стабильными, для того чтобы внешние помехи не учитывались в системе, и достаточно гибкими, для того чтобы при значительных изменениях в окружающей среде можно было обеспечить ответ. Эта задача обычно называется дилеммой стабильности-пластичности [4]. Очевидность ответа В концепции задачи определения изображений можно развивать нейронную сеть, которая определяет информацию не только для установления конкретного типа, но и для повышения надежности принимаемого решения. В дальнейшем эта информация может быть использована для устранения подозрительных решений, что может повысить эффективность нейронной сети. Контекстная информация В соответствии со структурой нейронной сети, информация в ней представляется с помощью ее состояния активации. Каждый нейрон сети потенциально может быть затронут влиянию всех остальных ее нейронов. В результате, существование нейронных сетей напрямую связано с контекстной информацией. Отказоустойчивость Нейронные сети, модулируемые блоками электроники, потенциально являются отказоустойчивыми. Это означает, что при стечении неблагоприятных условий, их производительность падает незначительно. Например, если поврежден какой-то нейрон или его соединения, извлечение сохранённой информации затрудняется. Однако, учитывая то, что нейронная сеть имеет распределенный характер хранения информации, она может гарантировать, что Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 21

только серьезные повреждения структуры нейронной сети могут оказывать существенное влияние на ее работоспособность. Поэтому снижение качества работы нейронной сети происходит медленно. Небольшое повреждение структуры никогда не приведет к катастрофическим последствиям. Это очевидное преимущество нейронных вычислений, однако его часто не принимают в расчет. Чтобы алгоритмы обучения гарантировали отказоустойчивость работы нейронной сети, в них нужно закладывать соответствующие поправки. Масштабируемость Параллельная архитектура нейронных сетей значительно ускоряет решение некоторых задач и обеспечивает масштабируемость нейронных сетей в рамках технологии VLSI (very large scaleintegrated). Одним из преимуществ технологий VLSI является возможность представления достаточно сложного поведения с помощью иерархической структуры. Единообразие анализа и проектирования Нейронные сети представляют из себя универсальный способ обработки информации. Это означает, что одно и то же спроектированное решение нейронной сети способно работать и во многих других предметных областях. Это свойство проявляется несколькими способами. – Нейроны являются основной составляющей частью в той или иной форме для любой нейронной сети. – Благодаря этому сходству возможно применять одни и те же теории и алгоритмы обучения для построения различных приложении на основе нейронных сетей. – Блочные сети могут быть спроектированы с использованием интеграции целых модулей. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 22

Аналогия с нейробиологией Структура нейронных сетей строится по аналогии с человеческим мозгом, являющимся ярким примером, доказывающим то, что параллельные отказоустойчивые вычисления не только физически реализуемы, но также обеспечит быстрые и мощные инструменты решения задач. 2.2 Область применения нейронных сетей Выполняемые сетью функции можно разделить на несколько основных групп: аппроксимации и интерполяции, распознавания и классификации образов, сжатия данных, прогнозирования, идентификации, управления, ассоциации. Традиционно нейронные сети применяются для распознавания образов (в широком смысле этого слова, т. е., например, как для обнаружения лиц на фотографиях, так и для распознавания текстов) и для сжатия информации. В последнее время, однако, нейронные сети все чаще применяются в задачах прогнозирования и управления. На фондовых рынках успешно действуют боты, написанные с применением нейронных сетей, принимающие решения о купле и продаже на основании значений индексов. 2.3 Общие черты нейронных сетей Широкий круг задач, решаемых нейронными сетями, не позволяет создавать мощные универсальные сети из-за ограниченности вычислительных ресурсов. И хотя разработчики вынуждены создавать специализированные нейронные сети, функционирующие по различным алгоритмам, эти отдельные типы сетей обладают несколькими общими чертами. Во-первых, общим для нейронных сетей является принцип параллельной обработки сигналов, который достигается путем объединения большого числа Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 23

нейронов в слои. Нейроны различных слоев определенным образом соединены, а также, в некоторых конфигурациях, соединены и нейроны одного слоя между собой, причем обработка взаимодействия всех нейронов ведется послойно. Во-вторых, основу каждой нейронной сети составляют относительно простые однотипные ячейки, имитирующие работу нервных клеток (нейронов) человеческого организма, которые в некоторых случаях объединяют в слои: Рисунок 2.1 – Однослойная и двухслойная нейронные сети Так как принцип работы искусственного нейрона основан на механизме функционирования нейронов настоящих, рассмотрим вначале их строение. Нервная клетка (нейрон) имеет тело, называемое сомой, со стандартным набором органелл и ядром. Можно выделить два типа отростков: 1) дендриты, многочисленные тонкие ветвящиеся отростки, играющие ключевую роль во взаимодействии нейронов друг с другом; 2) аксон, длинный и толстый отросток, ветвящийся на конце. Входные сигналы поступают в клетку через синапсы, а выходной сигнал отводится аксоном через его многочисленные нервные окончания, называемые коллатералями. Коллатерали взаимодействуют c дендритами и сомами других клеток, создавая новые синапсы. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 24

Рисунок 2.2 – Структура и взаимодействие нервных клеток C некоторыми упрощениями можно считать, что передача нервного импульса между двумя клетками основана на выделении особых химических веществ (нейромедиаторов), которые, попадая на клеточную мембрану, вызывают ее поляризацию. В силу неодинаковости размеров и формы синапсов, одно и то же количество нейромедиатора возбуждает клетку в разной степени. Отсюда следует, что в математической модели нейрона каждому синапсу следует сопоставить числовой коэффициент (вес), который по физическому смыслу был бы эквивалентен его электрической проводимости. Вернемся теперь к искусственному нейрону (в дальнейшем, чтобы избежать путаницы, под словом нейрон будет подразумеваться именно искусственный нейрон, т. е. ячейка нейронной сети). Каждый нейрон характеризуется собственным состоянием s, по аналогии с нервными клетками, которые могут быть возбуждены или заторможены. Нейрон обладает группой синапсов (входных связей), соединенных с выходами других нейронов, а также имеет аксон (выходную связь). Каждый синапс характеризуется величиной синаптической связи, или ее весом wi. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 25

Рисунок 2.3 – Искусственный нейрон Текущее состояние i-ого нейрона будем определять, как взвешенную сумму его входов: Æ OL ˝ TS Æ (1) @4 а выход — как функцию его состояния U L B: O; . Функция f(s) называется активационной, и, вообще говоря, может иметь различный вид. 2.4 Типы функций активации Активационные функции, представленные в формулах как f(s), определяют выход сигнала нейрона в зависимости от производного локального местоположения s. В основном существуют три типа функций активации. 1) Функция единичного скачка – функция Хевисайда – пороговая функция, или пороговая функция. Функция показана на рисунке 2.4(а), и описывается следующим выражением: sÆ ¨˛¸ B: O; L D rÆ ¨˛¸ Лит Изм. № докум. Подп. Дата OR r OO r БР-02069964-11.03.02-17-18 (2) Лист 26

2) Кусочно-линейная функция, представленная на рисунке 2.4(б), описывается следующим образом: sÆ ¨˛¸ : O; L OR s t s s P OP F t t s rÆ ¨˛¸ OQ F Æ t OÆ ¨˛¸ (3) Эту функцию активации можно рассматривать как аппроксимацию нелинейного усилителя. Следующие два варианта можно считать особой формой кусочно-линейной функции: – если линейная область оператора не достигает порога насыщения, он превращается в линейный сумматор; – если коэффициент усиления линейной области принять бесконечно большим, то кусочно-линейная функция вырождается в пороговую [3]. 3) Сигмоидальная функция. График этой функции похож на букву S. Она, вероятно, является наиболее распространенной функцией, используемой для создания искусственных нейронных сетей. Это быстро растущая функция, которая поддерживает баланс между линейным и нелинейным поведением. Примером сигмоидальной функции может служить логистическая функция, задаваемая следующим выражением: B: O; L s s E A? Æ (4) где a параметр наклона сигмоидальной функции. Изменяя параметр a, можно построить функции с различной крутизной (рисунок 2.4(в)). Первый график соответствует величине параметра, равной, а/2. в пределе, когда параметр наклона достигает бесконечности, сигмоидальная Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 27

функция вырождается в пороговую. Если пороговая функция может принимать только значения 0 и 1, то сигмоидальная функция принимает бесконечное множество значений в этом же диапазоне. При этом следует заметить, что сигмоидальная функция является дифференцируемой, в то время как пороговая – нет. 1,2 1,2 1 1 0,8 0,8 0,6 0,6 0,4 0,4 0,2 0,2 0 -2 -1,5 -1 -0,5 0 0 0,5 1 1,5 2 -2 -1,5 -1 -0,5 s (а) 0 0,5 1 1,5 2 s (б) 1,2 1 0,8 0,6 0,4 0,2 0 -10 -8 -6 -4 -2 0 2 4 6 8 10 s (в) Рисунок 2.4 – Типы функции акций активации а – функция единичного скачка, б – кусочно-линейная функция, в – сигмоидальные функции Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 28

3 Методы обучения нейронной сети Формирование весовых коэффициентов синапсов (ВКС) – главная задача по созданию нейронной сети (НС). От правильности решения напрямую будет зависеть вся работоспособность системы. Процесс поиска и структурирования ВКС условно называют обучением нейронной сети. Способы обучения можно объединить в две общие группы: 1) Обучение с учителем. При наличии тестового массива входящих данных и установленного соответствия на подачу выходного сигнала можно провести обучение с учителем. Нейронной сети предоставляют уже готовую информацию, которая подчиняется строгим правилам и алгоритмам. За счет этого ей удается сформировать последовательности и уже самостоятельно подстраивать веса синаптических связей. Сеть, на основе предоставленных примеров, устанавливает соответствие сигналов между потоками входных и выходных сигналов. 2) Обучение без учителя. Для поиска весовых коэффициентов синапсов здесь используются алгоритмы, которые зависят только от значений входных данных. 3.1 Обучение с учителем Для большего понимания изучим парадигмы обучения НС. На рисунке 3.1 показана блочная диаграмма, иллюстрирующая эту форму обучения. При использовании методики с учителем общая концепция строится на передачи знаний из окружающей среды, сформированных в пару вход-выход. Для нейронной сети в процессе обучения сама окружающая среда остается неизвестной. Если учителю и ученику в виде НС поступает обучающий вектор из внешней среды – учитель на основе своих знаний может передать и сформировать для сети необходимый отклик на поступающий сигнал. Это и Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 29

является функциональным решением задачи. В процессе обучения параметры нейронной сети могут корректироваться на основе входящих данных и сигналов ошибок (разности между требуемым результатом и текущим выходным откликом). Корректировка производится поэтапно, чтобы сформировать в НС симуляцию поведения учителя. Это является неотъемлемым процессом формирования самостоятельной работы нейронной сети. Только при понимании реакции на сигналы ошибок удастся передать знания от учителя в полном объеме. В дальнейшем нейронную сеть можно переводить на самостоятельную работу с поступающими сигналами от окружающей среды. Здесь важно понимание того, что при работе с учителем система является замкнутой. Постоянная обратная связь исключает воздействие окружающей среды. Рисунок 3.1 – Блочная диаграмма обучения с учителем Производительность нейронной сети оценивается по терминам среднеквадратической ошибки или сумме квадратов ошибок. На основе значений можно выстроить многомерную поверхность ошибки на координатах. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 30

Решения с учителем для конкретных пар вход-выход отмечается точкой на поверхности координат. Чтобы повысить производительность сети по времени, значение ошибки на координатах должно смещаться к минимуму на общей поверхности ошибок. Для реализации повышения производительности НС должна иметь в своей базе знаний полезную информацию о градиенте поверхностей ошибок для текущего поведения. Градиентом здесь выступает вектор, который определяет кратчайший спуск по выстроенной поверхности ошибок. При обучении с учителем происходит мгновенная оценка вектора, который является функцией времени. Если для системы регулярно предоставлять примеры на парах входвыход, задавать алгоритмы действий для минимизации функции стоимости, а также устанавливать продолжительный срок обучения – можно научить нейронную сеть самостоятельно и эффективно решать задачи по классификации и аппроксимации функций. 3.2 Обучение без учителя Вышеописанный процесс обучения находится под руководством учителя. Другая парадигма обучения без учителя самим названием подчеркивает отсутствие учителя, который контролирует процесс установления весовых коэффициентов. При использовании такого подхода не существует маркированных примеров, по которым проводится обучение сети. В этой альтернативной парадигме можно выделить два метода. 3.2.1 Обучение с подкреплением В обучении с подкреплением установление отражения входных сигналов во выходные выполняется в процессе взаимодействия с внешней средой с целью увеличения общего рейтинга производительности. На рисунке 3.2 показана Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 31

блочная диаграмма одной из форм системы обучения с подкреплением, который включает блок критики, преобразующий первичный сигнал подкрепления, полученный из внешней среды, в сигнал более высокого качества, называемый эвристическим сигналом подкрепления [3]. Все эти сигналы являются скалярными. Эта система подразумевает обучение с задержанным подкреплением. Это означает, что система получает извне последовательность возбуждающих сигналов (то есть, векторов состояния), приводящих к генерации эвристического сигнала подкрепления. Цель обучения – минимизация функции цены перехода, определенной как математическое ожидание кумулятивной цены действий, которые предприняты за нескольких шагов, а не только текущей цены. Может стать, что некоторые совершённые раньше в этой последовательности действия были решающими в формировании общего поведения системы целиком. Функция обучаемой машины, которая составляет второй элемент системы, распознает такие действия и формирует на основе них сигнал обратной связи, который направляется ко внешней среде. Рисунок 3.2 – Блочная диаграмма обучения с подкреплением Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 32

Реализация на практике обучения с отложенным подкреплением осложняется двумя причинами. – Нет учителя, который формирует желаемый отклик на каждом этапе обучения. – Из-за задержки формирования первичного сигнала подкрепления необходимо решить временную задачу присваивания коэффициентов доверия. Это означает, что обучаемая машина должна уметь присваивать коэффициенты недоверия и доверия действиям, которые выполняются на всех этапах, которые приводят к конечному результату. Первичный сигнал подкрепления формируется лишь на основании конечного результата. Вопреки этим сложностям, системы обучения с отложенным подкреплением очень привлекательны. Они являются базисом систем, которые взаимодействуют с внешней средой, формируя тем самым способность самостоятельного разрешения появляющихся задач на основании только собственного результата взаимодействия со средой. Обучение с подкреплением тесно связано с динамическим программированием – методологией, созданной Беллманом в 1957 году в контексте теории оптимально управления [118]. Динамическое программирование реализует математический формализм последовательного принятия решений. 3.2.2 Обучение без учителя При использовании методики без учителя отсутствует контроль за процессами настройки весовых коэффициентов. Здесь нет конкретных примеров на действие любых входящих данных при обучении НС. Процесс обработки массивов информации строится на основе предоставленных параметров качества для решаемой задачи. Все статистические закономерности, которые поступают из внешней среды, формируются нейронной сетью и кодируются по Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 33

установленным признакам входящих сигналов с последующим созданием нужных классов. Рисунок 3.3 – Блочная диаграмма обучения без учителя Для такой методики обучения эффективным приемом становится правило конкурентного обучения. Как пример, нейронную сеть создают из двух слоев входных и выходных сигналов. На первый слой отправляются данные. На второй слой передается информация, а нейроны в составе сети конкурируют между собой на получение права отклика. Но конкуренция возможно только в том случае, если входной сигнал удовлетворяет всем признакам для отбора. Говоря об обучении без учителя, стоит выделить алгоритм обучения по Хеббу. Он состоит в следующем. 1) На стадии инициализации всем весовым коэффициентам присваиваются небольшие случайные значения. 2) На входы сети подается входной образ, и сигналы возбуждения распространяются по всем слоям обычным образом: для каждого нейрона рассчитывается взвешенная сумма его входов, к которой затем применяется активационная (передаточная) функция нейрона, в результате чего получается : Æ; его выходное значение U , E—>r / ÆF s ?, E—: , где / Æ – число нейронов в слое n. 3) На основании полученных выходных значений нейронов по формулам Хебба производится изменение весовых коэффициентов. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 34

4) Цикл повторяется с шага 2, пока выходные значения сети не застабилизируются с заданной точностью. Применение этого способа определения завершения обучения обусловлено тем, что подстраиваемые значения синапсов фактически не ограничены. Обучение по Кохонену проводится так же, с тем лишь отличием, что на шаге 3 из всего слоя выбирается нейрон, значения синапсов которого максимально походят на входной образ, и подстройка весов по формуле Кохонена проводится только для него. Особый интерес представляют сети Хопфилда и Хэмминга, поскольку по приведенной классификации они не принадлежат, строго говоря, ни к одному из классов. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 35

4 Разработка и анализ алгоритмов работы сети Хопфилда 4.1 Нейронная сеть Хопфилда Сеть Хопфилда состоит из одного слоя нейронов. Число нейронов равно числу входов и выходов сети. Каждый нейрон связан синапсами со всеми остальными нейронами, а также с одним из входов. Структурная схема сети приведена на рисунке 4.1 Рисунок 4.1 – Структурная схема сети Хопфилда Сеть Хопфилда позволяет решать следующую задачу: пусть имеется набор двоичных сигналов, которые считаются образцовыми. Сеть должна уметь по неидеальному (зашумленному) сигналу распознать образцовый, либо же сообщить о том, что входные данные не соответствуют ни одному из образцов. Представим такой сигнал в виде вектора : L <T ª E—>r J F s ?Æ E—: =, T — <F s E s =, где n — число нейронов сети (отсюда видно, что размерность входного и выходного сигнала должна быть равна числу нейронов сети). Обозначим вектор, соответствующий k-ому образцу, за : , а его элемент — за , Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 36

T Æ G —>r I F s ?Æ G —: . Если сеть сможет распознать зашумленный сигнал, выходной вектор Y будет равен соответствующему образцу : , в противном случае, выходной вектор не совпадет ни с одним из образцов (скорее всего, на выходе окажется сигнал, составленный из различных кусков образцовых). На стадии инициализации сети весовые коэффициенты синапсов устанавливаются следующим образом: ?5 9 L ^ T T Æ EM FÆ ˝ @4 (5) rÆ E L FÆ где i и j — индексы, соответственно, предсинаптического и постсинаптического нейронов; T , T — i-ый и j-ый элементы вектора k-ого образца. Нулевая проводимость синапса при i = j обозначает на самом деле отсутствие синапса, ведущего на тот же нейрон, с которого он берет начало. Далее сеть функционирует по следующему алгоритму: 1) на входы сети подается неизвестный сигнал; 2) рассчитывается новое состояние нейронов: Æ? 5 O: L E s ; L ˝ S U : L; Æ FL r J F sÆ (6) @4 и новые значения аксонов: U : L E s ; L B O: L E s ; Æ (7) где f — активационная функция в виде скачка (рисунок 2.4(а), справа); Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 37

3) если значения аксонов на за последнюю итерацию изменились — переход к пункту 2, иначе (если выходы застабилизировались) — конец. При этом вектором выходных значений является образец, объективно сочетающийся с входными данными. 4.2 Методы нахождения кратчайшего пути Обеспечение эффективного применения сетевых ресурсов считается одной из основных задач маршрутизации. При этом основой математического решения задачи маршрутизации сетевого трафика в имеющихся протоколах (EIGRP, RIP, BGP, OSPF, IS-IS и пр.) является модель нахождения кратчайшего пути на графах. Ряд предложенных эвристических решений приустающий в некоторых по сфере управления сетевыми ресурсами в телекоммуникационной системе (ТКС), обладаем общим недостатком, которое выражается невысоком качестве получаемых решений. Это обстоятельство создается проблемы при реализации для работы в реальном времени для протоколов, а также необоснованное использование канальных и кэшируемых ресурсов [6]. Разработка и применение новых методов решения задач администрирования ТКС сетевых ресурсов и проблемы маршрутизации является выходом из сформировавшейся ситуации. Например, существующие протоколы обеспечивают периодическую или апериодический (при необходимости) перерасчет управляющих воздействий (таблицы маршрутизации, используя порядок каналов и буферных ресурсов) в соответствии с текущим состоянием изменения ТХС. Как правило, при осуществлении этих протоколов считаются незначительным количеством системных параметров, которые установлены в административном или определенных пути статистического усреднения результатов измерений. Однако, следует иметь в виде, что ТКС – это сложная динамическая многопараметрическая и слабо детерминированная система, позволяющий для возможности реализации различных стратегий управления и Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 38

методы управления. Следовательно, для достижения необходимого уровня адекватности математического описания ТКС в оптимальном управлении своими ресурсами возможно лишь в рамках моделей, учитывающих динамические характеристики системы. В данной работе, в целях повышения адекватности математического описания ТКС предлагается рассмотреть возможность использования для решения задачи маршрутизации Хопфилда нейронной сети. В типичном случае решение проблемы маршрутизации (определение кратчайшего пути) будет рассматриваться граф G: ) L :8Æ . ;Æ (8) где V – множество вершин, с количеством вершин равным N, а каждая вершина представляет собой узел (маршрутизатор) ТКС; L – множество рёбер графа, каждый из которых моделирует связь между узлами. Число рёбер графа равно М. %L c? gÆ (9) где ? – стоимость передачи пакета между узлами i и j. При этом предполагается, что ? и ? . Путь P от узла s к узлу d через вершины графа J ÆEL s Æ 0 , подразумевается упорядоченный набор: 2 L <OÆ J 5Æ J 6Æ Æ @= (10) Тогда, чтобы найти кратчайший путь, критерий C должен определяться минимумом следующего выражения: ˙ L˝ ˙ ˝ ? Q MÆ (11) @5 @5 Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 39

где Q – доля интенсивности пвходящего в ТКС потока, протекающего между узлами i и j. Как правило, должны быть выполнены правила, чтобы сохранить поток ТКС в узел, который может быть записан в следующем виде: ˙ ˙ Q F ˝ Æ (12) sÆ ¨˛¸ EL OÆ ¨˛¸ EL @Æ L ] FsÆ rÆ ¯ ¸— ˛ˆ (13) ˝ @5 • Q L @5 • где Q —<r Æ s= Решение задач поиска кратчайшего пути методами полиномиальных алгоритмов было продемонстрировано и описано в работе [7]. На основе этих алгоритмов является разработка современных полиномиальных- алгоритмических методов оптимизации. Одним из способов решить задачи маршрутизации являются нейронные сети. Одним из первых научных трудов по решению маршрутизации написал Хопфилд [8]. В работе [4] рассматривается решение задач оптимизации на примере решения задачи коммивояжера. Решение данной задачи было предложено проводить с использованием нейронной сети с обратными связями, называемой в дальнейшем нейронной сетью Хопфилда [4]. Главным результатом, проделанным в работах [9-12], является применение функции Ляпунова как решающей функции задачи оптимизации. Однако представленная в них функция, давала возможность находить замкнутый путь на графе, длина которого достаточно близка или даже равна минимальному пути: Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 40

’ L 7 E где t m˝ 5 t ˝ ˝ º t • 6 8 Qº F 0 q E ˝ 6 Qº Qº E ˝ ˝ t º ˝ ˝ Qº Q E ˝ º •º ?º Qº kQ ˝ º ˝ Æ> 5 EQ Æ? 5 oÆ (14) •º Æ EL ks Æ vo – весовые коэффициенты, В связи с эти, применение выражения (14) не дает решить в общем виде задачу маршрутизации. Следующий шаг к решению задачи маршрутизации был сделан в работе [5]. Был предложен следующий вид функции Ляпунова: ˙ ?5 ˙ ’ L # ˝ t ˙ ˝ ˙ ?5 ˙ Q ? Q ˝ >5 E @5 @5 @5 t ˝ ˝ ˙ ˝ Q Q E @5 @5 @5 % L˝ t ˙ 6 ˙ ˝ Q F 0 M Æ(15) @5 @5 где A, B, C – также некоторые весовые коэффициенты. Применение этой функции позволяет находить маршруты на произвольном графе и между произвольными узлами s и d, но у нее был существенный недостаток: для нахождения пути была необходимость точно знать количество узлов, которые будут задействованы в формировании пути. Это сильно сужало область применения такого подхода. Функция Ляпунова, представленная в работе [7], которая была усовершенствованием предыдущей, была предложена в работе [4], где ее вид представляется следующей оптимизационной функцией: 6 ˙ ’ L 5 t ˝ ˙ ˙ ? Q E ˝ @5 @5 • ˙ E Лит Изм. № докум. Подп. 8 t ˝ 6 t ˝ ˙ 7 Q E t @5 @5 • ˝ @5 ˙ ¨ ˝ ˙ ˙ Q F ˝ @5 • @5 • ˚ Q ¸ E ˙ Q ks F Q o E ˝ @5 @5 • Дата ˝ ˙ 9 t :s F Q ; (16) БР-02069964-11.03.02-17-18 Лист 41

Это была первая функция Ляпунова, которая решала задачу нахождения кратчайшего пути из узла s в узел d и была нечувствительна к изменению топологии ТКС и к динамическому изменению весов ? . Однако при реализации данной функции оказалось, что с ростом числа узлов в ТКС сеть склонна находить пути неоптимальной длины, а также циклические пути (петли). Для преодоления приведенных трудностей в работе [9] предложена следующая функция Ляпунова: 6 ˙ ’… L 5 t ˝ ˙ ˙ 6 ? Q E ˝ t @5 @5 • ˙ E 8 t ˝ ˙ ˝ ˝ ˙ Q E @5 @5 • 7 t ˝ @5 ˙ ˙ Q ks F Q o E ˝ @5 @5 • 9 t ˝ ˙ ¨ ˝ ˙ ˙ Q F ˝ @5 • Q F @5 • ˚ ¸ E ˙ ˝ Q Q (17) @5 @5 • Эта функция позволяет избежать циклических петель при нахождении пути и обеспечивает быструю сходимость к оптимальному решению, составляющему маршрут наименьшей длины. Но для еще более быстрой сходимости в работе [10] предложена усовершенствованная функция Ляпунова: ’ ”¸ L ’ … ˙ ˝ ˙ ˙ — ˛ E ˝ ˝ n ˝ Q F s r fiQ6 E t ˛˛ @5 @5 @5 • Æ ˇ • : ˙ ˝ ˙ ˙ — ; ˛ 6 E ˛˝ ˝ n ˝ Q F s r fiQ t ˛ @5 @5 @5 • Æ ˇ • (18) Как видно (18) – это развитие функции (17) путем ввода двух дополнительных слагаемых, обеспечивающих более быструю сходимость расчетной процедуры. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 42

Последующее развитие идей маршрутизации с применением нейронной сети Хопфилда получено в работе [11]. Предложенная в данной статье функция Ляпунова (энергии нейронной сети) выглядит так: ˙ ’ ˜` 5 L t ˙ E 7 t ˝ @5 ˙ ¨ ˝ ˝ ˙ ˙ ˙ :s F ? ;? r E nQ ˝ ˝ @5 • @5 @5 • ˙ ˙ Q F ˝ @5 • Q F @5 • ˙ E где Q L \ L \ s Æ¨˛¸ sÆ ¨˛¸ ¯˚ ¯˚ Применение ˇ¨˙ 9 t ˝ ˚ ¸ ˙ E ˚˛ˆˇ¸ rÆ ¯ ˙˘ˇ ˝ 8 t ˝ ˙ Q E ˝ @5 @5 • ˙ ˝ Q ks F Q o E @5 @5 • ˙ nQ ˝ @5 @5 • t 6 ˙ ˝ 6 Q r Æ (19) @5 • E¸ Fˆ¯¯¨ ˛ˆ¨ Æ ¯ ¨¨—¸¸ ˇ¨˙ ˚˛ˆˇ¸ E¸ F—¨¨¯¨ rÆ ¯ ˙˘ˇ ˛ˆ¨ функции (19) позволяет получить большую скорость сходимости решений для довольно большого количества узлов в ТКС. В работе [12] сделан анализ возможностей использования для решения задачи маршрутизации нейронных сетей, которые отличны от сетей Хопфилда. Полученные при этом данные говорят о том, что более приемлемыми для решения задач данного вида являются именно нейронные сети Хопфилда. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 43

5 Практическая реализация искусственной нейронной сети 5.1 Выбор среды проектирования Реализацию численного алгоритма, используемого для моего исследования, начато с прототипирования с помощью Matlab, но затем проект был переведен проект на C++, чтобы получить улучшение производительности в 10 до 100 раз. Есть много тонкостей работы обоих языков программирования: 1) Matlab является языком сценариев, но C++ компилируется. Matlab использует jit-компилятор для перевода скрипта в машинный код, однако, можно улучшить скорость не более чем в 1,5-2 раза, используя компилятор, который предоставляет Matlab. 2) Matlab код может быть в состоянии – полностью векторизован, но существует возможность оптимизировать свой код вручную в C++. Полностью векторизованный код Matlab может вызывать библиотеки, написанные на C++/C/Assembly. Но простой C++ код может быть достаточно векторизован современными компиляторами. 3) Наборы инструментов и подпрограммы, которые предоставляет Matlab, должны быть очень хорошо настроены и иметь разумную производительность. Кроме процедур линейной алгебры, производительность обычно плохая. Причины, по которым можно получить производительность 10x~100x в C++ по сравнению с векторизованным кодом Matlab: 1) Вызов внешних библиотек (MKL) в Matlab стоит времени. 2) Память в Matlab динамически выделяется и освобождается. Например, для умножения малых матриц требуется создание 2 временных матриц. А в C++, память выделяется вручную. И если это повторять 1000 раз, то происходит заметное увеличение производительности. Другое решение в C++ предоставляется C++11 Rvalue reference. Это одно из самых больших улучшений в C++ – код может быть так же быстр, как простой C код. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 44

3) При выполнении параллельной обработки, модель Matlab является многопроцессной, а путь C++ – многопоточным. Если у вас есть много небольших задач, требующих параллелизации, C++ обеспечивает линейный выигрыш до многих потоков, но у вас может быть отрицательный прирост производительности в Matlab. 4) Можно передать большие объекты, кусок памяти по ссылке в C++, но это довольно сложно в Matlab. 5) Векторизация в C++ включает использование встроенных функций / сборок, и иногда векторизация SIMD возможна только в C++. 6) Указатели творят чудеса в C++. Обмен изображениями двух матриц A и B: в Matlab он включает в себя 3-ю матрицу и требует 3*N*N элементарных операций копирования. Но в c++ это делается указателями с близкой к нулю стоимостью. 7) В C++ опытный программист может полностью избежать промаха кэша L2 и даже промаха кэша L1, тем самым подталкивая процессор к теоретическому пределу пропускной способности. Производительность Matlab может отставать от C++ в 10 раз только по этой причине. 8) В C++, интенсивные вычислительные инструкции иногда могут быть сгруппированы в соответствии с их задержками и зависимостей, таким образом, что теоретические IPC (инструкции на тактовый цикл) может быть достигнуто и процессорные конвейеры заполнены. Тем не менее, время разработки в C++ также является фактором 10x по сравнению с Matlab. Причины, по которым нужно использовать Matlab вместо C++: 1) Визуализация данных. Графики и модели C++ требуют больших временных затрат. 2) Низкая эффективность, но математически надежный встроенный процедур и инструментов. Сначала получить правильный ответ, а затем говорить Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 45

об эффективности. Люди могут делать небольшие ошибки в C++ (например, неявно преобразовывать double в int) и получать правильные результаты. 3) Код Matlab намного легче читать и намного короче, чем C++, и код Matlab может быть правильно выполнен без компилятора. Поскольку после векторизации кода Matlab программисту остается не так много для оптимизации, производительность кода Matlab гораздо менее чувствительна к качеству кода по сравнению с кодом С++. Поэтому лучше всего оптимизировать алгоритмы вычислений в Matlab, и незначительно лучшие алгоритмы обычно имеют незначительно лучшую производительность в Matlab. С другой стороны, тестирование алгоритмов на С++ требует от приличного программиста писать алгоритмы, оптимизированные более или менее таким же образом, и убедиться, что компилятор не оптимизирует алгоритмы по-другому. Поскольку нейронная сеть Хопфилда работает в тесном взаимодействии матриц, а C++ обеспечивает гораздо большую производительность по сравнению с Matlab, именно C++ был использован для моделирования работы нейронной сети. 5.2 Разработка программного кода Для проектирования была использована функция Ляпунова (19), предложенная в работе [11]. Эта функция является улучшенным вариантом (18) и из-за этого представляет интерес для дополнительных научных исследований и проверок. В проектируемой нейронной сети содержится 40x40 нейронов 8 L Q , соответствующих количеству узлов в сети. Блок схема работы алгоритма представлена на рисунке 5.1. При запуске программы пользователь вводит значения посещаемых узлов. В программе предоставляется возможность инициализации переменных при каждом Пуске или же единожды, для большей вариативности. После ввода узлов происходит последовательный перебор направлений. В каждом направлении проверяется Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 46

достижение указанной точки. Это происходит при расчете состояния нейронов через функцию активации, заданную сигмоидом. После того как весовые коэффициенты примут установившееся значение происходит проверка достижения узла. Если проверка пройдена, происходит переход на следующий отрезок маршрута, иначе происходит подсчет стоимости и вывод маршрута. Рисунок 5.1 – Блок схема работы алгоритма Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 47

5.3 Анализ полученных данных При проектировании искусственной нейронной сети Хопфилда для решения задачи маршрутизации и нахождения пути оптимальной длины будут использоваться ТКС с количеством узлов равным 40, представленной на рисунке 5.1. Чтобы найти путь минимальной длины и выразить процесс более полно, необходимо понять роль функции (19) и весовых коэффициентов 5 Æ 6 Æ7 Æ 8 Æ9 . Рисунок 5.2 – Структура ТКС с 40 узлами Первая составляющая функции (19), а также коэффициент 5 отвечают за скорость поиска минимальной стоимости передачи пакетов по маршруту из узла s в узел d. Введение компонента функции при коэффициенте 6 обусловлено использованием при поиске только существующих соединений. Например, не все дуги в графе могут существовать, т.е. не все маршрутизаторы подключены друг к другу, поэтому коэффициент ? будет равен бесконечности. В этом случае , отвечающий за связь между узлами, будет равен 1. При решении задач Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 48

маршрутизации это обеспечивает исключение несуществующих дуг за счет устранения внесения в маршрут несуществующих связей. Составляющая с коэффициентом 7 добавлено, чтобы гарантировать выполнение требование сохранения потока в узле в соотношении с условием (12). Чтобы убедиться, что условие Q —<r Æ s = выполнено, вводится член функции с коэффициентом 8, не позволяя получить преимущество какому либо нейрону. В процессе реализации поиска решения задачи маршрутизации нужно определить алгоритм изменения весов соединений в нейронной сети. Для этого определяется матрица весов в сети 7 L Q . В некоторых случае изменение весов связей в ИНС может быть выполнено с использованием следующего выражения: Q Q ’ L F F P Q (20) Используя метод градиентного спуска, можно минимизировать функцию активации и найти стабилизированное состояние сети Хопфилда, чтобы обеспечить кратчайший путь между узлами s и d. 5.3 Анализ полученных данных Значения коэффициентов нейронной сети, использованных в опытах, приведены в таблице 5.1. Результаты, полученные в результате работы, показанные в таблице 5.2, дают сведения о направлениях, проведенных в опытах, и процентной доле лучших путей. Таблица 5.1 – Коэффициенты нейронной сети Параметр 5 6 7 Значение 550 2550 1500 Лит Изм. № докум. Подп. Дата 8 250 9 1350 1 БР-02069964-11.03.02-17-18 ª 1 Лист 49

Таблица 5.2 – Результаты проектирования Соотношение оптимальных маршрутов, % Множество заданных O\ @ 1, 7, 15 95 1, 7, 8 97 1, 10 ,15, 26 87 1, 9 ,15, 19, 23 94 1, 9 ,15, 19, 23, 34 92 1, 22 73 1, 26 Маршрут не был найден за отведенное время Результаты, полученные в результате работы, показанные на рисунках 5.3 и 5.4, дают сведения о направлениях и процентной доле лучших и оптимальных путей в общем множестве рассчитанных маршрутов при реализации всех опытов. 3 3 94 1->8->7->9->7->15->18->19->20->22->23 1->4->6->9->7->15->18->19->20->22->23 1->5->7->9->7->15->18->19->20->22->23 Рисунок 5.3 – Результаты для маршрутов {1, 9 ,15, 19, 23} Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 50

5 11 11 73 1->8->7->13->21->22 1->8->7->14->20->22 1->8->15->14->20->22 1->5->7->14->20->22 Рисунок 5.4 – Результаты для маршрутов {1, 22} Из результатов видно, что, алгоритм применим для сетей малого объема (<20). Обеспечивает высокую оптимальность маршрута. Время затраченной на поиск всего маршрута варьируется от 10мс до 30мс. Также был проведен анализ работы сети при включении всего лишь одного цикла параллельной обработки полученной информации. Это дало прирост производительности в 2 раза, что еще раз подтверждает высокую продуктивность нейронных сетей при параллельном обрабатывании информации. Применение таких языков программирования как JAVA или Golang, могут обеспечить рост скорости работы алгоритма в десятки раз. Функциональный код программы приведен в приложении А. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 51

ЗАКЛЮЧЕНИЕ Сегодняшние искусственные нейросети представляют из себя устройства, которые используют огромное количество искусственных нейронов и нейронных связей. Невзирая на то, что цель разработки нейросетей – абсолютное моделирование человеческого мышления так и не достигнута, уже в наше время из применяют для решения огромного числа задач обработки изображений, управления робототехникой и непрерывными производствами, для синтеза и понимания речи, для диагностики болезней и технических неисправностях в приборах и машинах, для предсказания валютных курсов и пр. Если перейти на более прозаический уровень, то нейросети – это всего лишь сети, которые состоят из связанных простых элементов формальных нейронов. Центром используемых представлений выступает идея, что нейроны можно смоделировать относительно простыми автоматами, а сложность человеческого мозга, гибкость его работы и другие ключевые качества определяются нейронными связями. В отличие от микропроцессорных цифровых систем, которые представляют из себя сложные комбинации запоминающих и процессорных блоков, основанные на нейронных сетях нейропроцессоры, содержат память, которая распределена в связях между простыми процессорами. Таким образом, основные нагрузки на реализацию функций процессорами лежит на архитектуре системы, а её детали в свою очередь определяют межнейронные связи. Созданные на подобной структуре прототипы нейронных компьютеров выдают стандартные решения многих нестандартных задач. Необходимо отметить, что главное назначение сети Хопфилда – решать задачи обработки образов (ассоциативная память и фильтрация). Но, они позволяют находить решения комбинаторных задач оптимизации, если из можно сформулировать как задачи минимизации энергии. Если подобную сеть привести в случайное начальное состояние, то можно ждать, что результирующие Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 52

стабильное состояние предоставит субоптимальный путь, длиной не слишком превосходящим оптимальный, а может и со значительными отличиями от оптимального. Как следствие, для практического использования сеть необходимо запустить несколько раз, а потом выбрать лучший путь. Решение этой задачи является интересным не столько качеством (есть алгоритмы, которые решают её эффективнее), сколько подходом к оптимизационным задачам: если реально перевести условия какой-либо задачи в параметры нейронных связей, то сеть может её относительно неплохо решить без дополнительного анализа. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 53

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1 Томас М. Структура и реализация сетей на основе протокола OSPF, 2-е изд.: Пер. с англ. / М. Томас – М.: Издательский дом «Вильямс», 2004. – 816 с. 2 Фейт С., TCP/IP Архитектура, протоколы, реализация, 2-е изд. / С. Фейт – М.: Издательский дом «Лори», 2000. – 450 с. 3 Бакланов И. Г. NGN: принципы построения и организации / И. Г. Бакланов; под ред. Ю.Н. Чернышова. – М.: Эко-Трендз, 2008. – 400 с. 4 Хайкин С. Нейронные сети: полный курс. 2-е изд.: пер. с англ. / С. Хайкин – М.: Издательский дом «Вильямс», 2006. – 1105 с. 5 Grossberg S. Z. Neural Networks and Natural Intelligence / S. Z. Grossberg – Cambridge МА: MIТ Press, 1988. – 131-137 pp. 6 Обзор и сравнительный анализ основных моделей и алгоритмов многопутевой маршрутизации в мультисервисных телекоммуникационных сетях / [В. В. Поповский, А. В. Лемешко, Л. И. Мельникова и др.]. // Прикладная радиоэлектроника. – 2005. – 372-382 c. 7 Бертсекас Д. Сети передачи данных: Пер. с англ. / Д. Бертсекас, Р. Галлагер – М.: Мир, 1989. – 544 с. 8 Hopfield J.J. Neural computations of decisions optimization problems / J.J. Hopfield, D. W. Tank – Biol. Cybern Vol. 52, 1986. – 141-152 pp. 9 Zhang L. Neural network implementation of the shortrest path algorithm for trac routing in communication networks / L. Zhang, C. A. Thomopoulos – In Proceedings of International Conference Neural Networks, 1989. – 591 p. 10 Ali M. Neural networks for shortest path computation and routing in computer networks / M. Ali, F. Kamoun – IEEE Trans. on Neural Networks Vol. 4, No. 6, 1993. – 941-953 pp. 11 Park D.C. A Neural Network based Multi-destination Routing Algorithm for Communication Network / D.C. Park, S.E. Choi // Proc. of IJCNN, 1998. – 1673-1678 pp. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 54

12 Ahn C.W. Neural Network Based Near-Optimal Routing Algo-rithm / C.W. Ahn, R.S. Ramakrishna – Proc. of ICONIP Vol. 4, 2002. – 1771-1776 pp. 13 Dong-Chul P. A shortest path routing algorithm using Hopﬁeld neural network with an improved energy function / P Dong-Chul, K. Kyo-Reen – International Journal of General Systems Vol. 38, No. 7, 2009. – 777-791 pp. 14 Mehmet Ali. Neural Networks for Shortest Path Computation and Routing in Computer Networks / Ali Mehmet, Mustafa K., Faouzi Kamoun – IEEE transactions on neural networks, Vol. 4, No 6, 1993. – 941-954 pp. 15 Kulvir Kaur. Shortest path routing problem in networks and optimization algorithms / Kaur Kulvir. – М.: LAP Lambert Academic Publishing, 2012. – 80 p. 16 Khadija Fatima. A Study on Migration and Labour Market Outcomes in Pakistan / Fatima Khadija. – М.: LAP Lambert Academic Publishing, 2012. – 176 p. 17 Лавренков Ю. Н. Исследование и разработка комбинированных нейросетевых технологий для повышения эффективности безопасной маршрутизации информации в сетях связи / Ю. Н. Лавренков – К.: МГТУ им. Н. Э. Баумана (калужский филиал), 2012. – 208 с. 18 Павленко М. А. Решение задачи маршрутизации на основе использования нейронной сети Хопфилда с разработкой функции Ляпунова с заданными свойствами / М. А. Павленко, А. А. Романюк, В. Ю. Яковлев // Электронное научное специализированное издание – журнал «Проблемы телекоммуникаций», 2012. – 43-57 с. 19 Комарцова Л. Г. Нейрокомпьютеры. / Л. Г. Комарцова, А.В. Максимов. – М.: МГТУ им. Н. Э. Баумана, 2004. – 400 с. 20 Ярушкина Н. Г. Основы теории нечетких и гибридных систем. / Н. Г. Ярушкина – М.: Финансы и статистика, 2009. – 320 с. 21 Советов Б. Я. Представление знаний в информационных системах / Б. Я. Советов, В.В. Цехановский, В.Д. Чертовской – М.: Академия, 2012. – 144 с. 22 Барский А. Б. Логические нейронные сети / А. Б. Барский – М.: Интернет-университет информационных технологий, Бином. Лаборатория Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 55

знаний, 2007. – 352 с. 23 Костров Б. В. Архитектура микропроцессорных систем. / Б. В. Костров, В. Н. Ручкин – М.: Диалог-МИФИ, 2007. – 304 с. 24 Яхъяева Г. Э. Нечеткие множества и нейронные сети / Г. Э. Яхъяева – М.: Интернет-университет информационных технологий, Бином. Лаборатория знаний, 2011. – 320 с. 25 Романов В. П. Информационные технологии моделирования финансовых рынков / В. П. Романов, М. В. Бадрина – М.: Финансы и статистика, 2010. – 288 с. Лит Изм. № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 56

ПРИЛОЖЕНИЕ А (обязательное) Функциональный код программы Листинг A.1 – Главная функция программы. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 Лит Изм. #include #include #include #include #include #include #include #include #include "stdafx.h" "cmath" "iostream" "conio.h" "ctime" <string> <time.h> <windows.h> <ppl.h> using namespace std; using namespace concurrency; // ----- Число узлов и количество назначений ----- // #define NODE 20 #define TNODE 2 // ----- Общие параметры ----- // #define DELTA 0.0001 #define TAU 1 #define LAMBDA 1 //----#define #define #define #define #define Коэффиценты Park & Choi's -----// PARK_A 550 PARK_B 2550 PARK_C 1500 PARK_D 250 PARK_F 1350 double U[NODE][NODE]; double V[NODE][NODE]; double Cost[NODE][NODE]; int Gamma[NODE][NODE]; int SD[TNODE]; int SD_order[TNODE][NODE]; int randomize() { int a = 10; int b = 1000; return rand() % (b - a + 1) + a; } № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 57

43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 Лит Изм. //----- Сигмоид -----// double Sigmoid_Function(double in) { return(1 / (1 + exp(-LAMBDA*in))); } // ----- Номера узлов источника и получателей ----- // void Loading_Source_Desination(int Node, int Tnode) { // ----- Номера узлов источника и получателей ----- // SD[0] = 1; SD[1] = 7; for (int i = 0; i<Tnode; i++) { for (int j = 0; j<Node; j++) { SD_order[i][j] = -10; } } } //----- Значение phi -----// double PHI_Value(int a, int s, int d) { double Value; if (a == s) Value = 1.0; else if (a == d) Value = -1.0; else Value = 0.0; return(Value); } // ----- Верность пути от источника до получателя ----- // int Check_Valid_Path(int order, int number, int s, int d) { int Visit = -1, Count = 0, Position = 0, Value = 0; for (int i = 0; i<number; i++) { if (V[s][i]>0.8) { SD_order[order][0] = s; SD_order[order][1] = i; Visit = i; Position = i; Count = 3; } } if (d == Visit) { Value = Visit; № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 58

96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 Лит Изм. } else { for (int i = 0; i<number - 2; i++) { for (int j = 0; j<number; j++) { if (V[Position][j]>0.8) { if (d == j) { SD_order[order][Count - 1] = j; Visit = j; Value = Visit; } else { SD_order[order][Count - 1] = j; Count++; Position = j; } } } } } return(Value); } // ------- Подсчет количество путей из источника до получателя ------- // int Path_Count(int order, int number) { int count = 0; for (int i = 0; i<number; i++) { if (SD_order[order][i] != -10) count++; } return(count); } // ------- Стоимость между каждым источником и получателем ------- // double Cost_Value_Save(int order, int count) { double Cost_Sum = 0.0; for (int i = 0; i<count - 1; i++) { Cost_Sum += Cost[SD_order[order][i]][SD_order[order][i + 1]]; } return(Cost_Sum); } // ------- Получения пути следования ------- // string Get_Path(int order, int count) { string path = ""; for (int i = 0; i<count - 1; i++) { № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 59

149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 Лит Изм. path += to_string(SD_order[order][i] + 1) + "->"; if (order == TNODE - 2 && i == count - 2) { path += to_string(SD_order[order][i + 1] + 1); } } return(path); } //-----Park & Choi часть мю1-----// double Park_A_Term(int i, int j) { return(Cost[i][j]); } //-----Park & Choi часть мю2-----// double Park_B_Term(int i, int j) { return((double)Gamma[i][j]); } //----- Park & Choi часть мю3.1 -----// double Park_C_first_Term(int i, int s, int d, int Node) { double Sum = 0.0; for (int k = 0; k<Node; k++) { if (k != i) Sum += (V[i][k] - V[k][i]); } return(Sum - PHI_Value(i, s, d)); } //----- Park & Choi часть мю3.2 -----// double Park_C_second_Term(int j, int s, int d, int Node) { double Sum = 0.0; for (int k if (k != Sum += } return(Sum = 0; k<Node; k++) { j) (V[j][k] - V[k][j]); - PHI_Value(j, s, d)); } //----- Park & Choi часть мю4 double Park_D_Term(int i, int { return(1.0 - 2.0*V[i][j]); } //----- Park & Choi часть мю5 double Park_F_Term(int i, int { № докум. Подп. Дата -----// j) -----// j) БР-02069964-11.03.02-17-18 Лист 60

202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 Лит Изм. return((double)Gamma[i][j] * V[j][i]); } //----- Park & Choi общая -----// double Park_Update_Function(int i, int j, int s, int d, int Node) { double Value = 0.0; Value = U[i][j] + DELTA * (-U[i][j] / (double)TAU - 0.5*PARK_A*Park_A_Term(i, j) - 0.5*PARK_B*Park_B_Term(i, j) - PARK_C * Park_C_first_Term(i, s, d, Node) + PARK_C * Park_C_second_Term(j, s, d, Node) - 0.5*PARK_D*Park_D_Term(i, j) - 0.5*PARK_F*Park_F_Term(i, j) - 0.5*PARK_A*Cost[i][j] - 0.5*PARK_B*(double)Gamma[i][j] + PARK_C*PHI_Value(i, s, d) - PARK_C*PHI_Value(j, s, d) - 0.5*PARK_D ); return(Value); } //-----Пересчет состояний неронов-----// void Park_Hopfield_NN(int s, int d, int Node) { parallel_for(0, Node, [&](int x) { for (int i = 0; i<Node; i++) { U[x][i] = Park_Update_Function(x, i, s, d, Node); V[x][i] = Sigmoid_Function(U[x][i]); } }); } void main() { __int64 start, end, tps; QueryPerformanceFrequency((LARGE_INTEGER *)&tps); string Path = ""; int Check = -1; int Number, Epoch, Count; double T_Cost = 0.0; Loading_Source_Desination(NODE, TNODE); Loading_Link_Information(NODE); № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 61

255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 } Лит Изм. QueryPerformanceCounter((LARGE_INTEGER *)&start); for (int Order = 0; Order < TNODE - 1; Order++) { Number = NODE; Initialize_Value(NODE); Epoch = 0; while (SD[Order + 1] - 1 != Check && Epoch <= 10005) { Epoch++; Park_Hopfield_NN(SD[Order] - 1, SD[Order + 1] - 1, Number); Check = Check_Valid_Path(Order, Number, SD[Order]-1,SD[Order+1]-1); } if (Epoch >= 10000) { cout << "Алгоритм не сходится при данных условиях" << endl; break; } // --- Подсчитываем количество путей обхода для каждого S->D --- // Count = Path_Count(Order, Number); //---Общая длина---// T_Cost += Cost_Value_Save(Order, Count); Path += Get_Path(Order, Count); } QueryPerformanceCounter((LARGE_INTEGER *)&end); double time = ((double)(end - start) / tps) * 1000.; cout << "Time: " << Time << "ms" << endl; system("pause"); № докум. Подп. Дата БР-02069964-11.03.02-17-18 Лист 62

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв