кр. Ю. Ю. Громов, О. Г. Иванова, В. В. Алексеев, М. П. Беляев, Д. П. Швец, аи. Елисеев интеллектуальные информационные системы и технологии
 Скачать 2.03 Mb.
|
|
105 декомпозиция задачи разделение обязанностей выявление конфликтующих целей конкуренция за совместные ресурсы формирование правил поведения в коллективе. обучение поведению в коллективе и т.д. Особенностью коллективного поведения агентов является то, что их взаимодействие в процессе решения частных задач (или одной общей) порождает новое качество решения этих задач. При этом в моделях координации поведения агентов используются следующие основные идеи [4]. 1. Отказ от поиска наилучшего решения в пользу хорошего, что приводит к переходу от процедуры строгой оптимизации к поиску приемлемого компромисса, реализующего тот или иной принцип координации. Использование самоорганизации в качестве устойчивого механизма формирования коллективного поведения. 3. Применение рандомизации (случайно-вероятностного способа выбора решений) в механизмах координации для разрешения конфликтов. Реализация рефлексивного управления [6], сущность которого заключается в том, чтобы заставить субъекта осознанно подчиняться влиянию извне, те. сформировать у него такие желания и намерения интенции, которые совпадают с требованиями окружения. Наиболее известными моделями координации поведения агентов являются теоретико-игровые модели, модели коллективного поведения автоматов, модели планирования коллективного поведения, модели на основе BDI-архитектур (Belief–Desire–Intention), модели координации поведения на основе конкуренции. Теоретико-игровые модели. Предметом теории игр являются задачи выбора решений в условиях неопределённости и конфликта. Наличие конфликта предполагает существование как минимум двух участников, которых называют игроками. Множество решений, возможных для выбора каждым игроком, называется стратегией. Равновесными точками игры (оптимальными решениями) называют такие состояния, когда ни одному из игроков невыгодно менять свою позицию. Понятие равновесия оказалось весьма полезным в теории MAC, поскольку механизм поиска равновесных ситуаций может использоваться как средство самоорганизации коллективного поведения агентов. Следствием подобной интерпретации является подход, в котором необходимые атрибуты коллективного поведения агентов обеспечиваются путём конструирования правил игры. Кроме того, на основе развития теории игр в области MAC предпринимаются попытки построения эффективных, устойчивых, полностью распределённых протоколов переговоров, направленных на координацию коллективного поведения агентов. В работе [24] множество возможных ситуаций выбора поведения пары агентов классифицируется следующим образом. 1. Симметричная кооперация, когда существует непустое множество стратегий (переговорное множество, при использовании которых оба агента достигают своих целей и получают больший эффект, чем в ситуациях, когда они действуют поодиночке. 2. Симметричный компромисс, когда достижение цели в одиночку более выгодно для каждого агента, однако невозможно в присутствии другого агента. 3. Несимметричная кооперация или несимметричный компромисс один из агентов может самостоятельно достичь своей цели в присутствии другого агента, а другой – только за счёт кооперации с первым. 4. Конфликт – переговорное множество пустоте. не существует стратегий, обеспечивающих достижение целей обоих агентов. В этой же работе показано, что теоретико-игровые модели позволяют для всех перечисленных случаев сконструировать наборы правил переговоров, следуя которым агенты придут к некоторому соглашению, отвечающему состоянию равновесия. Это достигается за счёт использования множества дополнительных предположений и специальных приёмов. Например, кроме стоимости цели в рассмотрение вводится понятие ценности цели, а в качестве одной из возможных стратегий может выступать стратегия манипулирования информацией о ценности целей (те. агенты могут сообщать друг другу заведомо ложные значения. При этом нечестные агенты могут либо увеличить свой доход, либо освободиться отчасти своей работы. Модели коллективного поведения автоматов. Они основаны на идеях рандомизации, самоорганизации и полной распределённости [1, 14]. Модели этого типа подходят для построения протоколов переговоров в задачах, которые характеризуются большим количеством очень простых взаимодействий с неизвестными характеристиками. Модели планирования коллективного поведения. Планирование может быть централизованным, частично централизованным или рас- пределённым (децентрализованным. В последнем случае агенты сами принимают решения о выборе своих действий в процессе координации частных планов, в связи с чем возникают вопросы о рациональной децентрализации, о возможности изменения целей при возникновении конфликтов, а также проблемы вычислительной сложности. 107 Модели на основе BDI-архитектур [12, 17]. В моделях этого класса применяются аксиоматические методы теории игр и логической парадигмы искусственного интеллекта. Для описания агентов используются логические средства, в том числе темпоральные и модальные логики. Акцент делается на описании интенсиональных понятий, таких, как убеждения (belief), желания (desire) и намерения (intention). Задача координации поведения агентов решается путём согласования результатов логического вывода в базах знаний отдельных агентов, полученных для текущего состояния внешней среды, в которой действуют агенты. Логический вывод осуществляется непосредственно в процессе функционирования агентов, что приводит к высокой сложности моделей, вычислительным трудностями к проблемам, связанным сак- сиоматическим описанием нетривиальных ситуаций, например, когда перед агентом возникает выбор между решением собственной задачи и выполнением обязательств по отношению к партнёрам. Модели на основе конкуренции. В моделях данного класса используется понятие аукцион в качестве механизма координации поведения агентов. Использование механизма аукциона основано на предположении о возможности явной передачи полезности от одного агента к другому или к агенту-аукционеру, причём эта полезность обычно имеет смысл денег [4]. Аукционы принято разделять на открытые и закрытые. В первом случае предлагаемые цены объявляются всем участникам. В закрытом аукционе о предлагаемых ценах знает только аукционер. Открытые аукционы различаются по способу проведения. В так называемых английских аукционах обычно задаётся стартовая цена, которая может увеличиваться участниками входе торгов. Побеждает тот, кто даст максимальную цену. Голландский аукцион начинается с верхней цены, которая постепенно снижается. Победителем считается тот, кто дал наибольшую текущую цену. Закрытые аукционы разделяют на аукционы первой и второй цены. В аукционах первой цены побеждает тот, кто предложил самую высокую цену, известную только аукционеру. В аукционах второй цены победитель определяется таким же способом, но платит за товар не свою цену, а вторую по величине. Теоретически доказано, что все разновидности аукционов эквивалентны для аукционера, однако практика показывает иное. Например, если участники аукциона не склонны к риску, то аукционер стимулирует повышение цены продажи при проведении голландского аукциона первой цены. Существуют варианты групповых аукционов, когда один или несколько участников представляют интересы группы, ив случае выигрыша проводится аукцион внутри группы. При этом на внутреннем 108 аукционе товар продаётся поболее высокой цене по сравнению сценой внешнего аукциона. Полученная разница делится между участниками группы. Сам по себе механизм аукциона не затрагивает способов принятия решений участниками. Решения могут приниматься на основе некоторой модели рассуждений, которая может использовать различные типы знаний, доступных агентами разнообразные способы их обработки. Аукцион всегда должен заканчиваться. Для этого в стратегии его проведения должны быть заложены средства для разрешения возможных конфликтов (например, при наличии нескольких победителей. Одним из самых простых способов разрешения конфликтов является рандомизация, когда применяется случайный механизм выбора. 4.3. Примеры мультиагентных систем Рассмотрим практические примеры организации взаимодействия в мультиагентных системах с использованием различных механизмов координации поведения. Координация поведения на основе модели аукциона. Электронный магазин. Рассмотрим типичную задачу электронной коммерции, в которой участвуют агенты-продавцы и агенты-покупатели рис. 4.1). Торговля осуществляется в электронном магазине, который представляет собой программу, размещённую на сервере. Её основным назначением является организация взаимодействия агентов, интересы которых совпадают. Агенты действуют по поручению своих персональных пользователей. При этом агенты-продавцы стремятся продать свой товар по максимально возможной цене, а агенты-покупатели стремятся купить нужный товар по минимальной цене. Оба вида аген- Рис. 4.1. Схема электронного магазина – агент- продавец – агент- покупатель – процесс переговоров 109 тов действуют автономно и не имеют целей кооперации. Электронный магазин регистрирует появление и исчезновение агентов и организует контакты между ними, делая их видимыми друг для друга. Поведение агента-продавца характеризуется следующими параметрами желаемая дата, до наступления которой необходимо продать товар желаемая цена, по которой пользователь хочет продать товар самая низкая допустимая цена, ниже которой товар не прода- ётся; функция снижения цены во времени (линейная, квадратичная и др описание продаваемого товара. Агент-покупатель имеет симметричные параметры крайний срок покупки товара желаемая цена покупки самая высокая приемлемая цена функция роста цены во времени описание покупаемого товара. Торги ведутся по схеме закрытого аукциона первой цены. Поведение агентов описывается простой моделью, в которой не используются знания и рассуждения. Агент-продавец, получив от электронного магазина информацию о потенциальных покупателях своего товара, последовательно опрашивает их всех с целью принять решение о возможности совершения сделки. Сделка заключается с первым агентом- покупателем, который готов дать за товар запрашиваемую цену. Продавец не может вторично вступить в контакт с любым покупателем до тех пор, пока не опросит всех потенциальных покупателей. При каждом контакте агент-продавец ведёт переговоры, предлагая начальную цену либо снижая е. Агент-покупатель действует аналогичным образом, отыскивая продавцов нужного товара и предлагая им свою цену покупки, которую он может увеличить в процессе переговоров. Любая сделка завершается только в случае её одобрения пользователем агента. Данная схема переговоров представляет собой простейший случай взаимодействия автономных агентов, действующих реактивно. Тем не менее, итоговое поведение системы вполне адекватно реальности. Виртуальное предприятие. Создание виртуальных предприятий является одним из современных направлений бизнеса, которое в значительной мере стимулируется быстрым ростом информационных ресурсов и услуг, предоставляемых в сети Интернет. Кроме того, появлению виртуальных предприятий способствует сокращение времени 110 жизненного цикла создаваемых изделий и повышение уровня их сложности, так как при этом возникает необходимость оперативного объединения производственных, технологических и интеллектуальных ресурсов. Ещё одна немаловажная причина – ужесточение конкуренции на товарных рынках, стимулирующее объединение предприятий в целях выживания. Виртуальное предприятие можно определить как кооперацию юридически независимых предприятий, организаций и индивидуумов, которые производят продукцию или услуги в общем бизнес-процессе. Во внешнем мире виртуальное предприятие выступает как единая организация, в которой используются методы управления и администрирования, основанные на применении информационных и телекоммуникационных технологий. Целью создания виртуального предприятия является объединение производственных, технологических, интеллектуальных и инвестиционных ресурсов для продвижения на рынок новых товаров и услуг. Поскольку каждое реальное предприятие в рамках виртуального выполняет только часть работ из общей технологической цепочки, то при его создании решаются две главные задачи. Первая – это декомпозиция общего бизнес-процесса на компоненты (подпроцессы). Вторая задача заключается в выборе рационального состава реальных пред- приятий-партнёров, которые будут осуществлять технологический процесс. Первая задача решается с применением методов системного анализа, а для решения второй могут применяться средства мультиа- гентных технологий. Задача оптимального распределения множества работ (подпро- цессов) среди множества работников (реальных предприятий) в исследовании операций формулируется как задача о назначениях [5]. Ере- шение начинается сформирования множеств подпроцессов и потенциальных предприятий-участников. Затем строятся возможные отображения из множества участников на множество подпроцессов и делается выбор наиболее приемлемого отображения, которое соответствует конкретным назначениям предприятий на бизнес-процессы. Для этого можно использовать механизм аукциона. На рисунке 4.2 приведена схема аукциона по созданию виртуального предприятия, в котором выделены бизнес-процессы А, ВСЕ и участвуют четыре предприятия Р, Р, Р, Р, претендующие на их реализацию. Каждое из предприятий представлено интеллектуальным агентом, при этом одно из них (Р) выступает в роли инициатора (аукционера. Перед началом аукциона аукционер (менеджер) формирует базу данных и базу знаний об участниках аукциона. Затем он выставляет на продажу отдельные бизнес-процессы, информация о которых пред- 111 Рис. 4.2. Схема создания виртуального предприятия ставлена стартовой ценой и требованиями по заданному набору показателей. Каждый претендент выдвигает свои предложения по параметрам, которые он в состоянии обеспечить, и свою цену. Собрав и обработав эти предложения, аукционер с помощью некоторой модели рассуждения упорядочивает потенциальных претендентов с учётом собственной информации о них. После этого он принимает решение о выборе назначений или отвергает их и выдвигает новые предложения. Мультиагентная система для поддержки принятия решений на предприятии. Интеллектуальные мультиагентные системы принятия решений предназначены для оценки качества организационно- технических и экономических решений в процессе деятельности предприятия. В настоящее время происходит переход от концепции стабильного бизнеса к мобильному, в котором главную роль играют понятия конкурентоспособность и гибкость. Для работы в новых быстроизме- няющихся условиях предприятиям необходимо постоянно трансформировать свои производственные структуры и структуры бизнес- процессов. При этом становится неизбежным привлечение сторонних специалистов из области технологий, маркетинга, реинжиниринга и т.д. Оценка предлагаемых решений является сложными постоянным видом деятельности, требующим участия высококвалифицированных экспертов из разных областей знаний, которые, как правило, территориально удалены друг от друга. Этим обусловлена актуальность рас- пределённой компьютерной поддержки процессов принятия решений на предприятиях, которая может быть реализована с применением мультиагентных систем. 112 Рассмотрим пример мультиагентной системы принятия решений для многокритериальной оценки инновационной деятельности предприятия. Общая схема принятия решений включает следующие этапы 1) спецификация требований 2) генерация решений 3) оценка альтернатив 4) выбор эффективного решения. Оценку решений проводит рабочая группа, которая состоит из руководителя, аналитика и экспертов. Функции между участниками рабочей группы распределяются следующим образом. Руководитель формирует набор показателей (критериев, которые будут использоваться для оценки проектов (решений подбирает состав группы экспертов составляет персональный календарь, в соответствии с которым эксперты выполняют свои задания. Каждый эксперт работает по индивидуальному сценарию, предложенному руководителем. Аналитик, функции которого может выполнять руководитель, высказывает своё мнение о результатах проведённой экспертами работы. Для поддержки группового процесса принятия решений используется программная реализация метода анализа иерархий [10], где реализованы следующие основные процедуры формирование и согласование иерархической структуры показателей оценка и согласование качественных показателей проекта оценка и согласование важности показателей ранжирование альтернативных решений и согласование результатов. В решении перечисленных задач участвует множество экспертов, поэтому на каждом этапе предусмотрены процедуры согласования их мнений. Ядром мультиагентной системы «Multi Expert» (рис. 4.3) является менеджер знаний, использующий три внешних компонента информационную модель проблемной области в виде упорядоченного набора показателей качества решений средства технической и программной поддержки множество типов пользователей (руководитель, координатор, эксперт, аналитик. Для координации работы коллектива экспертов используется двухуровневый механизм согласования. Каждый из экспертов представлен агентом, в задачу которого входит оценка предлагаемых руководителем альтернатив по заданному набору показателей качества. 113 Рис. 4.3. Обобщённая структура мультиагентной системы принятия решений «Multi Expert» С помощью редактора знаний руководитель формирует задания экспертами проводит анализ полученной от них информации. Задача координации поведения агентов возложена на агента-координатора. Результатом работы системы являются согласованные экспертные оценки, на основании которых проводится многокритериальное ранжирование альтернатив. Рассмотрим основные функции агентов в системе «Multi Expert». Агент-руководитель: предоставляет набор процедур для облегчения работы руководителя в распределённой системе вычисляет конечный результат на основании данных, полученных от других агентов отслеживает согласованность решения, вырабатываемого групппой; предоставляет средства визуализации результатов работы подготавливает сообщения агенту-координатору; выполняет почтовые функции в распределённой среде. Агент-координатор: обеспечивает выполнение пошагового алгоритма принятия решения 114 поддерживает целостность баз данных системы на групповом уровне и вносит в них необходимые изменения подготавливает диалоговые формы для информационного обмена через Интернет. Агент-эксперт: поддерживает выполнение текущего шага задания готовит сообщения агенту-координатору; поддерживает целостность локальных баз данных выполняет почтовые функции в распределённой среде. Работа агентов осуществляется следующим образом. Руководитель формирует задания, оперируя справочниками, содержащими знания об экспертах, показателях качества и решениях, требующих рассмотрения. Далее задание в виде входного сообщения М поступает агенту-координатору, определяющему состав изменений, которые необходимо сделать в базах данных на локальном уровне. Координатор с помощью предоставленного ему набора функций готовит информацию для всех агентов-экспертов рабочей группы. Агенты-эксперты выполняют задания, предназначенные для своих пользователей, анализируя поступившие от координатора сообщения M ij ( j – номер эксперта, и отсылают ему ответные сообщения М 0j Агент-координатор собирает сообщения о готовности выполненных заданий от всех членов группы. При выполнении всего пакета заданий его состояние изменяется, и посылается сообщение агенту руководителя М 0ut Руководитель может выполнять проверку согласованности экспертных суждений либо на основе вычислений, либо с помощью логического анализа предоставленной ему информации. Решение руководителя о степени согласованности суждений посылается агенту- координатору, который продвигает задание наследующий шаг или возвращает экспертов на предыдущий этап в целях достижения лучшей согласованности. |