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

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

Издание выпускается ежегодно (том 1, ненумерованный, вышел в 2005 г., тома (вып.) 2–8 — в 2006–12 гг.) и содержит научные работы по стохастической оптимизации, особо выделяя приложения в информатике. Первый выпуск девятого тома составлен из поступивших в редколлегию рукописей и материалов одноименной регулярной серии семинаров для студентов, аспирантов и научных работников, проводившихся в 2013 г. на математико-механическом факультете С.-Петербургского университета под руководством профессора кафедры системного программирования О. Н. Граничина. Выпуск опубликован при поддержке гранта РФФИ № 13-07-00250-a.

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

ББК 32.811.7

Адаптивная мультиагентная операционная система реального времени

К. С. Амелин, к. ф.-м. н, М. В. Баклановский, О. Н. Граничин, д. ф.-м. н., Ю. В. Иванский, А. Д. Корнивец, Н. В. Мальковский, Д. Г. Найданов, Р. Е. Шеин

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

(konstantinamelin, oleg_granichin)@mail.ru

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

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

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

Работа выполнена в рамках исследований в СПбГУ по теме №6.38.71.2011 “Изучение свойств и возможностей применения рандомизированных алгоритмов кластеризации, оптимизации и оценивания” и при поддержке РФФИ (проект №13-07-00250-а).

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

[1] Виттих В.А., Скобелев П.О. Метод сопряженных взаимодействий для управления распределением ресурсов в реальном масштабе времени // Автометрия. 2009. №. 2. С. 78–87.

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

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

[4] Амелин К.С., Амелина Н.О., Граничин О.Н., Корявко А.В. Применение алгоритма локального голосования для достижения консенсуса в децентрализованной сети интеллектуальных агентов // Нейокомпьютеры: разработка и применение. 2012. №11. С. 39–47.

[5] Амелина Н.О., Фрадков А.Л. Приближенный консенсус в стохастической динамической сети с неполной информацией и задержками в измерениях // Автоматика и Телемеханика. 2012. №11. С. 6–30.

[6] Виттих В.А. Введение в теорию интерсубъективного управления. — Самара. Самарский научный центр РАН, 2013. — 64 с.

[7] Сергеев С.Ф. Психологические основания проблемы искусственного интеллекта // Мехатроника, автоматизация, управление. 2011. №7. С. 2–6.

[8] Амелин К.С., Антал Е.И., Васильев В.И., Амелина Н.О. Адаптивное управление автономной группой беспилотных летательных аппаратов // Стохастическая оптимизация в информатике. Т. 5. 2009. С. 157–166.

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

Н. О. Амелина, к. ф.-м. н.

К. С. Амелин, к. ф.-м. н.

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

Д. Д. Вергадос, PhD

Норвежский университет науки и технологии

(natalia_amelina, konstantinamelin)@mail.ru, djvergad@gmail.com

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

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

Работа выполнена при частичной финансовой поддержке ФЦП “Кадры” (соглашения 8846, 8855), а также при поддержке РФФИ (проекты 11-08-01218-а, 13-07-00250-а).

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

[1] Амелина Н.О., . Применение протокола локального голосования для децентрализованной балансировки загрузки сети с переменной топологией и помехами в измерениях // Вестник СПбГУ. Сер. 1: Математика. Механика. Астрономия.— 2013.

[2] Akyildiz, I. F., Wang X., Wang W., Wireless mesh networks: a survey // Computer networks. — 2005. — Vol. 47, no. 4. — Pp. 445–487.

[3] Amelina, N., Granichin O, Kornevetc A., Local voting protocol in decentralized load balancing problem with switched topology, noise, and delays // Proc. 52nd IEEE Conference on Decision and Control (CDC 2013). — 2013.

[4] Bettstetter, C., Hartmann C., Connectivity of wireless multihop networks in a shadow fading environment // Wireless Networks. — 2005. — Vol. 11, no. 5. — Pp. 571–579.

[5] J. Li, C. Blake, De Couto D. S. et al. Capacity of ad hoc wireless networks // Proceedings of the 7th annual international conference on Mobile computing and networking. — 2001. — Pp. 61–69.

