Стохастические методы оптимизации в информатике

Стохастические системы

Множества достижимости и притяжения линейных систем с ограниченным управлением: описание с помощью инвариантных эллипсоидов

Б. Т. Поляк, д. т. н., П. С. Щербаков, д. ф.-м. н.

Институт проблем управления РАН, Москва

boris@ipu.ru sherba@ipu.ru

Исследуется задача описания множеств достижимости и притяжения линейной системы, заданной в пространстве состояний. Рассматриваются ограниченные управления в виде линейной обратной связи по состоянию, а также управления с насыщением. Множества достижимости и притяжения таких систем описываются в терминах инвариантных эллипсоидов с применением техники линейных матричных неравенств и задач полуопределенного программирования. Для управлений с насыщением используется идеология теории абсолютной устойчивости.

Ключевые слова: множество притяжения, инвариантный эллипсоид, линейные матричные неравенства, абсолютная устойчивость.

Исследование динамического объекта с ограничениями по выходным координатам c использованием метода инвариантного погружения

В. М. Понятский, к. т. н.

ГУП “Конструкторское бюро приборостроения”, Тула

kbkedr@tula.net, pwmru@rambler.ru

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

Ключевые слова: идентификация, динамический объект, оценка, параметры, ограничения.

Рандомизированные алгоритмы

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

А. Т. Вахитов, Л. С. Гуревич

Санкт-Петербургский государственный университет

av38@yandex.ru, gurevich.lev@gmail.com

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

Ключевые слова: стохастическая оптимизация, рандомизация, нестационарность, оптимизация, псевдоградиентный метод.

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

М. Ш. Мисриханов, д. т. н., В. Н. Рябченко, д. т. н.

Магистральные Электрические Сети Центра, Mосква

mms@mes-centra.ru rvn@mes-centra.ru

Описывается алгоритм решения задачи определения инвариантных нулей большой динамической системы с многими входами и многими выходами (MIMO). Задача определения инвариантных нулей путем рандомизированного квадрирования исходной MIMO-системы сводится к стандартной задаче на собственные значения числовых матриц. Практические приложения лежат в области больших электроэнергетических систем.

Ключевые слова: MIMO-система, инвариантные нули, квадрирование системы, задача на собственные значения, большая электроэнергетическая система.

Системы массового обслуживания

Анализ некоторых методов реализации приоритетной очереди

Е. А. Аксенова, канд. ф.-м. н., А. В. Соколов, д. ф.-м. н.

ИПМИ КарНЦ РАН, Петрозаводск

aksenova@krc.karelia.ru avs@krc.karelia.ru

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

Ключевые слова: приоритетная очередь, случайные блуждания, цепи Маркова.

Оптимальное размещение в памяти одного уровня n стеков и/или очередей

А. В. Драц, А. В. Соколов, д. ф.-м. н.

Петрозаводский универ-т, ИПМИ КарНЦ РАН, Петрозаводск

adeon88@mail.ru, avs@krc.karelia.ru

В работе рассмотрена проблема размещения n стеков и/или очередей в памяти одного уровня размера m для последовательного и связного способов представления. Предложены алгоритмы нумерации состояний и алгоритмы построения соответствующих поглощающих цепей Маркова и вычисления среднего времени до переполнения памяти для связного представления и нахождения оптимального (с точки зрения максимизации среднего времени до переполнения памяти) разбиения памяти для последовательных представлений. Приводятся результаты численных экспериментов.

Ключевые слова: LIFO-cтеки, FIFO-очереди, связанные списки, цепи Маркова, динамические структуры данных.

Вычисление показателя Ляпунова в стохастических динамических моделях систем с очередями

Н. К. Кривулин, к. ф.-м. н.

Санкт-Петербургский государственный университет

Nikolai@NK1200.spb.edu

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

Ключевые слова: стохастические динамические системы, показатель Ляпунова, идемпотентная алгебра, системы с очередями, среднее время цикла обслуживания.

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

