Соискатель-инженер
Тверской государственный технический университет
кандидат технических наук
УДК 004.94
1. Введение
Распределенные вычисления являются эффективным решением для приложений, требующих больших вычислительных усилий, поиска информации из географически распределенных ресурсов или и того, и другого. Такие приложения используют взаимосвязанные сети компьютеров или суперкомпьютеров, очень большие базы данных, программные инструменты для хранения и поиска, передовые устройства и научные инструменты [3-5].
Вычислительное решение GRID используется для реализации нескольких эпидемиологических моделей, но приложения в основном сосредоточены на совместном использовании очень больших баз данных. Статистические модели, используемые в этих приложениях, основаны на последовательном подходе без распараллеливания. Немногие приложения использовали вычислительные преимущества GRID [3-5]. eMicrob создает платформу GRID (eMicrob miniGrid), обеспечивающую безопасный доступ к гетерогенным данным и дорогостоящим ресурсам в разных местах. Представлена распределенная система характеристики когорт, которая применяется для анализа первого эпизода психоза [4]. GISE — это гибкая служба, построенная на сетевой инфраструктуре Globus 4, которая была протестирована в системе эпидемического мониторинга и надзора [5].
Насколько нам известно, GRID-сервисы, связанные с эпидемиологическими моделями, обычно относятся к управлению данными в GRID (рак молочной железы, маммография и т. д.), и лишь немногие приложения относятся к распараллеливанию кода для реализации эпидемиологических моделей.
Эпидемиология является одним из стандартных методов, используемых для определения здоровья населения [6-10]. Большинство эпидемиологических явлений имеют математическую модель, которая позволяет моделировать и прогнозировать развитие болезни. Распространенная математическая модель создается дифференциальными уравнениями [8]. Важная часть этих моделей использует многоступенчатые (компартментные) подходы. Эти компартментные подходы, которые используют обыкновенные дифференциальные уравнения, подходят для реализации на компьютерных системах с целью моделирования временной и пространственной эволюции явлений [8].
Математические модели, использующие обыкновенные дифференциальные уравнения, могут быть решены последовательно итеративными методами, численными методами или распараллеливанием алгоритма решателя, основанного на методах Эйлера или Рунге-Кутты. Эффективность этих алгоритмов зависит от того, сколько накладных расходов дается за счет связи между процессорами и балансировки нагрузки задач.
Спектр заболеваний для конечной популяции может быть спорадическим [10], эндемичным (регулярным, с постоянным появлением), эпидемическим (постоянный рост числа заболевших) или пандемическим (заболевают многие страны). Многие из этих моделей подвержены сезонным колебаниям (например, грипп, который чаще встречается зимой) или имеют сезонные колебания, которые известны как циклы всплесков после ряда лет. Эти шаблоны идентифицируются по сезонным закономерностям [11]. Наиболее распространенной моделью сезонных колебаний является периодическая функция, основанная на формулах синуса или косинуса.
В контексте передачи заболеваний некоторые исследования были сосредоточены на нескольких формах компьютерных сетей, которые определяются с точки зрения того, как люди распределены в пространстве (которое может быть географическим или социальным) и как формируются связи [17-24]. Этот сложный процесс имитирует пространственное распространение заболевания, которое происходит в реальных популяциях. Мы можем упомянуть эпидемиологические модели, которые попадают в этот случай: случайные сети, сети малого мира, пространственные сети, сети без масштабирования, экспоненциальные случайные графовые модели, решетки и клеточные автоматы (КА) [21]. Далее мы провели эксперименты с использованием КА и сетей малого мира.
Клеточные автоматы (КА) характеризуются своей дискретизацией пространства и времени. Эпидемиологическая модель, использующая клеточные автоматы, — это модель, которая фокусируется на пространственном распространении заболевания. Клеточные автоматы состоят из пространственной сетки, размещенной ячейками, которые характеризуются дискретным временем и состоянием. В каждый дискретный момент времени мы выполняем итерацию, в которой ячейки обновляются с использованием определенных правил. Коридоры распространения в клеточных автоматах можно рассматривать как улучшение модели с реальной ситуацией, когда инфицированные люди могут перемещаться в другие места (на поезде, автобусе или машине) и создавать новый узел заражения. Термин «сеть малого мира» относится к сетям, в которых по регулярной решетке вводится небольшое количество сокращений. Структура малого мира похожа на ситуацию, когда кластеры связанных людей (социальные группы) контактируют с «близлежащими» группами и «далекими» группами через редкие дальние связи.
Решетки демонстрируют высокую кластеризацию, но длинные пути требуют много шагов для перемещения между двумя случайно выбранными индивидуумами. Сети малого мира предлагают средства перемещения между жесткой организацией решеток и неструктурированными связями сетевых моделей. Высокий уровень кластеризации означает, что большая часть заражения происходит локально, но короткие пути означают, что эпидемия распространяется по сети быстро, и болезнь вряд ли будет ограничена небольшими регионами популяции.
Для представленной нами там модели онкологического заболевания получено дифференциальное уравнение, в котором сингулярный параметр, умножающий на производные максимального порядка, при котором проявляется явление граничной функции [25-28]. Основное предложение — построение асимптотического приближения решения возмущенной задачи как на внешности окрестности граничной функции, так и внутри ее. Это приближение носит асимптотический характер [29-35]. Построение асимптотического решения в общем случае сводится к решению задачи, менее сложной, чем возмущенная. Практическая ценность этого метода определяется возможностью эффективного нахождения этого асимптотического решения с помощью простой задачи.
Актуальность темы заключается в том, что разработка проблемно-ориентированных систем управления может способствовать предотвращению эпидемических вспышек. Среди ключевых инструментов для анализа таких систем — математическая модель, способная предсказывать пространственное распространение инфекционных заболеваний. Учитывая взаимодополняющий характер системно-динамических моделей передачи эпидемий, крайне важно использовать их совместно для эффективного прогнозирования динамики эпидемий. Этот подход требует детальной оценки характеристик и возможностей моделей. Эпидемии представляют собой динамические и пространственно распределенные системы, что делает их хорошо подходящими для моделирования с помощью клеточных автоматов для захвата их пространственно-временной эволюции.
Целью данного исследования является повышение эффективности контроля эпидемий и обеспечение визуализации моделей на основе клеточных автоматов с помощью численного моделирования.
Задачи исследования:
Для достижения поставленной цели необходимо решение следующих задач:
Научная новизна заключается в демонстрации эффективности моделей клеточных автоматов (КА) как инструмента прогнозирования в эпидемиологии. Исследование дает новое понимание того, как симуляции на основе КА могут точно представлять пространственно-временную динамику распространения заболеваний, предлагая эпидемиологам практичный и масштабируемый метод прогнозирования вспышек и поддержки процессов принятия решений.
2. Модели эпидемий и модель раковых заболеваний
Найти адекватную модель, подходящую для одной эпидемии, — сложная операция. Математическая модель — это компромисс между простотой, точностью и общностью. Модель должна аппроксимировать то, что происходит в реальном мире. Сложная модель может иметь большую точность, но ее может быть слишком сложно параметризовать и понять. Наиболее распространенными моделями являются компартментальные модели [8, 10].
2.1 Модель SEIR
Четырехкомпонентная модель сети малого мира распространения заболеваний имеет четыре категории популяций: S — восприимчивые (доля восприимчивых лиц, т.е. лиц, способных контактировать с заболеванием), E — подверженные воздействию (доля подвергшихся воздействию лиц, т.е. лиц, которые были инфицированы, но еще не заразны), I — заразные (доля лиц, способных передавать заболевание) и R — выздоровевшие (доля лиц, которые приобрели иммунитет) [36].
Компартментальная модель и переходы показаны на рисунке 1. Предположим, что коэффициент рождаемости и смертности μ постоянен.
Рис. 1. Четырехкомпонентная модель сетей малого мира для распространения болезней.
Предположим, что коэффициент рождаемости и смертности μ постоянен. Уравнения базовой модели SEIR следующие [22]:
В приведенных выше уравнениях 1/α — это средний латентный период заболевания, а 1/γ — это средний период инфекции [20]. Параметр β(t) представляет силу инфекции (скорость заражения) и может быть постоянным β = β0 = константа или может быть сезонным, то есть меняющимся со временем t в годах:
Пути передачи (граф перехода состояний) изображены на рисунке 2. Инфицированные особи могут создавать восприимчивых особей, с которыми связаны с некоторой вероятностью. Непосредственные соседи будут инфицированы с вероятностью p1, в то время как дальние связи будут инфицированы с вероятностью p2.
Рис. 2. Сетевые связи ближнего и дальнего действия (а) расположение узлов в сетке (б) локальное расположение узлов в малой сети.
Подвергшиеся воздействию лица заразятся с вероятностью r0, и, наконец, инфицированные лица станут иммунными (выздоровеют) с вероятностью r1. Распределение степеней может быть усеченной степенной формой (6) или дискретным экспоненциально затухающим распределением (7). Наши эксперименты используют форму, представленную в (7):
Клеточные автоматы (КА) характеризуются дискретизацией пространства и времени. Эпидемиологическая модель с использованием клеточных автоматов — это модель, которая фокусируется на пространственном распространении одной болезни. Клеточные автоматы состоят из пространственных сеток, размещенных ячейками, которые характеризуются дискретным временем и состоянием. В каждый дискретный момент времени мы выполняем итерацию, в которой ячейки обновляются по определенным правилам. Коридоры распространения в клеточных автоматах можно рассматривать как улучшение модели с реальной ситуацией, когда инфицированные люди могут перемещаться в другие места (на поезде, автобусе или автомобиле), и эти люди могут создавать новый узел заражения [37-55].
Коридоры рассматриваются только в четырех направлениях (север, юг, восток и запад). Эти коридоры позволяют распространять болезнь без связей клетка-к-клетке. Расширение с другими четырьмя промежуточными точками усложняет проблему, и эти расширения будут рассмотрены для дальнейшего исследования [56-61].
Городское население из городов имеет повышенную вероятность роста числа инфицированных людей, если в городской зоне присутствует хотя бы один инфицированный [62-68]. Эвристика разделения основана на попытке равномерного распределения населения каждого процессора и выделения целого города одному процессору без разделения местоположения между процессорами (рисунок 3).
Рис. 3. Распределение процессоров.
2.2 Модель ракового заболевания
Вторая модель относится к n асимптотическому решению нулевой степени для нелинейной системы дифференциальных параболических уравнений с уникальным, с малым параметром, приложением к раковому заболеванию [27-28]. Модель задается дифференциальным уравнением с малым параметром с возмущением.
Для модели, которую мы собираемся представить в этой работе, репрезентативным является дифференциальное уравнение, в котором сингулярный параметр, умножающий на производные максимального порядка, для которого проявляется явление граничной функции. Основное предложение состоит в построении асимптотического приближения решения возмущенной задачи как на внешности окрестности граничной функции, так и внутри этой окрестности. Это приближение имеет асимптотический характер. Построение асимптотического решения в общем случае сводится к решению задачи, менее сложной, чем возмущенная. Практическая ценность этого метода определяется возможностью эффективного нахождения этого асимптотического решения с помощью простой задачи.
Возмущенная задача (Pε) имеет вид, заданный уравнением (8). Начальные условия для этой возмущенной задачи: U(x,0,ε)=A; V(x,0,ε) =B; W(x,0,ε)=C. Рассмотрим асимптотику задачи нулевого порядка в этой форме (9).
Условия (10) в медицинских терминах означают, что раковые клетки, находящиеся в злокачественной фазе, не способны перемещаться вдоль омега-граничной массы. Рассмотрим Ω как среду обитания раковых клеток.
Нормальный вектор на Ω границе U, V, W представляет собой плотность раковых клеток на трех стадиях. Последняя стадия W считается предраковой стадией. Для модели мутации на трех стадиях, которая может привести к злокачественным клеткам, эволюция стадий имеет вид, представленный на рисунке 4.
Рис. 4. Модель трехэтапной мутации.
Например, при раке пищевода клетки проходят следующие стадии: начальная, быстрый рост клеток и их инвазия, ангиогенез и метастазирование (злокачественная стадия). Раковые стадии с плотностью W — это те клетки, которые претерпели мутации на предыдущих стадиях и приспособились к новым условиям. Термин dVW представляет собой взаимодействие клеток, претерпевших мутации, с окружающими клетками в их борьбе за выживание и новые ресурсы.
Константа D представляет собой способность раковых клеток перемещаться в здоровые клетки. Если D = 0, раковые клетки метастазировали. Тот факт, что D является единственным числом, показывает нам способность клеток, которые подверглись мутациям, перемещаться по трем стадиям борьбы за ресурсы. В медицинской литературе D также называют миграционным фактором. Параметр ε из первого уравнения задачи (PE) измеряет подвижность клеток предраковой стадии по сравнению со здоровыми клетками. При малом значении ε миграционная способность клеток предраковой стадии растет. Можно сказать, что параметр e измеряет агрессивность предраковых клеток по отношению к здоровым клеткам в их конкуренции за выживание. Коэффициенты a, b, c, d называются коэффициентами взаимодействия.
2.3 Параллелизация модели раковых заболеваний
Параллельный алгоритм кратко описан на рисунке 5. Распределение процессоров предлагаемого алгоритма изображено на рисунке 6. Пусть будет m пользователей, которые хотят управлять моделью с различными параметрами одновременно (нижняя граница m=1). Обозначим через Pi(j, k) процесс i, который принадлежит пользователю k на шаге j.
Рис. 5. Параллельно предложенный алгоритм для применения при раковых заболеваниях.
Если у нас есть p процессоров, то каждый процессор имеет o блок из p процессов, из упорядоченного списка LP, в порядке блок за блоком. Граф планирования процессов параллельно показан на рисунке 6.
Рис. 6. Распределение процессоров раковых заболеваний.
3. Экспериментальные результаты
Модель имеет параметры L= 1500, N=L2 = 2250000, n1 = 4, r0 следует геометрическому распределению fX (x) = (1-p)x-1p, p1 = 1/n1(0,27-μp2), r0 = 0,135, r1 = 0,25, μ = 7 значений, частично вдохновленных из [13] с моделью SEIR для SARS. Мы использовали p2 в диапазоне [0, 0,07].
Мы протестировали моделирование распространения заболевания в параллельной реализации для 2-9 процессоров (Рисунок 7). Тесты проводились с несколькими ограничениями: (1) моделирование проводится в течение T дней, при этом распространение заболевания не пересекает границы прямоугольников, выделенных процессорам (2) масштабируемость алгоритма тестируется только для максимум 8 процессоров (3) мы сравнили параллельный алгоритм с последовательной версией, которая выполняется на одном процессоре.
Рис. 7. Результат моделирования (наилучший и неблагоприятный случай).
Эволюция после 122 дней представлена (в процентах времени последовательного алгоритма) следующим образом: 2 процессора – 99,6%, 3 процессора – 97,6%, 4 процессора – 96%, 5 процессоров 94,6%, 6 процессоров – 92,9%, 7 процессоров – 91,7%, 8 процессоров – 91,2%. Мы должны отметить, что производительность параллельных алгоритмов увеличивается с эволюцией заболевания, но она ограничена количеством процессоров. Каждая новая область получает распределение процессора, и этот процессор будет вычислять все операции из ячеек в выделенной области.
Клеточная модель оказалась неисправной. Основная проблема заключается в том, что семена дальнего действия для нового кластера инфекции, несмотря на улучшение коридора, испытывают трудности. Коридоры трудно моделировать в соответствии с принципом клеточного автомата и реалистичным случаем. По этим причинам в данной статье приводятся только предварительные результаты относительно модели клеточного автомата. Эксперименты используют городское местоположение, город среднего размера (450000 жителей), и учитываются только вертикальные коридоры. Результаты через 257 дней не очень удовлетворительны, поэтому мы не продолжили в этом направлении.
Эксперименты с моделью ракового заболевания начинались с различных значений для нахождения численных решений системы сингулярно возмущенных уравнений. Моделирование решения невозмущенной задачи по параметрам: a=0.3, b=0.1, c=0.7, d=0.4 представлено на рис. 8-9.
Рис. 8. Моделирование решения невозмущенной задачи по параметрам: a=0,3, b=0,1, c=0,7, d=0,4 (V0).
Выживание мутантной клетки под давлением отбора может привести к другой мутации. Общее количество раковых клеток в организме зависит от скорости их деления и уничтожения иммунной системой.
Рис. 9. Моделирование решения невозмущенной задачи по параметрам: a=0,3, b=0,1, c=0,7, d=0,4 (V0).
Моделирование решений в возмущенной задаче можно интерпретировать так, что опухоль питается кислородом и питательными веществами, которые диффундируют к ее поверхности. Но эти запасы не могут проникнуть глубоко в опухоль, поэтому клетки в этом случае становятся спящими или умирают от голода. Моделирование решений в возмущенной задаче можно интерпретировать так, что асимптотическое решение, включающее уравнения в частных производных, часто сталкивается с трудностями, связанными с негладкостью некоторых членов асимптотических разложений.
С другой стороны, нулевое и первое приближения к решению, которые обычно достаточны для практических предложений, можно получить несколько проще, используя метод граничной функции. Мы рассмотрим случай, когда негладкость членов асимптотического ряда имеет иную природу. Мы предположили, что все постоянные параметры (a,b,c,d) не зависят от реакций, включая влияние непрерывных изменений окружающей среды на нагрузку ДНК на мутацию. Эти изменения неизбежны и могут вызвать последовательность мутаций. Более агрессивные мутантные клетки способны эксплуатировать окружающую среду и ресурсы гелей предыдущей стадии и имеют больше шансов на выживание.
Сервисы анализа данных, используемые в нашей Grid, представляют собой два отдельных компонента: компонент анализа данных, разработанный на языке C++ с использованием библиотеки стандартных шаблонов C++ и моделей коммуникации MPI 2.0. Компонент Grid сервиса конечного пользователя, который устанавливает связь между двумя модулями, разработан на языке Java (рисунок 10).
Рис. 10. Графический пользовательский интерфейс (GUI) для эпидемиологической службы, разработанный на JAVA.
Заключение
В этом исследовании представлен параллельный подход к моделированию распространения эпидемии сиспользованием моделей клеточных автоматов, с инициализацией моделирования из одной точки заражения. Хотя более реалистичные сценарии могут включать несколько точек затравки, они будут изучены в будущей работе. В настоящее время модель опирается на синтетические данные, признавая, что реальные коэффициенты изменяются в зависимости от оценок эпидемии на ранней стадии. Хотя интервалы параметров могут быть определены в оптимистичных и пессимистичных пределах, большие диапазоны могут давать нереалистичные результаты, такие как преждевременное исчезновение болезни.
Эффективность параллелизации чувствительна к количеству используемых процессоров; накладные расходы на связь могут свести на нет преимущества в меньших установках. Однако для моделирования в больших областях, таких как вспышки пандемического масштаба, и мелкозернистых пространственных разделов предлагаемый алгоритм предлагает значительные вычислительные преимущества. Конфигурация границ разделов имеет решающее значение; неоптимальные контуры могут привести к увеличению вычислительной нагрузки, особенно когда каждый процессор должен проверять назначения граничных ячеек, чтобы избежать ошибок между разделами.
Несмотря на эти проблемы, модель оказывается хорошим приближением для эволюции эпидемии. Регулируя параметры, включая вероятность передачи заболевания, модель допускает распространение через любую ячейку сетки в течение правдоподобного периода времени, тем самым приспосабливаясь к широкому спектру реальной динамики эпидемий. Кроме того, подход решает практические проблемы решения обыкновенных дифференциальных уравнений, которые лежат в основе многих эпидемиологических моделей.
Будущая работа будет включать расширение этой пространственной модели для охвата более широких географических регионов, что потребует обширных географических и демографических наборов данных. Другим многообещающим направлением является разработка более общего параллельного решателя, разработанного специально для вычислений на основе сетки, способного поддерживать различные компартментальные модели, используемые в эпидемиологических исследованиях.
Комментарии пользователей:
Оставить комментарий