5.6.  Искусственная жизнь и MAC

Как уже указывалось выше в настоящей главе, сегодня основные направления в MAC — распределенный искусственный интеллект и искусственная жизнь (в узком смысле). Чаще всего исследователи рассматривают второе направление как выживание, адаптацию и самоорганизацию в динамической враждебной среде большого числа простых и, необязательно, интеллектуальных агентов. В этом плане рассмотренная популяция автоматов (§ 5.3) и представляет собой «коллективный интеллект» (collective intelligence) или «интеллект роя» (swam intelligence). Здесь механизмы реакции агентов на воздействия внешней среды и локальных взаимодействий агентов не используют прогнозирование, планирование, знания и т. п., хотя и позволяют решать сложные задачи. Как мы видели, коллектив довольно простых автоматов демонстрирует не только адаптивные способности по отношению к среде, но и способность регулировать численность своей популяции в зависимости от внешней среды. Как один из следующих шагов в направлении развития искусственной жизни, рассмотрим популяцию интеллектуальных агентов, но не взаимодействующих друг с другом для достижения общей цели, как это рассматривалось в предыдущем разделе, а решающих некоторую общую задачу и существующих в эволюционирующей популяции. То есть, нас интересуют интеллектуальные агенты как некоторые особи, образующие популяцию, решающие некоторую задачу, и, соответственно, эволюция популяции при решении этой задачи (выполнении некоторой деятельности).

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

алъных агентов (или групп агентов). Это принципиальное отличие MAC и системы искусственной жизни (в широком смысле этого понятия).

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

При представлении сложной системы в виде MAC используется некоторое множество когнитивных агентов {А1,А2,..., А^}. При этом для оптимального управления некоторой сложной системой с помощью данной MAC необходимым является оптимизация поведения каждого агента в MAC. Каждый і-й агент характеризуется набором параметров (ац, ,...

..., din), которые и определяют его поведение в системе. Рассмотрим систему однотипных по структуре когнитивных агентов с одинаковым набором параметров:

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

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

где

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

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

Эволюционная стратегия реализуется следующим образом (рис. 5.30).

1.   Генерация начальной популяции. На всем пространстве поиска

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

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

3.   N ^ Л^тах? Проверяется условие окончания работы алгоритма, а именно, условие окончания развития популяции, при котором текущее число поколений N становится больше или равно максимальному числу поколений для данной популяции Л^тах.

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

с другой особью в популяции. Схема алгоритма скрещивания изображена. на рис. 5.31. Скрещивание особей в популяции происходит следующим образом:

•    Выбор очередной особи в популяции (Особь і). Выбирается очередная особь в популяции с номером г.

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

Таким образом перебираются по очереди все особи в популяции.

•    Подбор пары (Особь j) для і-й особи. Реализует подбор пары для г-й особи. Для этого случайным образом выбирается Особь j из всех особей в популяции. Если при этом выбралась Особь і, т. е. г = j, тогда процесс выбора пары для г-й особи повторяется.

•    Р(ОК) > Р(ОК)3? Определяется, произойдет ли скрещивание между очередными двумя особями в популяции. Для этого случайным образом на интервале (0,1) генерируется число Р(ОК) — вероятность скрещивания. Если Р(ОК) больше, чем заданная вероятность скрещивания Р(ОК)з, то происходит скрещивание между данными особями. При этом Особь і будет иметь три потомка. Если же данное условие не выполняется, то скрещивания не происходит, и Особь і будет иметь одного потомка.

•    Определение 2-го и 3-го потомков і-й особи. Реализуется в случае выполнения условия скрещивания особей. При этом образуются второй и третий потомки г-й особи посредством оператора скрещивания. Оператор скрещивания представляет собой механизм одноточечного скрещивания двух особей с разрывом хромосом по одной позиции.

•    Определение 1-го потомка і-й особи. Реализует получение 1-го потомка г-й особи посредством самовоспроизведения. При этом образуется потомок, который является точной копией родителя. Необходимо отметить, что, независимо от условий скрещивания, для каждой особи в популяции определяется первый потомок.

