Рандомизированные алгоритмы распределения ресурсов в адаптивных мультиагентных системах тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Мальковский Николай Владимирович

• Мальковский Николай Владимирович
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Мальковский Николай Владимирович

1.1 Потоковые процессы

1.1.1 Оптимальные динамические процессы

1.1.2 Динамические потоковые процессы

1.1.3 Стохастические потоковые процессы

1.2 Метод проталкивания предпотока для потоковых задач линейного

программирования

1.2.1 Задача о максимальном потоке

1.2.2 Задача о параметрическом потоке

1.3 Две потоковых задачи мультиагентного распределения ресурсов

1.3.1 Задача балансирования загрузки в сети

1.3.2 Сбор информации группой БПЛА

2 Два метода построения оптимальных потоковых процессов в нестационарном случае

2.1 Метод на основе усредняемых функций

2.1.1 Класс усредняемых функций

2.1.2 Динамические потоковые процессы с меняющимися во времени пропускными способностями

2.1.3 Подбор параметров алгоритма в

стохастическом случае

2.2 Адаптивный метод основанный на рандомизированной стохастической

аппроксимации

2.2.1 Общая схема метода балансирования дуг

2.2.2 Сходимость методов

2.2.3 Сходимость синхронного алгоритма

2.2.4 Сходимость рандомизированного алгоритма

2.2.5 Извлечение решения задачи о

максимальном потоке

2.2.6 Реализация алгоритмов в мультиагентных

системах

3 Экспериментальные результаты

3.1 Пакет прикладных программ для симуляции процесса

распределения загрузки

3.2 Эффективное решение задачи о

параметрическом потоке

3.3 Тестирование алгоритмов

балансирования загрузки

Заключение

Литература

Список иллюстраций

Список таблиц

Введение диссертации (часть автореферата) на тему «Рандомизированные алгоритмы распределения ресурсов в адаптивных мультиагентных системах»

Введение

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

Все рассматриваемые в работе модели подразумевают отыскание некоторого оптимального по времени процесса (выполнение группы заданий за наименьшее время, передача набора сообщений в группе мобильных роботов за наименьшее время). В теории управления, основная масса работ по построению оптимальных динамических процессов основана на принципе динамического программирования [46] и принципе максимума Понтрягина [30]. В случае отсутствия неопределенностей и изменений параметров системы во времени, рассматриваемые задачи вырождаются в задачи математической оптимизации. В общем виде такие задачи рассматривались Канторовичем [19] (общая теория линейного программирования), Хачияном [33] (метод эллипсоидов), Поляком [29] (общая теория выпуклой оптимизации), Кармаркаром [77] (полиномиальный метод внутренней точки для задач линейного программирования), Нестеровым и Немировским [90] (полиномиальные методы для задач нелинейной выпуклой оптимизации), Бойдом и Ванденберге [52] (современная теория оптимизации) и многими другими.

Для диссертационной работы особую роль играют свойства задач потокового типа, большое значение имеет задача о максимальном потоке и задача о потоке минимальной стоимости (Форд и Фалкерсон, [64]), задача о параметрическом потоке (Галло, Григориадис и Тарьян [65]). Эти задачи являются базовыми статическими потоковыми задачами. Во многих случаях изучение протекающих во времени потоковых процессов может быть сведено к рассмотрению стационарных потоковых задач. Так, например, в работах Теодоровича и Вукадиновича [103], Холла [39], Кассета [55], Гасникова [37] рассмотрены статические методы моделирования транспортных потоков, в работах Форда и Фалкерсона [62], Ску-теллы [99] рассмотрены динамические потоковые процессы, задачи нахождения оптимального процесса со статическими пропускными способностями и временами перехода сведены к статическим потоковым задачам. Несмотря на более полувека с момента появления, постановки этих задач, допускающие неопределенности некоторых характеристик, появились относительно недавно в работах Глокнера и Немхаузера [67], Хана, Пенга и Ванга [72], Шенга и Гао [98]. При этом, на данный момент отсутствуют работы, изучающие потоковые задачи в условиях динамически изменяющихся параметров и внешних неконтролируемых возмущений.

Задачи, рассматриваемые в диссертационной работе, мотивированны изменчивостью и стохастической природой реальных физических процессов. Задачи математической оптимизации в условиях различного рода неопределенностей изучались в работах работах Роббинса и Монро [96] (общий метод стохастической аппроксимации), Кифера и Воль-фовица [79] (метод конечных разностей), Калмана и Бьюси [75] (фильтр Калмана-Бьюси), Винера и Колмогорова [104] (фильтр Винера-Колмогорова), Граничина [12, 14] (решение оптимизационных задач с нестатистическими помехами), Кампи и Калафиоре [54] (сценарный подход), Хлебникова, Поляка и Кунцевича [34]. В работах Бенвенисте, Мети-вье и Приоро [48], Бодсона и Дугласа [50], Антал, Граничина и Леви [44] изучаются адаптивные алгоритмы, в работах Парфенова и Орехова [27], Копетца [82], Мельникова и Мельниковой [26] изучаются смежные вопро-

сы о системах реального времени.

