Оптимальное управление распространением вирусов: аналитические и численные результаты::Журнал СА 1-2.2017
www.samag.ru
     
Поиск   
              
 www.samag.ru    Web  0 товаров , сумма 0 руб.
E-mail
Пароль  
 Запомнить меня
Регистрация | Забыли пароль?
Журнал "Системный администратор"
Журнал «БИТ»
Подписка
Архив номеров
Где купить
Наука и технологии
Авторам
Рекламодателям
Контакты
   

  Опросы
  Статьи

Дата-центры  

Дата-центры: есть ли опасность утечки данных?

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

 Читать далее...

Книжная полка  

Защиты много не бывает

Среди книжных новинок издательства «БХВ» есть несколько изданий, посвященных методам социальной инженерии

 Читать далее...

Событие  

В банке рассола ждет сисадмина с полей фрактал-кукумбер

Читайте впечатления о слете ДСА 2024, рассказанные волонтером и участником слета

 Читать далее...

Организация бесперебойной работы  

Бесперебойная работа ИТ-инфраструктуры в режиме 24/7 Как обеспечить ее в нынешних условиях?

Год назад ИТ-компания «Крок» провела исследование «Ключевые тренды сервисного рынка 2023». Результаты

 Читать далее...

Книжная полка  

Читайте и познавайте мир технологий!

Издательство «БХВ» продолжает радовать выпуском интересных и полезных, к тому же прекрасно

 Читать далее...

СУБД PostgreSQL  

СУБД Postgres Pro

Сертификация по новым требованиям ФСТЭК и роль администратора без доступа к данным

 Читать далее...

Критическая инфраструктура  

КИИ для оператора связи. Готовы ли компании к повышению уровня кибербезопасности?

Похоже, что провайдеры и операторы связи начали забывать о требованиях законодательства

 Читать далее...

Архитектура ПО  

Архитектурные метрики. Качество архитектуры и способность системы к эволюционированию

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

 Читать далее...

Как хорошо вы это знаете  

Что вам известно о разработках компании ARinteg?

Компания ARinteg (ООО «АРинтег») – системный интегратор на российском рынке ИБ –

 Читать далее...

Графические редакторы  

Рисование абстрактных гор в стиле Paper Cut

Векторный графический редактор Inkscape – яркий представитель той прослойки open source, с

 Читать далее...

День сисадмина  

Учите матчасть! Или как стать системным администратором

Лето – время не только отпусков, но и хорошая возможность определиться с профессией

 Читать далее...

День сисадмина  

Живой айтишник – это всегда движение. Остановка смерти подобна

Наши авторы рассказывают о своем опыте и дают советы начинающим системным администраторам.

 Читать далее...

Виртуализация  

Рынок решений для виртуализации

По данным «Обзора российского рынка инфраструктурного ПО и перспектив его развития», сделанного

 Читать далее...

Книжная полка  

Как стать креативным и востребованным

Издательский дом «Питер» предлагает новинки компьютерной литературы, а также книги по бизнесу

 Читать далее...

1001 и 1 книга  
19.03.2018г.
Просмотров: 6311
Комментарии: 0
Машинное обучение с использованием библиотеки Н2О

 Читать далее...

12.03.2018г.
Просмотров: 7020
Комментарии: 0
Особенности киберпреступлений в России: инструменты нападения и защита информации

 Читать далее...

12.03.2018г.
Просмотров: 4302
Комментарии: 0
Глубокое обучение с точки зрения практика

 Читать далее...

12.03.2018г.
Просмотров: 3056
Комментарии: 0
Изучаем pandas

 Читать далее...

12.03.2018г.
Просмотров: 3852
Комментарии: 0
Программирование на языке Rust (Цветное издание)

 Читать далее...

19.12.2017г.
Просмотров: 3868
Комментарии: 0
Глубокое обучение

 Читать далее...

19.12.2017г.
Просмотров: 6359
Комментарии: 0
Анализ социальных медиа на Python

 Читать далее...

19.12.2017г.
Просмотров: 3211
Комментарии: 0
Основы блокчейна

 Читать далее...

19.12.2017г.
Просмотров: 3502
Комментарии: 0
Java 9. Полный обзор нововведений

 Читать далее...

16.02.2017г.
Просмотров: 7322
Комментарии: 0
Опоздавших не бывает, или книга о стеке

 Читать далее...

