Эволюционные алгоритмы автоматизированного формирования интеллектуальных алгоритмов

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

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

Другим, не менее важным, направление интеллектуальных технологий являются интеллектуальные агенты. Сфера их применения очень велика. Они широко применяются как в простых информационных устройствах, так и в сложных системах.

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

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

Объект исследования

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

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

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

Понятие агента и виды их архитектур

Существует большое множество определений агента. На Токийской встрече в октябре 1996 года определение агента было сформулировано следующим образом [5, стр. 165; 7, стр. 92]: «Агент - это сущность, которая находится в некоторой среде, от которой она получает данные и которые отражают события, происходящие в среде, интерпретирует их и воздействует на среду. Агент может содержать программные и аппаратные компоненты. Отсутствие четкого определения мира агентов и присутствие большого количества атрибутов, с ним связанных, а также существование большого разнообразия примеров агентов говорят о том, что агенты - это достаточно общая технология, которая аккумулирует в себе несколько различных областей».

В общем смысле агент это программный модуль, который способен достигать поставленные цели, выполняя определенный набор функций, обладая собственной природой поведения, адаптирующийся к изменениям окружающей среды. Интеллект при этом понимается, как способность агента создавать в ходе самообучения программы для решения задач определенного класса сложности и решать эти задачи. При этом под термином «интеллектуальный агент» понимается некая разумная сущность, способная к пониманию и достижению поставленных целей, и действующая в некой окружающей среде, не изменяя ее. Уровень интеллектуальности агента можно оценить, как способность агента использовать свои знания в заранее неизвестных ему ситуациях и проблемных областям, и при этом приобретать новые знания [6, стр. 77-78]. Таким образом, важным отличительным свойством агента от простой программы, является наличие внешней среды, которая оказывает огромное влияние на его поведение. При этом взаимодействуя с внешней средой, агент может влиять на нее, но не может контролировать.

Агентом считается все, что действует (слово агент произошло от латинского слова agere – действовать). Как описано выше, компьютерные агенты обладают атрибутами, которые отличают их от обычных программ, например, способность функционировать под автономным управлением, воспринимать свою среду, существовать в течение продолжительного периода времени, адаптироваться к изменениям и обладать способностью взять на себя достижение целей, поставленных другими [6, стр. 86]. Таким образом, можно сформулировать следующее: агент в интеллектуальных системах - это сущность (вычислительная система), которая может воспринимать внешнюю среду с помощью датчиков (сенсоров) и воздействовать на нее с помощью исполнительных механизмов (рисунок 1).

Рисунок 1 - Агент взаимодействует со средой с помощью датчиков и исполнительных механизмов

Функцией агента является абстрактное математическое описание того, что должен делать агент. Задачей искусственного интеллекта является разработка программы агента, то есть того, как именно должен действовать агент [1, стр. 38; 3]. Предполагается, что эта программа должна работать в вычислительном устройстве с физическими датчиками и исполнительными механизмами. В целом эти компоненты именуются архитектурой. Структуру агента можно представить следующим образом: Агент = Архитектура + Программа. В понятие архитектуры агента входят механизмы взаимодействия с окружающей средой. А программой агента является агентская функция, которая проектирует результат в действие агента или в некоторый элемент обратной связи, способный повлиять на дальнейшее действие агента.

Виды архитектур агентов

При рассмотрении архитектуры агентов задается модель, описывающая функции агента, определяющая внутреннее состояние агента и его взаимодействие с внешней средой и с другими агентами в многоагентной системе. В настоящее время выделяют четыре основных типа моделей, и следовательно, архитектур [6, стр. 93; 7, стр. 103-110]:

• 1)    Агенты, основанные на модели классической логики или на знаниях.

• 2)    Реактивные агенты (архитектура, основанная на реакции системы на события окружающей среды).

• 3)    BDI - агенты (внутреннее состояния и принимаемые решения определяются структурой данных, которые представляют собой такие ментальные понятия агента, как убеждения, желания, намерения).

• 4)    Многоуровневые модели (описание агента и используемой им модели рассуждений производится на различных уровнях абстракции или обобщения).

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

Архитектуры агентов, основанные на классической логике и на знаниях

В архитектуре, основанной на модели классической логики, содержится символьная модель мира, в которой принятие решений о предпринятых агентом действиях осуществляется на основе рассуждений логического или псевдо-логического типов [7, стр. 119]. Другими словами, логические агенты обладают базой знаний (куда входит представление о внешней среде) и механизмом принятия решений (рисунок 1). Такой агент сначала строит план по достижению цели, а потом выполняет его путем циклического повторения трех основных процедур: выбрать цель, сгенерировать план ее достижения, исполнить план, выбрать новую цель и т.д. Логические агенты имеют ярко выраженную индивидуальность и характеризуются целесообразным поведением. Благодаря своим возможностям рассуждений, такие агенты могут запоминать и анализировать различные ситуации, предвидеть возможные реакции на свои действия, делать выводы и в результате планировать свое поведение.

Архитектура на основе планирования (реактивная архитектура)

Реактивная архитектура в общем смысле представляет собой описание множества вариантов поведения, каждый из которых моделируется конечным автоматом, входами которого являются воспринимаемые агентом состояния внешней среды, а выходами являются реакции агента [6, стр. 99]. У таких агентов нет пошаговых рассуждений, они практически не способны планировать свои действия. Реактивные агенты работают на уровне стимульно - реактивных связей, обладая сильной зависимостью от внешней среды (в том числе и от других агентов).

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

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

Взаимодействуя между собой, агенты образуют систему. В многоагентной системе агенты наделены рядом характеристик []:

• 1)    Автономность (агенты хотя бы частично являются независимыми).

• 2)    Ограниченность представления (ни один агент не имеет полного представления о системе).

• 3)    Децентрализация (ни один агент не управляет всей системой).

Многоагентные системы (МАС) могут строиться как объединение отдельных интеллектуальных агентов, основанных на знаниях, как системы взаимодействующих реактивных агентов, и как гибридные системы, основанные на построении механизмов взаимодействия интеллектуальных (логических) и реактивных агентов.

Интеллектуальные (логические) агенты сотрудничают с другими агентами «сознательно», преследуя при этом определенные цели. Взаимодействие между реактивными агентами является непреднамеренным, так как оно основано на естественных реакциях агентов.

При выборе архитектуры МАС необходимо учитывать два основных аспекта:

• 1)    выбор архитектуры взаимодействия агентов в системе;

• 2)    архитектуру отдельного агента (рассмотрены выше).

Основное назначение архитектуры взаимодействия агентов в системе в том, чтобы скоординировать поведения агентов при решении общей или личных задач. Выделяют два основных варианта архитектуры [7, стр. 123124]:

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

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

Агенты в МАС образуют многоуровненность двух видов [7, стр. 124126]:

• 1)    горизонтальную (все уровни агента имеют доступ к уровню восприятия и действий. Недостатком такой архитектуры МАС является сложность организации согласованной работы всех уровней);

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

При создании МАС каждый отдельный агент способен решать некоторую подзадачу. Для распределения задач необходимо каждому агенту назначить определенные роли, меру ответственности и требования к опыту. Выделяют два основных вида системы в зависимости от того, как производится распределение ролей (от поставленной задачи или от возможности конкретного агента) [2, стр. 45; 4, стр. 119]:

• •    Системы распределенного решения задачи (МАС проектируется сверху вниз на основе разбиения общей задачи на отдельные подзадачи и предварительного определения ролей агентов).

• •    Системы децентрализованного искусственного интеллекта (распределение задач происходит случайно в процессе взаимодействия агентов).

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

• •    кооперация (сотрудничество);

• •   конкуренция (конфронтация, конфликт);

• •   компромисс (учет интересов других агентов);

• •    конформизм (отказ от своих интересов в пользу других);

• •    уклонение от взаимодействия .

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

Как было описано выше, в данной статье рассматривается формирование систем с реактивными агентами. Такие агенты действуют в режиме реального времени, основываясь на небольшом количестве информации и простых правилах «ситуация - действие». Реактивная архитектура является альтернативой архитектуры агентов, основанных на знаниях (более подробно с алгоритмом автоматизированного формирования таких агентов можно ознакомиться в других моих работах).

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

Агент 1

Сообщение

Агент 2

Рисунок 2 – Общая схема обмена сообщениями между двумя агентами

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

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

Для формирования топологии сообщений предлагается использовать алгоритм генетического программирования. Общая схема генетического программирования выглядит следующим образом [8]:

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

Шаг 2. Оценивание текущей популяции. В соответствии с выбранной функцией пригодности каждому решению в популяции ставится в соответ -ствие число, характеризующее качество данного решения.

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

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

Шаг 5. Мутация. Листья дерева выбираются с некоторой вероятностью и заменяются на другие, выбранные случайным образом.

Шаг 6. Проверка условия останова. Если условие выполняется, то выбирается лучший индивид, который и считается найденным решением, иначе - переход на шаг 2.

В рамках проектирования необходимо определить способ представления решения и способ расчета пригодности.

Рассмотрим первый вопрос. Топология по своей сути является сетевой структурой. Для представления сетевых структур в генетическом программировании удобно выбирать непрямое кодирование, т.е. когда кодируется не сама структура, а формирующая ее программа.

В этом случае терминальным множеством будут фрагменты такой сети, а функциональным множеством операторы связывающие фрагменты в единую сеть. Например, пусть имеется следующий набор терминального и функционального множества (соответственно): Т={a12, a34, a} и F={*, >, <>}, где a12 – коммуникация между агентами 1 и 2; a34 – коммуникация между агентами 3 и 4; a – одиночный агент; * - общая доска с сообщениями; > - последовательная коммуникация между агентами (последний агент связывается с первым); <> - все агенты связываются со всеми в случайном порядке. Тогда дерево коммуникаций и соответствующая ему сеть будут иметь вид, представленный на рисунке 3.

Рисунок 3 – Дерево коммуникации агентов (а), кодирующего сеть (б)

Основные виды коммуникаций между агентами, представлены в таблице 1.

Главное отличие коммуникации «общая доска» от коммуникации «все со всеми» заключается в том, что при наступлении события (сообщения) при коммуникации «все со всеми» связь наступает только между двумя агентами, а в случае с коммуникацией «общая доска» связь возникает у всех агентов с доской.

Таблица 1 – Примеры коммуникаций между агентами

<> (связь «все со всеми»)

С1 j С з j С 2 7С 4 J

В зависимости от природы решаемой задачи агенты могут быть именованы по умолчанию (так называемые готовые агенты), либо именованы после обучения, либо вообще обезличены на всем протяжении работы МАС. Пример дерева именованных агентов представлен на рисунке 3. На рисунке 4 представлено дерево обезличенных агентов и кодируемая с помощью него сеть:

а)

Рисунок 4 - Дерево обезличенных агентов (а) и кодируемая с помощью него сеть (б)

б)

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

Рисунок 5 – Схема вычисления оценки пригодности

Работоспособность предложенных алгоритмов исследована на множестве тестовых и практических задач. Более подробно о практических результатах можно ознакомиться в других моих работах.

Заключение

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