Все выпуски

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

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

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

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

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

Врабо те рассматривается известная игра «Морской бой». Цель статьи — предложить модифицированную версию «Морского боя» и найти оптимальные стратегии действий игроков в новых правилах. Изменения коснулись как применяемых атакующих стратегий (добавлена новая возможность атаки, охватывающая четыре клетки за один выстрел), размера поля (использовались варианты игры для полей 10 × 10, 20 × 20, 30 × 30), так и правил расстановки кораблей в процессе боя (добавлена возможность перемещения корабля из зоны обстрела). Игра решалась с применением аппарата теории игр: составлены платежные матрицы для каждого варианта изменяемых правил, для них найдены оптимальные смешанные и чистые стратегии. При решении платежных матриц использовался итерационный метод. Симуляция состояла в применении пяти алгоритмов атаки и шести алгоритмов защиты с вариацией параметров при игре «каждого с каждым». Атакующие алгоритмы варьировались в разрезе 100 различных наборов значений, алгоритмы защиты — в разрезе 150 каждый. Важным результатом стало то, что в рамках этих ал- горитмов модифицированный «Морской бой» может быть решен, — то есть могут быть найдены устойчивые чистые или смешанные стратегии поведения, обеспечивающие сторонам оптимальный исход с точки зрения теории игр. Помимо этого, сделана оценка влияния изменений правил стандартного «Морского боя» на результат противостояния. Приведено сравнение с результатами, полученными авторами в предыдущей работе по данной тематике. На основе сопоставления полученных платежных матриц со статистическим анализом, проведенным ранее, отмечено, что стандартный «Морской бой» может быть представлен как частный случай рассмотренных в данной работе модификаций. Задача актуальна как с точки зрения ее применения в военном деле, так и в гражданских областях. Использование результатов статьи способно сохранить ресурсы при геологоразведке, обеспечить преимущество в военном противостоянии, сохранить детали, подвергающиеся разрушительному воздействию, и так далее.

В Лаборатории информационных технологий (ЛИТ) Объединенного института ядерных исследований (ОИЯИ) планируется создание облачного центра параллельных вычислений, что позволит существенно повысить эффективность выполнения численных расчетов и ускорить получение новых физически значимых результатов за счет более рационального использования вычислительных ресурсов. Для оптимизации схемы параллельных вычислений в облачной среде эту схему необходимо протестировать при различных сочетаниях параметров оборудования (количества и частоты процессоров, уровней распараллеливания, пропускной способности коммуникационной сети и ее латентности). В качестве тестовой была выбрана весьма актуальная задача параллельных вычислений длинных джозефсоновских переходов (ДДП) с использованием технологии MPI. Проблемы оценки влияния вышеуказанных факторов вычислительной среды на скорость параллельных вычислений тестовой задачи было предложено решать методом имитационного моделирования, с использованием разработанной в ЛИТ моделирующей программы SyMSim.

Работы, выполненные по имитационному моделированию расчетов ДДП в облачной среде с учетом межпроцессорных соединений, позволяют пользователям без проведения серии тестовых запусков в реальной компьютерной обстановке подобрать оптимальное количество процессоров при известном типе сети, характеризуемой пропускной способностью и латентностью. Это может существенно сэкономить вычислительное время на счетных ресурсах, высвободив его для решения реальных задач. Основные параметры модели были получены по результатам вычислительного эксперимента, проведенного на специальном облачном полигоне для MPI-задач из 10 виртуальных машин, взаимодействующих между собой через Ethernet-сеть с пропускной способностью 10 Гбит/с. Вычислительные эксперименты показали, что чистое время вычислений спадает обратно пропорционально числу процессоров, но существенно зависит от пропускной способности сети. Сравнение результатов, полученных эмпирическим путем, с результатами имитационного моделирования показало, что имитационная модель корректно моделирует параллельные расчеты, выполненные с использованием технологии MPI, и подтвердило нашу рекомендацию, что для быстрого счета задач такого класса надо одновременно с увеличением числа процессоров увеличивать пропускную способность сети. По результатам моделирования удалось вывести эмпирическую аналитическую формулу, выражающую зависимость времени расчета от числа процессоров при фиксированной конфигурации системы. Полученная формула может применяться и для других подобных исследований, но требует дополнительных тестов по определению значений переменных.

