All issues

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

Представлена новая модификация парного фильтра Калмана, основанная на применении модифицированной взвешенной ортогонализации Грама–Шмидта и LD-разложении ковариационных матриц. Основными результатами данной работы являются: новая LD-модификация парного фильтра Калмана (теорема 1); новый алгоритм LD-ПФК для оценки состояния парных марковских моделей на основе прямой процедуры модифицированной взвешенной ортогонализации Грама–Шмидта и LD-разложения ковариационных матриц (алгоритм 2); результаты сравнительного анализа вычислительных свойств алгоритмов парной фильтрации. Полученные теоретические результаты дополняют теорию парной фильтрации в классе линейных дискретных парных марковских моделей с гауссовыми шумами.

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

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

The paper addresses the state estimation problem for pairwise Markov models with Gaussian noises. The class of pairwise Markov models generalizes the classical hidden Markov models. The key difference lies in the assumption that the Markov property holds not for the hidden process alone, but for the pair consisting of the state and the observation. This allows modeling more complex dependencies and, in particular, eliminates the requirement of Markovianity for the hidden process. For linear Gaussian pairwise models, Kalman filtering methods remain applicable, leading to the concept of the pairwise Kalman filter.

This work proposes a new modification of the pairwise Kalman filter based on the application of modified weighted Gram – Schmidt orthogonalization and the LD decomposition of covariance matrices. The main results are as follows: a novel LD modification of the pairwise Kalman filter (Theorem 1); a new LD-PKF algorithm for state estimation of pairwise Markov models, based on a direct procedure of modified weighted Gram–Schmidt orthogonalization and LD decomposition of covariance matrices (algorithm 2); results of comparative analysis on the numerical properties of pairwise discrete filtering algorithms.

The obtained theoretical results complement the theory of pairwise filtering in the class of linear discrete pairwise Markov models with Gaussian noises.

The developed algorithm is implemented in MATLAB. A series of numerical experiments are conducted, and the results demonstrate its effectiveness and numerical advantages over other existing modifications of the pairwise Kalman filter.

The presented results can be further used to develop new methods for parameter identification of pairwise Markov models.

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

This article describes a method to model the course of forest ecosystem succession to the climax state by means of a Markov chain. In contrast to traditional methods of forest succession modelling based on changes of vegetation types, several variants of the vertical structure of communities formed by late-successional tree species are taken as the transition states of the model. Durations of succession courses from any stage are not set in absolute time units, but calculated as the average number of steps before reaching the climax in a unified time scale. The regularities of succession courses are revealed in the proper time of forest ecosystems shaping. The evidences are obtained that internal features of the spatial and population structure do stochastically determine the course and the pace of forest succession. The property of developing vegetation of forest communities is defined as an attribute of stochastic determinism in the course of autogenous succession.

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

We consider one of the problems of transport modelling — searching the equilibrium distribution of traffic flows in the network. We use the classic Beckman’s model to describe time costs and flow distribution in the network represented by directed graph. Meanwhile agents’ behavior is not completely rational, what is described by the introduction of Markov logit dynamics: any driver selects a route randomly according to the Gibbs’ distribution taking into account current time costs on the edges of the graph. Thus, the problem is reduced to searching of the stationary distribution for this dynamics which is a stochastic Nash – Wardrope equilibrium in the corresponding population congestion game in the transport network. Since the game is potential, this problem is equivalent to the problem of minimization of some functional over flows distribution. The stochasticity is reflected in the appearance of the entropy regularization, in contrast to non-stochastic case. The dual problem is constructed to obtain a solution of the optimization problem. The universal primal-dual gradient method is applied. A major specificity of this method lies in an adaptive adjustment to the local smoothness of the problem, what is most important in case of the complex structure of the objective function and an inability to obtain a prior smoothness bound with acceptable accuracy. Such a situation occurs in the considered problem since the properties of the function strongly depend on the transport graph, on which we do not impose strong restrictions. The article describes the algorithm including the numerical differentiation for calculation of the objective function value and gradient. In addition, the paper represents a theoretical estimate of time complexity of the algorithm and the results of numerical experiments conducted on a small American town.

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

A new discrete ecological-evolutionary mathematical model is presented, in which the search mechanisms for evolutionarily stable migration routes of fish populations are implemented. The proposed adaptive designs have a small dimension, and therefore have high speed. This allows carrying out calculations on long-term perspective for an acceptable machine time. Both geometric approaches of nonlinear analysis and computer “asymptotic” methods were used in the study of stability. The migration dynamics of the fish population is described by a certain Markov matrix, which can change during evolution. The “basis” matrices are selected in the family of Markov matrices (of fixed dimension), which are used to generate migration routes of mutant. A promising direction of the evolution of the spatial behavior of fish is revealed for a given fishery and food supply, as a result of competition of the initial population with mutants. This model was applied to solve the problem of optimal catch for the long term, provided that the reservoir is divided into two parts, each of which has its own owner. Dynamic programming is used, based on the construction of the Bellman function, when solving optimization problems. A paradoxical strategy of “luring” was discovered, when one of the participants in the fishery temporarily reduces the catch in its water area. In this case, the migrating fish spends more time in this area (on condition of equal food supply). This route is evolutionarily fixes and does not change even after the resumption of fishing in the area. The second participant in the fishery can restore the status quo by applying “luring” to its part of the water area. Endless sequence of “luring” arises as a kind of game “giveaway”. A new effective concept has been introduced — the internal price of the fish population, depending on the zone of the reservoir. In fact, these prices are Bellman's private derivatives, and can be used as a tax on caught fish. In this case, the problem of long-term fishing is reduced to solving the problem of one-year optimization.