САНКТ-ПЕТЕРБУРГСКИЙ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
НИИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
СТОХАСТИЧЕСКАЯ ОПТИМИЗАЦИЯ В ИНФОРМАТИКЕ
Издается с 2005 года
ВЫПУСК 5
Издательство С.-Петербургского университета
2009
УДК 519.712 БКК 32.811.7 С82
Ответственный редактор д. ф.-м. н., проф. О.Н. Граничин
Редакционная коллегия: Н. К. Кривулин (С.-Петерб. гос. ун-т),
Г. А. Леонов (С.-Петерб. гос. ун-т),
Б. Т. Поляк (ИПУ РАН),
А. В. Соколов (ИПМИ КарНЦ РАН),
А. Н. Терехов (С.-Петерб. гос. ун-т),
M. К. Чирков (С.-Петерб. гос. ун-т),
П. С. Щербаков (ИПУ РАН)
Печатается по постановлению
Редакционно-издательского совета
математико-механического факультета
С.-Петербургского государственного университета
С82 Стохастическая оптимизация в информатике.
Вып. 5 / Под ред. О. Н. Граничина -- СПб.: Издательство С.-Петербургского университета, 2009. - 240с. ISSN 1992-2922
Издание выпускается ежегодно (вып. 1, ненумерованный,
вышел в
Издание предназначено для специалистов в области информатики, студентов старших курсов и аспирантов, обучающихся на специальностях, связанных с обработкой информации.
ББК 32.811.7
© Авторы статей, 2009
Compressive Sensing
Рандомизация измерений и l1-оптимизация
О. Н. Граничин, д. ф.-м. н.
Санкт-Петербургский государственный университет
В последнее время активно развивается новая парадигма
кодирования/декодирования многоразрядных сигналов, имеющих “разреженное” (sparse)
представление в некотором базисе. В ее основе лежат идея рандомизации
измерений и ^-оптимизация. В работе описан новый метод “захватывания” и
представления сжимаемых сигналов значительно меньшим количеством разрядов, чем
в традиционном представлении сигналов по Найквисту. В англоязычной литературе
этот метод называется “Compressive Sensing” (сжимающим ощущение).
Ключевые слова:
рандомизированные
измерения, l_1-оптимизация, восстановление разреженных сигналов.
Рандомизированные
алгоритмы
Нестационарная стохастическая
оптимизация рандомизированными алгоритмами в случае бесконечной дисперсии
неопределенностей
А. Т. Вахитов
Санкт-Петербургский
государственный университет
В статье описана постановка задачи нестационарной
стохастической оптимизации. Предлагается рандомизированный алгоритм
стохастической аппроксимации с фиксированным шагом. Приводятся условия
стабилизации оценок и вероятностные границы невязки оценивания.
Ключевые
слова: нестационарная стохастическая оптимизация,
алгоритмы с фиксированным шагом, случайные величины с бесконечной дисперсией.
Рандомизированный
алгоритм R/S-анализа финансовых рядов
А. А. Гачков
Санкт-Петербургский
государственный университет
В последнее время активно развивается фрактальный подход к
оценке рисков на финансовых рынках. В качестве меры риска того или иного финансового
актива предлагается использовать фрактальную размерность динамики курса актива
за определенный период времени. Для того чтобы более точно оценивать риски
присущие этому активу, необходимо использовать более точные и адекватные
алгоритмы вычисления фрактальной размерности. На сегодняшний момент для этой
цели чаще всего используют алгоритм R/S-анализа, впервые разработанный
английским гидрологом Г. Херстом. Этот алгоритм достаточно хорошо работает на
входных данных, очищенных от помех. Однако при добавлении в систему помех и
отклонений, которые могут появляться, например, в результате воздействия
крупных рыночных игроков во время спекулятивной торговли, алгоритм выдает
большую погрешность. В статье предложен алгоритм рандомизированного
R/S-анализа, который позволяет более точно оценивать фрактальную размерность в
случае систематических помех.
Ключевые слова: R/S-анализ,
рандомизация, анализ финансовых данных.
О
быстрых вариантах алгоритма отжига (simulated annealing)
Тихомиров А. С., к. ф.-м. н.
Новгородский государственный
университет, Великий Новгород
Tikhomirov.AS@mail.ru,
TikhomirovAlesha@gmail.com
Получены быстрые варианты алгоритма simulated annealing. Показано, что число вычислений невырожденной целевой функции, необходимое для достижения требуемой точности ε решения задачи при аппроксимации “по аргументу”, может медленно (логарифмически) стремиться к бесконечности при стремлении ε к нулю.
Ключевые слова: алгоритм отжига, случайный поиск, стохастический поиск, глобальная оптимизация, стохастическая оптимизация.
Генерирование
устойчивых полиномов
П. С. Щербаков, д. ф.-м. н.
Институт проблем управления
РАН, Москва
В работе предпринимается попытка представить общий взгляд
на возможности рандомизированного подхода к построению устойчивых полиномов:
с единых позиций рассматриваются различные методы случайного генерирования
устойчивых полиномов в непрерывном и дискретном времени. Сравниваются свойства
и особенности методов, в частности, с точки зрения их реализации в системе
Matlab. Приведены иллюстративные результаты моделирования и указаны возможные
приложения.
Ключевые
слова:
устойчивые полиномы, рандомизация, методы случайного генерирования,
параметризация, Matlab-реализация.
Системы массового
обслуживания
Анализ
некоторых методов размещения в памяти очереди с n приоритетами
А. В. Драц, А. В. Соколов, д. ф.-м. н.
Петрозаводский универ-т, ИПМИ
КарНЦ РАН, Петрозаводск
adeon88@mail.ru, avs@krc.karelia.ru
В работе рассматриваются представления очереди с n
приоритетами в памяти одного уровня в виде массива и в виде n последовательных
FIFO-очередей. Возможны операции “вставить”, “удалить элемент с наибольшим
приоритетом” и “найти элемент”. Предложены алгоритмы нумерации состояний,
построения соответствующих поглощающих цепей Маркова и нахождения оптимального
разбиения памяти с точки зрения максимизации среднего времени работы до
переполнения. Приводятся результаты численных экспериментов.
Ключевые слова: очереди с приоритетами, FIFO-очереди, случайное блуждание, цепи Маркова, динамические структуры данных.
Специальные
процедуры оптимизации периодически нестационарных стохастических автоматов
А. Ю. Пономарева, к. ф.-м. н., Р. М. Строилов, М. К. Чирков, д. ф.-м. н.2
Санкт-Петербургский
государственный университет
Работа посвящена решению некоторых специальных проблем
оптимизации нестационарного стохастического конечного автомата с периодически
меняющейся структурой, которые связаны с теоретическим обоснованием и разработкой
ряда процедур, позволяющих в определенных условиях производить дополнительную
оптимизацию числа состояний такого автомата в различных структурных тактах с
учетом задания для него ограниченного множества начальных условий.
Ключевые слова: периодически нестационарные стохастические автоматы, оптимизация
стохастических автоматов, недостижимые состояния, ограниченные начальные
условия.
Модель
задачи ранжирования и ее исследование
А. В. Тимонина
МФТИ (ГУ), Москва
Изучаются системы большой размерности на примере сети Интернет. Исследование проводится с целью разработки алгоритма, который позволит наиболее точно находить PageRank web-страницы. В работе построена тестовая задача, на примере которой демонстрируется наличие существенного расхождения между точным значением “веса” страницы и значением, полученным из алгоритма PageRank.
Ключевые
слова: ранг, стохастическая матрица, собственный
вектор, ранг web-страницы, степенной метод.
Обучение и
адаптация
Адаптивное
управление автономной группой беспилотных летательных аппаратов
К. С. Амелин, Е. И. Антал, В.
И. Васильев, Н. О. Граничина
Санкт-Петербургский
Государственный Университет
konstantinamelin@mail.ru, cathrineantal@gmail.com, gnome@bk.ru, ngranichina@mail.ru
В статье рассматривается возможность применения мультиагентной адаптивной системы для управления группой “Беспилотных летательных аппа-ратов”(БПЛА, Unmanned Aerial Vehicles, UAV). Система основана на автономном общении агентов через радиосигнал. Адаптивность позволит группе оперативно принимать эффективные решения по изменению сценария выполнения поставленной задачи.
Ключевые
слова: мультиагентные
системы, адаптивность, беспилотные летательные аппараты, автономная группа
БПЛА.
Рандомизированный
алгоритм устойчивой кластеризации
Н. О. Граничина, Д. С.
Шалымов
Санкт-Петербургский
государственный университет
(ngranichina, shalydim)@mail.ru
Кластеризация активно изучается в таких областях, как статистика, распознавание образов, машинное обучение и др. В работе дается определение понятий кластеризации и устойчивости кластеризации, описывается актуальность и основные проблемы кластеризации, предлагается и обосновывается новый рандомизированный алгоритм устойчивой кластеризации.
Ключевые слова: кластеризация, устойчивость кластеризации, рандомизированные
алгоритмы, рандомизированный алгоритм устойчивой кластеризации.
Обучение
без учителя и статистический подход для сегментации и распознавания вьетнамских
слов
Ле Чунг Хьеу
Санкт-Петербургский
государственный университет
В работе рассматриваются две основные проблемы: (i) применение вероятностных моделей для распознавания и сегментации вьетнамских слов и фраз; (ii) итеративное построение оптимальной вероятностной модели с помощью обучения. На каждой итерации распознаются новые слова и их слоги соединяются друг с другом. Процесс соединения слогов повышает точность статистических функций, которые улучшают способность распознавания новых слов. Это обеспечивает сходимость вероятностной модели к оптимальной. Для эксперимента данные были взяты из 250 034 онлайн статей, в которых около 15 000 000 фраз. Точность алгоритма сегментации составляет более 90%. Получившийся вьетнамский словарь содержит более 100 000 слов и словосочетаний.
Ключевые слова: распознавание слов и словосочетаний на
вьетнамском языке, сегментация вьетнамских документов, методы статистической
обработки, обучение без учителя.
Электроэнергетика
Итерационный критерий статической устойчивости электроэнергетической системы, заданной в алгебро-дифференциальной форме
М. Ш. Мисриханов, д. т. н., В. Н. Рябченко, д. т. н.
Магистральные
Электрические Сети Центра, Mосква
(mms,
rvn)@mes-centra.ru
Описан новый итерационный критерий статической устойчивости электроэнергетической системы, заданной в алгебро-дифференциальной форме. Критерий построен на основе итерационного алгоритма вычисления обобщенной матричной сигнум-функции. В качестве примера рассмотрена задача анализа статической устойчивости модели ОЭС Центра, заданной в форме Коши и в алгебро-дифференциальной форме.
Ключевые слова: электроэнергетическая система, алгебро-дифференциаль-ная форма, статическая устойчивость, обобщенная матричная сигнум-функция, итерационная процедура.
Научное издание
Стохастическая
оптимизация в информатике
Выпуск 5
Печатается без издательского редактирования
Обложка художника Е. А. Соловьевой
Оригинал–макет О. Н. Граничина
Подписано в печать 12.11.09. Формат 60 × 84/16.
Бумага офсетная. Печать офсетная
Усл. печ. л. 15,0. Тираж 100 экз.
Заказ №
Издательство СПбГУ. 199004, С.-Петербург, В.О., 6-я линия, 11/21
Тел. (812) 328–96–17; факс (812) 328–44–22
E-mail: editor@unipress.ru
По вопросам реализации обращаться по адресу:
С.-Петербург, В.О., 6-я линия, д. 11/21, к. 21
Телефоны: 328–77–63, 325–31–76
E-mail: post@unipress.ru
Типография Издательства
СПбГУ
199061, С.-Петербург, Средний пр., 41