[6] Cruz, R. L.,. Santhanam A. V, Optimal routing, link scheduling and power control in multihop wireless networks // INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. — 2003. — Vol. 1. — Pp. 702–711.

[7] Dimakis, A., Walrand J., Sufficient conditions for stability of longest-queue-first scheduling: Second-order properties using fluid limits // Advances in Applied probability. — 2006. — Pp. 505–521.

[8] I. Rhee, A. Warrier, J. Min, L. Xu, Drand: distributed randomized tdma scheduling for wireless ad-hoc networks // Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing. — 2006. — Pp. 190–201.

[9] D. J. Vergados, A. Sgora, D. D. Vergados et al. Fair tdma scheduling in wireless multihop networks // Telecommunication Systems. — 2012. — Vol. 50, no. 3. — Pp. 181–198.

[10] Grossglauser, M., Tse D. N., Mobility increases the capacity of ad hoc wireless networks // Ieee/Acm Transactions On Networking. — 2002. — Vol. 10, no. 4. — Pp. 477–486.

[11] Gupta, P., Kumar P. R., Critical power for asymptotic connectivity in wireless networks // Stochastic Analysis, Control, Optimization and Applications. — Springer, 1998. — Pp. 547–566.

[12] Gupta, P., Kumar P. R., The capacity of wireless networks // IEEE Transactions on Information Theory. — 2000. — Vol. 46, no. 2. — Pp. 388–404.

[13] Hammond, J. L., Russell H. B., Properties of a transmission assignment algorithm for multiple-hop packet radio networks // IEEE Transactions on Wireless Communications. — 2004. — Vol. 3, no. 4. — Pp. 1048–1052.

[14] Z. Ning, L. Guo, Y. Peng, X. Wang, Joint scheduling and routing algorithm with load balancing in wireless mesh network // Computers & Electrical Engineering. — 2012. — Vol. 38, no. 3. — Pp. 533 – 550.

[15] Joo, C., X. Lin, N. B. Shroff, Understanding the capacity region of the greedy maximal scheduling algorithm in multihop wireless networks // IEEE/ACM Transactions on Networking (TON). — 2009. — Vol. 17, no. 4. — Pp. 1132–1145.

[16] Kiess, W., M. Mauve, A survey on real-world implementations of mobile ad-hoc networks // Ad Hoc Networks. — 2007. — Vol. 5, no. 3. — Pp. 324–339.

[17] Li, Y., A. Ephremides, A joint scheduling, power control, and routing algorithm for ad hoc wireless networks // Ad Hoc Networks. — 2007. — Vol. 5, no. 7. — Pp. 959–973.

[18] Lin, X., N. B. Shroff, Joint rate control and scheduling in multihop wireless networks // 43rd IEEE Conference on Decision and Control, CDC-2004. — 2004. — Vol. 2. — Pp. 1484–1489.

[19] Pottie, G. J. Wireless sensor networks // Information Theory Workshop, 1998. — 1998. — Pp. 139–140.

[20] Salem, N.B., J.-P. Hubaux, A fair scheduling for wireless mesh networks // Proc. IEEE Workshop on Wireless Mesh Networks (WiMesh). — 2005.

[21] Tassiulas, L., A. Ephremides, Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks // IEEE Transactions on Automatic Control. — 1992. — Vol. 37, no. 12. — Pp. 1936–1948.

[22] Weber, S., J. G. Andrews, N. Jindal, An overview of the transmission capacity of wireless networks // IEEE Transactions on Communications. — 2010. — Vol. 58, no. 12. — Pp. 3593–3604.

[23] Wolf, B. J., J. L. Hammond, H. B. Russell, A distributed load-based transmission scheduling protocol for wireless ad hoc networks // Proceedings of the 2006 international conference on Wireless communications and mobile computing. — 2006. — Pp. 437–442.

Восстановление 3D-образов из скомпрессированных данных УЗИ

Ю. В. Иванский

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

ivanskiy.yuriy@gmail.com