Е. Н. Мосягина, М. К. Чирков, д. ф.-м. н.

Санкт-Петербургский государственный университет

vakh@star.math.spbu.ru

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

Ключевые слова: периодически нестационарный стохастический автомат, система автоматов, «нечеткая» среда, нечеткие условия, оптимальная стратегия.

Обучение и адаптация

Адаптивное оценивание параметров в параллельных многопользовательских параллельных вычислительных системах

А. Т. Вахитов

Санкт-Петербургский государственный университет

av38@yandex.ru

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

Ключевые слова: распределение заданий, параллельные вычисления, линейное оценивание, стохастическая оптимизация

Обзор алгоритмов стереозрения

А. Т. Вахитов, Л. С. Гуревич, Д. В. Павленко

Санкт-Петербургский государственный университет

av38@yandex.ru, gurevich.lev@gmail.com, dmit10@gmail.com

Задача стереозрения состоит в использовании двух или нескольких камер для получения данных о дальности до объекта. При этом входные данные могут представлять собой как просто отдельные изображения, так и видеоряд. Мы приводим обзор алгоритмов, связанных с частным случаем — сопоставлением двух изображений.

Ключевые слова: стереозрение.

Автоматическое выделение слов и словосочетаний из вьетнамских печатных текстов

Ле Чунг Хьеу Санкт-Петербургский гос. университет

Ле Ань Ву Университет ELTE, Бyдaпeшт, Венгрия

Ле Чунг Кьен Гуэ Университет, Вьетнам

vkhhieukien@yahoo.com, leanhvu@inf.elte.hu, hieukien@hotmail.com

В работе рассматриваются способы применения методов статистической обработки для построения списка вьетнамских слов и словосочетаний. На основе полученных результатов могут быть подготовлены входные данные для автоматической обработки текстов (Natural Language Processing) на естественном вьетнамском языке.

Ключевые слова: распознавание слов и словосочетаний на вьетнамском языке, методы статистической обработки, адаптация.

Адаптивный метод управления потоком решения изолированных заданий в параллельной вычислительной среде

М. А. Паньшенсков

Санкт-Петербургский государственный университет

mpansh@gmail.com

Модель решения изолированных заданий формулируется в расширенных терминах потока управления. Идентифицируются узкие места потока управления: пересылка данных по коммуникационным каналам, вычисление заданий на узлах. Для каждого из случаев предлагается алгоритм управления потоком решения заданий. Дается оценка времени исполнения предлагаемого алгоритма в зависимости от условий гетерогенной среды, в которой производятся вычисления.

Ключевые слова: распределенные вычисления, распределение заданий, адаптивные методы, коммуникация.

Исследование способов реализации адаптивной системы управления с фильтром Калмана

В. М. Понятский, к. т. н.

ГУП “Конструкторское бюро приборостроения”, Тула

kbkedr@tula.net, pwmru@rambler.ru

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

Ключевые слова: система управления, адаптация, динамическая ошибка, фильтр Калмана, полоса пропускания.

Обнаружение и локализация объектов в пространстве посредством самообучающейся модели кластеризации

В. Халидов, F. Forbes, M. Hansard, E. Arnaud, R. Horaud

Inria, Grenoble, France

vkhalidov@yahoo.com

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

Ключевые слова: обнаружение и локализация объектов, аудио и видео сенсоры, самообучение, кластеризация.

Алгоритмы устойчивой кластеризации на основе индексных функций и функций устойчивости

Д. С. Шалымов

Санкт-Петербургский государственный университет

shalydim@mail.ru

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

Ключевые слова: кластеризация, устойчивость кластеризации.

Информационные системы

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

О. Н. Граничин, д. ф.-м. н., О. А. Граничина, к. ф.-м. н.

Санкт-Петербургский государственный университет

Российский гос. педагогический университет им. А. И. Герцена

Oleg_granichin@mail.ru Olga_granichina@mail.ru

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

Ключевые слова: контроль качества, образовательный процесс, информационная система, метод рандомизированных сводных показателей.