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

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

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

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

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

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

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

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

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

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

Здесь:

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

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

Обозначим:

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

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

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

 (1)

 (2)

 (3)

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

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

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

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

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

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

 (4)

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

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

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

 (5)

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

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

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

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

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

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

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

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

ψ₁(T) = 0, ψ₂(T) = 0

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

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

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

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

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

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

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

Отсюда:

 и 

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

 (6)

 (7)

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

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

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

 (8)

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

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

S(0) = S₀, I(0) = I₀, ψ₁(T) = 0, ψ₂(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, С₂ = 0.4, С₃ = 0.5, T = 1

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

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

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

 (9)

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

,  ,  

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

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

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

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

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

ψ₁(T) = 0, ψ₂(T) = 0, ψ₃(T) = 0

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

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

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

 (10)

 (11)

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

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

 (12)

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

Краевые условия для (12): S(0) = S₀, I(0) = I₀, ψ₁(T) = 0, ψ₂(T) = 0, ψ₃(T) = 0. Из этих условий можно сразу аналитически найти ψ₃(t) = C₀(T – t). Строим численное решение задачи сиспользованием метода пристрелки.

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

Рисунок 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.

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