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

Р е ц е н з е н т ы: д-р физ.-мат. наук проф. В. Б. Мелас (С.-Петерб. гос. ун-т) д-р физ.-мат. наук проф. Е. А. Крук (С.-Петерб. гос. ун-т аэрокосм. приборостр.)

Рекомендовано к изданию Редакционно-издательским советом математико-механического факультета С.-Петербургского государственного университета

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

С82 Межвуз. сб. / Под ред. О. Н. Граничина. СПб.: Изда-

тельство С.-Петербургского универститета, 2005. - 296 с. ISBN 5-288-03700-0

Сборник посвящен вопросам стохастической оптимизации в информатике и составлен по материалам одноименной регулярной серии семинаров для студентов, аспирантов и научных работников, проводившихся в 2003-2004 гг. на математико-механическом факультете С.-Петербургского универститета под руководством профессора кафедры системного программирования О.Н. Граничина.

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

ББК 32.811.7

Нестандартная машина Тьюринга

А. Г. Владимирович, О. Н. Граничин, А. А. Макаров

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

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

Проблемы тестирования сервера как задачи о моделировании редких событий

О. Н. Граничин, С. C. Сысоев, Д. С. Чуйко

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

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

Рандомизированный подход к обнаружению разрывов функции

О. Н. Граничин, В. И. Халидов

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

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

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

О. А. Измакова

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

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

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

С. Н. Комаров

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

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

Метод отжига

Лопатин А. С.

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

В работе рассмотрены реализации и свойства различных вариантов метода отжига.

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

Б. Т. Поляк

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

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

Нелинейная стохастическая оптимизация методом Монте-Карло

Л. Сакалаускас

Институт математики и информатики, Вильнюс, Литва

Рассматривается метод нелинейной стохастической оптимизации сериями выборок Монте-Карло. Предложена процедура останова алгоритма, основанная на проверке статистической гипотезы равенства градиента целевой функции нулю и оценке ее доверительного интервала. Предложены правила регулирования объема выборок и доказана п. н. сходимость с линейной скоростью по числу итераций полученной процедуры к решению задачи. Численное моделирование и решение практических примеров подтвердили теоретические выводы и показали, что разработанный метод позволяет решать задачи стохастической оптимизации с заданной точностью за приемлемое вычислительное время.

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

С. C. Сысоев

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

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

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

В. А. Терехов, И. Ю. Тюкин

Санкт-Петербургский государственный электротехнический университет (ЛЭТИ),

Institute for Physical and Chemical Research (RIKEN), Japan

Обсуждается подход к построению универсальных или типовых адаптивных регуляторов на основе обучаемых искусственных нейронных сетей (“нейроконтроллеров”), применимых для управления классом нелинейных динамических объектов. Анализируется проблема синтеза перестраиваемых в условиях неопределенности нелинейных законов управления, формируемых нейронной сетью в процессе ее обучения по целевым макропеременным.

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

Хантулева Т. А.

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

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

Регистровое представление чисел в ЭВМ и моделирование равномерно распределенных чисел с большим периодом

В. Б. Христинич, О. В. Христинич

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

В работе вводится удобное представление больших чисел в ЭВМ с учетом архитектуры процессоров типа Intel P6. Исходя из введенного представления рассматривается вопрос о моделировании равномерных псевдослучайных чисел с большим периодом. Основание системы счисления и форма представления случайного числа связываются с информативностью системы счисления.

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

С. И. Якушкин

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

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

Научное издание

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

Печатается без издательского редактирования

Обложка художника Е. А. Соловьевой Оригинал-макет О. Н. Граничина

Лицензия ИД №05697 от 24.08.2001

Подписано в печать 26.04.05. Формат 60 X 84/1₆.

Бумага офсетная. Печать офсетная

Усл. печ. л. 17,21

Заказ №

Издательство СПбГУ. 199034, С.-Петербург, Университетская наб., 7/9

Тел. (812) 328–96–17; факс (812) 328–44–22

E-mail: editor@unipress.ru

www.unipress.ru

Типография Издательства СПбГУ

199061, С.-Петербург, Средний пр., 41