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

СОДЕРЖАНИЕ

Амелина Н.О. (СПбГУ), Фрадков А.Л. (ИПМАШ РАН)

Метод усредненных моделей в задаче достижения консенсуса ............ 3

Васильев В.И. (СПбГУ)

Новый сетевой подход для задач, не имеющих однозначного решения.. 40

Кияев В.И. (СПбГУ), Герасимов Р.В. (СПбГУЭФ)

Интеллектуальный CRM на базе мультиагентного подхода.................... 50

Кривоконь Д.С. (СПбГУ)

Задача одновременной подстройки параметров камер и положений

наблюдаемых ими точек............................................................................ 95

Шац В.Н. (СПб) Обучающаяся модель самоорганизующейся системы 101

Комаров С.Н., Нестеров А.В., Серебрякова Г.М. (СПбГУ)

Информационная система вуза для целей учета и эффективного

использования недвижимого имущества ............................................................................................................... 115

Граничин О.Н. (СПбГУ)

48-50-е Международные конференции "Принятие решений и управление"

(IEEE CDC/CCC 2009, CDC 2010 и CDC-ECC 2011) ............................................................................................................... 142

Abstracts .................................................................................................................... 152

Amelina N.O. (SPbSU), Fradkov A.L. (SPbSU, IPME)

The method of averaged models for consensus problem............................................................................................................... 152

Vasilev V. I. (SPb) The new network-based approach for problems

without single solution ............................................................................................................... 153

Kiyaev V.I. (SPbSU),Gerasimov R.V. Smart CRM based on multi-agent approach.................................................................................................................... 154

Krivokon D.S. (SPbSU) Simultaneous adjustment of camera parameters and

positions of observed points ............................................................................................................... 155

Shats V.N. (SPb) Learning model of the self-organizing system .................................................................................................................... 156

Komarov S.N., Nesterov A.V., Serenryakova CM. (SPbSU)

The information system of the university for accounting purposes and

effective usage of real estate ............................................................................................................... 157

Granichin O.N. (SPbSU) 48-50th International Conference "Conference on

Decision and Control" (IEEE CDC/CCC 2009, CDC 2010, CDC-ECC 2011) ............................................................................................................... 158

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

НИИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

СТОХАСТИЧЕСКАЯ ОПТИМИЗАЦИЯ В ИНФОРМАТИКЕ

Издается с 2005 года

ТОМ 8

Выпуск 1

Издательство С.-Петербургского университета , 2 0 12

УДК 519.712 ВКК 32.811.7

С82

Ответственный редактор д. ф.-м. н., проф. О. Н. Граничин

Редакционная коллегия: Н. К. Кривулин (С.-Петерб. гос. ун-т),

Г. А. Леонов (С.-Петерб. гос. ун-т),

Б. Т. Поляк (ипу ран),

А. В. Соколов (ИПМИ КарНЦРАН),

А. Н. Терехов (С.-Петерб. гос. ун-т),

М. К. Чирков (С.-Петерб. гос. ун-т),

П. С. Щербаков (ипу ран)

Печатается по постановлению

Редакционно-издателъского совета

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

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

Стохастическая оптимизация в информатике. Том 8 (Вып. 1) / Под ред. О. Н. Граничина — СПб.: Издательство С.-Петербургского университета, 2012. — 160 с.

ISSN 1992-2922

Издание выпускается ежегодно (том 1, ненумерованный, вышел в 2005 г., тома (вып.) 2—7 — в 2006—11 гг.) и содержит научные работы по стохастической оптимизации, особо выделяя приложения в информатике. 8-й том составлен из поступивших в редколлегию рукописей и материалов одноименной регулярной серии семинаров для студентов, аспирантов и научных работников, проводившихся в 2011-12 гг. на математико-механическом факультете С.-Петербургского университета под руководством профессора кафедры системного программирования О. Н. Граничина и организованных совместно с Лабораторией системного программирования и информационных технологий (СПРИНТ) СПбГУ, которая была создана при поддержке корпорации Intel.

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

ББК 32.811.7

Мулътиагентные системы

Метод усредненных моделей в задаче достижения консенсуса

Н. О. Амелина, аспирант

А. Л. Фрадков, д. т. н.

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

Институт проблем машиноведения РАН

leishe@mail.ru, fradkov@mail.ru

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

Ключевые слова: достижение консенсуса, мультиагентные системы, метод усредненных моделей.

Список литературы

[1] Агаев Р.П., Чеботарев П.Ю. Сходимость и устойчивость в задачах согласования характеристик (обзор базовых результатов) // Управление большими системами. Спец. выпуск 30.1 "Сетевые модели в управлении". 2010. С. 470-505.

[2] Ren W., Beard R. W. Distributed Consensus in Multi-vehicle Cooperative Control: Theory and Applications — Communication and Control Engineering Series. Springer Verlag. New York. 2007. 319 p.

