Авторитетность издания
ВАК - К1
RSCI, ядро РИНЦ
Добавить в закладки
Следующий номер на сайте
№4
Ожидается:
09 Декабря 2024
Статьи журнала №1 2022
1. Интеллектуальный анализ и обработка больших разнородных данных для парирования угроз в сложных распределенных системах [№1 за 2022 год]Авторы: Брекоткина Е.С. (brekotkina@mail.ru) - Уфимский государственный авиационный технический университет (доцент), кандидат экономических наук; Павлов А.С. (asp.gis@gmail.com) - Уфимский государственный авиационный технический университет (доцент), кандидат технических наук; Павлов С.В. (psvgis@mail.ru) - Уфимский государственный авиационный технический университет (профессор), доктор технических наук; Христодуло О.И. (o-hristodulo@mail.ru ) - Уфимский государственный авиационный технический университет (профессор), доктор технических наук;
Аннотация: Предложен метод для прогнозирования некоторых угроз в сложных распределенных системах. Метод основан на интеллектуальном анализе и обработке больших разнородных данных, полученных в результате автоматического контроля изменения уровня воды в водных объектах и температуры воздуха в точке измерения. Такой контроль позволяет повысить эффективность планирования и реализации мероприятий по парированию подобных угроз. Будущее значение уровня воды в точке измерения выбирается по результатам обработки данных, накопленных за все предыдущие паводковые периоды. В качестве анализируемых данных используются измеренные в равноотстоящие моменты времени значения температуры воздуха и уровня воды, вычислительные значения изменения уровня воды и температуры воздуха, а также прогнозные значения (по официальным данным гидрометслужбы) изменения температуры воздуха. На основании вычисления ретроспективной частоты изменения этой температуры и уровня воды в соответствующей точке в качестве прогнозируемого значения предлагается выбрать то, которому соответствует максимальная частота появления такого сочетания измеряемых параметров. Результаты экспериментальной оценки точности прогнозирования уровня воды в водных объектах Республики Башкортостан в паводковый период 2021 г. подтверждают применимость предложенного метода прогнозирования для поддержки принятия решений по парированию угроз в сложных распределенных системах от резкого подъема воды даже при недостаточно автоматизированной системе наблюдений. При более широком изменении высокоавтоматизированных программно-аппаратных комплексов мониторинга паводковой ситуации существенно возрастает количество анализируемых и обрабатываемых программными средствами данных. Это, с одной стороны, усложнит применение традиционных методов использования данных, а с другой – повысит эффективность и востребованность предложенного в данной работе метода.
Abstract: The paper proposes a method of intelligent analysis and processing of large heterogeneous data for predicting threats in complex distributed systems. The method is based on the results of automatic monitoring of changes in water level in water bodies and air temperature at the measurement point. Such monitoring makes it possible to increase the efficiency of planning and implementing measures to fend off such and similar threats.
The method is based on general approaches and mathematical models previously used by the au-thors to develop adaptive algorithms for controlling gas turbine engines. It is particularly relevant in the context of the increasingly widespread introduction of software and hardware systems for monitor-ing the state of complex distributed systems and the exponential growth in the number of data used to support decision-making.
The choice of the future value of the water level at the measurement point is based on the results of processing the data accumulated over all previous flood periods on the compliance of the water level and its changes per day with the values of air temperature and its changes over the same day. The ana-lyzed data are the values of air temperature and water level measured at equidistant points in time, computational values of changes in the water level and air temperature, as well as forecast values (ac-cording to the official data of the hydrometeorological service) of changes in air temperature. Based on the calculation of the retrospective frequency of changes in this temperature and the water level at the corresponding point, it is proposed to choose as the predicted the value that corresponds to the maxi-mum frequency of occurrence of such a combination of measured parameters.
The paper presents the results of an experimental assessment of the accuracy of forecasting the wa-ter level in the water bodies of the Republic of Bashkortostan in the flood period of 2021 are. They confirm the applicability of the proposed forecasting method to support decision making to fend off threats in complex distributed systems from a sharp rise in water, even with the current insufficiently automated observation system. With a wider change in highly automated software and hardware com-plexes for monitoring the flood situation, the amount of data analyzed and processed by software sig-nificantly increases, which will complicate the application of traditional methods of data use, and, on the other hand, will increase the efficiency and relevance of the method proposed in this paper.
Ключевые слова: прогнозирование уровня воды, программно-аппаратные системы, прогнозирование угроз, сложные распределенные системы, интеллектуальный анализKeywords: water level forecasting, software and hardware systems, threat forecasting, complex distributed systems, intelligent analysis
Просмотров: 4025
2. Архитектура программной платформы разработки и тестирования нейросетевых моделей для создания специализированных словарей [№1 за 2022 год]
Авторы: Пуртов Д.Н. (idmitry.purtov@gmail.com) - Поволжский государственный технологический университет (аспирант); Сидоркина И.Г. (SidorkinaIG@volgatech.net) - Поволжский государственный технологический университет (профессор), доктор технических наук;
Аннотация: Предложена реализация программной платформы для создания нейросетевых моделей с их тестированием, используемых для формирования специализированных словарей автоматизиро-ванных систем. Она позволяет ускорить процесс поиска оптимального метода для разработки нейросетевой модели. В основе платформы лежит обзор существующих инструментов и методов, используемых для создания моделей анализа текстов и технологий виртуализации ПО. Авторами исследования разработана архитектура программной платформы для формирования специализированных словарей, обеспечивающая одновременное создание разных нейросетевых моделей в виртуальных контейнерах. Контейнерная виртуализация программных элементов, создающих и тестирующих нейросетевые модели, обеспечивает проведение всех математических расчетов по обработке текстовой информации, обучению и тестированию нейросетевой модели децентрализованно, параллельно и изолированно друг от друга. Обмен данными между виртуальными контейнерами, а также хранение результатов их работы осуществляются через специальную шину данных, представляющую собой дисковое пространство, к которому имеют доступ все контейнеры. Применение разработанной платформы позволит ускорить процесс поиска алгоритма создания специализированных словарей через проверку гипотез, основанных на использовании различных методов построения моделей. Ускорение процесса происходит благодаря параллельности и повторному использованию математических результатов общих этапов алгоритмов, математические расчеты которых проведены похожим алгоритмом. Это позволяет масштабировать и дробить процесс обучения за счет параллельного создания различных моделей, а также на уровне отдельных этапов создания моделей. Предложенная платформа была успешно применена для поиска локально-оптимального метода создания модели в текстах узкой тематики.
Abstract: The authors propose the implementation of a software platform for creating neural network models with their testing, used to create specialized dictionaries for automated systems. The software platform allows speeding up the process of finding the optimal method for creating a neural network model. The platform is based on an overview of existing tools and methods used to create clock analysis models and software virtualization technologies.
A research result is the proposed architecture of a software platform for creating specialized dic-tionaries that ensures the simultaneous creation of different neural network models in virtual contain-ers. A container virtualization of software elements that create and test neural network models provides all mathematical calculations for processing text-based information; decentralized, in parallel and iso-lated training and testing a neural network model. The data exchange between virtual containers, as well as the storage of all the results of the container's operation occurs through a special data bus, which is disk space that all containers have access to.
The use of the developed platform can speed up the process of searching for an algorithm for creat-ing specialized dictionaries through testing various hypotheses based on various methods for con-structing models. The process acceleration occurs due to the parallelism and reuse of the mathematical results of the general stages of algorithms whose mathematical calculations were carried out by a simi-lar algorithm. This allows scaling and splitting the learning process not only through the parallel crea-tion of various models, but also at the level of individual model creation stages. The proposed platform was successfully used to find a locally optimal method for creating a model in highly specialized lim-ited-field texts.
Ключевые слова: модульная архитектура, docker, sklearn, python, нейросетевая модель, виртуализация средыKeywords: modular architecture, docker, sklearn, python, a neural network, environment virtualization
Просмотров: 3922
3. Системы и подходы для обработки информации, представленной большими динамическими графами [№1 за 2022 год]
Автор: Гуляевский С.Е. (sgulyaevsky@gmail.com) - Институт систем информатики им. А.П. Ершова СО РАН (аспирант);
Аннотация: В статье сделан обзор ключевых особенностей и преимуществ основных существующих под-ходов и систем обработки больших графов на персональном компьютере, таких как GraphChi, TurboGraph, GraphChi-DB и другие, а также распределенных систем, таких как Apache GraphX. Особое внимание уделено задачам, требующим в процессе вычислений существенных изменений в структуре графа, и особенностям реализации таких задач в системах обработки графов. Проведены сравнительные эксперименты с использованием известного алгоритма восстановления сети связей между узлами по наблюдаемому распространению инфекций среди населения или распространению новостей и мемов в социальных сетях. В используемом алгоритме для по-лучения оценок изменяющейся во времени структуры и временной динамики предполагаемой сети применяется стохастический градиент. Алгоритм был реализован для моделей вычисления GraphChi и Apache Spark, измерена скорость выполнения для различных наборов реальных и синтетических данных, описаны ограничения для этих моделей вычисления, обнаруженные в процессе экспериментов. Для реализации GraphChi вычисления проведены на одиночном компьютере, для Apache Spark – на различном количестве серверов в кластере. Показано, что существующие системы разделяются на три класса: быстрые системы со стати-ческим разбиением графа на разделы и дорогим переразбиением при существенных изменениях структуры; в среднем более медленные системы, способные эффективно обрабатывать большие объемы изменений; еще более медленные, но хорошо масштабируемые системы, компенсирующие низкую удельную производительность возможностью масштабировать вычисления на кластеры из большого количества узлов. Сделан вывод, что проблема эффективного хранения и об-работки динамических графов в полной мере не решена и требует дополнительного исследования.
Abstract: The paper performes an overview of the key features and advantages for the main existing approaches and systems for processing large graphs on a personal computer. The analysis involves single PC graph processing systems such as GraphChi, TurboGraph, GraphChi-DB and distributed systems like Apache GraphX. Special attention is paid to the problems that require significant changes in the graph structure during the commutation process and the details of implementing such algorithms in graph processing systems.
The conducted experiments used a well-known algorithm for network inference based on the ob-served spread of infections among the population, or the spread of news and memes in social networks. The algorithm relies on a stochastic gradient to obtain estimates of the time-varying structure and tem-poral dynamics of the proposed network. The algorithm was implemented for GraphChi and Apache Spark computations models. The authors measured the performance for various real and synthetic da-tasets, described several limitations for these computation models discovered during experiments. Computations were performed on a single computer for GraphChi, and on a cluster of various sizes for the Apache Spark based implementation.
According to the results of the review and the conducted experiments, the existing systems are di-vided into three classes: fast systems with static graph partition and expensive repartition with signifi-cant structure changes; on average, slower systems that are able to handle large amounts of changes ef-ficiently; even more slower but highly scalable systems that compensate low single node performance with the ability to scale computation to a large number of nodes. The conclusion drawn from the con-ducted review and experiments shows that the problem of dynamic graphs efficient storage and pro-cessing is still not solved and requires additional research.
Ключевые слова: структуры данных, разработка и анализ алгоритмов, динамические графы, системы управления данными, алгоритмы на графахKeywords: data structures, algorithm design and analysis, dynamic graphs, data management systems, graph algorithms
Просмотров: 3895
4. Метод адаптивной классификации изображений с использованием обучения с подкреплением [№1 за 2022 год]
Автор: Елизаров А.А. (artelizar@gmail.com) - Казанский (Приволжский) федеральный университет (магистрант);
Аннотация: В статье представлен метод классификации изображений с использованием, помимо базовой нейронной сети, дополнительной, способной адаптивно концентрироваться на классифицируемом объекте изображения. Задача дополнительной сети является задачей о контекстном многоруком бандите и сводится к предсказанию такой области на исходном изображении, при вырезании которой в процессе классификации возрастет уверенность базовой нейронной сети в принадлежности объекта на изображении правильному классу. Обучение дополнительной сети происходит с помощью методов обучения с подкреплением и стратегий достижения компромисса между эксплуатацией и исследованием при выборе действий для решения задачи о контекстном многоруком бандите. На подмножестве набора данных ImageNet-1K проведены различные эксперименты по выбору архитектуры нейронной сети, алгоритма обучения с подкреплением и стратегии исследования при обучении. Рассмотрены такие алгоритмы обучения с подкреплением, как DQN, REINFORCE и A2C, и такие стратегии исследования, как -жадная, -softmax, -decay-softmax и метод UCB1. Большое внимание уделено описанию проведенных экспериментов и обоснованию полученных результатов. Предложены варианты применения разработанного метода, демонстрирующие увеличение точности классификации изображений по сравнению с базовой моделью ResNet. Дополнительно рассмотрен вопрос о вычислительной сложности данного метода. Дальнейшие исследования могут быть направлены на обучение агента на изображениях, не задействованных при обучении сети ResNet.
Abstract: The paper proposes a method for image classification that uses in addition to a basic neural network for image classification an additional neural network able to adaptively concentrate on the classified im-age object. The task of the additional network is the contextual multi-armed bandit problem, which re-duces to predicting such area on the original image, which is, when cut out of the classification process, will increase the confidence of the basic neural network that the object on the image belongs to the cor-rect class. The additional network is trained using reinforcement learning techniques and strategies for compromising between exploration and research when choosing actions to solve the contextual multi-armed bandit problem.
Various experiments were carried out on a subset of the ImageNet-1K dataset to choose a neural network architecture, a reinforcement learning algorithm and a learning exploration strategy. We con-sidered reinforcement learning algorithms such as DQN, REINFORCE and A2C and learning explora-tion strategies such as -greedy, -softmax, -decay-softmax and UCB1 method. Much attention was paid to the description of the experiments performed and the substantiation of the results obtained.
The paper proposes application variants of the developed method, which demonstrate an increase in the accuracy of image classification in comparison with the basic ResNet model. It additionally consid-ers the issue of the computational complexity of the developed method.
Ключевые слова: задача о контекстном многоруком бандите, обучение с подкреплением, классификация изображений, компьютерное зрение, нейронные сети, машинное обучение, искусственный интеллектKeywords: contextual multi-armed bandit problem, time, reinforcem ent learnin, image classification, computer vision, neural network, machine learning, artificial intelligence
Просмотров: 5298
5. Формальная модель многоагентных систем для федеративного обучения [№1 за 2022 год]
Авторы: Юлейси Г.П. (yuleisy2688@gmail.ru) - Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина) (аспирант); Холод И.И. (iiholod@mail.ru) - Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина) (доцент), кандидат технических наук;
Аннотация: В статье представлена формальная модель многоагентных систем для федеративного обучения. Концепция федеративного обучения очень близка к многоагентным системам, поскольку агенты позволяют обучать модели машинного обучения на локальных устройствах, сохраняя при этом конфиденциальную информацию. Возможности агентов взаимодействовать друг с другом позволяют обобщать (агрегировать) такие модели и повторно их использовать. В работе описываются взаимодействие и координация агентов, которые должны осуществляться с учетом стратегий обучения: последовательно, когда модель обучается по очереди на каждом узле; централизованно, когда модели обучаются параллельно на каждом узле и агрегируются на центральном сервере; децентрализованно, когда обучение и агрегация выполняются на каждом из узлов. Выделены основные типы агентов, необходимые для выполнения полного цикла федеративного обучения: принимающий задачу от пользователя, собирающий информацию о среде, выполняющий планирование обучения, выполняющий обучение на узле с данными, предоставляющий информацию и доступ к данным, осуществляющий агрегацию моделей. Для каждого из агентов определены основные действия и типы сообщений, которыми они обмениваются. Проанализированы и описаны конфигурации размещения агентов для каждой из стратегий федеративного обучения. На основе предложенной формальной модели можно осуществлять разработку многоагентных систем, используемых для задач федеративного обучения, а на основе выделенных типов агентов и видов сообщений – платформы агентов, сами агенты и протоколы их взаимодействия.
Abstract: Recently, the concept of federated learning has been actively developing. This is due to the tightening of legislation in the field of working with personal data. Federated learning involves performing data training directly on the nodes where the data is stored. As a result, there is no need to transfer data an-ywhere, and they remain with the owners. To generalize the trained models, they are sent to the server that performs the aggregation.
The concept of federated learning is very close to a multi-agent system, since agents allow training machine learning models on local devices while maintaining confidential information. The ability of agents to interact with each other makes it possible to generalize (aggregate) such models and reuse them.
Taking into account the tasks that are solved by the federated learning methods, there are several learning strategies. Learning be carried out as follows: sequentially when the model is trained in turn at each node; centrally when models are trained in parallel at each node and aggregated on a central serv-er; or decentralized where training and aggregation is performed on each of the nodes. Interaction and coordination of agents should be carried out taking into account these learning strategies.
This article presents a formal model of multi-agent systems for federated learning. It highlights the main types of agents required to complete the full cycle of federated learning: an agent that accepts a task from a user; an agent that collects information about the environment; an agent performing train-ing planning; an agent performing training on a data node; an agent providing information and access to data; an agent performing model aggregation. For each of them, the paper defines the main actions and types of messages exchanged by such agents. It also analyzes and describes the configurations of agent placement for each of the federated learning strategies.
Ключевые слова: модель, мультиагентные системы, коммуникация, федеративное обучение, агентKeywords: mathematical model, multi-agent systems, communication, federated learning, agent
Просмотров: 4983
6. Прототип программного комплекса для анализа аккаунтов пользователей социальных сетей: веб-фреймворк Django [№1 за 2022 год]
Авторы: Олисеенко В.Д. (vdo@dscs.pro) - Санкт-Петербургский федеральный исследовательский центр РАН, лаборатория теоретических и междисциплинарных проблем информатики (младший научный сотрудник); Абрамов М.В. (mva@dscs.pro) - Санкт-Петербургский федеральный исследовательский центр РАН, лаборатория теоретических и междисциплинарных проблем информатики (руководитель лаборатории), кандидат технических наук; Тулупьев А.Л. (alt@dscs.pro) - Санкт-Петербургский федеральный исследовательский центр РАН, лаборатория теоретических и междисциплинарных проблем информатики, Санкт-Петербургский государственный университет, кафедра информатики (профессор, главный научный сотрудник), доктор физико-математических наук; Иванов К.А. (mail@dscs.pro) - Санкт-Петербургский государственный университет, кафедра информатики (бакалавр);
Аннотация: В статье рассматриваются вопросы реализации прототипа исследовательско-практического комплекса для автоматизации анализа аккаунтов пользователей в социальных сетях. Данный прототип используется в качестве инструмента для косвенной оценки выраженности психологиче-ских особенностей пользователей, их уязвимостей к социоинженерным атакам и выработки рекомендаций по защите от них. Прототип разработан на языке программирования Python 3.8 с применением веб-фреймворка Django 3.1, а также PostgreSQL 13.2 и Bootstrap 4.6. Цель работы заключается в повышении оперативности процесса извлечения информации из размещаемых в социальных сетях данных, позволяющей косвенно оценить психологические, поведенческие и иные особенности пользователей, и достигается через автоматизацию извлечения указанных данных и разработку инструментария для их анализа. Предметом исследования являются методы автоматизированного извлечения, предобработки, унификации и представления данных из аккаунтов пользователей социальных сетей в контексте их защиты от социоинженерных атак. Предложенный прототип приложения на основе веб-фреймворка Django решает задачу автоматизированного извлечения, предобработки, унификации и представления данных со страниц пользователей социальных сетей, что является одним из важных этапов в построении системы анализа защищенности пользователей от социоинженерных атак, опирающейся, в свою очередь, на синтез профиля пользователей. Теоретическая значимость работы заключается в комбинировании и апробации через автоматизацию разработанных ранее методов и подходов для восстановления пропущенных значений атрибутов аккаунта и сопоставления аккаунтов пользователей социальных сетей на предмет их принадлежности одному пользователю. Практическая значимость состоит в разработке прикладного инструмента, размещенного на поддомене sea.dscs.pro и позволяющего производить первичный анализ аккаунтов пользователей социальных сетей.
Abstract: The paper considers the issues implementing a prototype of a research and practical complex to auto-mate the analysis of user accounts in social networks. Such prototype is used as a tool to indirectly as-sess users’ psychological features manifestation, their vulnerabilities to social engineering attacks as well as to develop recommendations for protection against these attacks. The prototype is developed in the Python 3.8 programming language using the Django 3.1 web framework and PostgreSQL 13.2, Boot-strap 4.6.
This paper aims to increase the efficiency of extracting information from data posted by users in social networks, which allows indirect assessment of psychological, behavioral and other characteris-tics of users. The goal is achieved by automating data extraction and developing tools for their analy-sis. The subject of the study is the methods of automated extraction, pre-processing, unification, and presentation of data from users' accounts in social networks to protect them against social engineering attacks.
A prototype application based on the Django web framework solves the problem of automated ex-traction, preprocessing, unification, and presentation of data from user accounts in social networks. The solution of this problem is one of the essential steps to build a system for analyzing the security of users from social engineering attacks. The theoretical significance of the work is in the combination and validation through the automation of previously developed methods and approaches to recover missing values of the attributes of the account, the comparison of online social networks users' ac-counts for their belonging to the same user.
The practical significance comes from the development of an application tool located on the sub-domain sea.dscs.pro, which allows performing primary analysis of users' accounts in social networks.
Ключевые слова: социальные сети, социоинженерные атаки, информационная безопасность, веб-фреймворк django, анализ аккаунта пользователя в социальной сетиKeywords: social networks, social engineering attacks, infosecurity, web framework django, analysis of the user's social network account
Просмотров: 4778
7. Программное обеспечение для решения обобщенной задачи коммивояжера с ограничениями предшествования [№1 за 2022 год]
Авторы: Петунин А.А. (a.a.petunin@urfu.ru, aapetunin@gmail.com) - Уральский федеральный университет им. первого Президента России Б.Н. Ельци-на (профессор), доктор технических наук; Уколов С.С. (s.s.ukolov@urfu.ru) - Уральский федеральный университет им. первого Президента России Б.Н. Ельци-на (младший научный сотрудник); Хачай М.Ю. (mkhachay@imm.uran.ru) - Институт математики и механики им. Н.Н. Красовского УрО РАН (профессор, зав. отделом), доктор физико-математических наук;
Аннотация: В статье рассматривается обобщенная задача коммивояжера с ограничениями предшествования (PCGTSP), в которой подобно классической задаче коммивояжера (TSP) ищется замкнутый цикл минимальной стоимости, при этом множество вершин разбито на непустые попарно непересекающиеся подмножества – кластеры и каждый допустимый маршрут обязан посетить каждый из кластеров в единственной вершине. Кроме того, множество допустимых маршрутов стеснено дополнительным ограничением на порядок посещения кластеров, то есть некоторые кластеры должны посещаться раньше других. Такая задача в отличие от TSP и обобщенной задачи коммивояжера (GTSP) является слабо исследованной как теоретически, так и с точки зрения проектирования и реализации алгоритмов. В данной работе предлагаются первые специализированные алгоритмы ветвей и границ, использующие в качестве начального приближения решения, полученные при помощи недавно разработанной эвристики PCGLNS. Исходная задача PCGTSP подвергается нескольким релаксациям, в результате чего получаются несколько нижних оценок на решение исходной задачи, наибольшая из которых используется для отсечения ветвей дерева поиска и сокращения тем самым перебора. Алгоритмы реализованы в виде открытого ПО на языке программирования Python 3 с использованием специализированной библиотеки NetworkX. Производительность предложенных алгоритмов оценивается на тестовых примерах из общедоступной библиотеки PCGTSPLIB в сравнении с общеизвестным солвером Gurobi, использующим недавно предложенную авторами модель MILP, и представляется вполне конкурентоспособной даже в текущей реализации. Разработанные алгоритмы могут применяться в широком классе практических задач, например, для оптимальной маршрутизации инструмента машин листовой резки с ЧПУ, а также для оценки качества решений, получаемых другими методами.
Abstract: The paper considers the generalized problem of the precedence constraint traveling salesman (PCGTSP). Like the classical traveling salesman problem (TSP), the authors search a minimum cost closed cycle in this problem, while the set of vertices is divided into nonempty pairwise disjoint sub-sets that are clusters; each feasible route must visit each cluster in a single vertex. In addition, the set of valid routes is constrained by an additional restriction on the order of visiting clusters, that is, some clusters must be visited earlier than others. In contrast to the TSP and the generalized traveling sales-man problem (GTSP), this problem is poorly studied both theoretically and from the point of view of algorithm design and implementation.
The paper proposes the first specialized branch-and-bound algorithms using the solutions obtained using the recently developed PCGLNS heuristic as an initial guess. The original PCGTSP problem un-dergoes several relaxations, therefore there are several lower bounds for the original problem; the larg-est of them is used to cut off the branches of the search tree and thereby reduce the enumeration. The algorithms are implemented as open source software in the Python 3 programming language using the specialized NetworkX library. The performance of the proposed algorithms is evaluated on test exam-ples from the PCGTSPLIB public library in comparison with the state-of-the-art Gurobi solver using the MILP model recently proposed by the authors, and seems to be quite competitive even in the cur-rent implementation.
The developed algorithms can be used in a wide class of practical problems, for example, for opti-mal tool routing for CNC sheet cutting machines, as well as for assessing the quality of solutions ob-tained using other methods.
Ключевые слова: схема хелда–карпа, динамическое программирование, метод ветвей и границ, ограничения предшествования, gtspKeywords: held-karp algorithm, dynamic programming, branch-and-bound method, precedence constraint, gtsp
Просмотров: 4010
8. Алгоритм поиска идиом в исходных текстах программ, использующий подсчет поддеревьев [№1 за 2022 год]
Авторы: Орлов Д.А. (orlovdmal@mpei.ru) - Национальный исследовательский университет «МЭИ» (доцент), кандидат технических наук;
Аннотация: Статья посвящена разработке алгоритма извлечения программных идиом из корпуса исходных текстов программ. Программные идиомы – это фрагменты исходных текстов программ, которые встречаются в исходных текстах различных программ и служат для решения одной типичной за-дачи. В данной работе программная идиома рассматривается как поддерево абстрактного синтаксического дерева (Abstract Syntax Tree, AST) программы, обеспечивающее максимальное сокращение информации в исходном коде программы при замене всех его вхождений на отдельную синтаксическую конструкцию (например, на вызов функции). Разработана метрика ценности поддерева в качестве идиомы, оценивающая сокращение количества информации от такой замены. Таким образом, поиск программных идиом сводится к поиску максимума функции ценности поддерева на множестве поддеревьев AST. Чтобы сократить перебор поддеревьев, поиск максимума функции ценности поддерева предлагается осуществлять методом наискорейшего спуска: на каждом шаге в поддерево добавляется узел, обеспечивающий наибольшее увеличение ценности поддерева. Для хранения поддеревьев используется структура, являющаяся обобщением префиксного дерева. Предложен алгоритм ускоренного извлечения программных идиом. Ускорение достигается за счет повторного использования результатов поиска максимума функции ценности поддерева. Для программной реализации разработанных алгоритмов, а также для исследования выбран язык Python, поскольку он имеет большой корпус исходных текстов и удобные средства построения AST. С помощью разработанной программной реализации проведен эксперимент по извлечению программных идиом из корпусов исходных текстов программ с открытым исходным кодом на языке Python. Полученные в результате программные идиомы являются осмысленными фрагментами исходных текстов программ. Показано, что применение разработанных алгоритмов к исходному коду одного проекта позволяет выявить варианты рефакторинга исследуемой программы.
Abstract: The paper is dedicated to programming idiom extraction algorithm design. Programming idiom is the fragment of source code which often occurs in different programs and used for solving one typical pro-gramming task. In this research the programming idiom is a source code fragment that often occurs in different programs and used for solving one typical programming task. In this research, the program-ming idiom is considered as the part of a program abstract syntax tree (AST), which provides maximum reduce of information quantity in a source code, when all of programming idiom occurrences are re-placed with certain syntax construction (e.g., function call).
The developed subtree value metric estimates information amount reduce after such replace. There-fore, the idiom extraction is reduced to search of subtree value function maximum on AST subtree set. To reduce a number of subtrees inspected, the authors use steepest descent method for subtree value function maximum search. At each step subtree is extended with one node, which provides maximum increase of a subtree value metric. Subtrees are stored in a data structure that is a generalization of a trie data structure.
The paper proposes an accelerated algorithm of idiom extraction. Programming idiom extraction speedup is achieved through reusing results of idiom efficiency maximum search. The paper also de-scribes the implementation of the developed algorithms. The algorithms are implemented in Python programming language. The implementation extracts programming idioms from source code written in Python. This programming language is chosen due to a large corpus of texts written in such language; it also includes convenient tools for building AST.
The authors carried out an idiom extraction experiment using the developed implementation. The idioms were extracted from corpora of an open-source program source code. The extracted program-ming idioms are source code fragments with own meaning. It is also shown that applying developed al-gorithms to a source code of a single software project can reveal possibilities of investigated program refactoring.
Ключевые слова: python, абстрактное синтаксическое дерево, извлечение данных, рефакторинг, анализ программ, программная идиомаKeywords: python, ast, data mining, refactoring, program analysis, programming idiom
Просмотров: 4045
9. Анализ эффективности процесса обслуживания потока заявок на создание ИТ-сервисов с использованием имитационной модели [№1 за 2022 год]
Авторы: Абдалов А.В. (senya@academ.msk.rsnet.ru) - Академия Федеральной службы охраны России (сотрудник); Гришаков В.Г. (liv@academ.msk.rsnet.ru) - Академия Федеральной службы охраны Российской Федерации, г. Орел, кандидат технических наук; Логинов И.В. (liv@academ.msk.rsnet.ru) - Академия Федеральной службы охраны России, г. Орел, кандидат технических наук;
Аннотация: В статье анализируется эффективность процесса обслуживания потока заявок на создание ИТ-сервисов с использованием метода имитационного моделирования. Показано, что известные средства имитационного моделирования не позволяют полностью сымитировать процесс обслуживания заявок в подразделениях администрирования инфокоммуникационными инфраструктурами, отличающийся управляемым характером потока ресурсов. В рамках исследования разработано ПО имитационного моделирования процесса обслуживания потока заявок на создание ИТ-сервисов. Основным отличием разработки является возмож-ность управления источником ресурсов в процессе обслуживания заявок и одновременного про-ведения экспериментов на одних исходных данных с несколькими дисциплинами обслуживания. Имитационная модель разработана в среде Microsoft Visual Studio и состоит из пяти макроблоков: генератор заявок, генератор ресурсов, обслуживающий прибор, блок алгоритма и блок про-ведения эксперимента. Блок алгоритма позволяет подключать внешние модели в виде блоков библиотек, реализующих через унифицированный интерфейс обработку потока заявок, включая возможность генерации команд на управление источником ресурсов. Блок эксперимента позволяет выполнять потоковые эксперименты на основе заданных настроек, а также сохраненных файлов экспериментов. Главным отличием разработанной имитационной модели является создание множества независимых потоков обслуживания заявок для различных алгоритмов. Возможность проведения сравнительного анализа проиллюстрирована серией экспериментов со стационарными и нестационарными потоками заявок и стационарным, нестационарным и управляемым потоками ресурсов на базе семейства альтернативных алгоритмов управления. Результаты применения имитационной модели процесса обслуживания заявок на создание инфокоммуникационных сервисов позволили оценить эффективность перспективных алгоритмов управления, разработанных в рамках исследования.
Abstract: The paper discusses the issues of analyzing the effectiveness of the process of servicing the flow of requests for creating IT services using the simulation modeling method. It shows that the well-known sim-
ulation tools do not allow full simulation of the application service process in information and communication in-frastructure administration units characterized by the controlled resource flow nature.
The study involved the development of software to simulate the process of servicing the flow of requests for creating IT services. Its main difference was the ability to manage the resource source during the process of servic-ing requests and the possibility of simultaneous experiments on the same source data with several service disci-plines.
The simulation model was developed in the Microsoft Visual Studio environment and consists of five mac-roblocks: a request generator, a resource generator, a service device, an algorithm block and an experiment block. The algorithm block allows connecting external models in the form of library blocks that implement the request flow processing through a unified interface, including the ability to generate commands to manage the resource source. The experiment block allows performing streaming experiments based on the specified settings and saved experiment files.
The main difference of the developed simulation model is the creation of multiple independent request service flows for various algorithms. The possibility of conducting comparative analysis experiments is illustrated by a se-ries of experiments with stationary and non-stationary request flows and stationary, non-stationary and controlled resource flow based on a family of alternative control algorithms.
The results of using a simulation model of the process of servicing requests for creating infocommunication services made it possible to evaluate the effectiveness of the developed promising control algorithms within the framework of the study.
Ключевые слова: ит-инфраструктура, адаптивное управление, распределение ресурсов, ит-подразделение, ит-сервисKeywords: IT-infrastructure, adaptive management, resource allocation, it department, it services
Просмотров: 4043
10. Метод создания параллельных программных средств моделирующих комплексов военного назначения [№1 за 2022 год]
Автор: Аксенов М.А. (aksen1985@mail.ru) - Военная академия воздушно-космической обороны им. Г.К. Жукова (адъюнкт);
Аннотация: В статье рассмотрены вопросы выбора алгоритмов распараллеливания, реализованных в инструментальных средствах разработки параллельных программ для многоядерных (многопроцессорных) вычислительных систем с общей памятью. Целью данного исследования является оценка влияния времени выполнения распараллеленных циклических участков целевой программы при многопоточном параллельном выполнении программы в многоядерных (многопроцессорных) ПЭВМ на показатели результатов имитационного моделирования боевых действий. Научная новизна заключается в разработке нового метода создания параллельных программных средств моделирующих комплексов военного назначения. Проведенный анализ современных программных средств моделирующих комплексов военного назначения показал, что на оперативность их применения при использовании по назначению в значительной степени оказывает влияние продолжительность расчетов при проведении моделирования. В работе приведены примеры расчетов в среде Mathcad. Для исключения ошибок выбора предпочтительных алгоритмов распараллеливания анализ производился на основе элементов математической статистики с введением вероятности доверительного интервала для оценки времени выполнения цикла определенным алгоритмом по верхней границе доверительного интервала. Предложен вариант построения программных средств на примере внедрения технологических разработок в программную архитектуру моделирующего комплекса.
Abstract: Nowadays modeling systems are actively created and used all over the world including the Armed Forces of the Russian Federation. The basis of these systems are modeling complexes, which are a set of technical and software tools providing calculations and imitation modeling.
The analysis of modern software tools for modeling military complexes has shown that the duration of the cal-culations performed during imitation largely influence the efficiency of their application when used directly.
Specific technological tools used in the development of parallelization of labor-intensive cyclic sections of modeling complexes allow minimizing the time spent on modeling under conditions of limited terms of using software tools. However, nowadays they are not implemented in the general software architecture of modeling complexes accepted for supply in the Armed Forces of the Russian Federation.
The paper considers the issues of choosing parallelization algorithms implemented in parallel software devel-opment tools for multi-core (multiprocessor) shared memory computing systems.
The purpose of the paper is to assess the impact of the execution time of parallelized cyclic sections of a target program with multithreaded parallel execution of the program in multi-core (multiprocessor) PCs on the results of combat imitation. The scientific novelty is in the development of a new method for creating parallel software tools for modeling military complexes.
The paper provides numeric examples of calculations in the Mathcad. To avoid errors in choosing preferred parallelization algorithms, the entire analysis is based on mathematical statistics elements with the probability of a confidence interval for estimating the cycle execution time by a certain algorithm considering the upper limit of the confidence interval. The author proposes a variant of constructing software tools on the example of introduc-ing technological developments into a software architecture of a modeling complex.
Ключевые слова: программное средство, моделирующий комплекс, алгоритм распараллеливания, цикл, число итераций, время выполненияKeywords: software, modeling complex, parallelization algorithm, cycle, number of iterations, execution time
Просмотров: 3687
| 1 | 2 | Следующая → ►