В работе проведено исследование применимости подхода опознания со сжатием (compressive sensing, CS) для сокращения размеров каналов связи датчиков УЗИ (ультразвуковых исследований) с процессорным блоком. Разработана и реализована принципиальная имитационная модель УЗИ-сканера, позволяющая проводить сжатие, передачу, восстановление сигналов по заранее сгенерированным данным ультразвуковых исследований. На модели проведена серия имитационных экспериментов с разными характеристиками (параметрами), результаты которых показывают границы применимости подхода опознания со сжатием в ходе УЗИ и возможное качество восстановления исходных данных при обработке в процессорном блоке.

Ключевые слова: рандомизированные измерения, ℓ₁-оптимизация, восстановление разреженных сигналов, сжатие информации, Compressive sensing, УЗИ.

Работа выполнена в рамках исследований в СПбГУ по теме №6.38.71.2011 “Изучение свойств и возможностей применения рандомизированных алгоритмов кластеризации, оптимизации и оценивания” и при частичной поддержке РФФИ (проект №13-07-00250-а).

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

[1] Stergiopoulos S. (Editor) Advanced Signal Processing Handbook: Theory and Implementation for Radar, Sonar, and Medical Imaging Real Time Systems. — CRC Press LLC. 2001.

[2] Котельников В.А. О пропускной способности эфира и проволоки в электросвязи — Всесоюзный энергетический комитет. // Материалы к I Всесоюзному съезду по вопросам технической реконструкции дела связи и развития слаботочной промышленности. 1933. Репринт статьи в журн. УФН. 176:7. 2006. C. 762–770.

[3] Nyquist H. Certain topics in telegraph transmission theory // Trans. AIEE. 1928. Vol. 47. Pp. 617–644.

[4] Shannon C.E. Communication in the presence of noise // Proc. Institute of Radio Engineers. 1949. Vol. 37(1). Pp. 10–21.

[5] Candes E., Romberg J., Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information // IEEE Trans. Inform. Theory. Vol. 52(2). 2006. Pp. 489–509.

[6] Donoho D. Compressed sensing // IEEE Trans. Inform. Theory. Vol. 52(4). 2006. Pp. 1289–1306.

[7] Lustig M., Donoho D., Pauly J.M. Sparse MRI: The application of compressed sensing for rapid MR imaging // Magnetic Resonance in Medicine. Vol. 58(6). Pp. 1182–1195. December 2007.

[8] Lustig M., Donoho, D.L., Santos J.M., Pauly J.M. Compressed sensing MRI // Signal Processing Magazine. Vol. 25(2). March 2008. Pp. 72–82.

[9] Mackenzie D. What’s Happening in the Mathematical Sciences. 2009. Vol. 7. Pp. 115–127.

[10] Duarte M.F., Davenport M.A., Takhar D., Laska J.N., Ting S., Kelly K.F., Baraniuk R.G. Single-pixel imaging via compressive sampling // IEEE Signal Processing Magazine. 2008. Vol. 25. No. 2. Pp. 83–91.

[11] Compressive Imaging: A New Single-Pixel Camera. Электронный ресурс. http://dsp.rice.edu/cscamera/

[12] Кашин Б.С., Темляков В.Н. Замечание о задаче сжатого измерения // Математические заметки. 2007. Т. 82. № 6. C. 829–837.

[13] Граничин О.Н. Рандомизация измерений и l₁-оптимизация // Стохастическая оптимизация в информатике. 2009. Т. 5. С. 3– 23.

[14] Граничин О.Н., Павленко Д.В. Pандомизация данных и l₁-оптимизация // Компьютерные инструменты в образовании. 2010. № 1. С. 5–13.

[15] Граничин О.Н., Павленко Д.В. Рандомизация получения данных и l₁-оптимизация (опознание со сжатием) (Обзор) // Автоматика и телемеханика. 2010. № 11. С. 3–28.

[16] Исаев О.П. Аппаратная реализация на базе FPGA рандомизированного метода сжатия изображений // Стохастическая оптимизация в информатике. 2010. Т. 6. С. 52–73.

[17] Murtaza A., Magee D., Dasgupta U. Signal Processing Overview of Ultrasound Systems for Medical Imaging — White Paper. Nov. 2008. [Online]. Available: http://www.ti.com/lit/wp/sprab12/sprab12.pdf