[3] Cortes J., Bullo F. Coordination and geometric optimization via distributed dynamical systems // SIAM Journal on Control and Optimization. 2005. Vol. 44. No. 5. P. 1543-1574.

[4] Миркин Б.М. Адаптивное децентрализованное управление с модельной координацией // Автоматика и Телемеханика. 1999. № 1. С. 90-100.

[5] Olfati-Saber R., Murray R.M. Consensus problems in networks of agents with switching topology and time-delays // IEEE Trans. Automatic Control. Sept. 2004. Vol. 49. P. 1520-1533.

[6] Armbruster D., Mikhailov A.S., Kaneko K. (eds.) Networks of Interacting Machines: Production Organization in Complex Industrial Systems and Biological Cells — World Scientific. Singapore. 2005. 267 p.

[7] Glashenko A., Inozemtzev S., Grachev I., Skobelev P. Magenta Technology: case studies of Magenta i-scheduler for road transportation // Proc. of Int. Conf. on Autonomous Agents and Multi Agent Systems (AAMAS-6). Hawaii. 2007. P. 1385-1392.

[8] Городецкий В.И., Грушинский М.С., Хабалов А.В. Многоагентные системы (обзор) // Новости искусственного интеллекта. 1998. №2. С. 64-116.

[9] Каляев И.А., Мельник Э.В. Децентрализованные системы компьютерного управления. — Ростов на Дону: ЮНЦ РАН. 2011. 196 с.

[10] Амелина Н., Лада А., Майоров И., Скобелев П., Царев А. Исследование моделей организации грузовых перевозок с применением мультиагентной системы адаптивного планирования грузовиков в реальном времени // Проблемы управления. 2011. № 6. С. 31-37.

[11] Huang M. Stochastic Approximation for Consensus with General Time-Varying Weight Matrices // Proc. of IEEE Conf. on Decision and Control (CDC-49). 2010. Atlanta. USA. P. 7449-7454.

[12] Ren W., Beard R.W. Consensus seeking in multiagent systems under dynamically changing interaction topologies // IEEE Trans. Automat. Control. 2005. Vol. 50. No. 5. P. 655-661.

[13] Tsitsiklis J.N., Bertsekas D.P., Athans M. Distributed asynchronous deterministic and stochastic gradient optimization algorithms // IEEE Trans. Autom. Contr. 1986. Vol. 31. No. 9. P. 803-812.

[14] Kar S., Moura J.M.F. Distributed consensus algorithms in sensor networks with imperfect communication: link failures and channel noise // IEEE Trans. Sig. Process. 2009. Vol. 57. No. 1. P. 355-369.

[15] Li Т., Zhang J.-F. Mean square average-consensus under measurement noises and fixed topologies // Automatica. 2009. Vol. 45. No. 8. P. 1929-1936.

[16] Цыпкин Я.З. Информационная теория идентификации. — М.: Наука. 1995. 336 с.

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

[18] Поляк Б. Т., Цыбаков А. Б. Оптимальные порядки точности поисковых алгоритмов стохастической аппроксимации // Проблемы передачи информации. 1990. № 2. С. 126-133.

[19] Фомин В.Н. Методы управления линейными дискретными объектами. — Л.: Изд-во Ленингр. ун-та. 1985. 336 с.

[20] Spall J.C. Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation // IEEE Trans. Automat. Contr. 1992. Vol. 37. No. 3. P. 332-341.

[21] Kushner H.J., Yin G.G. Stochastic Approximation Algorithms and Applications. — New York: Springer-Verlag. 2002. 415 p.

[22] Granichin O., Vakhitov A., Vlasov V. Adaptive control of SISO plant with time-varying coefficients based on random test perturbation // Proc. of American Control Conf. (ACC-2010). 2010. Baltimore. USA. P. 4004-4009.

[23] Baxumoe А.Т., Граничин О.Н., Гуревич Л.С. Алгоритм стохастической аппроксимации с пробным возмущением на входе в нестационарной задаче оптимизации // Автоматика и телемеханика. 2009. №11. С. 70-79.

[24] Granichin О., Gurevich L., Vakhitov A. Discrete-time minimum tracking based on stochastic approximation algorithm with randomized differences // Proc. of IEEE Conf. on Decision and Control (CDC-48). 2009. Shanghai. P.R. China. P. 5763-5767.

[25] Borkar V.S. Stochastic Approximation: a Dynamical Systems Viewpoint — New York: Cambridge University Press. 2008. 164 p.

[26] Chai Wah Wu Synchronization in complex networks of nonlinear dynamical systems — World Scientific Publishing Company. 2007. 168 p.

[27] Деревицкий Д.П., Фрадков А.Л. Две модели для анализа динамики алгоритмов адаптации // Автоматика и телемеханика. 1974. № 1. С. 67-75.

