All issues

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

This article reviews both historical achievements and modern results in the field of Markov Decision Process (MDP) and convex optimization. This review is the first attempt to cover the field of reinforcement learning in Russian in the context of convex optimization. The fundamental Bellman equation and the criteria of optimality of policy — strategies based on it, which make decisions based on the known state of the environment at the moment, are considered. The main iterative algorithms of policy optimization based on the solution of the Bellman equations are also considered. An important section of this article was the consideration of an alternative to the $Q$-learning approach — the method of direct maximization of the agent’s average reward for the chosen strategy from interaction with the environment. Thus, the solution of this convex optimization problem can be represented as a linear programming problem. The paper demonstrates how the convex optimization apparatus is used to solve the problem of Reinforcement Learning (RL). In particular, it is shown how the concept of strong duality allows us to naturally modify the formulation of the RL problem, showing the equivalence between maximizing the agent’s reward and finding his optimal strategy. The paper also discusses the complexity of MDP optimization with respect to the number of state–action–reward triples obtained as a result of interaction with the environment. The optimal limits of the MDP solution complexity are presented in the case of an ergodic process with an infinite horizon, as well as in the case of a non-stationary process with a finite horizon, which can be restarted several times in a row or immediately run in parallel in several threads. The review also reviews the latest results on reducing the gap between the lower and upper estimates of the complexity of MDP optimization with average remuneration (Averaged MDP, AMDP). In conclusion, the real-valued parametrization of agent policy and a class of gradient optimization methods through maximizing the $Q$-function of value are considered. In particular, a special class of MDPs with restrictions on the value of policy (Constrained Markov Decision Process, CMDP) is presented, for which a general direct-dual approach to optimization with strong duality is proposed.

Разработана программа, которая позволяет имитировать работу конвейера гибкого автоматизированного цеха сборки персональных компьютеров (ПК), с применением современного объектно-ориентированного языка программирования C#. Приведена диаграмма классов имитационной модели ГАЦ сборки ПК в режиме массового производства. Приводится анализ результатов моделирования.

Using modern object-oriented programming language C# a program for simulation of operation of the conveyor for flexible automated assembly of PC was developed. Class diagram of the simulation model of a flexible automated assembly line for PC assembly in mass production mode is presented. Simulation results analysis is presented.

С 50-х годов XX века транспортное моделирование крупных мегаполисов стало усиленно развиваться. Появились первые модели равновесного распределения потоков по путям. Наиболее популярной (и использующейся до сих пор) моделью была модель Бэкмана и др. 1955 г. В основу этой модели положены два принципа Вардропа. На современном теоретико-игровом языке можно кратко описать суть модели как поиск равновесия Нэша в популяционной игре загрузки, в которой потери игроков (водителей) рассчитываются исходя из выбранного пути и загрузках на этом пути, при фиксированных корреспонденциях. Загрузки (затраты) на пути рассчитываются как сумма затрат на различных участках дороги (ребрах графа транспортной сети). Затраты на ребре (время проезда по ребру) определяется величиной потока автомобилей на этом ребре. Поток на ребре, в свою очередь, определяется суммой потоков по всем путям, проходящим через заданное ребро. Таким образом, затраты на проезд по пути определяются не только выбором пути, но и тем, какие пути выбрали остальные водители. Таким образом, мы находимся в стандартной теоретико-игровой постановке. Специфика формирования функций затрат позволяет сводить поиск равновесия к решению задачи оптимизации (игра потенциальная). Эта задача оптимизации будет выпуклой, если функции затрат монотонно неубывающие. Собственно, различные предположения о функциях затрат формируют различные модели. Наиболее популярной моделью является модель с функцией затрат BPR. Такие функции используются при расчетах реальных городов повсеместно. Однако в начале XXI века Ю. Е. Нестеровым и А. де Пальмой было показано, что модели типа Бэкмана имеют серьезные недостатки. Эти недостатки можно исправить, используя модель, которую авторы назвали моделью стабильной динамики. Поиск равновесия в такой модели также сводится к задаче оптимизации. Точнее, даже задаче линейного программирования. В 2013 г. А. В. Гасниковым было обнаружено, что модель стабильной ди- намики может быть получена предельным переходом, связанным с поведением функции затрат, из модели Бэкмана. Однако обоснование упомянутого предельного перехода было сделано в нескольких важных (для практики), но все- таки частных случаях. В общем случае вопрос о возможности такого предельного перехода, насколько нам известно, остается открытым. Данная работа закрывает данный зазор. В статье в общем случае приводится обоснование возможности отмеченного предельного перехода (когда функция затрат на проезд по ребру как функция потока по ребру вырождается в функцию, равную постоянным затратам до достижения пропускной способности, и равна плюс бесконечности, при превышении пропускной способности).