17.05.2016г.
Просмотров: 10685
Комментарии: 0
Теория вычислений для программистов

 Читать далее...

30.03.2015г.
Просмотров: 12409
Комментарии: 0
От математики к обобщенному программированию

 Читать далее...

18.02.2014г.
Просмотров: 14050
Комментарии: 0
Рецензия на книгу «Читаем Тьюринга»

 Читать далее...

13.02.2014г.
Просмотров: 9172
Комментарии: 0
Читайте, размышляйте, действуйте

 Читать далее...

12.02.2014г.
Просмотров: 7119
Комментарии: 0
Рисуем наши мысли

 Читать далее...

10.02.2014г.
Просмотров: 5428
Комментарии: 3
Страна в цифрах

 Читать далее...

18.12.2013г.
Просмотров: 4660
Комментарии: 0
Большие данные меняют нашу жизнь

 Читать далее...

18.12.2013г.
Просмотров: 3465
Комментарии: 0
Компьютерные технологии – корень зла для точки роста

 Читать далее...

04.12.2013г.
Просмотров: 3191
Комментарии: 0
Паутина в облаках

 Читать далее...

03.12.2013г.
Просмотров: 3434
Комментарии: 0
Рецензия на книгу «MongoDB в действии»

 Читать далее...

02.12.2013г.
Просмотров: 3063
Комментарии: 0
Не думай о минутах свысока

 Читать далее...

Друзья сайта  

 Оптимальное управление распространением вирусов: аналитические и численные результаты

Архив номеров / 2017 / Выпуск №1-2 (170-171) / Оптимальное управление распространением вирусов: аналитические и численные результаты

Рубрика: Наука и технологии

Без фото КЛИМЕНКОВА О.Д., бакалавр МИЭМ НИУ ВШЭ, Москва, по направлению «прикладная математика», odklimenkova@edu.hse.ru

Оптимальное управление распространением вирусов:
аналитические и численные результаты

В работе рассматривается задача управления для SIR-модели эпидемий с переменным количеством узлов. Изучается задача минимизации затрат для модели SIR, управлениями вкоторой выступают «вакцинация» и «лечение» узлов. Исследуются два различных функционала и обсуждаются их особенности. На основе принципа максимума Понтрягина получена структура оптимального управления для каждого функционала. Найдены численные решения с использованием методов пристрелки и Рунге-Кутта 4-го порядка. Исследуется зависимость решения от параметров задачи

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

В связи с тем, что математические модели распространения вирусов описываются системами нелинейных дифференциальных уравнений, многие результаты удается получить только численно. Компьютерное моделирование очень часто проводят с использованием пакета Matlab [1]. Однако следует иметь в виду, что одной из проблем при моделировании процессов заражения остается не выбор среды, где будет проходить моделирование, а корректность поставленной задачи и выбора способа решения.

В настоящей работе рассматривается SIR-модель. В данной модели узлы в сети делятся на три группы:

  • Восприимчивые (S) − это те узлы, которые могут быть заражены вирусом.
  • Зараженные (I) − это уже пораженные вирусом узлы.
  • Восстановленные (R) − это узлы, которые были «вылечены», то есть был удален вирус и установлена антивирусная программа.

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

Такая модель описывается следующими уравнениями:

     

Здесь:

  • u – интенсивность «лечения» Зараженных узлов,
  • β – интенсивность передачи вируса от Зараженных узлов в системе Восприимчивым узлам.

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

Обозначим:

  • u1 − интенсивность «вакцинирования» Восприимчивых,
  • u2 − интенсивность «лечения» Зараженных узлов.

Кроме того, добавим условие, что под действием вируса узлы выходят из строя с интенсивностью α.

Тогда процесс распространения вирусов в сети можно описать следующими дифференциальными уравнениями:

 (1)

 (2)

 (3)

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

В [1] изучается модель SIR. Особенность этой работы в том, что в модели учитывается, что количество узлов в системе может меняться: появляются новые узлы, выходят из строя старые узлы. В работе проведен анализ устойчивости решений.

В [2] модель SIR применяется для исследования распространения ВИЧ-инфекции. В работе доказана теорема о существовании оптимального решения, для поиска минимума функционала используется принцип максимума Понтрягина. Найдена структура оптимального управления. Выведенные уравнения решаются численно.

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

