All issues

Алгоритмы сопряженных градиентов представляют собой важный класс алгоритмов безусловной оптимизации с хорошей локальной и глобальной сходимостью и скромными требованиями к памяти. Они занимают промежуточное место между методом наискорейшего спуска и методом Ньютона, поскольку требуют вычисленияи хранения только первых производных и как правило быстрее методов наискорейшего спуска. В данном исследовании рассмотрен новый подход в задаче восстановления изображений. Он наследует одновременно методу сопряженных градиентов Флетчера – Ривза (FR) и трехкомпонентному методу сопряженных градиентов (TTCG), и поэтому назван авторами гибридным трехкомпонентным методом сопряженных градиентов (HYCGM). Новое направление спуска в нем учитывает текущее направления градиента, предыдущее направления спуска и градиент из предыдущей итерации. Показано, что новый алгоритм обладает свойствами глобальной сходимости и монотонности при использовании неточного линейного поиска типа Вулфа при некоторых стандартных предположениях. Для подтверждения эффективности предложенного алгоритма приводятся результаты численных экспериментов предложенного метода в сравнении с классическим методом Флетчера – Ривза (FR) и трехкомпонентным методом Флетчера – Ривза (TTFR).

Conjugate gradient algorithms represent an important class of unconstrained optimization algorithms with strong local and global convergence properties and simple memory requirements. These algorithms have advantages that place them between the steep regression method and Newton’s algorithm because they require calculating the first derivatives only and do not require calculating and storing the second derivatives that Newton’s algorithm needs. They are also faster than the steep descent algorithm, meaning that they have overcome the slow convergence of this algorithm, and it does not need to calculate the Hessian matrix or any of its approximations, so it is widely used in optimization applications. This study proposes a novel method for image restoration by fusing the convex combination method with the hybrid (CG) method to create a hybrid three-term (CG) algorithm. Combining the features of both the Fletcher and Revees (FR) conjugate parameter and the hybrid Fletcher and Revees (FR), we get the search direction conjugate parameter. The search direction is the result of concatenating the gradient direction, the previous search direction, and the gradient from the previous iteration. We have shown that the new algorithm possesses the properties of global convergence and descent when using an inexact search line, relying on the standard Wolfe conditions, and using some assumptions. To guarantee the effectiveness of the suggested algorithm and processing image restoration problems. The numerical results of the new algorithm show high efficiency and accuracy in image restoration and speed of convergence when used in image restoration problems compared to Fletcher and Revees (FR) and three-term Fletcher and Revees (TTFR).

Вывозка лесоматериалов из удаленных лесозаготовительных районов Сибири характеризуется высоким уровнем транспортных издержек. Наличие протяженных участков грунтовых лесовозных дорог, сезонные ограничения (весенняя распутица, зимники) и значительные расстояния от лесосек до магистральных транспортных узлов (50–200 км) обусловливают необходимость систематического решения задачи рационального планирования маршрутов вывозки.

В настоящей работе предложена математическая модель двухэшелонной маршрутизации транспортных средств (2E-VRP), адаптированная к условиям вывозки лесоматериалов в макрорегионе Урала и Сибири. Модель учитывает переменные транспортные затраты (пробег лесовозов), фиксированные затраты на задействование каждой единицы техники ($c_{fix}$ = 30 000 руб./рейс) и ограничения грузоподъемности. Задача приведена к форме QUBO — квадратичной безусловной бинарной оптимизации; емкостные ограничения интегрированы посредством штрафного коэффициента $\lambda_{cap} = 500$. Такое представление обеспечивает совместимость модели с современными специализированными решателями (квантовыми отжигателями и цифровыми аннилерами).

Апробация модели выполнена на реальной географии Уральского и Сибирского федеральных округов: 207 узлов логистической сети, 65 предприятий-потребителей, 8 магистральных транспортных узлов. Предложенный трехстадийный алгоритм «Допустимость прежде всего» формирует допустимый маршрутный план за 1,7 с и обеспечивает снижение суммарных транспортных затрат на 69% относительно базового генетического алгоритма. Последующая оптимизация методом имитации отжига дополнительно улучшает значение целевой функции QUBO на 55%.

The haulage of timber from remote logging areas of Siberia is characterized by high transportation costs. Long stretches of unpaved logging roads, seasonal constraints (spring thaw and winter roads), and considerable distances from cutting areas to main transport hubs (50–200 km) make systematic route planning essential.