Since 1950s the field of city transport modelling has progressed rapidly. The first equilibrium distribution models of traffic flow appeared. The most popular model (which is still being widely used) was the Beckmann model, based on the two Wardrop principles. The core of the model could be briefly described as the search for the Nash equilibrium in a population demand game, in which losses of agents (drivers) are calculated based on the chosen path and demands of this path with correspondences being fixed. The demands (costs) of a path are calculated as the sum of the demands of different path segments (graph edges), that are included in the path. The costs of an edge (edge travel time) are determined by the amount of traffic on this edge (more traffic means larger travel time). The flow on a graph edge is determined by the sum of flows over all paths passing through the given edge. Thus, the cost of traveling along a path is determined not only by the choice of the path, but also by the paths other drivers have chosen. Thus, it is a standard game theory task. The way cost functions are constructed allows us to narrow the search for equilibrium to solving an optimization problem (game is potential in this case). If the cost functions are monotone and non-decreasing, the optimization problem is convex. Actually, different assumptions about the cost functions form different models. The most popular model is based on the BPR cost function. Such functions are massively used in calculations of real cities. However, in the beginning of the XXI century, Yu. E. Nesterov and A. de Palma showed that Beckmann-type models have serious weak points. Those could be fixed using the stable dynamics model, as it was called by the authors. The search for equilibrium here could be also reduced to an optimization problem, moreover, the problem of linear programming. In 2013, A.V.Gasnikov discovered that the stable dynamics model can be obtained by a passage to the limit in the Beckmann model. However, it was made only for several practically important, but still special cases. Generally, the question if this passage to the limit is possible remains open. In this paper, we provide the justification of the possibility of the above-mentioned passage to the limit in the general case, when the cost function for traveling along the edge as a function of the flow along the edge degenerates into a function equal to fixed costs until the capacity is reached and it is equal to plus infinity when the capacity is exceeded.

В работе рассматривается структура моделей перколяции узлов на трехмерных квадратных решеткахпри различныхфор мах (1,π)-окрестности. Для этихмо делей предложены изо- и анизотропные модификации алгоритма инвазивной перколяции с (1,0)- и (1,π)-окрестностями. Все рассмотренные алгоритмы являются частными случаями анизотропного алгоритма инвазивной перколяции на n-мерной решетке с (1,π)-окрестностью. Данный алгоритм положен в основу библиотеки SPSL, выпущенной под лицензией GNU GPL-3 с использованием свободного языка программирования R.

In this paper we consider the structure of site percolation models on three-dimensional square lattices with various shapes of (1,π)-neighborhood. For these models, are proposed iso- and anisotropic modifications of the invasion percolation algorithm with (1,0)- and (1,π)-neighborhoods. All the above algorithms are special cases of the anisotropic invasion percolation algorithm on the n-dimensional lattice with a (1,π)-neighborhood. This algorithm is the basis for the package SPSL, released under GNU GPL-3 using the free programming language R.

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