Следующие работы рассматривают схожие с поставленными в диссертационной работе прикладными задачами: в работах Тантави и Таус-ли [101], Кима и Камеды [80], Чогууна и Камеды [57] рассматриваются алгоритмы оптимального статического балансирования загрузки для типовых сетей (звезда, кольцо и т.п.) с достаточно общими предположениями о пропускной способности сети. В работе Гросу и Хронопулоса [70] рассматриваются игровые модели задачи распределения нагрузки. Стохастические постановки задач распределения ресурсов появились относительно недавно и были предложены в работах Амелиной [5], Амелиной и Фрадкова [6], Граничина и Амелиной и др. [42].

Большинство из перечисленных работ составляют общий математический фундамент задачи распределения ресурсов, лишь небольшая часть работ изучает особенности реализации математических методов в муль-тиагентных системах. Основной сложностью такой реализации является децентрализованность. Традиционная парадигма параллельных вычислений подразумевает наличие центрального узла, имеющего информацию о всем вычислительном процессе. В мультиагентных системах такие узлы обычно отсутствуют, что значительно упрощает построение системы и её масштабируемость, однако во многих случаях затрудняет вычислительный процесс. Один из общих вопросов, изучению которого направлена эта работа, - возможна ли эффективная реализация классических методов оптимального распределения ресурсов в мультиагентных системах? В работе получен положительный ответ для нескольких конкретных задач распределения ресурсов, основанных на решении потоковых задач оптимизации. Алгоритмы такого рода обычно называются распределенными или мультиагентными и широко используются на практике: в работах Бойда и др. [51], Шаха [97], Кемпе и др. [78] изучаются применение распределенных алгоритмов, называемых "сплетнями", в работах Маггса и др. [85], Хе и др. [73] изучаются алгоритмы синхронизации времени в распределенных сетях, в работах Манфреди [88], Жу и др. [105] изучаются алгоритмы согласования показаний сенсорных сетей,

в работах Олфати-сабера и Мюррея [91], Факса и Мюррея [59], Рена и др. [94], Рикоса и др. [95], Амелиной [5], Амелиной и Фрадкова [6], Пар-сегова, Полякова и Щербакова [93] изучаются протоколы консенсуса и их приложения, в работах Каляева, Гайдука и Капустяна [17,18], Факса и Мюррея [59] рассматриваются задачи коллективного взаимодействия групп мобильных роботов.

Как уже было отмечено, общее преимущество мультиагентного подхода заключается в простоте организации и масштабируемости системы. Детально особенности таких систем были изучены в работах Виттиха и Скобелева [9], Скобелева, Соллогуба, Иващенко и др. [32], Ржевского [31], Городецкого [10], Городецкого, Грушинского и Хабалова [11].

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

1. Исследовать возможность применения методов оптимизации динамических процессов потокового типа для эффективного распределения ресурсов в мультиагентных сетях.

2. Разработать и обосновать новые алгоритмы эффективного распределения ресурсов в мультиагентных сетях.

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

4. Реализовать исследованные методы и провести их апробацию для решения задач распределения ресурсов в мультиагентных сетях в

условиях неопределенностей и изменяющихся со временем параметров сети и окружающей среды.

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

Основные положения, выносимые на защиту.

1. Предложена формулировка класса задач мультиагентного распределения ресурсов в виде задачи нахождения оптимального динамического процесса потокового типа.

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

3. Доказана асимптотическая оптимальность первого разработанного метода в случае усредняемых пропускных способностей (теоремы 2.1 и 2.2) и получены оценки скорости сходимости для второго метода (теорема 2.6).

4. Разработана программная реализация предложенных методов.

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

Научная новизна. Все основные научные результаты диссертации являются новыми.

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

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

Аппробация работы. Материалы диссертации докладывались на семинарах кафедры системного программирования, кафедры теоретической кибернетики СПбГУ, на российских и международных конференциях по программированию, информатике, оптимизации и теории управления: всероссийское совещание по проблемам управления ВСПУ-2014, VI, VII, VIII традиционных всероссийских молодежных летних школах "Управление, информация и оптимизация" (2014, 2015, 2016), 1st Conference on Modelling, Identification and Control of Nonlinear Systems (MICNON, 2015), 12th IFAC International Workshop on Adaptation and Learning in Control and Signal Processing (ALCOSP, 2016). По результатам работы была зарегистрирована программа для разработки и тестирования алгоритмов распределения загрузки вычислительной сети №2016661548 [38].

Публикации. Основные результаты работы опубликованы в [2,16, 22-25,41,86,87] из них две публикации в журналах, входящих в перечень рецензируемых научных журналов, в которых ложны быть опубликованы основные научные результаты диссертаций на соискание ученой степени кандидата наук, [23,25], три публикации в периодических изданиях, входящих в базу SCOPUS [41,86,87]. Работы [2,16,41] написаны в соавторстве. В [2,16] автору принадлежит общее математическое описание задач распределения ресурсов. В [41] автору принадлежит описание связи "сплетен", задачи консенсуса и Simultaneous Perturbation Stochastic Approximation (SPSA) метода.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы, включающего 1G5 источников. Текст занимает 1G3 страницы, содержит 12 рисунков и одну таблицу.

Содержание работы

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

В первой главе приводятся общие сведения о потоковых задачах линейного программирования: максимального потока, параметрического потока; сформулирована общая задача оптимального потокового динамического процесса и его стохастическая вариация, описаны две задачи мультиагентного распределения ресурсов.

В пункте 1.1 представлена общая специфика потоковых процессов, описано, как эта специфика интерпретируется в различных практических ситуациях, перечислены основные математические модели и задачи, схожие с теми, которые рассматриваются в диссертационной работе. В пункте 1.1.1 описана общая задача нахождения оптимального процесса (задача быстродействия) и описано сведение этой задачи к математической оптимизации. В пункте 1.1.2 описана специфика задач нахождения оптимальных потоковых процессов. В пункте 1.2 подробно описаны задачи о максимальном потоке, задача о параметрическом потоке и эффективные алгоритмы решения этих задач. В пункте 1.3 описаны две практические задачи мультиагентного распределения ресурсов.

Во второй главе описаны два метода построения потоковых процессов. В пункте 2.1.1 описан класс усредняемых функций и приведены основные свойства такие функций. В пункте 2.1.2 показано, что для потоковых процессов с усредняемыми пропускными способностями допустимо построение субоптимального процесса через "усредненную" модель, доказана асимптотическая оптимальность такого подхода. В пункте 2.1.3 приведен пример построения оценок задержки для случая случайных процессов. В пункте 2.2.1 описана общая схема метода балансирования дуг для вспомогательной задачи, в пунктах 2.2.2-2.2.4 проанализирована скорость сходимости методов, в пункте 2.2.5 описан способ получения решения задачи о максимальном потоке из решения вспомогательной за-

дачи, в пункте 2.2.6 описаны реализации методов в мультиагентных или распределенных системах.

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

В пункте 3.1 приведено описание пакета прикладных программ, разработанного для симуляции процесса распределения загрузки в сети, в пункте 3.2 описана реализация эффективного алгоритма для решения задачи о параметрическом потоке и приведены результаты экспериментального сравнения с библиотекой А. Гольдберга. В пункте 3.3 приведены результаты симулирования процессов распределения загрузки с использованием разработанных методов и метода, основанного на протоколе локального голосования.

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

Глава 1

Потоковые процессы и их приложение в задачах мультиагентного распределения ресурсов

1.1 Потоковые процессы

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

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

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

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

ются машины, ребра - дороги / улицы, узлы - пересечение дорог / улиц.

жидкость или газ, ребра - трубы, узлы - трубопроводные краны, распределительные станции.

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

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

Длина, время перехода

Л

Пропускная \ способность Л

VI_

Рис. 1.1: Параметры дуги в транспортной сети.

2. Частицы потока проходят по ребру не мгновенно, а на протяжении некоторого интервала времени.

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

Ключевым аспектом этой работы является изучение динамических моделей потоковых процессов, т.е. таких моделей, которые учитывают изменения со временем различных аспектов системы и окружающей среды. Во многих случаях изучение протекающих во времени потоковых процессов может быть сведено к рассмотрению стационарных потоковых задач. Так, например, в [37,39,55,103] рассмотрены статические методы моделирования транспортных потоков, в [62] и [99] рассмотрены динамические потоковые процессы, задачи нахождения оптимального процесса со статическими пропускными способностями сведены к статическим потоковым задачам. Работы [62,81,99] имеют постановки, схожие с рассматриваемыми в этой работе, и, в том числе, показывают актуальность этих задач. Эти работы имеют прямое отношение к задаче о максимальном потоке и задаче о потоке минимальной стоим,ости, введенным в [64]. Несмотря на более полувека с момента появления, постановки этих задач, допускающие неопределенности некоторых характеристик, появились относительно недавно (см. [67,72,98]). При этом, на данный

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

1.1.1 Оптимальные динамические процессы

Традиционно, динамика управляемой системы (с непрерывным временем) описывается уравнением

(1.1) X = I(х, и),

где х(1) = (х\(£),..., хп(£))т £ X - вектор состояния (фазовые переменные), и(£) = (п\(1),... , пто(£))т £ и - управляющее воздействие. Далее, задана некоторая функция д(х, и) - целевой функционал минимизации, который можно интерпретировать как "сложность" или "стоимость" управления и в состоянии х, в фазовом пространстве выделены два вектора (краевые условия) х-,х+ £ X. Оптимальной траекторией системы (1.1), переводящей систему из состояния х- в состоянне х+ по отношению к функционалу д(^, •) является траектория х : [0,т] ^ Кп, х(£) £ X и соответствующее ей управление и : [0,т] ^ и(£) £ и, кото-

и

минпмнзирует функционал (1.2)

(1.2) Г д(х(£), и(£))^

Jo

и удовлетворяет граничным условиям (1.3)

(1.3) х(0) = х-, х(т) = х+.

В случае д(-, •) = 1 значение функционала (1.2) равно т, а задача заключается в нахождении наименьшего возможного времени перевода системы из состояния х- в состоян не х+. Далее в работе будут рассматри-

ваться только такие задачи.

Основными инструментами анализа задач оптимальных процессов являются уравнение Беллмана (динамическое программирование [46] и принцип максимума [30]). Если правая часть (1.1) не зависит от x, то ни уравнение Беллмана, ни принцип максимума не дают никакой полезной информации. С точки зрения теории оптимального управления такие задачи являются вырожденными, а основная сложность заключается в нахождении решений некоторых статических оптимизационных задач. Дальнейший анализ формально показывает вырожденность такого класса задач (формулировки принципа максимума и уравнения Беллмана для задач оптимального управления приведены в [30]).

Пусть ф Е Rn, определим функцию H как

H (ф, x, u) = фт f (x, u).