This paper proposes a mathematical model of the two-echelon vehicle routing problem (2E-VRP) adapted to timber haulage in the macro-region of the Urals and Siberia. The model incorporates variable transportation costs (truck mileage), fixed costs of using each vehicle ($c_{fix}$ = 30 000 RUB per trip), and vehicle-capacity constraints. The problem is transformed into a QUBO (quadratic unconstrained binary optimization) formulation; capacity constraints are integrated through the penalty coefficient $\lambda_{cap}$ = 500. This representation makes the model compatible with modern specialized solvers, including quantum annealers and digital annealers.

The model is tested on the real geography of the Ural and Siberian Federal Districts: 207 nodes in the logistics network, 65 customer enterprises, and 8 main transport hubs. The proposed three-stage “Feasible-First” algorithm constructs a feasible routing plan in 1.7 s and reduces total transportation costs by 69% relative to a baseline genetic algorithm. Subsequent simulated annealing further improves the QUBO objective value by 55%.

Дана постановка задачи управления движения тела в вязкой жидкости. Движение тела индуцируется перемещением внутренних материальных точек. На основе численного решения уравнений движения тела и гидродинамических уравнений получены аппроксимирующие зависимости для вязких сил. С применением аппроксимаций решается задача оптимального управления движением тела по заданной траектории с применением гибридного генетического алгоритма. Установлена возможность направленного движения тела под действием возвратно-поступательного движения внутренней точки. Оптимальное управление направлением движения осуществляется движением другой внутренней точки по круговой траектории с переменной скоростью.

Statement of a problem of management of movement of a body in a viscous liquid is given. Movement bodies it is induced by moving of internal material points. On a basis the numerical decision of the equations of movement of a body and the hydrodynamic equations approximating dependencies for viscous forces are received. With application approximations the problem of optimum control of body movement dares on the set trajectory with application of hybrid genetic algorithm. Possibility of the directed movement of a body under action is established back and forth motion of an internal point. Optimum control movement direction it is carried out by motion of other internal point on circular trajectory with variable speed.

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

In this paper, we propose a new software for simulation of fluid-structure interaction. The software is designed for solving coupled problems and provides an interface for synchronization synchronisation and data exchange between existing fluid and structural solvers. Algorithms of coupling solvers and mesh deformation are discussed. The software can be used on hybrid CPU/GPU platforms.

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

Based on the modeling method using a mesh system, an algorithm is implemented for solving a unsteady problem with moving bodies The algorithm takes into account the movement and rotation of bodies according to a given law of motion. The algorithm is applied to analysis the flow around an infinite composed of cylinders with an elliptical cross-section, which either move across the flow or rotate with a change in the angle of attack. To simulate the flow of bodies with a sharp edge, characteristic of the profiles of gas turbine machines, an algorithm for constructing a mesh of type C with the inclusion of a certain area behind the profile is implemented. The program for modeling the flow near the profile is implemented within the framework of models of Euler equations, Navier – Stokes equations in the approximation of a thin layer with laminar viscosity and turbulent viscosity in the framework of an algebraic viscosity model. The program has also been adapted to solve the problems of internal gas dynamics of turbomachines. For this purpose, the method of setting the boundary conditions at the entrance and exit from the calculated area from the velocity to the pressure drop, as well as at the lateral boundaries from the free flow to the periodicity, was changed. This made it possible to simulate the flow of gas in the inter-blade channels of compressors and turbines of gas turbine engines. To refine the algorithm, a series of calculations of the aerodynamic parameters of several turbine cascades in various subsonic and supersonic modes and their comparison with the experiment were carried out. Calculations of turbine grating parameters were carried out within the framework of the inviscid and viscous gas model. The calculation and experiment were compared by the distribution of gas parameters near the profile, as well as by the energy losses of the flow in the cascade. Calculations have shown the applicability and correctness of the program to solve this class of problems. To test the program on the problems of external subsonic aerodynamics, calculations of the aerodynamic characteristics of an isolated airfoil in an undisturbed flow were performed. The results obtained allow us to assert the applicability of the hybrid grid method to various classes of problems of applied gas dynamics.

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

In this paper, we present new parallel algorithms for finite element analysis implemented in the FEStudio software framework. We describe the programming model of finite element method, which supports parallelism on different stages of numerical simulations. Using this model, we develop parallel algorithms of numerical integration for dynamic problems and local stiffness matrices. For constructing and solving the systems of equations, we use the CUDA programming platform.