We consider an approach based on linear algebra methods to analyze the rate of electron transport through the cytochrome $b_6 f$ complex. In the proposed approach, the dependence of the quasi-stationary electron flux through the complex on the degree of reduction of pools of mobile electron carriers is considered a response function characterizing this process. We have developed software in the Python programming language that allows us to construct the master equation for the complex according to the scheme of elementary reactions and calculate quasi-stationary electron transport rates through the complex and the dynamics of their changes during the transition process. The calculations are performed in multithreaded mode, which makes it possible to efficiently use the resources of modern computing systems and to obtain data on the functioning of the complex in a wide range of parameters in a relatively short time. The proposed approach can be easily adapted for the analysis of electron transport in other components of the photosynthetic and respiratory electron-transport chain, as well as other processes in multienzyme complexes containing several reaction centers. Cryo-electron microscopy and redox titration data were used to parameterize the model of cytochrome $b_6 f$ complex. We obtained dependences of the quasi-stationary rate of plastocyanin reduction and plastoquinone oxidation on the degree of reduction of pools of mobile electron carriers and analyzed the dynamics of rate changes in response to changes in the redox state of the plastoquinone pool. The modeling results are in good agreement with the available experimental data.

Данная работа нацелена на программистов и разработчики, заинтересованных в использовании технологии параллельного программирования для увеличения производительности приложений. Программное обеспечение Oracle Solaris Studio обеспечивает современную оптимизацию и распараллеливание компиляторов для языков C, C ++ и ФОРТРАН, продвинутый отладчик, и оптимизированные математи- ческие и быстродействующие библиотеки. Также включены чрезвычайно мощный инструмент анализа производительности для профилирования последовательных и параллельных приложений, инструмент анализа для обнаружения состязания при передаче данных и блокировки в памяти параллельных программ и IDE. Программное обеспечение Oracle Message Passing Toolkit обеспечивает высокопроизводительные MPI библиотеки и сопряжённую среду во время работы программы, необходимую для приложений передачи сообщений, которые могут работать на одной системе или по всему множеству вычислительных систем с высокопроизводительным сетевым оснащением, включая Gigabit Ethernet, 10 Gigabit Ethernet, InfiniBand и Myrinet. Примеры OpenMP и MPI представлены по всему тексту работы, включая их использование через программные продукты Oracle Solaris Studio и Oracle Message Passing Toolkit для развития и развертывания последовательных и параллельных приложений на основе систем SPARC и x86/x64. В работе продемонстрировано, как развивать и развертывать приложение, распараллеленное с OpenMP и/или MPI.

This paper targets programmers and developers interested in utilizing parallel programming techniques to enhance application performance. The Oracle Solaris Studio software provides state-of-the-art optimizing and parallelizing compilers for C, C++ and Fortran, an advanced debugger, and optimized mathematical and performance libraries. Also included are an extremely powerful performance analysis tool for profiling serial and parallel applications, a thread analysis tool to detect data races and deadlock in memory parallel programs, and an Integrated Development Environment (IDE). The Oracle Message Passing Toolkit software provides the high-performance MPI libraries and associated run-time environment needed for message passing applications that can run on a single system or across multiple compute systems connected with high performance networking, including Gigabit Ethernet, 10 Gigabit Ethernet, InfiniBand and Myrinet. Examples of OpenMP and MPI are provided throughout the paper, including their usage via the Oracle Solaris Studio and Oracle Message Passing Toolkit products for development and deployment of both serial and parallel applications on SPARC and x86/x64 based systems. Throughout this paper it is demonstrated how to develop and deploy an application parallelized with OpenMP and/or MPI.