[18] MATLAB. Официальный сайт MathWorks. http://www.mathworks.com/products/matlab/

[19] l₁-MAGIC. Электронный ресурс. http://users.ece.gatech.edu/ justin/l1magic/

[20] Candes E., Romberg J. l₁-magic: Recovery of Sparse Signals via Convex Programming. Caltech. October 2005. [Online]. Available: http://users.ece.gatech.edu/ justin/l1magic/downloads/l1magic.pdf

Определение координат летательных аппаратов по разностно-дальномерным измерениям при наличии индивидуальных систематических погрешностей

Ю. К. Кисин, к. т. н.

Северодвинск

yurasdv@yandex.ru

В статье рассматривается задача определения координат летательного аппарата по разностно-дальномерным измерениям при наличии индивидуальных систематических погрешностей в каждой разности дальностей. Приведены результаты моделирования.

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

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

[1] Шебшаевич В.С., Дмитриев П.П., Иванцевич Н.В. и др. Под ред. Шебшаевича В.С. Сетевые спутниковые радионавигационные системы. — М.: Радио и связь. 1993. 408 с.

[2] Яценков В.С. Основы спутниковой навигации. Системы GPS NAVSTAR и ГЛОНАСС. М: Горячая линия — Телеком. 2005. 272 с.

[3] Соловьев Ю.А. Системы спутниковой навигации. — М.: Эко-Трендз, 2000. 267 с.

[4] Барабанов О.О., Барабанова Л.П. Математические задачи дальномерной навигации. — М.: ФИЗМАТЛИТ. 2007. 272 с.

[5] Жданюк Б.Ф. Основы статистической обработки траекторных измерений. — М.: Советское радио. 1978. 384 с.

[6] Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений. — М.: Мир. 1984. 280 с.

[7] Тихонов А.Н., Уфимцев М.В. Статистическая обработка результатов экспериментов. — М.: Изд-во Московского университета. 1988. 174 с.

[8] Катковник В.Я. Непараметрическая идентификация и сглаживание данных: метод локальной аппроксимации. — М: Наука. Главная ред. Физ-мат лит. 1985. 336 с.

[9] Айвазян С.А., Мхитарян В.С. Прикладная статистика и основы эконометрики. — М: ЮНИТИ. 1998. 1005 с.

Доверительные множества при почти произвольных помехах в контексте линейных моделей рекомендательных систем

А. А. Сенов, аспирант

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

sensanek@gmail.com

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

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

Работа выполнена в рамках исследований в СПбГУ по теме №6.38.71.2011 “Изучение свойств и возможностей применения рандомизированных алгоритмов кластеризации, оптимизации и оценивания” и при частичной поддержке РФФИ (проект №13-07-00250-а).

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

[1] Top 20 Countries with the Highest Number of Internet Users. “Miniwatts Marketing Group”. June. 2012.

[2] O'Reilly T. “What is web 2.0”. Sept. 2005.

[3] Bell R., Koren Y., Volinsky C. The Bellkor Solution to the Netflix Prize. 2007.

[4] Ricci F., Rokach L., Shapira B. Introduction to Recommender Systems Handbook. Springer. 2011. Pp. 1–35.

[5] Linden G.D., Jacobi J.A., Benson E.A. Collaborative recommendations using item-to-item similarity mappings. Sept. 1998.

[6] Jafarkarimi H., Sim A., Saadatdoost R. A naive recommendation model for large databases // International Journal of Information and Education Technology. 2012.

[7] Adomavicius A.T.G. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions // IEEE Transactions on Knowledge and Data Engineering. 2005. Pp. 734–749.

[8] Alspector J., Kolcz A., Karunanithi N. Comparing feature-based and clique-based user models for movie selection // Proceedings of the Third ACM Conference on Digital Libraries. 1998. Pp. 11–18.

[9] Sarwar B., Karypis G., Konstan J., Riedl J. Item-based collaborative filtering recommendation algorithms // In Proc. of the 10th International WWW Conference. 2001.

