Вычислительные сложности моделирования динамических систем с антиципацией

Abstract

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

Поняття антиципації передбачає залежність майбутніх станів не лише від минулих, а й від самих майбутніх станів. Одна з основних причин, що обумовлює актуальність дослідження систем із антиципацією, — це надресурсоємність задачі моделювання систем із множинними сценаріями розвитку, оскільки антиципаційні системи часто передбачають багатозначність розв’язків. Невелика кількість робіт в даній області інформатики також обумовлена часто некоректністю постановки задачі в силу існування кількох можливих розв’язків. Тим самим системи із антиципацією представляють новий напрям в кібернетиці та моделі на основі антиципації більш точно можуть формально описувати велику кількість існуючих систем та процесів порівняно з класичними моделями із запізненням. Розглянуто такі нелінійні дискретні динамічні системи із сильною антиципацією, у яких майбутні стани можна представити явною залежністю від минулих за допомогою оператора Хатчинсона. Еволюція таких динамічних систем здійснюється в хаусдорфовому метричному просторі. Розглянуто принципову проблему моделювання таких систем — обсяг використання обчислювальних ресурсів. Введено ряд означень для дослідження динаміки систем із антиципацією. Представлено необхідні поняття теорії обчислювальних складностей. Важливий інструмент дослідження динаміки систем — карта динамічних режимів, побудова якої вимагає адаптації процедур пошуку періодичних траєкторій для систем такого типу. Запропоновано та детально описано процедури пошуку періодичних траєкторій динамічних систем із антиципацією. Послідовно отримано часові та просторові складності побудови станів, траєкторій та цих процедур в цілому. З метою мінімізації часової складності в ході симуляції систем із антиципацією обґрунтовано представлення станів відповідних динамічних систем за допомогою мультимножин. З метою подальшої оптимізації обчислювальних витрат слід враховувати структуру фазового простору динамічної системи із антиципацією, комбінуючи запропоновані процедури.

The concept of anticipation stands for the dependence of future states not only on the past, but also on themselves. One of the main reasons for the relevance of the study of the anticipatory systems is the over-complexity of modeling of the systems with multiple possible scenarios, since anticipatory systems often imply multiple solutions. A non-prevalence of this field of computer science is also often caused by not well-posing of the problem due to non-uniqueness of the solutions. Thus, systems with anticipation represent a new direction in cybernetics and the models based on anticipation can more formally describe a large number of existing systems and processes, compared with classical models with delay. In current paper, we consider such nonlinear discrete dynamical systems with strong anticipation, in which future states can be represented by an explicit dependence on the past with the help of the Hutchinson operator. The evolution of such dynamical systems is carried out in a Hausdorff metric space. The article focuses on the fundamental problem of modeling such systems – the amount of use of computing resources. A number of definitions have been introduced to study the dynamics of anticipatory systems. The necessary concepts of the theory of computational complexity are presented. An important tool for studying the dynamics of systems is the Atlas of Charts of dynamic regimes. The construction of which requires the adaptation of procedures for finding periodic trajectories for systems of this type. The article proposes and describes in detail the procedures for searching for periodic trajectories of dynamical systems with anticipation. Time and spatial complexities are obtained for the construction of states, trajectories, and these procedures in general. In order to minimize the time complexity during the simulation of anticipatory systems, the presentation of the states of the corresponding dynamical systems with the help of multisets is justified. In order to optimize further computational costs, one should take into account the structure of the phase space of a dynamical system with an anticipation, thereby combining the proposed procedures.