Согласно принципу максимума, если u*(t) - такое управление (1.1), что выполняются граничные условия (1.3) и при этом т принимает минимальное возможное значение, то существует такая функция '(t) Е Rn, что вдоль траектории движения выполняются условия

(1.4) Vt Е [0,т] : H('(t),x(t),u*(t)) = supH('(t),x(t),u),

ueU

(1.5)

и

d' dt

dH д x

(1.6) Н(ф(т), х(т), и*(т)) > 0.

Пусть теперь /(х, и) не зависит от х, т.е. /(х, и) = ^(и). Тогда обе части (1.4) не зависят от х. Тогда в силу (1.5) ф(£) не зависит от а значит для любой допустимой траектории х(£) можно взять ф тождественно

равной 0n = (0, . „ , О)T.

n

Согласно принципу динамического программирования, существует функция w(x), такая что

(1.7) sup Vw (x)T f (x, u) = 1,

u eU

w(x) < 0 w(x+) = 0. Физический смысл функции w(-) заключается в том, что "—w(x)" - минимальное время, за которое можно добраться из x в x+. При фиксироваином x управление u, на котором (1.7) достигает

x

Таким образом, оптимальное управление u*(t) удовлетворяет

Vt e [0,т] : Vw(x(t))Tf (x(t), u*(t)) = 1.

Для траектории x(t), порождаемой оптимальным управлением u*(t), вектор ^(t) = Vw(x(t))T удовлетворяет (1.5), (1.6) и (1.4), при этом в последнем правая часть равна единице, что не позволяет взять ^(t) = 0n для f (x, u) = F(u). Подставив F(u) вместо f (x, u) в (1.7) получаем, что Vw(x) не зависит от x, а значит ш(^) есть линейная функция, что позволяет сделать вывод, что оптимальное управление приходит в точку x+ по прямой (при условии сугцествования функции ш).

Пусть теперь F(u) = Bu, вектор состояния x(t) принадлежит в любой момент времени некоторому выпуклому множеству X, множество допустимых управляющих воздействий U также является выпуклым. Собрав вместе все условия, получаем следующую задачу

минимизировать т,

x = B u,

(1.8)

при условии

x(0) = x-; x(t) = x+, x(t) e X, u(t) e U.

Предположим теперь, что (t*, u*) - оптимальное решение (1.8). Pac-

смотрим

и =— и*.

Т * Л

Так как У£ Е [0,т*] : и*(£) Е и и и выпукло получаем

*

1 г

и(£) = -* и* Е и. т ,/0

В силу системы получаем, что

+

х(т *) = х- + / В и = х- + / В и* = х

Так как управляющее воздействие постоянно, порождаемая траектория имеет вид х(£) = х- + Т*(х+ — х-), в силу выпуклости ограничений ж«(£) Е X и факта, что х- и х+ - допустимые состояния, получаем, что и - допустимое управление. Так как при этом оно переводит систему в состояние х+ за оптимальное время т*, то и является оптимальным управлением. Таким образом выполнено следующее утверждение.

Лемма 1.1. Если в задаче (1.8) пропускные способности не зависят от времени, се(£) = се? то существует оптимальное управление, не зависящее от времени, т. е. функция и(^) = и7 являющаяся решением (1.8).

Теперь, учитывая вышесказанное, можно избавиться от динамической составляющей (1.8): так как любая линейная траектория, переводящая систему из х- в х+ допустима (в силу выпуклости X), то для нахождения минимального времени перехода достаточно решать следующую задачу оптимизации

минимизировать г,

и и.

(1.9) \ тВи = х+ - х

при условии

Таким образом, для построения оптимального процесса в задаче (1.8)

т *

т *

т *

0

0

достаточно решить статическую оптимизационную задачу (1.9). Стоит обратить внимание, что при т > 0 можно поделить первое условие (1.9) па т и сделать замену Л = -1, получая при этом

Такая задача проще, чем (1.9), так как содержит только линейные неравенства. Учитывая выпуклость и, задача подпадает под класс задач выпуклой оптимизации, подробно изученной во многих работах (см. [52,

1.1.2 Динамические потоковые процессы

Здесь и далее будем предполагать, что дан некоторый ориентированный граф О = (V, Е), описывающий сеть и взаимодействие внутри этой сети. V - множество вершин, Е € V х V - множество дуг и пусть IV| = п, |Е| = ш. В этой сети циркулирует поток, для которого можно выбирать "интенсивность" (или скорость) движения по дуге. Если по дуге (г, ^) € Е за некоторый интервал времени прошел единичный поток, то это означает, что этот единичный поток сначала находился на вершине г, затем перебрался па вершину Далее считаем, что на каждой вершине содержится неограниченное хранилище, которое может хранить частицы потока, и обозначим через - количество потока, находящееся на вершине г в момент времени В силу физических причин основное возникающее ограничение - пропускная способность дуг, ограничивающая сверху количество передаваемого потока по дуге за единицу времени. Обозначим за с = (с1,..., ст)т - вектор пропускных способностей. Для потоковых процессов х- является начальным распределением потока по

максимизировать Л,

при условии

В и = Л(х+ - х-), и е и.

90]).

сети, x+ - желаемое распределение. Пусть В - матрица инцидентности:

1, e выходит из i, Bie = ^ -1, e входит в i,

О в остальных случаях.

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

(1.10)

минимизировать г,

при условии

X = B u,

x(0) = x-; х(т) = x+ x(t) > 0,

0 < Ue(t) < Ce.

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