[10] Фомин В.Н. Рекуррентное оценивание и адаптивная фильтрация. — М.: Наука. 1984. 288 c.

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

[12] Montgomery D.C., Peck E.A., Vining G.G. Introduction to Linear Regression Analysis. Wiley-Interscience. 2007.

[13] Граничин О.Н., Фомин В.Н. Адаптивное управление с использованием пробных сигналов // Автоматика и телемеханика. 1986. № 2. С. 100–112.

[14] Граничин О.Н. Алгоритм стохастической аппроксимации с возмущением на входе для идентификации статического нестационарного дискретного объекта // Вестник Ленинградского университета, cер. 1, 1988. Вып. 3(15). С. 92–93.

[15] Граничин О.Н. Оценивание точки минимума неизвестной функции, наблюдаемой на фоне зависимых помех // Проблемы передачи информации. 1992. №2. C 16–20.

[16] Goldenshluger A.V., Polyak B.T. Estimation of regression parameters with arbitrary noise // Mathematical Methods of Statistics. 1993. Vol.2(1). Pp. 18–29.

[17] Граничин О.Н. Оценивание параметров линейной регрессии при произвольных помехах // Автоматика и телемеханика. 2002. № 1. C. 30–41.

[18] Granichin O.N. Linear regression and filtering under nonstandard assumptions (arbitrary noise) // IEEE Trans. on Automatic Control. Vol. 49(10). 2004. Pp. 1830–1835.

[19] Граничин О.Н. Неминимаксная фильтрация при неизвестных ограниченных помехах в наблюдениях // Автоматика и телемеханика. 2002. № 9. C. 125–133.

[20] Fedin D.S., Granichin O.N., Dedkov Yu.S., Molodtsov S.L. Method of measurements with random perturbation: Application in photoemission experiments // Review of Scientific Instruments. Vol. 79. 2008. 036103.

[21] Льюнг Л., Сёдерстрём T. Идентификация систем: теория для пользователя. — М.: Hаука. 1991. 431 с.

[22] Amelin K., Amelina N., Granichin O., Granichina O. Two procedures with randomized controls for the parameters’ confidence region of linear plant under external arbitrary noise // Proc. of the IEEE Int. Symposium on Intelligent Control (ISIC). 2012. Pp. 1226–1231.

[23] Amelin K., Amelina N., Granichin O., Granichina O. Combined procedure with randomized controls for the parameters’ confidence region of linear plant under external arbitrary noise // Proc. of the 51st Conference on Decision and Control (CDC2012). 2013. Pp. 2134–2139.

[24] Amelin K., Granichin O. Randomized Controls for Linear Plants and Confidence Regions for Parameters under External Arbitrary Noise // Proc. of the American Control Conference (ACC). 2012. Pp. 743–1618.

[25] Граничин О.H. Неасимптотическое доверительное множество для параметров линейного объекта управления при почти произвольных помехах // Автоматика и телемеханика. 2012. № 1. C. 24–35.

[26] Csaji B.C., Campi M.C., Weyer E. Non-asymptotic confidence regions for the least-squares estimate // Proceedings of the 16th IFAC Symposium on System Identification (SYSID 2012). June. 2012. Pp. 227-232.

[27] Wei C.P., Shaw M.J., Easley R.F. A survey of recommendation systems in electronic commerce // E-Service: New Directions in Theory and Practice. 2001.

[28] Граничин О.Н., Павленко Д.В. Рандомизация получения данных и ℓ₁-оптимизация (опознание со сжатием) (Обзор) // Автоматика и телемеханика. 2010. № 11. С. 3–28.

Эффективный алгоритм построения генетических карт по полностью секвенированным участкам геномов

С. С. Сысоев, к. ф.-м. н.

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

sysoev@petroms.ru

В статье рассмотрен новый подход к построению генетических карт на основе полностью секвенированных участков данных (маркеров). На основе предлагаемого подхода разработан алгоритм с программной реализацией на языке python. Представлены результаты апробации алгоритма на генетических данных семейства кошек с 35 маркерами.

Ключевые слова: генетика, генетическая карта, секвенирование, алгоритм, фенотип, генотип.

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