•    Рассмотрены все особи? Проверяет условие окончания блока скрещивания для популяции. Если все особи в популяции получили потомков, то о суще ствляетс я переход к следующему блоку алгоритма.

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

только второй и третий потомки каждой особи. Сделано это с целью поддержания накопленного уровня развития «эволюционной линии» каждой особи. При этом гарантируется, что каждая особь в последующем поколении не хуже своего родителя из предыдущего поколения. Схема мутации изображена на рис. 5.32. Мутация производится следующим образом:

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

•    Особь имеет 3 потомка ? Если особь имеет три потомка, тогда переход к следующему блоку Если же особь имеет одного потомка, то мутации потомков не происходит.

•    Р(ОМ) > Р(ОМ)з? Определяется, произойдет ли мутация 2-го и 3-го потомков г-й особи. Для этого случайным образом на интервале (0,1) генерируется число Р(ОМ) — вероятность мутации. Если Р(ОМ) больше, чем заданная вероятность

мутации Р(ОМ)3, то происходит мутация 2-го и 3-го потомков.

•    Мутация 2-го и 3-го потомков. Реализуется в случае выполнения условия мутации. При этом применяется оператор мутации ко второму и третьему потомкам г-й особи. Оператор мутации представляет собой механизм однобитной мутации, при которой инвертируется один бит строки- хромосомы.

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

6. Блок воспроизведения популяции. Реализует воспроизведение особей и формирование новой популяции. Для каждой особи в последующую популяцию отбирается один лучший потомок (с наибольшей ФП), тем самым, продолжая «эволюционную линию» данной особи. Особь родитель при этом погибает. Таким образом, число особей в последующей популяции равно числу особей в предыдущей популяции и неизменно при переходе популяции от поколения к поколению. Схема, воспроизведения популяции изображена, на. рис. 5.33. Она. работает следующим образом:

•    Создание новой популяции особей. Создается новая популяция особей, которая будет состоять из потомков особей текущей популяции, причем

в новую популяцию отбирается по одному потомку от каждой особи текущей популяции. Номер поколения N для новой популяции увеличивается на единицу по сравнению с номером поколения текущей популяции.

•    Выбор очередной особи в популяции (Особь і). Выбирается очередная особь в текущей популяции с номером і.

Параметр і представляет собой значения счетчика, изменяющегося в пределах от 1 до числа особей в популяции. Таким образом перебираются по очереди все особи в популяции.

•    Выбор лучшего потомка і-й особи (Потомок /’). Если Особь г имеет три потомка, то выбирается лучший (с максимальной ФП) потомок. Если же особь имеет одного потомка, то он и является лучшим потомком г-й особи.

•    Добавление в новую популяцию потомка і. Потомок і добавляется в новую популяцию под номером і, тем самым, продолжая «эволюционную линию» г-й особи.

•    Рассмотрены все особи? Проверяет условие окончания блока воспроизведения популяции. Если новая популяция полностью сформирована, то старая популяция удаляется.

•    Удаление старой популяции особей. Старая популяция удаляется. При этом «погибают» старые особи.

Покажим работу модели «Искусственной жизни» на тестовой задаче. Задача заключается в следующем.

Имеется дискретное (с шагом 2-8) двумерное пространство с изменением координат от 0 до 1. В пространстве имеется 25 точек-оптимумов (для каждой особи-агента), равноудаленных друг от друга. В данном пространстве «живут» 25 особей-агентов и каждая особь-агент имеет свой оптимум, к которому стремится в результате развития популяции. Визуально пространство поиска показано на рисунке (рис. 5.34). Здесь в кружках, равномерно распределенных по пространству поиска, проставлены номера агентов, для которых данные кружки являются оптимальным расположением по отношению к другим агентам.

Для сравнения, эта же задача решается также методом случайного перебора, в котором: количество генераций случайных особей-агентов на каждом поколении равно числу агентов потомков в модели «Искусственная жизнь». Сделано это для того, чтобы уравнять вычислительные

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

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

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

 

 

 

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

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