Сверхпластическая формовка сплавов на основе титана и никеля широко применяется в аэрокосмической промышленности. Основным преимуществом использования эффекта сверхпластичности является возможность формования материала до очень высоких деформаций при значительных растягивающих напряжений в материале. Представленная работа посвящена изучению возможности программного комплекса, основанного на методе конечных элементов, SFTC DEFORM прогнозировать разнотолщинность наноструктурного сплава ВТ6 при низкотемпературной сверхпластической формовке. Экспериментально разнотолщинность при свехпластической формовке наблюдается при локализации пластического течения и усугубляется локальным разупрочнением материала, которое обусловлено структурными изменениями. Для анализа экспериментально наблюдаемого течения металла была построена теоретическая модель. При расчете использовались два подхода. Первый подход включал использование интегрированной в программный комплекс модели ползучести. Так как эффект сверхпластичности наблюдается только в материалах с ультрамелкозернистой структурой, второй подход заключался в разработке комбинированной реологической модели материала с учетом структурного состояния. С помощью пользовательского программирования на языке Fortran уравнения реологической модели с учетом структурных превращений были интегрированы в DEFORM на солверном уровне. Использование КЭ-моделирования для подобных задач позволяет оценивать скорость деформации в разных точках заготовки, что является важным для поддержания состояния сверхпластичности в материале. Сопоставление применяемых моделей пластического течения позволило выявить влияние эволюции микроструктуры на течение сплава в режиме сверхпластичности. Результаты моделирования и теоретические выводы подтверждаются результатами стандартного испытания по Эриксону. В результате проведения работы было установлено следующее: а) программный пакет DEFORM позволяет спрогнозировать формообразование при низкотемпературной сверхпластичности; б) для повышения достоверности прогнозирования мест локализации деформации при сверхпластической деформации СМК материалов необходимо учитывать влияние измерения микроструктурного состояния и его влияние на свойства материалов в процессе деформирования.

Superplastic forming of Ni and Ti based alloys is widely used in aerospace industry. The main advantage of using the effect of superplasticity in sheet metal forming processes is a feasibility of forming materials with a high amount of plastic strain in conditions of prevailing tensile stresses. This article is dedicated to study commercial FEM software SFTC DEFORM application for prediction thickness deviation during low temperature superplastic forming of UFG Ti-6-4 alloy. Experimentally, thickness deviation during superplastic forming can be observed in the local area of plastic deformation and this process is aggravated by local softening of the metal and this is stipulated by microstructure coarsening. The theoretical model was prepared to analyze experimentally observed metal flow. Two approaches have been used for that. The first one is the using of integrated creep rheology model in DEFORM. As superplastic effect is observed only in materials with fine and ultrafine grain sizes the second approach is carried out using own user procedures for rheology model which is based on microstructure evolution equations. These equations have been implemented into DEFORM via Fortran user’s solver subroutines. Using of FEM simulation for this type of forming allows tracking a strain rate in different parts of a workpiece during a process, which is crucial for maintaining the superplastic conditions. Comparison of these approaches allows us to make conclusions about effect of microstructure evolution on metal flow during superplastic deformation. The results of the FEM analysis and theoretical conclusions have been approved by results of the conducted Erichsen test. The main issues of this study are as follows: a) the DEFORM software allows an engineer to predict formation of metal shape under the condition of low-temperature superplasticity; b) in order to augment the accuracy of the prediction of local deformations, the effect of the microstructure state of an alloy having sub-microcristalline structure should be taken into account in the course of calculations in the DEFORM software.

Радиофармацевтические препараты, меченные радиоизотопами йода, в настоящее время широко применяются в визуализирующих и невизуализирующих методах ядерной медицины. При оценке результатов радионуклидных исследований структурно-функционального состояния органов и тканей существенную роль приобретает параллельное моделирование кинетики радиофармпрепарата в организме. Сложность такого моделирования заключается в двух противоположных аспектах. С одной стороны, в чрезмерном упрощении анатомо-физиологических особенностей организма при разбиении его на компартменты, что может приводить к потере или искажению значимой для клинической диагностики информации, с другой — в излишнем учете всех возможных взаимосвязей функционирования органов и систем, что, наоборот, приведет к появлению избыточного количества абсолютно бесполезных для клинической интерпретации математических данных, либо модель становится вообще неразрешимой. В нашей работе вырабатывается единый подход к построению математических моделей кинетики радиофармпрепаратов с изотопами йода в организме человека при диагностических и терапевтических процедурах ядерной медицины. На основе данного подхода разработаны трех- и четырехкамерные фармакокинетические модели и созданы соответствующие им расчетные программы на языке программирования C⁺⁺ для обработки и оценки результатов радионуклидной диагностики и терапии. Предложены различные способы идентификации модельных параметров на основе количественных данных радионуклидных исследований функционального состояния жизненно важных органов. Приведены и проанализированы результаты фармакокинетического моделирования при радионуклидной диагностике печени, почек и щитовидной железы с помощью йодсодержащих радиофармпрепаратов. С использованием клинико-диагностических данных определены индивидуальные фармакокинетические параметры транспорта разных радиофармпрепаратов в организме (транспортные константы, периоды полувыведения, максимальная активность в органе и время ее достижения). Показано, что фармакокинетические характеристики для каждого пациента являются сугубо индивидуальными и не могут быть описаны усредненными кинетическими параметрами. В рамках трех фармакокинетических моделей получены и проанализированы зависимости «активность – время» для разных органов и тканей, в том числе для тканей, в которых активность радиофармпрепарата невозможно или затруднительно измерить клиническими методами. Также обсуждаются особенности и результаты моделирования и дозиметрического планирования радиойодтерапии щитовидной железы. Показано, что значения поглощенных радиационных доз очень чувствительны к кинетическим параметрам камерной модели — транспортным константам. Поэтому при индивидуальном дозиметрическом планировании радиойодтерапии следует уделять особое внимание получению точных количественных данных ультразвукового исследования и радиометрии щитовидной железы и на их основе идентификации параметров моделирования. Работа основана на принципах и методах фармакокинетики. Для численного решения систем дифференциальных уравнений фармакокинетических моделей мы использовали методы Рунге–Кутты и метод Розенброка. Для нахождения минимума функции нескольких переменных при идентификации параметров моделирования использовался метод Хука–Дживса.