[1] Strachan T., Read E. Human Molecular Genetics, 2nd Edition. — NY: Willey-Liss. 1999.

[2] Needleman S.B., Wunsch C.D. A General method applicable to the search for similarities in amino acid sequence of two proteins // Journal of Molecular Biology. Vol. 48 (3). 1970. Pp. 443–53.

[3] Smith T.F., Waterman M.S. Identification of common molecular subsequences // Journal of Molecular Biology. Vol. 147. 1981. Pp. 195–197.

[4] Mendel G. Experiments in Plant Hybridization. 1865.

[5] Morton M.E. Sequential tests for the detection of linkage // American Journal of Human Genetics. Vol. 7(3). 1955. Pp. 277– 318.

[6] Elston R.C., Stewart J. A general model for the genetic analysis of pedigree data // Human Heredity. Vol. 21. 1971. Pp. 523–542.

[7] Lander E.S., Green P. Construction of multilocus genetic linkage maps in humans // Proceedings of the National Academy of Sciences. Vol. 84(8). Pp. 2363–2367.

[8] Lander E.S., Green P., Abrahamson J., Barlow A., Daly M.J., Lincoln S.E., Newburg L. MAPMAKER: An interactive computer package for constructing primary genetic linkage maps for experimental and natural populations // Genomics. Vol. 1. 1987. Pp. 174–181.

LMI-подход к построению ограниченного стабилизирующего управления для линейных систем

М. В. Хлебников, д. ф.-м. н.

П. С. Щербаков, д. ф.-м. н.¹

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

mkhlebnikov2008@yandex.ru, cavour118@mail.ru

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

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

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

[1] Boyd S., El Ghaoui L., Feron E., and Balakrishnan V. Linear Matrix Inequalities in System and Control Theory. Philadelphia: SIAM, 1994.

[2] Поляк Б. Т., Щербаков П. С. Робастная устойчивость и управление. М.: Наука, 2002.

[3] Hu T. and Lin Z. Control Systems with Actuator Saturation: Analysis and Design, Birkhauser, Boston, 2001.

[4] Hu T. and Lin Z. On the tightness of a recent set invariance condition under actuator saturation // Syst. Control Lett., 2003. Vol. 49. Pp. 389–399.

[5] Alamo T, Cepedo A., and Limon D. Improved computation of ellipsoidal invariant sets for saturated control systems // In: Proc. 42-nd Conf. Decision Control, Seville, Spain, Dec. 2005. Pp. 6216– 6221.

[6] Polyak B. and Shcherbakov P. Ellipsoidal approximations to attraction domains of linear systems with bounded control // In: Proc. American Control Conf., St. Louis, USA, Jun 10–12, 2009. Pp. 5363–5367.

[7] Квакернаак Х., Сиван Р. Линейные оптимальные системы управления. М.: Мир, 1977. 650 с.

[8] Kalman R. When is a linear control system optimal? //J. Basic Engineering. Vol. 86, Issue 1. Pp. 51–60.

[9] Красовский А. А. Интегральные оценки моментов и синтез линейных систем // Автоматика и телемеханика. 1967. №10. С. 53–71.

[10] Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999.

[11] Хлебников М. В., Поляк Б. Т., Кунцевич В. М. Оптимизазция линейных систем при ограниченных внешних возмущениях (техника инвариантных эллипсоидов) // Автоматика и телемеханика. 2011. №11. С. 9– 59.

[12] Grant M., Boyd S. CVX: Matlab software for disciplined convex programming (web page and software). URL http://stanford. edu/~boyd/cvx

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

В. А. Хохулина,

М. К. Чирков, д. ф.-м. н.²

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

vakh08@mail.ru

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

Ключевые слова: нечеткие автоматные модели, нечеткие минимаксные автоматы, нечеткие языки, эквивалентность, специальный метод анализа.

Работа выполнена при поддержке гранта РФФИ 13-01-00538-а.

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

[1] Zadeh L.A. Fuzzy sets // Information and Control, Vol. 8. 1965. Pp. 338-353.

[2] Kandel A., Lee S.C. Fuzzy Switching and Automata: Theory and Applications. Crane Russak, New York, 1979. 303 p.

[3] Santos E.S. Maximin, minimax and composite sequential machines // J. Math. Anal. Appl. Vol. 24. 1968. Pp. 246–259.

[4] Santos E.S. Fuzzy automata and languages // Inform. Sci. Vol. 10, 1976. Pp. 193–197.

[5] Кабаве М., Чирков М.К. Об одном методе анализа обобщенных автоматов // Вестн. С.-Петербургского ун-та. Сер. 1. 1992. Вып. 3. №15. С. 95–97.

[6] Скорикова Я.И., Чирков М.К. Абстрактный анализ обобщенных нечетких автоматов // Математические модели. Теория и приложения. Вып. 6. СПб.: ВВМ. 2005. С. 110–122.

[7] Хохулина В.А. О разложении и анализе обобщенных нечетких автоматов и языков // Вестн. С.-Петербургского ун-та. Сер. 10. Вып. 4. 2009. С. 232–241.

[8] Чирков М.К., Кабаве М. Абстрактный анализ обобщенных конечных автоматов // Теория и приложения дискретных систем. СПб.: Изд-во С.-Петербургского ун-та. 1995. С. 3–36

[9] Хохулина В.А., Чирков М.К. О разложении «оптимистических» нечетких автоматов // Математические модели. Теория и приложения. Вып. 11. СПб.: ВВМ. 2010. С. 134–147.

[10] Пономарева А.Ю., Чирков М.К. Стационарные недетерминированные автоматы: анализ, синтез и оптимизация. (Теория автоматных моделей) — СПб.: ВВМ. 2012. 102 с.

Оптимальный синтез нестационарных недетерминированных конечных автоматов, предназначенных для функционирования в нечетких условиях

М. К. Чирков, д. ф.-м. н.

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

mkchirk@mail.ru

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

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

Работа выполнена при поддержке гранта РФФИ 13-01-00538-а.

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

[1] Zadeh L.A. Fuzzy sets // Information and Control, Vol. 8, 1965. Pp. 338–353.

[2] Kandel A., Lee S.C. Fuzzy Switching and Automata: Theory and Applications. Crane Russak, New York. 1979. 303 p.

[3] Заде Л. А. Основы нового подхода к анализу сложных систем и процессов принятия решений // Математика сегодня. — М.: «Знание», 1974. С. 5–49.

[4] Беллман Р., Заде Л. Принятие решений в расплывчатых условиях // Вопросы анализа и процедуры принятия решений. М., Мир, 1976. C. 172–215.

[5] Мосягина Е.Н., Чирков М. К. Оптимальное поведение периодически нестационарных детерминированных и недетерминированных автоматов в нечеткой среде (Теория автоматных моделей) — СПб.: ВВМ. 2011. 94 с.

[6] Мосягина Е.Н. Об оптимальном управлении периодически нестационарным недетерминированным автоматом в нечетко заданных условиях // Вестн. С.-Петербургского ун-та. Сер. 10. Вып. 4. 2009. С. 278–285.

[7] Пономарева А.Ю., Чирков М.К. Стационарные недетерминированные автоматы: анализ, синтез и оптимизация. (Теория автоматных моделей) — СПб.: ВВМ. 2012. 102 с.

Двухуровневая метрика и новая концепция машинного обучения

В. Н. Шац, д. т. н. Санкт-Петербург vlnash@mail.ru

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

Ключевые слова: машинное обучение, самоорганизующаяся система, метрика, обучение с учителем, обучение без учителя.

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

[1] Versace M., Chandler B. MoNETA: a mind made from memristor // IEEE Spectrum. 2010. Vol. 47. Pp. 30–37.

[2] Шац В.Н. Информация в самоорганизующейся системе. Новые концепции и методы машинного обучения. — Саарбрюкен: LAP LAMBERT Academic Publishing. 2013. 105 c.

[3] Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. –2nd ed. – Springer-Verlag. 2009. 764 p.

[4] Айвазян С.А. и др. Прикладная статистика: Классификация и снижение размерности: Справочное издание. М.: Финансы и статистика. 1989. 607 c.