[28] Деревицкий Д.П., Фрадков А.Л. Прикладная теория дискретных адаптивных систем управления. — М.: Наука. 1981. 216 с.

[29] Kushner H.J. Convergence of recursive adaptive and identification procedures via weak convergence theory // IEEE Trans. Aut. Control. 1977. No. 6. P. 921-930.

[30] Ljung L. Analysis of recursive stochastic algorithms // IEEE Trans. Aut. Control. 1977. No. 4. P. 551-575.

[31] Меерков СМ. Об упрощении описания медленных марковских блужданий I, II // Автоматика и Телемеханика. 1972. № 3. С. 6-75. № 5. С. 63-67.

[32] Романовский И.В. Дискретный анализ. — СПб: Невский Диалект, БХВ-Петербург. 4-е изд. 2008. 320 с.

[33] Агаев Р.П., Чеботарев П.Ю. Матрица максимальных исходящих лесов орграфа и ее применения // Автоматика и Телемеханика. № 9. 2000. С. 15-43.

[34] Гершгорин С.A. Uber die abgrenzung der eigenwerte einer matrix // Изв. АН СССР, отд. физ.-мат. наук. 1931. С. 749-754.

[35] Гелиг А.Х., Леонов Г.А., Якубович В.А. Устойчивость нелинейных систем с неединственным состоянием равновесия. — М.: Наука. 1978. 400 с.

[36] Fradkov A.L. Continuous-time averaged models of discrete-time stochastic systems: survey and open problems // Proc. of IEEE Conf. on Decision and Control (CDC-50). Orlando. USA. 2011. P. 2076-2081.

[37] Гихман И.И., Скороходов А.В. Стохастические дифференциальные уравнения. — Киев: Наук, думка. 1968. 356 с.

[38] Бернштейн СИ. Стохастические уравнения в конечных разностях и стохастические дифференциальные уравнения. // Сбор. соч. в 4-х т. М.: Наука. 1964. Т. 4. С. 484-542.

Новый сетевой подход для задач, не имеющих однозначного решения

В. И. Васильев, аспирант

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

gnome@bk.ru

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

Ключевые слова: интеллектуальные сети, нейрокомпьютеры, мультиагентные системы, коннективизм.

Список литературы

[1] Moore G.E. Cramming more Components onto Integrated Circuits // Electronics. 38(8). April 9. 1965.

[2] Шпаковский Г.И. Реализация параллельных вычислений: MPI, ОрепМР, кластеры, грид, многоядерные процессоры, графические процессоры, квантовые компьютеры. — М.: Изд-во Белорусского ГУ. 2011. 176 с.

[3] Minsky M.L. Вычисления и автоматы. Монография — Изд. Мил Месива. 1971

[4] Горбанъ А.Н. Нейроинформатика: кто мы, куда мы идем, как путь наш измерить? // Вычислительные технологии. Ч- М.: Машиностроение. Ч 2000. Ч №4. С. 10-14.

[5] Liп J., Dyer С. Data-Intensive Text Processing with Map Reduce. University of Maryland. April 2010.

[6] Граничин О.Н., Амелин К. С. Мультиагентное сетевое управление группой легких БПЛА // Нейрокомпьютеры: разработка, применение. 2011. № 6. С. 64-72.

[7] Rumelhart D.E., McClelland J.L. Parallel Distributed Processing: Explorations in the Microstructure of Cognition. Vol. 1,2: Foundations. Cambridge. MA: MIT Press. 1986.

[8] Владимирович А.Г., Граничин О.Н., Макаров А.А. Нестандартная машина Тьюринга // Стохастическая оптимизация в информатике. 2005. Т. 1. С. 29-47.

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

[10] Граничин О.Н., Жувикина И.А. Новая концепция процесса вычислений, основанная на эволюционных примитивах // Системное программирование. 2006. Т. 2. С. 68-83.

[11] Граничин О.Н., Васильев В.И. Гибридная модель процесса вычислений: обобщение концепции машины Тьюринга // Нейрокомпьютеры: разработка, применение. 2010. №6. С. 51-58.

[12] Granichin O.N., Vasilev V.I. Computational model based on evolutionary primitives. Turing machine generalization // International Journal of Nanotechnology and Molecular Computation. Vol. 2. 2010. No. 2. PP. 30-43.

Интеллектуальный CRM на базе мультиагентного подхода

В. И. Кияев, к. ф.-м. н.

Р. В. Герасимов

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

Санкт-Петербургский университет экономики и финансов

kiyaev@mail.ru

В статье описывается возможность использования мультиагентного подхода в клиентском обслуживании. Предлагается дополнить концепции широко применяемого клиентоориентированного подхода на базе CRM (Customer Relationship Management) мультиагентными системами и механизмами. Такой подход представляет собой новый способ решения проблемы управления клиентской сетью.