Список литературы диссертационного исследования кандидат наук Мальковский Николай Владимирович, 2017 год

Литература

[1] Амелин К. С., Граничин О. П., Кияев В. П., Иевлев П. В. Мобильность и супервычисления на охране природы // Компьютер-Информ. - 2011. - № 05-06, - С. 24-25.

[2] Амелин К. С., Граничин О. П., Мальковский П. В. Распределение ресурсов в контексте мультиагентных систем // сборник трудов 12 всероссийского совещания по проблемам управления ВСПУ-2014. -2014. - С. 9003-9013.

[3] Амелин К. С. Рандомизация в контуре управления легкого БПЛА при полете в условиях неизвестных изменений направления ветра // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления. - 2013. - № 2.

- С. 86-102.

[4] Амелин К. С. Технология программирования легкого БПЛА для мобильной автономной группы // Стохастическая оптимизация в информатике. - 2011. - Т. 7. - № 1. - С. 93-115.

[5] Амелина П. О. Применение протокола локального голосования для децентрализованной балансировки загрузки сети с переменной топологией и помехами в измерениях // Вестник Санкт-Петербургского университета. Серия 1. Математика. Механика. Астрономия. - 2013.

- Т. 46. Л" 3. - С. 118-125.

[6] Амелина П. О., Фрадков А. Л. Приближенный консенсус в стохастической динамической сети с неполной информацией и задержками в измерениях // Автоматика и телемеханика. - 2012. - № 11. -С. 6-29

[7] Ампилова П. В., Романовский И. В., Петренко Е. И. О максимизации энтропии при линейных ограничениях // Труды Междунар. науч. конференции «Космос, астрономия и программирование (Лавровские чтения)». - 2008. - С. 181-185.

[8] Батюков А. М. Анализ цифровых изображений, основанный на построении стационарного потока на графе // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления. - 2015. - № 2. - С. 115-122.

[9] Вит/тих В. А., Скобелев П. О. Мультиагентные модели взаимодействия для построения сетей потребностей и возможностей в открытых системах // Автоматика и телемеханика. - 2003. Л'° 1. С. 177-185.

[10] Городецкий В. И. Самоорганизация и многоагентные системы. II. Приложения и технология разработки // Известия РАН. Теория и системы управления. - 2012. Л'° 3. С. 55-75.

[11] Городецкий В. И., Грушипский М. С., Хабалов А. В. Многоагентные системы (обзор) // Новости искусственного интеллекта. - 1998. -Т. 2. - С. 64-117.

[12] Граничин О. Н. Процедура стохастической аппроксимации с возмущением на входе //Автоматика и телемеханика. - 1992. - № 2. - С. 97-104.

[13] Граничин О. Н. Оценивание параметров линейной регрессии при произвольных помехах // Автоматика и телемеханика. - 2002. Л'° 1. - С. 30-41.

[14] Граничин О. Н. Рандомизированные алгоритмы стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. - 2002. - № 2. - С. 44-55.

[15] Граничин О. Н. Поисковые алгоритмы стохастической аппроксимации с рандомизацией на входе // Автоматика и телемеханика. - 2015. _ № 5. _ с. 43-59.

[16] Граничин О. Н., Мальковский Н. В. Задача распределения ресурсов в контексте мультиагентных систем // Стохастическая оптимизация в информатике. - 2013. - Т. 9. - № 2. - С. 41-53.

[17] Каляев И. А., Гайдук А. Р., Капуст,ян С. Г. Модели и алгоритмы коллективного управления в группах роботов. М.: Физматлит. -2009. - 280 с.

[18] Каляев И. А., Гайдук А. Р., Капустян С. Г. Распределенные системы планирования действий коллективов роботов. М.: Янус-К. -2002. - 292 с.

[19] Канторович Л. В. Математические методы организации и планирования производства. - Издательство ЛГУ. - 1959.

[20] Карзанов А. В. Нахождение максимального потока в сети методом предпотоков // Доклады академии наук СССР. - 1974. - Т. 215. -№ 1. - С. 49-52.

[21] Левитин Е. С., Поляк Б. Т. Методы минимизации при наличии ограничений // Журнал вычислительной математики и математической физики. - 1966. - Т. 6. - № 5. С. 787-823.

[22] Малъковский П. В. Модель балансировки загрузки в вычислительной сети с использованием задачи параметрического потока // Стохастическая оптимизация в информатике. - 2014. - Т. 10. - № 1. -С. 39-62.

[23] Малъковский П. В. Актуальность задачи максимального потока в применении к современным вычислительным сетям // Компьютерные инструменты в образовании. - 2014. - № 4. - С. 3-9.

[24] Малъковский П. В. О числе Фидлера и асимптотической скорости сходимости лапласиановых систем // Стохастическая оптимизация в информатике. - 2015. - Т. 11. - № 2. - С. 30-35.

[25] Малъковский П. В. Рандомизированный распределенный адаптивный алгоритм решения задачи о максимальном потоке // Компьютерные инструменты образования. - 2016. - № 5, С. 46-61.

[26] Мельников Б. Ф., Мельникова Е. А. Кластеризация ситуаций в алгоритмах реального времени в некоторых задачах дискретной оптимизации // Изв. вузов (Поволжский регион), естественные науки. -2007. - С. 3-11.