Видоспецифическими поведенческими признаками дикого северного оленя Rangifer tarandus L. традиционно признаны сезонные миграции и стадный инстинкт. В период миграций эти животные вынуждены преодолевать водные преграды. Особенности поведения рассматриваются как результат процесса селекции, когда среди множества стратегий выбрана единственно эволюционно-стабильная, определяющая репродукцию и биологическую выживаемость дикого северного оленя как вида. Ввиду эскалации промышленного освоения Арктики в настоящее время естественные процессы в популяциях диких северных оленей таймырской популяции происходят на фоне увеличения влияния негативных факторов, поэтому естественно возникла необходимость выявления этологических особенностей этих животных. В настоящей работе представлены результаты применения классических методов теории оптимального управления и дифференциальных игр к исследованию миграционных этограмм диких северных оленей при преодолении водных преград, в том числе крупных рек. На основе этологических особенностей этих животных и форм поведения стадо представляется в качестве управляемой динамической системы. Также оно делится на два класса особей: вожак и остальное стадо, для которых строятся свои модели, описывающие траектории их движения. В основу моделей закладываются гипотезы, представляющие собой математическую формализацию некоторых схем поведения животных. Данный подход позволил найти траекторию важенки с использованием методов теории оптимального управления, а при построении траекторий остальных особей — применить принцип управления с поводырем. Апробация полученных результатов, которые могут быть использованы в формировании общей «платформы» для систематического построения моделей адаптивного поведения и в качестве задела для фундаментальных разработок моделей когнитивной эволюции, проводится численно на модельном примере, использующем данные наблюдений на реке Верхняя Таймыра.

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

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

В ходе исследования проанализированы различные режимы подачи субстрата в метантенк, температурные среды и виды сырья. Показано, что скорость образования биогаза при непрерывном режиме подачи сырья в 1.4–1.9 раза выше в мезофильной среде (в 1.9–3.2 — в термофильной среде), чем при периодическом режиме за период полной ферментации, что связано с большей скоростью подачи субстрата и большей концентрацией питательных веществ в субстрате. Однако выход биогаза за период полной ферментации при периодическом режиме вдвое выше выхода за период полной смены субстрата в метантенке при непрерывном режиме, что означает неполную переработку субстрата во втором случае. Скорость образования биогаза для термофильной среды при непрерывном режиме и оптимальной скорости подачи сырья втрое выше, чем для мезофильной среды. Сравнение выхода биогаза для различных типов сырья показывает, что наибольший выход биогаза наблюдается для отходов птицефабрик, наименьший — для отходов ферм КРС, что связано с содержанием питательных веществ в единице субстрата каждого вида.

В статье рассматривается проблема надежности эксплуатации открытой интеграционной платформы, обеспечивающей взаимодействие различных программных комплексов моделирования режимов транспорта газа, с учетом предоставления доступа к ним, в том числе через тонких клиентов, по принципу «программное обеспечение как услуга». Математически описаны функционирование, надежность хранения, передачи информации и реализуемость вычислительного процесса системы, что является необходимым для обеспечения работы автоматизированной системы диспетчерского управления транспортом нефти и газа. Представлено системное решение вопросов моделирования работы интеграционной платформы и тонких клиентов в условиях неопределенности и риска на базе метода динамики средних теории марковских случайных процессов. Рассматривается стадия стабильной работы — стационарный режим работы цепи Маркова с непрерывным временем и дискретными состояниями, которая описывается системами линейных алгебраический уравнений Колмогорова–Чепмена, записанных относительно средних численностей (математических ожиданий) состояний объектов исследования. Объектами исследования являются как элементы системы, присутствующие в большом количестве (тонкие клиенты и вычислительные модули), так и единичные (сервер, сетевой менеджер (брокер сообщений), менеджер технологических схем). В совокупности они представляют собой взаимодействующие Марковские случайные процессы, взаимодействие которых определяется тем, что интенсивности переходов в одной группе элементов зависят от средних численностей других групп элементов.

Через средние численности состояний объектов и интенсивностей их переходов из состояния в состояние предлагается многокритериальная дисперсионная модель оценки риска (как в широком, так и узком смысле, в соответствии со стандартом МЭК). Риск реализации каждого состояния параметров системы вычисляется как среднеквадратическое отклонение оцениваемого параметра системы объектов (в данном случае — средние численности и вероятности состояний элементов открытой интеграционной платформы и облака) от их среднего значения. На основании определенной дисперсионной модели риска функционирования элементов системы вводятся модели критериев оптимальности и рисков функционирования системы в целом. В частности, для тонкого клиента рассчитываются риск недополучения выгоды от подготовки и обработки запроса, суммарный риск потерь, связанный только с непроизводительными состояниями элемента, суммарный риск всех потерь от всех состояний системы. Для полученной многокритериальной задачи оценки рисков предлагаются модели (схемы компромисса) выбора оптимальной стратегии эксплуатации.

В данной статье проведен обзор как исторических достижений, так и современных результатов в области марковских процессов принятия решений (Markov Decision Process, MDP) и выпуклой оптимизации. Данный обзор является первой попыткой освещения на русском языке области обучения с подкреплением в контексте выпуклой оптимизации. Рассматриваются фундаментальное уравнение Беллмана и построенные на его основе критерии оптимальности политики — стратегии, принимающие решение по известному состоянию среды на данный момент. Также рассмотрены основные итеративные алгоритмы оптимизации политики, построенные на решении уравнений Беллмана. Важным разделом данной статьи стало рассмотрение альтернативы к подходу $Q$-обучения — метода прямой максимизации средней награды агента для избранной стратегии от взаимодействия со средой. Таким образом, решение данной задачи выпуклой оптимизации представимо в виде задачи линейного программирования. В работе демонстрируется, как аппарат выпуклой оптимизации применяется для решения задачи обучения с подкреплением (Reinforcement Learning, RL). В частности, показано, как понятие сильной двойственности позволяет естественно модифицировать постановку задачи RL, показывая эквивалентность между максимизацией награды агента и поиском его оптимальной стратегии. В работе также рассматривается вопрос сложности оптимизации MDP относительно количества троек «состояние–действие–награда», получаемых в результате взаимодействия со средой. Представлены оптимальные границы сложности решения MDP в случае эргодического процесса с бесконечным горизонтом, а также в случае нестационарного процесса с конечным горизонтом, который можно перезапускать несколько раз подряд или сразу запускать параллельно в нескольких потоках. Также в обзоре рассмотрены последние результаты по уменьшению зазора нижней и верхней оценки сложности оптимизации MDP с усредненным вознаграждением (Averaged MDP, AMDP). В заключение рассматриваются вещественнозначная параметризация политики агента и класс градиентных методов оптимизации через максимизацию $Q$-функции ценности. В частности, представлен специальный класс MDP с ограничениями на ценность политики (Constrained Markov Decision Process, CMDP), для которых предложен общий прямодвойственный подход к оптимизации, обладающий сильной двойственностью.

В работе предложен оптимизационный подход к имитационному моделированию микроструктур. Решены задачи оптимизации функции пористости, поиска оптимальной модели гранулометрического состава и введен критерий качества моделирования. Проведена проверка адекватности предложенных методов на примерах и предложена регрессионная модель качества имитационного моделирования микроструктур. Актуальным приложением предложенного подхода является задача 3D-реконструкции микроструктуры керна. Полученные результаты дают основания для продолжения исследований в выбранном направлении.

В работе рассматривается применение метода сбалансированной идентификации для построения многофакторной функциональной зависимости нетто СО₂-обмена (NEE) от факторов внешней среды и ее дальнейшего использования для заполнения пропусков в рядах наблюдений за потоками СО₂ на верховом сфагновом болоте в Тверской области. Измерения потоков на болоте проводились с помощью метода турбулентных пульсаций в период с августа по ноябрь 2017 года. Из-за дождливых погодных условий и высокой повторяемости периодов с низкой турбулентностью на протяжении всего периода наблюдений доля пропусков в измерениях NEE на исследуемом болоте превысила 40%. Разработанная для заполнения пропусков модель описывает NEE верхового болота как разность экосистемного дыхания (RE) и валовой первичной продукции (GPP) и учитывает зависимость этих параметров от приходящей суммарной солнечной радиации (Q), температуры почвы (T), дефицита упругости водяного пара (VPD) и уровня болотных вод (WL). Используемый для этой цели метод сбалансированной идентификации основан на поиске оптимального соотношения между простотой модели и точностью повторения измерений — соотношения, доставляющего минимум оценке погрешности моделирования, полученной методом перекрестного оценивания. Полученные численные решения обладают минимально необходимой нелинейностью (кривизной), что обеспечивает хорошие интерполяционные и экстраполяционные свойства построенных моделей, необходимые для восполнения недостающих данных по потокам. На основе проведенного анализа временной изменчивости NEE и факторов внешней среды была выявлена статистически значимая зависимость GPP болота от Q, T и VPD, а RE — от T и WL. При этом погрешность применения предложенного метода для моделирования среднесуточных данных NEE составила менее 10%, а точность выполненных оценок NEE была выше, чем у модели REddyProc, учитывающей влияние на NEE меньшего числа внешних факторов. На основе восстановленных непрерывных рядов данных по NEE была проведена оценка масштабов внутрисуточной и межсуточной изменчивости NEE и получены интегральные оценки потоков СО₂ исследуемого верхового болота для выбранного летне-осеннего периода. Было показано, что если в августе 2017 года на исследуемом болоте скорость фиксации СО₂ растительным покровом существенно превышала величину экосистемного дыхания, то, начиная с сентября, на фоне снижения GPP исследуемое болото превратилось в устойчивый источник СО₂ для атмосферы.

В теоретико-игровой постановке рассмотрена модель борьбы с коррупцией при распределении ресурсов. Система распределения ресурсов включает в свой состав одного принципала (субъект управления верхнего уровня), одного или нескольких супервайзеров (субъектов среднего уровня) и нескольких агентов (субъекты нижнего уровня). Отношения между субъектами разных уровней строятся на основе иерархии: субъект верхнего уровня воздействует (управляет) на субъектов среднего уровня, а те, в свою очередь, на субъектов нижнего уровня. Предполагается, что коррупции подвержен средний уровень управления. Агенты предлагают супервайзеру взятки, в обмен на которые он предоставляет им дополнительные доли ресурса. Предположим также, что принципал не подвержен коррупции и является бескорыстным, не преследующим частных целей. Исследование модели проведено с точки зрения как супервайзера, так и агентов. C точки зрения агентов, возникает некооперативная игра, в которой находится равновесие Нэша. При этом задачи оптимального управления для частного вида входных функций решаются аналитически с помощью принципа максимума Понтрягина. C точки зрения супервайзера, возникает игра, которая ведется в соответствии с регламентом игры Гермейера Г_2t. Указан алгоритм построения равновесия. Стратегия наказания находится аналитически. Стратегия поощрения в случае входных функций общего вида находится численно. Строится дискретный аналог непрерывной модели. Предполагается, что все субъекты управления могут изменять свои стратегии поведения в одни и те же моменты времени конечное число раз. В результате от задачи максимизации своего целевого функционала супервайзер переходит к задаче максимизации целевой функции многих переменных. Для нахождения ее наибольшего значения используется метод качественно репрезентативных сценариев. Идея этого метода состоит в том, что из множества потенциально возможных сценариев управления выбираются только сценарии, позволяющие представить качественно различные пути развития системы. В результате мощность этого множества не слишком велика и удается осуществить полный перебор качественно репрезентативных сценариев и найти стратегию поощрения агентов. После ее нахождения супервайзер предлагает агентам механизм управления с обратной связью по управлению, состоящий в наказании агентов при отклонении от выбранной супервайзером стратегии и поощрении в противном случае.