Материал: Оптимизация и моделирование в автоматизированных системах

Литература

1.Котенко, А.П. Матричный алгоритм Беллмана–Мура / А.П. Котенко // Управление организационно-экономическими системами. Вып. 10. Самара: Изд-во Самарского гос. аэрокосм. ун-та, 2013. С. 33-37.

2.Котенко, А.П. Сведение задачи о числе кластеров к вычислению кратчайших расстояний на графе / А.П. Котенко, М.С. Щербаков // Перспективные информационные технологии. Труды Международной научно-тех. конференции. Самара: СНЦ РАН, 2016. С. 893-895.

ФГБОУ ВО «Самарский государственный технический университет», Россия

УДК 621.391.1:519.8

М.Ю. Ивашура, О.И. Каляпина

РАЗРАБОТКА НЕЙРОСЕТЕВОЙ МОДЕЛИ ЗАДАЧИ МАРШРУТИЗАЦИИ В СИСТЕМАХ СВЯЗИ ВОЕННОГО НАЗНАЧЕНИЯ И ЕЕ АЛГОРИТМИЗАЦИЯ

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

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

В качестве критериев оптимальности могут быть, например:

1.Пропускная способность канала связи;

2.Загруженность каналов связи;

3.Задержки, вносимые каналами;

4.Количество промежуточных транзитных узлов;

5.Надежность каналов и транзитных узлов.

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

Граф представляет собой совокупность непустого множества вершин и рёбер (наборов пар вершин). Говорят, что две вершины в графе являются смежными, если они соединяются общим ребром. Обозначим cij длину ребра, соеди-

няющего две вершины i и j . Тогда кратчайшим путём из вершины S (исток) в

20

вершину t (сток) будет называться путь, который имеет минимальное значение суммы

При этом необходимо учитывать правила сохранения потока в сети:

1.Из начальной вершины (истока) путь может только выходить.

2.В конечную вершину (сток) путь может только входить.

3.Если путь «зашел» в промежуточную вершину, то он должен из неё и

выйти.

На основе приведенных правил сохранения потока формируются ограничения задачи:

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

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

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

Обозначим узлы, которые может «посетить» пакет, буквами A, B, C, … , а

расстояния между ними − cAB , cAC , cBC … Решением является упорядоченное

множество из n узлов. Последовательность, в которой обходятся узлы, удобно представлять матрицей n× n , строки которой соответствуют узлам, а столбцы номерам узлов в маршруте. Например, имеется пять узлов A, B, C, D, E, а последовательность их обхода задана матрицей.

Таким образом, узел C посещается первым (исток), узел А − вторым и т.д. Узел D посещается последним (сток). Длина маршрута равна cCA + cAE + cEB + cBD

21

В каждом столбце и в каждой строке этой матрицы может быть только одна единица, так как в каждый момент посещается только один узел и каждый узел посещается только один раз. Матрицу вида (3) можно интерпретировать

как состояние нейронной сети из N = n2 нейронов. Задача состоит в том, чтобы из всех допустимых маршрутов выбрать путь с наименьшей длиной. Так как выходом бинарного нейрона может быть только 0 или 1 (промежуточных уровней нет), то текущее состояние сети является двоичным числом, каждый бит которого является выходным сигналом некоторого нейрона. В общем случае система с N нейронами имеет 2N различных состояний и может быть представлена N-мерным единичным гиперкубом. В соответствии с моделью Хопфилда, когда подается новый входной вектор, сеть переходит из вершины в вершину гиперкуба, пока не стабилизируется. В этом случае устойчивая вершина определяется сетевыми весами, текущими входами и величиной порога, благодаря чему сеть ассоциируется с некоторым объектом. Из этого делается заключение о том, что сети Хопфилда обладают ассоциативными возможностями. Сети Хопфилда относятся к классу рекуррентных нейронных сетей, обладающих тем свойством, что за конечное число тактов времени они из произвольного начального состояния приходят в состояние устойчивого равновесия, которое называется аттрактором. Объем ассоциативной памяти сети Хопфилда определяется количеством аттракторов. Недостатком сети Хопфилда является отсутствие гарантии, что стабилизация сети произойдет в точке глобального минимума, есть вероятность, что сеть стабилизируется в локальном экстремуме.

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

Состояние каждого нейрона отобразим двумя индексами, первый из которых соответствует узлу, а второй указывает порядковый номер его посеще-

ния в маршруте. Таким образом, vxj = 1 показывает, что узел x является j-м по

порядку узлом маршрута.

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

22

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

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

тели.

Функция вычислительной энергии рассматриваемой нейронной сети должна удовлетворять следующим требованиям. Во-первых, функция энергии должна быть построена таким образом, чтобы поддерживались устойчивые состояния системы в форме матрицы вида (3). Во-вторых, функция энергии должна из всех возможных решений поддерживать те решения, которые соответствуют наиболее коротким маршрутам. Перечисленным требованиям удовлетворяет функция Ляпунова (4), в которой переменные являются булевыми величинами vxj = 0, 1. Первое, второе и третье слагаемые выражения (4) поддер-

живают правило сохранения потока в сети, четвёртое слагаемое отвечает за минимизацию длины маршрута. Заметим, что первое слагаемое равно нулю, если каждая строка x содержит не больше одной единицы. Второе слагаемое равно нулю, если каждый столбец содержит не более одной единицы. Третье слагаемое обращается в нуль, если в матрице вида (3) содержится ровно n единиц. Таким образом, без учёта четвёртого слагаемого функция энергии E имеет минимальное значение, равное 0, во всех состояниях сети, представленных матрицей с одной 1 в каждом столбце и в каждой строке. Все другие состояния нейронной сети имеют более высокую энергию. Четвёртое слагаемое функции

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

Теперь рассмотрим алгоритм обучения сети Хопфилда для задачи о крат-

гональные элементы матрицы весов равны 0 и она симметрична, т.е. должны задаваться условия wii=0, wij=wji .

23

5. Проверить условие стабилизации сети. Если оно наступило, то решение получено. Если сеть еще не стабилизировалась, то присвоить значениям входных нейронов полученные на шаге 4 значения выходных нейронов и вернуться к шагу 2.

Останов алгоритма можно произвести также по исчерпанию заданного лимита времени или предельного числа итераций (эпох).

Литература

1. Комашинский, В.И. Нейронные сети и их применение в системах управления и связи / В.И. Комашинский, Д.А. Смирнов. – М.: Горячая линия-

Телеком, 2003. – 94 с.

ВУНЦ ВВС ВВА им. профессора Н.Е. Жуковского и Ю.А. Гагарина, Россия

УДК 004.942

К.А. Маковий, Ю.В. Хицкова, Я.В. Метелкин

ПРОЕКТИРОВАНИЕ АВТОМАТИЗИРОВАННОЙ СИСТЕМЫ ОПТИМИЗАЦИИ РАЗМЕЩЕНИЯ ВИРТУАЛЬНЫХ МАШИН

ВЦЕНТРАХ ОБРАБОТКИ ДАННЫХ

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

24