Ключевые слова: мультиагентный подход, управление клиентской сетью.

Список литературы

[1] Граничин О.И., Кияев В.И. Информационные технологии в управлении. 2-е изд. — СПб: Изд-во ВВМ. 2012. - 354 с.

[2] Албитов А., Соломатин Е. CRM (Customer Relationship Management) — М: Изд-во Клерк.RU. 2003.

[3] Аншина М. История и будущее, понятие, внедрение, сопровождение CRM (Customer Relationship Management] // Сетевой. -№10. 2002.

[4] Батищев С, Скобелев П. Основные этапы разработки мультиагентных систем в инструментальной среде для создания Интернет-приложений // Известия Самарского научного центра Российской академии наук. - 2002. - Т. 4. № 1. - Самара: Изд-во Самарского научного центра РАН(Самара).

[5] Воронин Б. CRM - новая стратегия со старыми принципами // Электронная коммерция. - 2005.

[6] Глибовец Н. Использование JADE (Java Agent Development Environment) для разработки компьютерных систем поддержки дистанционного обучения агентного типа // Educational Technology & Society. 2005. №8(3).

[7] Городецкий В.И., Грушинский М.С., Хабалов А.В. Многоагентные системы // Новости искусственного интеллекта. 1997. №1. С. 15-30.

[8] Амелин К.С, Граничин О.Н., Кияев В.И., Корявко А.В. Введение в разработку приложений для мобильных платформ. — СПб: Изд-во ВВМ. 2011. - 507 с.

[9] Де Роза К. Планирование ресурсов, синхронизированное с покупателем (CSRP) [Электронный ресурс] / К. Де Роза// SYMIX. - Режим доступа: http://www.symix.com.

[10] Дмитриев С. Блеск и нищета CRM-технологий // Маркетинг, реклама и сбыт. Март (№3). - М: ECOMAN.EDU.RU. 2004.

[11] Зайцев М. Вопросы философии. Массовое внедрение CRM-систем начнется, когда бизнес будет больше ориентироваться на клиента // Эксперт Северо-Запад. СПб: Эксперт Северо-Запад.RU. 2003.

[12] Кальченко Д. Агенты приходят на помощь // КомпьютерПресс. М: Компьютер Пресс.RU. 2005.

[13] Амелин К. С, Граничин О.И. Мультиагентное сетевое управление группой легких БПЛА // Нейрокомпьютеры: разработка, применение, 2011. №6. С. 64-72.

[14] Амелин К. С. Технология программирования легкого БПЛА для мобильной автономной группы // Стохастическая оптимизация в информатике. Т. 7. 2011. С. 93-115.

[15] Амелин К.С, Граничин О.Н Применение мультиагентного подхода для решения задач мониторинга местности группой легких БПЛА // Сборник трудов межд. научно-практической конференции "Управление большими системами - 2011". Москва, 2011. Т. 3, с. 209-214.

[16] Амелина И.О. Мультиагентные технологии, адаптация, самоорганизация, достижение консенсуса // Стохастическая оптимизация в информатике. Т. 7. С 149-185. 2011.

[17] Келеберда И., Лесная И., Репка В. Использование мультиа-гентного онтологического подхода к созданию распределенных систем дистанционного обучения // Educational Technology & Society. - 2004. - № 7(2).

[18] Кириллов В., Кравченко О. Двойное преимущество // Intelligent Enterprise. 24 сентября (№17). - М: Intelligent Enterprise.RU. 2003.

[19] Клышинский Э. Некоторые аспекты построения агентных систем [Электронный ресурс] / Э. Клышинский // Программирование магических игр. - М: pmg.org.RU, 2004 - Режим доступа: http://pmg.org.ru/russian/agent.htm.

[20] Костяков С. Анализ клиента и синтез бизнеса [Электронный ресурс]/ С. Костяков // ITBC.ru. - М: ITBC.ru, 2004. - Режим доступа: http://www.itbc.ru/default. asp? ACT=70&id=0&cat=6&add=85.

[21] Ивушкин К. и др. Мультиагентная система для решения задач логистики // Труды Седьмой национальной конференции по искусственному интеллекту с международным участием КИИ. - 2000. - 27 октября 2000. - Москва: Издательство физмат литературы. Т. 2. С. 789-798.

[22] Одел Д. Агенты и сложные системы // Открытые системы. 2002. №10.

[23] Скобелев П. Виртуальные миры и интеллектуальные агенты для моделирования деятельности компании // Труды VI Национальной конференции по искусственному интеллекту. 1998. 5 ноября 1998. Т. 2. С. 714-719.

[24] Скобелев П. Холистический подход к созданию открытых мультиагентных систем // Труды III Международной конференции по проблемам управления и моделирования в сложных системах. 4 сентября. - Самара: СНЦ РАН. 2001. С. 147-160.