[27] Парфенов В. В., Терехов А. П. ЯТЯТ-технология программирования встроенных систем реального времени // Системная информатика. - 1997. - № 5. - С. 228-256.

[28] Поляк Б. Т. Новый метод типа стохастической аппроксимации // Автоматика и телемеханика. - 1990. - № 7. - С. 98-107.

[29] Поляк Б. Т., Введение в оптимизацию. - М.:Наука. Гл. ред. физ.-мат. лит. - 1983. - 384 с.

[30] Понтрягин Л. С. Математическая теория оптимальных процессов.

- Гос. изд-во Физико-математической лит-ры. - 1961. 392 с.

[31] Ржевский Д. Мультиагентные системы в логистике и е-коммерции / / Консалтинговая компания iTeam [Электронный ресурс], URL:http: / / iteam.ru / publications/logistics / section_80 / article_ 2689

[32] Скобелев П. О., Соллогуб А. В., Иващенко А. В. и др. Мультиагентные технологии в задачах дистанционного зондирования Земли // Труды XIII Международной конференции «Проблемы управления и моделирования в сложных системах». Самара: СНЦ РАН. - 2011.

- С. 426-434.

[33] Хачиян Л. Г. Полиномиальные алгоритмы в линейном программировании // Журнал вычислительной математики и математической физики. - 1980. - Т. 20. Л" 1. С. 51-68.

[34] Хлебников М. В., Поляк Б. Т., Кунцевич В. М. Оптимизация линейных систем при ограниченных внешних возмущениях (техника инвариантных эллипсоидов) // Автоматика и телемеханика. - 2011.

И. - С. 9-59.

[35] Библиотека для решения задачи о максимальном потоке [Электронный ресурс], URL:http://www.avglab.com/andrew/soft/hipr.tar (дата обращения 01.09.2016)

[36] Библиотека для решения задачи о параметрическом потоке [Электронный ресурс], URL: http://research.microsoft.com/en-us / downloads / d3adb5f7-49ea-4170-abde-ea0206b25de2 / default.aspx (дата обращения 01.09.2016)

[37] Введение в математическое моделирование транспортных потоков / Под ред. Гасникова А. В. - Московский центр непрерывного математического образования. - 2015. - 426 с.

[38] Система моделирования потоквых процессов в вычислительной сети [Электронный ресурс], URL: https://github.com/Malkovsky/load-balancing (дата обращения 01.09.2016)

[39] Handbook of Transportation Science / Под ред. Hall R.. - Springer Science & Business Media. - 2012. - 532 p.

[40] Alakeel A. M. A guide to dynamic load balancing in distributed computer systems // International Journal of Computer Science and Information Security. - 2010. - Vol. 10. ..V" 0. P. 153-160.

[41] Amelina N., Erofeeva V., Granichin O., Malkovskii N. Simultaneous perturbation stochastic approximation in decentralized load balancing problem // IFAC-PapersOnLine. - 2015. - Vol. 48. - № 11. - P. 936-941.

[42] Amelina N., Granichin O., Granichina O., Jiang Y. Differentiated consensuses in decentralized load balancing problem with randomized topology, noise, and delays // In: Proc. of the 53rd IEEE Annual Conference on decision and control (CDC). - 2014. - P. 6969-6974.

[43] Amelin K., Amelina N., Granichin 0., Granichina O., Andrievsky B. R. Randomized algorithm for uavs group flight optimization // In: Proc. of the 11th IFAC International Workshop on Adaptation and Learning in Control and Signal Processing. - 2013. - P. 205-208.

[44] Anta,I G., Granichin 0., Levi S. Adaptive autonomous soaring of multiple uavs using simultaneous perturbation stochastic approximation // In: Proc. of the 49th IEEE Annual Conference on Decision and Control (CDC). - 2010. - P. 3656-3661.

[45] Babenko M.. Goldberg A. V. Experimental Evaluation of a Parametric Flow Algorithm. - Technical report, Microsoft Research, 2006. MSR-TR-2006-77.

[46] Bellman R. E., Dreyfus S. E. Applied Dynamic Programming. - 1962.

- 365 p.

[47] Bertsekas D. P. Dynamic Programming and Stochastic Control. - 1976.

[48] Benveniste A., Metivier M.. Priouret P. Adaptive algorithms and stochastic approximations. - Springer Science & Business Media. - 2012.

- T. 22. - 364 p.

[49] Blum J. R. Multidimensional stochastic approximation methods // The Annals of Mathematical Statistics. - 1954. - P. 737-744.

[50] Bodson M.. Douglas S. Adaptive algorithms for the rejection of sinusoidal disturbances with unknown frequency // Automatica. - 1997.

- Vol. 33. - № 12. - P. 2213-2221.

[51] Boyd S., Ghosh A., Prabhakar B., Shah D. Randomized gossip algorithms // IEEE Transactions on Information Theory. - 2006. -Vol. 52. - № 6. - P. 2508-2530.

[52] Boyd S., Vandenberghe L. Convex Optimization. - Cambridge university press. - 2009. - 716 p.

[53] Burkard R. E., Dlaska K., Klinz and B. The quickest flow problem // Zeitschrift fur Operations Research. - 1993. - Vol. 37. A" 1. P. 31-58.

[54] Calafiore G. C., Campi M. C. et a,I. The scenario approach to robust control design // IEEE Transactions on Automatic Control. - 2006. -Vol. 51. - № 5. - P. 742-753.

[55] Cascetta E. Transportation Systems Engineering: Theory and Methods.

- Springer Science & Business Media. - 2013. - 709 p.

[56] Cherkassky B. V., Goldberg A. V. On implementing the push—relabel method for the maximum flow problem // Algorithmica. - 1997. -Vol. 19. - № 4. - P. 390-410.

[57] Chonggun K., Kameda H. Optimal static load balancing of multi-class jobs in a distributed computer system // IEICE TRANSACTIONS (1976-1990). - 1990. - Vol. 73. - № 7. - P. 1207-1214.

[58] Doddini Probhuling L. Load balancing algorithms in cloud computing // International Journal of Advanced Computer and Mathematical Sciences. - 2013. - Vol. 2. - P. 2230-9624.

[59] Fax J. A., Murray R. M. Information flow and cooperative control of vehicle formations // IEEE Transactions on Automatic Control. - 2004.

- Vol. 49. - № 9, P. 1465-1476.

[60] Fiedler M. Algebraic connectivity of graphs // Czechoslovak mathematical journal. - 1973. - Vol. 23. - № 2, P. 298-305.

[61] Fiedler M. Bounds for eigenvalues of doubly stochastic matrices // Linear Algebra and Its Applications. - 1972. - Vol. 5, - № 3. - P. 299-310.

[62] Ford L. R., Fulkerson D. R. Constructing maximal dynamic flows from static flows // Operations research. - 1958. - Vol. 6. - № 3. -P. 419-433.

[63] Ford L. R., Fulkerson D. R. Maximal flow through a network // Canadian journal of Mathematics. 1956. - Vol. 8. ..V" 3. P. 399-404.

[64] Ford L. R., Fulkerson D. R. Flows in Networks. - Princeton Princeton University Press. - 1962. - 195 p.

[65] Gallo G., Grigoriadis M. D., Tarjan R. E. A fast parametric maximum flow algorithm and applications // SIAM Journal on Computing. - 1989.

- Vol. 18. ..V" 1. - P. 30-55.

[66] Garg N., Koenemann J. Faster and simpler algorithms for multicommodity flow and other fractional packing problems // SIAM Journal on Computing. - 2007. - Vol. 37. - № 2. - P. 630-652.

[67] Glockner G. D., Nemhauser G. L. A dynamic network flow problem with uncertain arc capacities: formulation and problem structure // Operations Research. - 2000. - Vol. 48. - № 2. - P. 233-242.

[68] Goldberg A. V., Tarjan R. E. A new approach to the maximum-flow problem // Journal of the ACM (JACM). - 1988. - Vol. 35. - № 4. -P. 921-940.

[69] Goldberg A. V., Tarjan R. E. Efficient maximum flow algorithms // Communications of the ACM. - 2014. - Vol. 57. - № 8. - P. 82-89.

[70] Grosu D., Chronopoulos A. T. noncooperative load balancing in distributed systems // Journal of Parallel and Distributed Computing.

- 2005. - Vol. 65. ..V" 9. P. 1022-1034.

[71] Granichin O., Volkovich V., Toledano-Kitai D. Randomized Algorithms in Automatic Control and Data Mining. - Springer. - 2014. - 251 p.

[72] Han S., Peng Z., Wang S. The maximum flow problem of uncertain network // Information Sciences. - 2014. - Vol. 265. - P. 167-175.

[73] He J., Cheng P., Shi L., Chen J., Sun Y. Time synchronization in wsns: a maximum-value-based consensus approach // IEEE Transactions on Automatic Control. - 2014. - Vol. 59. ..V" 3. P. 660-675.

[74] Herty M.. Kirchner C., Moutari S., Rascle M. et a,I. Multicommodity flows on road networks // Communications in Mathematical Sciences.

- 2008. - Vol. 6. - № 1. - P. 171-187.

[75] Kalman R. E. A new approach to linear filtering and prediction problems // Journal of basic Engineering. - 1960. - Vol. 82. 1. P. 35-45.

[76] Kameda H., Li J., Kim C., Zhang Y. Optimal Load Balancing in Distributed Computer Systems. - Springer Publishing Company Incorporated. - 2011. - 250 p.

[77] Karmarkar N. A new polynomial-time algorithm for linear programming // In: Proc. of the 16th Annual ACM symposium on Theory of computing. - 1984. - P. 302-311.

[78] Kempe D., Dobra A., Gehrke J. Gossip-based computation of aggregate information // In: Proc. of the 44th IEEE Annual Symposium on Foundations of Computer Science. - 2003. - P. 482-491.

[79] Kiefer J., Wolfowitz J. et al. Stochastic estimation of the maximum of a regression function // The Annals of Mathematical Statistics. - 1952.

- Vol. 23. ..V" 3. P. 462-466.

[80] Kim C., Kameda H. An algorithm for optimal static load balancing in distributed computer systems // IEEE Transactions on Computers. -1992. - Vol. 41. A" 3. P. 381-384.

[81] Köhler E., Möhring R. H., Skutella M. Traffic networks and flows over time // In: Algorithmics of Large and Complex Networks. - 2009. -Springer. - P. 166-196.

[82] Kopetz H. Real-Time Systems: Design Principles for Distributed Embedded Applications. - Springer Science & Business Media. - 2011.

- 376 p.

[83] Letchford A. N., Salazar-González, J. J. Stronger multi-commodity flow formulations of the Capacitated Vehicle Routing Problem // European Journal of Operational Research. - 2015. - Vol. 244. A" 3. P. 730-738.