Radiopharmaceuticals with iodine radioisotopes are now widely used in imaging and non-imaging methods of nuclear medicine. When evaluating the results of radionuclide studies of the structural and functional state of organs and tissues, parallel modeling of the kinetics of radiopharmaceuticals in the body plays an important role. The complexity of such modeling lies in two opposite aspects. On the one hand, excessive simplification of the anatomical and physiological characteristics of the organism when splitting it to the compartments that may result in the loss or distortion of important clinical diagnosis information, on the other – excessive, taking into account all possible interdependencies of the functioning of the organs and systems that, on the contrary, will lead to excess amount of absolutely useless for clinical interpretation of the data or the mathematical model becomes even more intractable. Our work develops a unified approach to the construction of mathematical models of the kinetics of radiopharmaceuticals with iodine isotopes in the human body during diagnostic and therapeutic procedures of nuclear medicine. Based on this approach, three- and four-compartment pharmacokinetic models were developed and corresponding calculation programs were created in the C⁺⁺ programming language for processing and evaluating the results of radionuclide diagnostics and therapy. Various methods for identifying model parameters based on quantitative data from radionuclide studies of the functional state of vital organs are proposed. The results of pharmacokinetic modeling for radionuclide diagnostics of the liver, kidney, and thyroid using iodine-containing radiopharmaceuticals are presented and analyzed. Using clinical and diagnostic data, individual pharmacokinetic parameters of transport of different radiopharmaceuticals in the body (transport constants, half-life periods, maximum activity in the organ and the time of its achievement) were determined. It is shown that the pharmacokinetic characteristics for each patient are strictly individual and cannot be described by averaged kinetic parameters. Within the framework of three pharmacokinetic models, “Activity–time” relationships were obtained and analyzed for different organs and tissues, including for tissues in which the activity of a radiopharmaceutical is impossible or difficult to measure by clinical methods. Also discussed are the features and the results of simulation and dosimetric planning of radioiodine therapy of the thyroid gland. It is shown that the values of absorbed radiation doses are very sensitive to the kinetic parameters of the compartment model. Therefore, special attention should be paid to obtaining accurate quantitative data from ultrasound and thyroid radiometry and identifying simulation parameters based on them. The work is based on the principles and methods of pharmacokinetics. For the numerical solution of systems of differential equations of the pharmacokinetic models we used Runge–Kutta methods and Rosenbrock method. The Hooke–Jeeves method was used to find the minimum of a function of several variables when identifying modeling parameters.

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

The paper presents an implementation of branch and bound algorithm employing coarse grained parallelism. The system is based on CBC (COIN-OR branch and cut) open-source MIP solver and inter-process communication capabilities of Erlang. Numerical results show noticeable speedup in comparison to single-threaded CBC instance.