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




Скачать 389.32 Kb.
НазваниеМатематико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов
страница1/6
Дата17.04.2013
Размер389.32 Kb.
ТипЗадача
  1   2   3   4   5   6


САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Математико-механический факультет

Кафедра системного программирования


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


Дипломная работа студента 544 группы

Вахитова Александра Тимуровича


Научный руководитель,

профессор………………………………………………………/О.Н. Граничин/


Рецензент,

аспирант……………………………………………………../В.Е. Краснощеков/


“Допустить к защите”

Заведующий кафедрой,

профессор………………………………………………………./А.Н. Терехов/


Санкт-Петербург
2007 г.

Оглавление





Оглавление 2

Аннотация 3

Введение 3

Сравнение с близкими продуктами 6

Глава 1. Рандомизированные алгоритмы стохастической аппроксимации 9

Основные предположения. Постановка задачи 14

Глава 2. Сервис рекуррентных алгоритмов RecService 15

Язык описания компонентов и задач 18

Глава 3. Применения 19

Вводный пример 19

Интерактивный определитель в Интернет 20

Метод адаптивной балансировки 22

Задача балансировки 25

Алгоритм балансировки 26

Метод подстройки пользовательских приоритетов при поиске по коллекциям изображений 28

Задача подстройки приоритетов 30

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

Заключение. Результаты 36

Язык описания моделей, с которым работает сервис, не обеспечивает поддержки асинхронных процессов. Такая поддержка является существенным для реализации более сложных, чем описанные здесь, моделей в задачах искусственного интеллекта, например см. [43]. Тогда с помощью сервиса станет возможным интегрирование многоагентных систем. 36

ПРИЛОЖЕНИЕ 1. 37

Литература 38



Аннотация


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

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

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

Введение



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

Такие системы являются многокомпонентными и гибридными, то есть демонстрирующими как непрерывные, так и дискретные аспекты поведения (см. [1]). При этом оказывается, что непрерывные компоненты в иерархии управления системой являются более низкоуровневыми, в дискретных же содержится высокоуровневая логика (см. [1,2]).

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

Задача поиска экстремума может быть решена аналитически либо численно. В ряде случаев «в силу сложности или невозможности построения аналитического решения задача … может считаться решенной, если указан алгоритм, позволяющий численно построить приближенное решение с требуемой точностью» [3]. Рекуррентный алгоритм оптимизации имеет набор параметров, пересчитываемых на каждом шаге работы дискретной системы, на основе сделанных на этом шаге измерений (наблюдений) для оптимизации некоторой (неизвестной, не полностью заданной) функции стоимости (минимизации штрафной функции). При таком определении, в класс рекуррентных алгоритмов оптимизации попадает широкое множество алгоритмов для решения прикладных задач информатики и управления, примеры которых будут разобраны более детально в главе 3.

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

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

Глава 1 посвящена рекуррентным алгоритмам стохастической оптимизации. Автору совместно с О.Н. Граничиным и С.С. Сысоевым принадлежит результат о расширении класса допустимых помех для сходимости алгоритмов с пробным возмущением. Глава 2 посвящена описанию сервиса RecService, предназначенного для реализации моделей на основе рекуррентных алгоритмов стохастической оптимизации и им подобных.

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

В Заключении перечислены результаты работы и обсуждаются перспективы развития сервиса и расширения его функциональности.

Сравнение с близкими продуктами



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

Универсальные пакеты по сфере применения могут быть либо математическими, либо относиться к классу пакетов компонентного моделирования. Математические пакеты предполагают полное математическое задание систем (примером такого пакета является MATLAB). Пакеты компонентного моделирования предполагают отдельное описание каждого компонента системы, которое не обязательно полностью математически характеризует объект. Для пакетов компонентного моделирования характерна способность к проведению численных экспериментов над моделями. В [1] пакеты компонентного моделирования разделяются на промышленные и исследовательские.

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

Основными чертами RecService являются:

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

  • ориентация на веб-службы позволяет достаточно легко наблюдать работу систем и интегрировать их с приложениями, работающими в Интернете;

  • сервис способен инициировать процесс вычислений в рамках модели и продолжать его произвольно длительное время;

  • простота стандарта для реализации алгоритмов, в том числе декларативность описания данных для инициализации и хранения состояния компонента, обеспечивает легкость внедрения и изменения алгоритмов;

  • на основе сервиса можно организовывать сложные схемы совместного решения задач (метод классной доски, [4]). Сервис подразумевает реализацию надстроек для задания таких схем.

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

В первую очередь в составе сервиса реализуются алгоритмы стохастической оптимизации [5,6], которая является одной из областей прикладной математики, хорошо себя зарекомендовавшей при использовании в динамических и многопараметрических системах с существенной неопределенностью. О разнообразном опыте применения методов можно узнать на страницах сайта Applied Physics Laboratory John Hopkins University, США [7] и в публикациях [8].

Важной чертой RecService является использование шаблона внедрение зависимости (dependency injection) [9] и технологии веб-служб [10], а также средств хранения данных и сопоставления объектной модели реляционных отношений базы данных [11]. Частичным аналогом разрабатываемого сервиса является продукт Simulink компании MathWorks, средство для построения моделей динамических систем в рамках MATLAB, описанное в [12].
  1   2   3   4   5   6

Похожие:

Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconПетербургский Государственный Университет Математико-Механический Факультет Кафедра Системного Программирования
Сравнение различных методов хранения xml в реляционных базах данных и в разных системах
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования «Мультиагентные платформы и их применение в сетевых задачах»
Мас концентрируют все необходимые для таких технологий свойства с наибольшей выразительностью и полнотой. Результаты внедрения агентных...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Генерация веб-сервисов C#. net на основе bpel
Задача кодогенерации веб-сервисов возникла в рамках проекта «К700». «К700» — это проект создания рабочих мест оператора и инженера...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Поддержка структурных изменений в процессах загрузки данных
Исследование необходимости поддержки структурных изменений в источниках данных 35
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Разработка системы сравнения производительности субд
Существует большое количество разнообразных субд (Система управления базами данных), предназначенных для разных задач, однако обычно...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Разработка jre на ecma cli
Виртуальная машина, включая сборщик мусора и jit компилятор, является наиболее крупным монолитным компонентом среды управляемого...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Создание режима быстрого прототипирования в case-системе qreal
Использование различных видов диаграмм и сущностей позволяет пользователям наглядно и подробно описать необходимые модули и поведение...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет

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

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

Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница