ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2012, № 2, с. 92-120
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 519.687.1/4
САМООРГАНИЗАЦИЯ И МНОГОАГЕНТНЫЕ СИСТЕМЫ. I. МОДЕЛИ МНОГОАГЕНТНОЙ САМООРГАНИЗАЦИИ*
© 2012 г. В. И. Городецкий
Санкт-Петербург, Санкт-Петербургский ин-т информатики и автоматизации РАН Поступила в редакцию 07.12.10 г., после доработки 07.06.11 г.
В настоящее время возникает много задач, сложность которых значительно превосходит возможности современных информационных технологий. Такие задачи встречаются в экономике и экологии, в управлении инфраструктурами государственного масштаба и глобальными компьютерными и телекоммуникационными системами, в сфере обеспечения безопасности общества и во многих других областях. Несмотря на внешнее разнообразие, эти задачи обладают множеством общих свойств, которые обусловливают и общие проблемы их практической реализации. К ним относятся крупномасштабность, открытость, непредсказуемая динамика, сложность структуры, мобильность компонент и ряд других. Управление в таких задачах представляет собой серьезный вызов, который требует пересмотра современных взглядов, моделей, архитектур, а также технологий их разработки. Одним из современных ответов на этот вызов является активизация работ в области принципов и механизмов самоорганизации, а также программных инструментов для их разработки. Хотя парадигма самоорганизующихся систем управления не нова, в настоящее время она переживает новый этап развития, который характеризуется, в частности, ее интеграцией с парадигмой многоагент-ных систем. Данная работа имеет целью анализ современного состояния разработок в области многоагентных самоорганизующихся систем, критический обзор разработанных приложений, анализ методов разработки и обобщение результатов в этой области. Работа состоит из двух частей. В первой части анализируется современное понимание принципов самоорганизации и рассматриваются причины, по которым ее технологическая интеграция с достижениями в области многоагентных систем обеспечивает новый импульс развития информационных технологий в контексте самых сложных современных приложений. Приводится систематизация и дается краткая характеристика моделей и механизмов самоорганизации, реализуемых в архитектуре многоагентных систем и биологических механизмов самоорганизации. Описываются приложения самоорганизующихся многоагентных систем в области телекоммуникаций, в задачах управления ресурсами грид1 и маршрутизации в сетях динамической топологии, а также их применение в области распределенного обучения, в частности, в задаче обнаружения вторжений в компьютерные сети.
Введение. Основные тенденции развития современных информационных технологий во многом определяются наиболее важными практическими задачами, зачастую, глобальной значимости. Такие задачи возникаютв экономике, экологии, управлении глобальными компьютер -ными инфраструктурами, обеспечении безопасности общества и отдельного человека, в обеспечении высокого ур овня качества жизни человека в шир оком смысле этого слова и др. В последнее десятилетие в связи с глобализацией экономики и экологических пр облем, возрастанием и качественным изменением угр оз безопасности, а также в связи с р остом р азличий в ур овне жизни населения в р азных стр анах эти задачи, с одной стороны, становятся все более и более сложными, а с другой стор оны — их важность постоянно возрастает. Большие достижения в области компьютерной техники и сетевых технологий предоставляют в этом контексте не только новые возможности, но и выдвигают новые требования к информационным технологиям.
Несмотря на большое содержательное разнообразие упомянутых актуальных задач, а также программных систем, реализующих их, они обладают множеством общих черт, которые главным образом и определяют, с одной стороны, требования к современным информационным технологиям, а с другой — тенденции их развития. Среди таких черт следует, прежде всего, отметить круп-
*Результаты, представленные в разд. 5.4, получены при выполнении проекта № 214 Программы Президиума РАН № 14.
1Грид (англ. grid — сеть, решетка) — виртуальный (географически) распределенный суперкомпьютер, который представлен кластером слабосвязанных гетерогенных компьютеров, соединенных в сеть и работающих совместно при выполнения потока задач. Грид-вычисления — это форма распределенных вычислений на грид, когда выбор конкретного компьютера для решения той или иной задачи выполняется системой управления грид.
номасштабность. Как правило, такие системы состоят из огромного числа автономных сущностей, число которых может иметь порядок тысяч, сотен тысяч, миллионов и даже более. Эти сущности обычно распределены в пространстве, образуя сетевую структуру, преследуют свои локальные цели, которые могут быть отличными от глобальных целей системы, в которую они входят, но они или вынуждены или заинтересованы во взаимодействии по тем или иным причинам. Реализующие их программные системы должны быть открытыми, поскольку составляющие их автономные сущности могут входить в систему и покидать ее в любой момент времени, а связи между ними могут постоянно изменяться, так что такие сетевые системы являются динамическими как по составу компонент, так и по своей топологии. При этом отдельные автономные сущности обладают весьма ограниченными знаниями о других компонентах сети, их целях и возможностях, а также ограниченной информацией о топологии сети в целом. Как правило, такие программные системы функционируют в динамической внешней среде, и при этом каждая автономная сущность системы может воспринимать только ограниченное множество характеристик своего непосредственного окружения. Дополнительные особенности возникают в том случае, когда компоненты системы (составляющие ее автономные сущности) являются мобильными (подвижными) устройствами с ограниченной дальностью связи. Говорить об оптимальном управлении такими системами, а тем более, об оптимальном централизованном управлении нереально. Это нереально не только ввиду огромной размерности задачи управления, непредсказуемости динамики ее структуры, динамики внешней среды и разнообразия целей составляющих ее автономных сущностей, но также и по организационным соображениям, поскольку в таких системах может просто отсутствовать единый центр управления. Такими являются, например, системы, базирующиеся на сети Интернет.
В этих условиях очевидна необходимость развития принципиально нового подхода к методам управления и архитектуре построения систем, развития новых информационных технологий. Практическая реализация систем, примеры которых даны выше, представляет собой серьезный вызов, требующий пересмотра многих современных взглядов, методов, моделей и средств проектирования, а также методов и инструментов для разработки программных систем. Понимание этого факта отражено, в частности, в новой инициативе в области информационных технологий, сформулированной в совместном проекте стран большой восьмерки, озаглавленном "Interdisciplinary Program on Application Software towards Exascale Computing for Global Scale Issues" ("Междисциплинарная программа по прикладному программному обеспечению для сверхскоростных вычислений в интересах проблем глобального значения") [1]. Этот проект предполагает объединение усилий исследователей ведущих стран с целью разработки новой парадигмы построения программного обеспечения, создания инфраструктурных и инструментальных программных средств и сверхскоростных вычислительных систем, способных обеспечить эффективное решение задач глобального масштаба и глобального значения.
Одним из современных ответов на такой вызов является значительная активизация исследований в области принципов, моделей и механизмов самоорганизации, а также программных инструментов для разработки самоорганизующихся систем. Хотя впервые термин "самоорганизация" встречается еще в работах Р. Декарта, в области кибернетики понятие самоорганизующейся системы было введено В.Р Эшби [2], который определяет ее как систему, которая сама изменяет свою организацию. Несколько позже понятие самоорганизации как взаимодействия элементов системы через внешнюю среду было введено П.П. Грассе [3], который изучал общественное поведение в колониях насекомых. В частности, он исследовал механизмы координации поведения термитов при строительстве гнезда. Для такого вида самоорганизации им был введен термин "стигмёрджи (stigmergy). В настоящее время он активно используется для механизмов самоорганизации, в которых отсутствует прямое взаимодействие автономных сущностей, составляющих систему.
В 1959 г. в США состоялась первая междисциплинарная конференция, посвященная проблеме самоорганизации [4]. Она собрала практически всех ведущих специалистов в кибернетике на то время. Среди них были Ф. Розенблат, У. Мак-Калок, Ф. Ньюэлл, Г. Саймон и другие, впоследствии получившие мировое признание в области искусственного интеллекта. На этой конференции ими были сформулированы принципиальные задачи в области самоорганизации, решение которых, однако, стало возможным уже в значительно более позднее время. Проблемы, обсуждавшиеся на конференции, относились главным образом к машинному обучению, поведению автоматов, логическим моделям решения проблем, селективному отбору и т.п. В то же время серьезное внимание обращалось на значение обратной связи от окружающей среды, подчеркива-
2 Это слово не имеет перевода на русский язык, поэтому оно используется далее в соответствии с его произношением.
лась необходимость глубокого изучения принципов надежного функционирования биологических систем и нейроподобных структур, важность сетевой организации компонент самоорганизующихся систем. Содержание этой дискуссии намного опередило свое время. Например, в докладе Г. Ферстера, хотя и в неявной форме, были высказаны некоторые мысли о термодинамической концепции самоорганизации, которая спустя 17 лет была четко сформулирована И.Пригожиным [5] как процесс возникновения в открытой системе порядка из хаоса, когда в нее поступает энергия извне.
Следует отметить, что самоорганизация как не
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.