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




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

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

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


В [29] описан алгоритм стохастической аппроксимации с рандомизированным пробным возмущением с проектированием. Для моделирования его сходимости в случае нерегулярных помех, описанного в [29], была построена модель (см рис. 1). В ней участвуют упомянутый алгоритм (компонент SPSA) и управляемый объект, а также проектор P для проецирования точек наблюдения, генерируемых алгоритмом, источник случайных возмущений Δ, источник нерегулярной помехи v, внутреннего зашумления объекта w.

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



Рис. 1

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


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

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

Теория подобных систем, определяющих принадлежность объекта к какому-либо множеству с уникальным присущим этому множеству набором свойств через серию экспериментов - вопросов известна как теория вопросников. Определяется множество допустимых вопросов T и множество событий E. Событие заключается в определении (класса, уникального свойства) некоторого объекта. Вопросом является опыт, нетривиально разделяющий какое-либо (не единичной мощности) подмножество E. План сложного эксперимента, то есть совокупность вопросов и последовательности, в которой они должны быть поставлены для идентификации событий множества E, называется вопросником для E. Множество T допустимых вопросов является подмножеством множества всех возможных вопросов. Естественным требованием к T является возможность отделить каждый элемент E от любого другого элемента E вопросами из T. Множество допустимых вопросов, совпадающее с множеством всех вопросов, называется полным, иначе – неполным. Подробно теория вопросников освещена в [32].

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

Субоптимальные методы решения задачи изложены в [34,35,36]. Среди них есть и адаптивные, основанные на рекуррентном пересчете оценок [36].



Рис. 2 Общая модель определителя с компонентом
для расчета по методу Лобанова


На рис. 2 показана декомпозиция процесса работы с ключом Webkey-X. Модель состоит из трех компонентов: базы данных ключа, алгоритма сортировки признаков, определяющего вопросник на каждом шаге, и пользователя, обеспечивающего ответ на один из предложенных вопросов. Инициирует каждый следующий шаг вычисления пользователь, посылая пару (C(k),s(k)) - выбранный вопрос и ответ на него.

В рамках работы по гранту Российского фонда фундаментальных исследований разработано несколько алгоритмов сортировки признаков для построения вопросника, близкого к оптимальному, которые в рамках этой модели можно заменять, так как они представляют собой разные компоненты, решающие одну задачу.
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
обратиться к администрации
Библиотека
Главная страница