Постановка задачи

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

 (4)

на траекториях системы (1)-(3) с начальными условиями S(0) = S0, I(0) = I0, R(0) = R0.

Функционалы такого вида типичны для задач управления распространением вирусов в сетях [1]-[2]. В этом функционале, с одной стороны, учитывается число «зараженных» узлов (и связанные с этим затраты), с другой стороны, затраты на «лечение» и «вакцинацию» узлов.

В качестве управления рассмотрим параметры u1(t) и u2(t). Будем предполагать, что u1(t) и u2(t) – измеримые, ограниченные на отрезке [0;T] функции:

 (5)

С использованием теоремы Филиппова [5] можно показать, что решение в задаче (1)-(5) существует.

Заметим, что целевой функционал не зависит от переменной R, правая часть уравнений (1) и (2) также не содержит переменную R. Поэтому можно уменьшить размерность задачи, исключив из рассмотрения уравнение (3).

Необходимые условия оптимальности

Применим к задаче принцип максимума Понтрягина [3].

Запишем функцию Понтрягина:

Пусть (S*(t), I*(t)) − оптимальное решение в задаче (1)-(5), (u1*(t), u2*(t)) − соответствующие оптимальные управления. Тогда согласно принципу максимума Понтрягина найдутся постоянная λ0 ≥ 0 и кусочно-непрерывно дифференцируемая вектор функция ψ(t) = (ψ1(t), ψ2(t)), такие, что:

1) ψ(t) удовлетворяет системе дифференциальных уравнений:

2) Выполнены условия трансверсальности:

ψ1(T) = 0, ψ2(T) = 0

3) Выполнено условие максимума для функции H:

Заметим, что для данной задачи λ0 ≠ 0. В дальнейшем положим λ0 = 1.

Анализ условия максимума

Рассмотрим подробнее условие максимума:

Выпишем отдельно слагаемые с управлением u1 и управлением u2.

Функции F(u1) и G(u2) являются вогнутыми, следовательно, максимум достигается в стационарных точках функции F и G, если эти точки являются допустимыми. Если стационарная точка не является допустимой, то минимум надо искать на границе области.

Найдем стационарные точки функций F и G.

Отсюда:

 и 

Получаем следующую структуру оптимального управления:

 (6)

 (7)

Заметим, что в силу условий трансверсальности управления в заключительный момент времени Т равны 0: u1*(T) = u2*(T) = 0.

Алгоритм численного решения задачи

Выпишем систему уравнений принципа максимума Понтрягина:

 (8)

где u1(t), u2(t) определяются из (6), (7).

Имеем следующие краевые условия для системы (8):

S(0) = S0, I(0) = I0, ψ1(T) = 0, ψ2(T) = 0

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

Система (8) решается численно в обратном времени начиная с момента Т. Задаются некоторые начальные условия S(T) и I(T). Затем задача Коши для системы уравнений сначальными условиями на правом конце решается численно и сравниваются полученные S(0) и I(0) с заданными, если они совпали с нужной нам точностью, то процесс завершается, если нет, то процесс повторяется с новыми S(T) и I(T), вычисленными по особому правилу [4].

Влияние параметров на оптимальные решения 

Анализ зависимости оптимального значения функционала от параметров задачи выявил следующую особенность: с ростом α (интенсивность фатального выхода из строя узлов поддействием вируса) оптимальное значение функционала уменьшается. Хотя интуитивно ясно, что интенсивный выход из строя узлов должен играть «отрицательную» роль. Очевидно, что такое влияние параметра α на функционал не является адекватным. Таким образом, нужно изменить функционал так, чтобы на оптимальном решении уменьшить число сломанных узлов и увеличить число восстановленных узлов.

Рисунок 1. Оптимальные решения системы при значениях α = 0.1, β = 0.75, С1 = 1, С2 = 0.4, С3 = 0.5, T = 1

Рисунок 1. Оптимальные решения системы при значениях α = 0.1, β = 0.75, С1 = 1, С2 = 0.4, С3 = 0.5, T = 1

Рисунок 2. Зависимость функционала от параметра α

Рисунок 2. Зависимость функционала от параметра α

Задача максимизации числа восстановленных узлов с учетом затрат

Рассмотрим следующую задачу оптимального управления: минимизировать функционал:

 (9)

на траекториях системы:

,  ,  

с начальными условиями: S(0) = S0, I(0) = I0, R(0) = R0, и ограничениями на управления (5).

Запишем функцию Понтрягина:

Пусть (S*(t), I*(t), R*(t)) − оптимальное решение в задаче, − оптимальное управление. Тогда согласно принципу максимума Понтрягина найдутся постоянная λ0 ≥ 0 икусочно-непрерывно дифференцируемая вектор-функция ψ(t) = (ψ1(t), ψ2(t), ψ3(t)), такие, что:

1) ψ(t) удовлетворяет системе дифференциальных уравнений:

2) Выполнены условия трансверсальности:

ψ1(T) = 0, ψ2(T) = 0, ψ3(T) = 0

3) Выполнено условие максимума для функции H:

Заметим, что в данной задаче также можно положить λ0 = 1.

По аналогии с предыдущим случаем найдем структуру оптимального управления.

 (10)

 (11)

Алгоритм численного решения задачи

Выпишем систему уравнений принципа максимума Понтрягина:

 (12)

где u1(t), u2(t) определяются из (10), (11).

Краевые условия для (12): S(0) = S0, I(0) = I0, ψ1(T) = 0, ψ2(T) = 0, ψ3(T) = 0. Из этих условий можно сразу аналитически найти ψ3(t) = C0(Tt). Строим численное решение задачи сиспользованием метода пристрелки.

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

Рисунок 3. Зависимость функционала от параметра α

Рисунок 3. Зависимость функционала от параметра α

Заключение

В работе изучается SIR-модель распространения вирусов в компьютерных сетях. Рассматриваются задачи управления для данной модели:

  • минимизация числа зараженных узлов с учетом затрат, где управление − интенсивность «вакцинации» и интенсивность «лечения»;
  • максимизация числа восстановленных узлов с учетом затрат, где управление − интенсивность «вакцинации» и интенсивность «лечения».

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

В дальнейшем предполагается построить функционал, который имеет «правильное» поведение, то есть уменьшается с ростом α.

  1. Yusuf T. T., Benyah F. Optimal control of vaccination and treatment for an SIR epidemiological model.// World Journal of Modelling and Simulation, Vol. 8(2012) No. 3, pp. 194-204.
  2. Bakare E. A., Nwagwo A., Danso-Addo E. Optimal control analysis of an SIR epidemic model with constant recruitment.// International Journal of Applied Mathematical Research, 3 (3) (2014) 273-285.
  3. Понтрягин Л.С. Математическая теория оптимальных процессов. − М.: Наука, 1976.
  4. Григорьев К.Г., Григорьев И.С., Заплетин М.П. Практикум по численным методам в задачах оптимального управления. Дополнение I. – М.: Издательство Центра прикладных исследований при механико-математическом факультете МГУ, 2007.
  5. Филиппов А. Ф., О некоторых вопросах теории оптимального регулирования. // Вестник МГУ, сер. матем., мех., астрон., физ., хим., 1959, №2, с. 25-32.
  6. Sun Zh. Epidemic spreading survey// [Электронный ресурс]: 8 February 2009. – Режим доступа: http://www.ccs.neu.edu/home/austin/writeups/epispread.pdf, свободный (дата обращения: 14.10.16).

Optimal control for virus spreading: analytical and numerical results

Klimenkova O.D., Bachelor MIEM NRU HSE, Moscow «applied mathematics», odklimenkova@edu.hse.ru

Abstract: In this work, optimal control problem for a SIR model with variable size of population is considered. Our goal is to solve a problem of costs minimization. We investigate a SIR model with «vaccination» and «treatment» as controls. We consider two different functional and discuss their characteristics. Structures of optimal control are defined for every functional. Pontryagin’smaximum principle is used to characterize the optimal levels of controls. The optimality system is solved numerically. Then we analyze the dependence of solutions on parameter of problems. The simulation results are discussed.

Keywords: SIR-model, optimal control, Pontryagin’s maximum principle.


Комментарии отсутствуют

Добавить комментарий

Комментарии могут оставлять только зарегистрированные пользователи

               Copyright © Системный администратор

Яндекс.Метрика
Tel.: (499) 277-12-45
E-mail: sa@samag.ru