[84] Madry A. Navigating central path with electrical flows: From flows to matchings, and back // In: Proc of the 54th IEEE Annual Symposium on Foundations of Computer Science (FOCS). - 2013. - P. 253-262.

[85] Maggs M. K., O'Keefe S. G., Thiel D. V. Consensus clock synchronization for wireless sensor networks // IEEE sensors Journal. -2012. - Vol. 12. ..V" 6. P. 2269-2277.

[86] Malkovskii N. Asymptotically Optimal Solution for Transportation Problem with Almost ArbitraryCapacities // IFAC-PapersOnLine. -2016. - Vol. 48. - № 11. - P. 936-941.

[87] Malkovskii N. Optimal static network load balancing using parametric flow approach // IFAC-PapersOnLine. - 2015. - Vol. 48. - № 11. -P. 668-673.

[88] Manfredi S. Design of a multi-hop dynamic consensus algorithm over wireless sensor networks // Control Engineering Practice. - 2013. -Vol. 21. - № 4. - P. 381-394.

[89] Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., Teller E. Equation of state calculations by fast computing machines // The Journal of Chemical Physics. - 1953. - Vol. 21. - № 6. P. 1087-1092.

[90] Nesterov Y., Nemirovskii A., Ye Y. Interior-Point Polynomial Algorithms in Convex Programming // Society for Industrial and Applied Mathematics (SIAM). - 1994. - T. 13. 405 p.

[91] Olfati-Saber R., Murray R. M. Consensus problems in networks of agents with switching topology and time-delays // IEEE Transactions on Automatic Control. - 2004. - Vol. 49. ..V" 9. P. 1520-1533.

[92] Orlin J. B. Max flows in O(nm) time, or better // In: Proc. of the 45th annual ACM symposium on Theory of computing. - 2013. - P. 765-774.

[93] Parsegov S., Polyakov A., Shcherbakov P. Nonlinear fixed-time control protocol for uniform allocation of agents on a segment //In: Proc. of the 51st IEEE Annual Conference on Decision and Control (CDC). -2012. - P. 7732-7737.

[94] Ren W., Beard R. W., Atkins E. M. Information consensus in multivehicle cooperative control // Control Systems. - 2007. - Vol. 27. _ ^ 2. - P. 71-82.

[95] Rikos A. I., Charalambous T., Hadjicostis C. N. Distributed weight balancing over digraphs // IEEE Transactions on Control of Network Systems. - 2014. - Vol. 1. - № 2. - P. 190-201.

[96] Robbins H., Monro S. A stochastic approximation method // The Annals of Mathematical Statistics. - 1951. - P. 400-407.

[97] Shah D. Gossip Algorithms. - Now Publishers Inc. - 2008. - 125 p.

[98] Sheng Y., Gao J. Chance distribution of the maximum flow of uncertain random network // Journal of Uncertainty Analysis and Applications. - 2014. - Vol. 2. ..V" 1. P. 1-14.

[99] Skutella M. An introduction to network flows over time //In: Research Trends in Combinatorial Optimization. - 1958. - Springer. - P. 451-482.

[100] Spall J. C. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation / / IEEE Transactions on Automatic Control. - 1992. - Vol. 37. ..V" 3. P. 332-341.

[101] Tantawi A. N., Towsley D. Optimal static load balancing in distributed computer systems // Journal of the ACM (JACM). - 1985. - Vol. 32. -..V" 2. P. 445-465.

[102] Tarjan R., Ward J., Zhang B., Zhou Y., and Mao J. Balancing applied to maximum network flow problems // European Symposium on Algorithms. - 2006. - P. 612-623.

[103] Teodorovic D., Vukadinovic K. Traffic Control and Transport Planning: A Fuzzy Sets and Neural Networks Approach. - Springer Science & Business Media. - 2012. - 385 p.

[104] Wiener N. Extrapolation, Interpolation, and Smoothing of Stationary Time Series. - MIT press Cambridge. - 1949. - Vol. 2. - 159 p.

[105] Zhu, S., Chen C., Li W., Yang B., Guan X. Distributed optimal consensus filter for target tracking in heterogeneous sensor networks // IEEE transactions on cybernetics. - 2013. - Vol. 43. A'0 6. P. 19631976.

Список иллюстраций

1.1 Параметры дуги в транспортной сети................................14

1.2 Расширенный граф (формулировка через т), Для наглядности дуги проиндексированы двумя буквами — началом и концом дуги..........21

1.3 Расширенный граф (формулировка через Л). Для наглядности дуги проиндексированы двумя буквами — началом и концом дуги..........22

1.4 Потоковые задачи в информатике....................................25

Л

breakpoint GGT......................................................37

1.6 Граф для задачи балансирования нагрузки ........................40

1.7 Пример балансирования нагрузки...... ......................41

1.8 Пример траекторий БПЛА и зон взаимодействия....................43

1.9 Общий вид функции пропускных способностей. Основную часть времени пропускная способность равна нулю. Если траектории полета периодичны, то и пропускная способность периодична................43

3.1 Топологии сети, используемые для тестирования............86

3.2 Результаты симуляции для звезды............................88

3.3 Результаты симуляции для кольца со случайными дугами 89

Список таблиц

3.1 Среднее время работы алгоритмов на стандартных топологиях сети............................ 87