[5] Вапник В.Н., Червоненкис А.Я. Теория распознавания образов (статистические проблемы обучения). – М.: Наука. 1974. 416 c.

[6] Webb J.I., Boughton R.J., Wang Z. Not so naive Bayes: aggregating one-dependence estimators // Machine Learning, Vol. 58. 2005. Pp. 5–24.

[7] Шац В.Н. Обучающаяся модель самоорганизующейся системы // Стохастическая оптимизация в информатике. 2012. Т. 8. Вып. 1. C. 101–114.

[8] Asuncion A., Newman D.J. UCI Machine Learning Repository. Irvine CA: University of California, School of Information and Computer Science. 2007.

[9] Хьюбер П. Робастность в статистике. - М.: Мир. 1984. 303 c.

[10] Вапник В.Н. Восстановление зависимости по эмпирическим данным. – М.: Наука. 1979. 448 c.

[11] Воронцов К.В., Каневский Д.Ю. Коэволюционный метод обучения алгоритмических композиций // Таврический вестник информатики и математики, 2005. Т. 2. С. 51–66.

Laplace Transform of Time-to-Default for a Specific Class Reflected Surplus Processes with Budget Constraints

P. T. Stoynov,

Sofia University “St. Kliment Ohridski”

Sofia, Bulgaria

todorov@feb.uni-sofia.bg

In this paper we consider a risk model based on reflected surplus processes. This kind of processes can represent the surplus of companies with steady outflows and sporadic inflows. We consider the case where the company can adjust its expense rate by reducing it if no inflow is made by a random time with a specific distribution following the last inflow. Laplace transforms for the time-to-default are calculated for this model.

Key words: surplus processes, reflected surplus processes, budget restriction.

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

[1] Asmusen S., Avram F., Usabel M. Erlangian approximation for finite-horizon ruin probabilities // Astin Bulletin. 2002. 32(2). Pp. 267–281.

[2] Avram F., Usabel M. Finite time ruin probabilities with one Laplace inversion // Insurance: Mathematics and Economics. 2003. 32. Pp. 371–377.

[3] Landriault D., Sendova K. A direct approach to a first-passage problem with applications in risk theory // Stochastic Models. 2011. 27. Pp. 388–406.

[4] Melnikov B., Radionov A., Gumayunov V. Some special heuristics for discrete optimization problems // In: Proc. 8th Int. Conf. on Enterprise Information Systems, ICEIS 2006. Paphos. 2006. Pp. 360–364.

[5] Stoynov P. Parametric estimation of Po´lya-Stoynov distribution by the method of moments // In: Proc. of the Fourth Int. Conf. Financial and Actuarial Mathematics FAM 2011, PERUN-SPRINT Ltd., Sofia, Bulgaria. 2011. Pp. 102–106.

[6] Stoynov P. Sums of a special class generalized Stoynov distributions // In: Proc. of the of the Int. Conf. Financial and Actuarial Mathematics FAM 2012, PERUN-SPRINT Ltd., Sofia, Bulgaria. 2012. Pp. 3–7.

[7] Stoynov P. Some properties of a special class generalized Stoynov distributions // In: Proc. of the of the Int. Conf. Financial and Actuarial Mathematics FAM 2012, PERUN-SPRINT Ltd., Sofia, Bulgaria. 2012. Pp. 102–106.

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

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

Том 9

Выпуск 1

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

Обложка художника Е. А. Соловьевой

Оригинал-макет О. Н. Граничина

Подписано в печать 21.09.13. Формат 60 х 84/1 Бумага офсетная. Печать офсетная. Усл. печ. л. 10,0. Тираж 100 экз. Заказ №

Издательство СПбГУ. 199004, С.-Петербург, В.О., 6-я линия, 11/21

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

E-mail: editor@unipress.ru

www.unipress.ru

По вопросам реализации обращаться по адресу:

С.-Петербург, В.О., 6-я линия, д. 11/21, к. 21

Телефоны: 328-77-63, 325-31-76

E-mail: post@unipress.ru

Типография Издательства СПбГУ 199061, С.-Петербург, Средний пр., 41