Оглавление 2

Аннотация 3

Введение 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература 38

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

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

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

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

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

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

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

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

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

1. Колесов Ю.Б. Объектно-ориентированное моделирование сложных динамических систем. СПб. Изд-во СПбГПУ. 2004.

2. Звягин П.Н., Нечаев Ю.И. Нейросетевое управление морским динамическим объектом. Научная сессия МИФИ-2006. Нейроинформатика - 2006. Часть 2 Модели адаптивного поведения. Применение нейронных сетей. Применение нейронных сетей. Теория нейронных сетей. Изд-во МИФИ. 2006. С. 81-87

3. Поляк Б.Т. Введение в оптимизацию. М.: Наука. 1983.

4. Corkill D.D. Blackboard Systems. AI Expert, 6(9), 1991, pp. 40-47

5. Граничин О.Н., Поляк Б.Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М., Наука. 2003.

6. Kushner H., Yin G. Stochastic Approximation and Recursive Algorithms and Applications, 2nd ed., Springer, 2003.

7. SPSA: A Method For System Optimization, http://www.jhuapl.edu/spsa

8. Стохастическая оптимизация в информатике, сб. под ред. проф. Граничина О.Н. Т. 1. 2005., т. 2. 2006.

9. Fowler M., Inversion of Control Containers and the Dependency Injection pattern, http://www.martinfowler.com/articles/injection.html

10. Poutsma A., Spring Web Services - Reference Documentation, http://static.springframework.org/spring-ws/site/reference/html/index.html

11. Hibernate - Relational Persistence for Idiomatic Java. Hibernate Reference Documentation http://www.hibernate.org/hib_docs/v3/reference/en/html/

12. Черных И.В., Simulink: Инструмент моделирования динамических систем, http://www.nsu.ru/matlab/MatLab_RU/simulink/book1/index.asp.htm

13. Robbins H., Monro S., A stochastic approximation method, Ann. Math. Statist. V. 22, 1951, pp. 400-407

14. Kiefer J., Wolfowitz J. Statistical estimation on the maximum of a regression function. Ann. Math. Statist., V. 23, 1952, pp. 462-466.

15. Spall J. C. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation, IEEE Transactions on Automatic Control, V. 37, 1992, pp. 332-341.

16. Граничин О.Н. Об одной стохастической рекуррентной процедуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения, Вестник Ленингр. ун-та, сер. 1, в. 1, 1989, с. 92-93

17. Поляк Б.Т., Цыбаков А.Б. Оптимальные порядки точности поисковых алгоритмов стохастической аппроксимации, Проблемы передачи информации, 2, 1990, с. 45-53.

18. Blum J. R. Multidimensional stochastic approximation, Ann. Math. Statist., V. 9, 1954, pp. 737-744.

19. Вазан М., Стохастическая аппроксимация, М.: Мир, 1972.

20. Невельсон М.Б., Хасьминский Р.З. Стохастическая аппроксимация и рекуррентное оценивание, М.: Наука, 1972.

21. Михалевич В.С., Гупал А.М., Норкин В.И. Методы невыпуклой оптимизации , М.: Наука, 1987.

22. Fabian V. Stochastic approximation of minima with improved asymptotic speed, Ann. Math. Statist., v. 38., 1967. pp. 191-200.

23. Граничин О.Н., Процедура стохастической аппроксимации с возмущением на входе, Автоматика и телемеханика, 2, 1992, с. 97-104

24. Граничин О.Н. Оценивание точки минимума неизвестной функции, наблюдаемой на фоне зависимых помех, Проблемы передачи информации, 2, 1992, с. 16-20.

25. Граничин О.Н., Оптимальная скорость сходимости рандомизированных алгоритмов стохастической аппроксимации при почти произвольных помехах, Автоматика и телемеханика, 2, 2003, с. 88-99.

26. Chen H. F., Duncan T. E., Pasik-Duncan B. A Kiefer-Wolfowitz algorithm with randomized differences, IEEE Transactions on Automatic Control, V. 44, N 3, 1999. pp. 442-453.

27. Granichin O.N., Vakhitov A.T. Accuracy for the SPSA algorithm with two measurements. WSEAS Transactions on Systems. № 5. v. 5. May 2006. pp. 953-957.

28. Вахитов А.Т., Граничин О.Н., Сысоев С.С. Точность оценивания рандомизированного алгоритма стохастической оптимизации. Автоматика и телемеханика, 2006, № 4 , с.86-96.

29. Вахитов А.Т., Граничин О.Н.(СПбГУ) Рандомизированные алгоритмы оценивания при нерегулярных помехах, в сб. под ред. проф. Граничина О.Н., т. 2, 2006.

30. Milner R., The Polyadic pi-Calculus: A Tutorial, in Logic and Algebra of Specification. Springer-Verlag, 1993.

31. Johnson R. etc. The Spring Framework - Reference Documentation, 2.0.5, http://static.springframework.org/spring/docs/2.0.x/reference/index.html

32. Пархоменко П.П. Теория вопросников (обзор). Автоматика и телемеханика, №4 (1970)

33. Valdes-Perez R., Pericliev V., Pereira F. Concise, Intelligible, and Approximate Profiling of Multiple Classes. International Journal of Human-Computer Studies, Volume 53, Number 3, September 2000, pp. 411-436(26)

34. Свиридов А.В. Ключи в биологической систематике: теория и практика. М: Изд-во МГУ, 1994. 224 с.

35. Лобанов А.Л. Оценка диагностической ценности рядов признаков в многовходовых определителях, рассчитанных на использование ЭВМ. Тезисы докладов VI Коми республиканской молодежной научной конференции. 1974. Сыктывкар. c. 125-126.

36. Вахитов А.Т., Граничина О.А. Алгоритмы классификации за минимальное число шагов в сб. Стохастическая оптимизация в информатике под ред. Граничина О.Н., вып. 2, 2006, с. 167-174

37. Владимирович А.Г.(СПбГУ) Субоптимальный алгоритм распознавания образов в дискретном случае. в сб. Стохастическая оптимизация в информатике под ред. Граничина О.Н., вып. 1, 2005, с. 8-16

38. Шошмина И.В. и др. Использование Grid-технологий для крупномасштабных научных экспериментов. Часть 1. Введение в Grid-технологии с примерами практических занятий на базе ARC Nordugrid. СПб:Копи-Сервис, 2006. – 49 с.

39. Squire D., Muller W. and Muller H. Relevance feedback and term weighting schemes for content-based image retrieval, Visual Information and Information Systems. 1999. pp. 549-556.

40. Измакова О.А., Сысоев С.С. Алгоритм стохастической оптимизации с возмущением на входе в задаче самообучения. Труды Международной школы-семинара Адаптивные роботы 2004. М.-СПб, 2004, с. 49-52

41. Хованов Н. И. Анализ и синтез показателей при информационном дефиците. СПб., СПбГУ, 1996.

42. Гуревич Л.С., Адаптивный метод выбора каналов новостей. Дипломная работа, каф. системного программирования математико-механического факультета СПбГУ, 2007.

43. Граничин О.Н., Жувикина И.А. Новая модель процесса вычислений: обобщение концепции машины Тьюринга. Нейрокомпьютеры: разработка, применение, 2006, № 7 , с.24-31.

Примечаний нет.