Статья посвящена моделированию гидродинамических процессов мелководных водоемов на примере Азовского моря. В статье приведена математическая модель гидродинамики мелководного водоема, позволяющая вычислить трехмерные поля вектора скорости движения водной среды. Применение регуляризаторов по Б.Н. Четверушкину в уравнении неразрывности привело к изменению способа расчета поля давления, базирующегося на решении волнового уравнения. Построена дискретная конечно-разностная схема для расчета давления в области, линейные размеры которой по вертикали существенно меньше размеров по горизонтальным координатным направлениям, что является характерным для геометрии мелководных водоемов. Описаны метод и алгоритм решения сеточных уравнений с предобуславливателем трехдиагонального вида. Предложенный метод применен для решения сеточных уравнений, возникающих при расчете давления для трехмерной задачи гидродинамики Азовского моря. Показано, что предложенный метод сходится быстрее модифицированного попеременно-треугольного метода. Представлена параллельная реализация предложенного метода решения сеточных уравнений и проведены теоретические и практические оценки ускорения алгоритма с учетом времени латентности вычислительной системы. Приведены результаты вычислительных экспериментов для решения задач гидродинамики Азовского моря с использованием гибридной технологии MPI + OpenMP. Разработанные модели и алгоритмы применялись для реконструкции произошедшей в 2001 году в Азовском море экологической катастрофы и решения задачи движения водной среды в устьевых районах. Численные эксперименты проводились на гибридном вычислительном кластере К-60 ИПМ им. М.В. Келдыша РАН.

The article is devoted to modeling the shallow water hydrodynamic processes using the example of the Azov Sea. The article presents a mathematical model of the hydrodynamics of a shallow water body, which allows one to calculate three-dimensional fields of the velocity vector of movement of the aquatic environment. Application of regularizers according to B.N.Chetverushkin in the continuity equation led to a change in the method of calculating the pressure field, based on solving the wave equation. A discrete finite-difference scheme has been constructed for calculating pressure in an area whose linear vertical dimensions are significantly smaller than those in horizontal coordinate directions, which is typical for the geometry of shallow water bodies. The method and algorithm for solving grid equations with a tridiagonal preconditioner are described. The proposed method is used to solve grid equations that arise when calculating pressure for the three-dimensional problem of hydrodynamics of the Azov Sea. It is shown that the proposed method converges faster than the modified alternating triangular method. A parallel implementation of the proposed method for solving grid equations is presented and theoretical and practical estimates of the acceleration of the algorithm are carried out taking into account the latency time of the computing system. The results of computational experiments for solving problems of hydrodynamics of the Sea of Azov using the hybrid MPI + OpenMP technology are presented. The developed models and algorithms were used to reconstruct the environmental disaster that occurred in the Sea of Azov in 2001 and to solve the problem of the movement of the aquatic environment in estuary areas. Numerical experiments were carried out on the K-60 hybrid computing cluster of the Keldysh Institute of Applied Mathematics of Russian Academy of Sciences.

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

В подходе на основе гибридных генетических алгоритмов исходная задача минимизации интегрального функционала сводится к минимизации функции многих переменных. Заданный временной интервал разбивается на малые элементы, на каждом из которых управляющие воздействия аппроксимируются полиномами Лагранжа 2 и 3 порядков. Гибридные генетические алгоритмы при соответствующих настройках воспроизводят решение, близкое точному. Однако стоимость расчета 1 секунды физического процесса составляет порядка 300 секунд процессорного времени.

Для повышения быстродействия расчета управляющих воздействий предложен алгоритм на основе искусственных нейронных сетей. В качестве входного сигнала нейронная сеть принимает компоненты требуемого вектора перемещения. В качестве выходного сигнала возвращаются узловые значения полиномов Лагранжа, приближенно описывающих управляющие воздействия. Нейронная сеть обучается хорошо известным методом обратного распространения ошибки. Обучающая выборка генерируется с помощью подхода на основе гибридных генетических алгоритмов. Расчет 1 секунды физического процесса с помощью нейронной сети требует примерно 0.004 секунды процессорного времени. То есть на 6 порядков быстрее по сравнению в гибридным генетическим алгоритмом. Управление, рассчитанное с помощью искусственной нейронной сети, отличается от точного. Однако, несмотря на данное отличие, обеспечивает достаточно точное следование по заданной траектории.

In this paper we consider the controlled motion of a helical body with three blades in an ideal fluid, which is executed by rotating three internal rotors. We set the problem of selecting control actions, which ensure the motion of the body near the predetermined trajectory. To determine controls that guarantee motion near the given curve, we propose methods based on the application of hybrid genetic algorithms (genetic algorithms with real encoding and with additional learning of the leader of the population by a gradient method) and artificial neural networks. The correctness of the operation of the proposed numerical methods is estimated using previously obtained differential equations, which define the law of changing the control actions for the predetermined trajectory.

In the approach based on hybrid genetic algorithms, the initial problem of minimizing the integral functional reduces to minimizing the function of many variables. The given time interval is broken up into small elements, on each of which the control actions are approximated by Lagrangian polynomials of order 2 and 3. When appropriately adjusted, the hybrid genetic algorithms reproduce a solution close to exact. However, the cost of calculation of 1 second of the physical process is about 300 seconds of processor time.

To increase the speed of calculation of control actions, we propose an algorithm based on artificial neural networks. As the input signal the neural network takes the components of the required displacement vector. The node values of the Lagrangian polynomials which approximately describe the control actions return as output signals . The neural network is taught by the well-known back-propagation method. The learning sample is generated using the approach based on hybrid genetic algorithms. The calculation of 1 second of the physical process by means of the neural network requires about 0.004 seconds of processor time, that is, 6 orders faster than the hybrid genetic algorithm. The control calculated by means of the artificial neural network differs from exact control. However, in spite of this difference, it ensures that the predetermined trajectory is followed exactly.

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

The equilibrium configurations of charged electrons, confined in the hard disk potential, are analysed by means of the hybrid numerical algorithm. The algorithm is based on the interpolation formulas, that are obtained from the analysis of the equilibrium configurations, provided by the variational principle developed in the circular model. The solution of the nonlinear equations of the circular model yields the formation of the shell structure which is composed of the series of rings. Each ring contains a certain number of particles, which decreases as one moves from the boundary ring to the central one. The number of rings depends on the total number of electrons. The interpolation formulas provide the initial configurations for the molecular dynamics calculations. This approach makes it possible to significantly increase the speed at which an equilibrium configuration is reached for an arbitrarily chosen number of particles compared to the Metropolis annealing simulation algorithm and other algorithms based on global optimization methods.

Работа посвящена изучению волновых и релаксационных эффектов при импульсном истечении смеси газа с большим содержанием твердых частиц из цилиндрического канала при его начальном частичном заполнении. Задача сформулирована в двухскоростной двухтемпературной постановке и решалась численно гибридным методом крупных частиц второго порядка аппроксимации. Численный алгоритм реализован в виде параллельных вычислений с использованием базовых языковых средств Free Pascal. Применимость и точность метода для волновых потоков концентрированных газовзвесей подтверждены сопоставлением с тестовыми асимптотически точными решениями. Погрешность расчета на сетке невысокой детализации вх арактерных зонах течения двухфазной среды составила 10⁻⁶ . . . 10⁻⁵.

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

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

The paper is devoted to the study of wave and relaxation effects during the pulsed outflow of a gas mixture with a high content of solid particles from a cylindrical channel during its initial partial filling. The problem is formulated in a two-speed two-temperature formulation and was solved numerically by the hybrid large-particle method of the second order of approximation. The numerical algorithm is implemented in the form of parallel computing using basic Free Pascal language tools. The applicability and accuracy of the method for wave flows of concentrated gas-particles mixtures is confirmed by comparison with test asymptotically accurate solutions. The calculation error on a grid of low detail in the characteristic flow zones of a two-phase medium was 10^-6 . . . 10^-5.

Based on the wave diagram, the analysis of the physical pattern of the outflow of a gas suspension partially filling a cylindrical channel is performed. It is established that, depending on the degree of initial filling of the channel, various outflow modes are formed. The first mode is implemented with a small degree of loading of the high-pressure chamber, at which the left boundary of the gas-particles mixture crosses the outlet section before the arrival of the rarefaction wave reflected from the bottom of the channel. At the same time, the maximum value of the mass flow rate of the mixture is achieved. Other modes are formed in cases of a larger initial filling of the channel, when the rarefaction waves reflected from the bottom of the channel interact with the gas suspension layer and reduce the intensity of its outflow.

The influence of relaxation properties with changing particle size on the dynamics of a limited layer of a gas-dispersed medium is studied. Comparison of the outflow of a limited gas suspension layer with different particle sizes shows that for small particles (the Stokes number is less than 0.001), an anomalous phenomenon of the simultaneous existence of shock wave structures in the supersonic and subsonic flow of gas and suspension is observed. With an increase in the size of dispersed inclusions, the compaction jumps in the region of the two-phase mixture are smoothed out, and for particles (the Stokes number is greater than 0.1), they practically disappear. At the same time, the shock-wave configuration of the supersonic gas flow at the outlet of the channel is preserved, and the positions and boundaries of the energy-carrying volumes of the gas suspension are close when the particle sizes change.