Часть 17.

Поскольку генетическое программирование - это метод генерирования компьютерных программ, то его можно отнести к области автоматического программирования. Над проблемой автоматического создания компьютерных программ на основе фрагментар­ной информации исследователи работают с самого начала развития искусственного ин­теллекта [Shapiro, 1992]. Генетическое программирование можно рассматривать как од­но из средств в этой важной области исследований. В конце этого раздела будет приве­ден простой пример генетического программирования из [Mitchell, 1996].

Эволюция программы, моделирующей третий закон Кеплера о движении планет

В [Koza, 1992] описано много приложений метода генетического программирования, позволяющих решать интересные задачи. Однако большинство этих примеров слишком объемны и сложны. В то же время в [Mitchell, 1996] приводится простой пример, иллюстрирующий многие важные понятия генетического программирования. Третий закон Кеплера о движении планет описывает функциональные зависимости между периодом орбиты Р и средним расстоянием от этой планеты до Солнца Л.

Формула третьего закона Кеплера имеет вид

Р2=сА3

где с - константа. Если считать, что единицей измерения величины Р является земной год, а величина А - это количество средних расстояний от Земли до Солнца, то с=1. Для этого отношения s-выражение имеет вид

P=(sqrt(*A(AA))).

Целевая программа, реализующая это соотношение, представлена в виде древовидной структуры на рис. 11.7.

В этом примере множество конечных символов выбирается очень просто: оно включает только одно значение А. Набор функций тоже задается несложно, в частности {+, -, *, /, sq, sqrt}. Создадим случайным образом популяцию программ. Исходная популяция может иметь вид

(*А(-{*А A)(sqrt А))) мера качества: 1 (/А(/(/А А){/А А))) мера качества: 3 (+А(*( sqrt A)A)) мера качества: О

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

Определим набор тестов для программ этой популяции. Допустим, нам известна некоторая информация о планетах, которая должна найти свое подтверждение при работе программы. Предположим, известны данные, приведенные в табл. 11.3. Эти сведения получены из работы [Urey, 1952].

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

504 Часть IV. Машинное обучение

11.3. Искусственная жизнь и эмерджентное обучение

Ранее в этой главе была описана упрощенная версия игры "Жизнь". Эта игра, которую можно эффективно визуализировать на компьютере, имеет очень простое описание. Впервые она была предложена математиком Джоном Хортоном Конвеем (John Horton Conway) и получила широкую популярность благодаря ее описанию в журнале Scientific American в 1970-1971 годах. Игра "Жизнь"- это простой пример модели вычислений, получившей название клеточных автоматов (cellular automata). Клеточный автомат - это семейство простых конечных автоматов, демонстрирующее интересное эмерджент­ное поведение при взаимодействии элементов популяции.

ОПРЕДЕЛЕНИЕ

МАШИНА С КОНЕЧНЫМ ЧИСЛОМ СОСТОЯНИЙ, или КОНЕЧНЫЙ АВТОМАТ Понятие конечного автомата включает следующие элементы.

Множество /, называемое входным алфавитом.

Множество S возможных состояний автомата.

Известное начальное состояние s0.

Функция N: Sx|?S, определяющая следующее состояние для каждой упорядоченной пары состояние-вход.

Глава 11. Машинное обучение на основе социальных и эмерджентных принципов 505

Выход машины с конечным числом состояний - это функция текущего состояния и состояний ближайших конечных автоматов. Так, состоянием конечного автомата в момент t +1 является функция от его собственного состояния и состояния его соседей в момент вре­мени f. Благодаря взаимодействию каждого элемента клеточного автомата со своими соседя­ми достигается гораздо более разнообразное поведение, чем поведение отдельного элемента. Такая взаимозависимость является одним из наиболее привлекательных свойств клеточных автоматов. Поскольку выход каждого элемента зависит от состояния его соседей, эволюцию состояний набора элементов можно описать как процесс социальной адаптации.

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

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

И, наконец, в отличие от обучения с учителем, эволюция не должна быть "направленной". Нельзя считать, что общество движется к некоторой заранее заданной точке "омега". При явном использовании меры качества в предыдущих разделах этой главы на самом деле ста­вилась задача сходимости процесса обучения. Однако, как отмечено в работах [Gould, 1977], [Gould, 1996], эволюцию нельзя рассматривать с точки зрения улучшения мира, а лишь с точки зрения его выживания. Единственной мерой прогресса является продолжение существования.

11.3.1. Игра "Жизнь"

Рассмотрим простую двухмерную решетку или игровую доску, показанную на рис. 11.9. На этом рисунке одна из клеток закрашена черным (занята), а восемь соседних - заштри

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

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

506 Часть IV. Машинное обучение

Например, рассмотрим состояние, показанное на рис. 11.10, а. Здесь ровно две клетки (обозначенные символом X) имеют ровно по три занятые соседние клетки. Следующее поколение показано на рис. 11.10, б. Здесь также существуют две клетки (обозначенные символом Y), у которых есть три занятых соседа. Несложно убедиться, что состояние жизни будет циклически переходить между рис. 11.10, а и 11.10, б. Читателю предлагается определить следующее состояние для рис. 11.11,аи 11.11, б, а также исследовать другие возможные конфигурации "мира". В работе [Poundstone, 1985] описано большое разнообразие и богатство структур, получаемых в результате игры "Жизнь", в том числе планеры (glider) - шаблоны ячеек, которые перемещаются по игровой доске в повто­ряющихся циклах изменения формы.

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

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

Помимо известных попыток специалистов по антропологии и других ученых заполнить бреши в изучении реальной эволюции, не прекращаются дискуссии о циклическом характере самой эволюции. Что бы произошло, если бы эволюция началась из других начальных условий? Что бы изменилось при включении других переходных процессов в нашей физической и биологической среде? Как пошел бы процесс развития? Что оста­лось бы нетронутым? Путь развития, который реально был пройден на Земле, - это

Глава 11. Машинное обучение на основе социальных и эмерджентных принципов 507

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

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

Одним из средств понимания мира является моделирование и анализ общества на основе взаимодействия и движения. Примером такой модели является игра "Жизнь". Последовательность жизненных циклов, показанная на рис. 11.12, иллюстрирует упомянутую ранее структуру "планер". Планер перемещается по жизненному пространству, циклически изменяя свою форму. За четыре такта он перемещается в новое положение со сдвигом на одну клетку вправо и вниз.

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

508 Часть IV. Машинное обучение

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

11.3.2. Эволюционное программирование

Игра "Жизнь" - это интуитивный описательный пример клеточного автомата. Описание клеточных автоматов можно обобщить, охарактеризовав их как машину с конечным числом состояний. В этом разделе будут рассмотрены сообщества связанных друг с другом машин с конечным числом состояний и проанализировано их взаимодействие. Эта область знаний получила название эволюционного программирования (evolutionary programming).

История эволюционного программирования возникла в момент зарождения самих компьютеров. В 1949 году в цикле лекций Джона фон Неймана исследован вопрос о том, какой уровень организационной сложности необходим для самовоссоздания. В [Burks, 1970] цель фон Неймана определена так: "...это не попытка моделировать самовоспроизводство естественной системы на уровне генетики и биохимии. Автор хотел абстрагироваться от естественной проблемы самовоспроизводства".

Не вдаваясь в химические, биологические и механические тонкости, фон Нейман постарался представить основные требования, необходимые для самовоспроизводства. Он разработал (но не реализовал) самовоспроизводящуюся автоматическую конструкцию, представляющую собой двухмерную решетку с большим числом отдельных автоматов с 29 состояниями. Каждое следующее состояние отдельного автомата конструкции являлось функцией его текущего состояния и состояний четырех ближайших соседей [Burks, 1970, 1987].

Интересно, что для обеспечения функциональности универсальной машины Тьюринга фон Нейману потребовалось спроектировать самовоспроизводящийся автомат, содержащий около 40 000 клеток. Это универсальное вычислительное устройство было также конструктивно универсальным в смысле его способности чтения входных данных с магнитной ленты, их интерпретации и использования специальной руки для создания описанной на ленте конфигурации в незанятой части клеточного пространства. Поместив на магнитной ленте описание самого автомата, фон Нейман создал самовоспроизводящийся автомат [Arbib, 1966].

Позднее, в 1968 году, Кодд (Codd) уменьшил число состояний самовоспроизводящегося автомата, необходимых для обеспечения вычислительной универсальности, с 29 до 8. Однако для этого ему потребовалось примерно 100 000 000 клеток. После этого Девор (Devore) упростил машину Кодда и разработал автомат, содержащий примерно 87 500 клеток. В последние десятилетия был разработан самовоспроизводящийся автомат, состоящий из 100 клеток по 8 состояний каждая, не обладающий вычислительной универсальностью [Langton, 1986], [Hightower, 1992], [Codd, 1992]. Подробные описания этих

Глава 11. Машинное обучение на основе социальных и эмерджентных принципов 509

научных результатов содержатся в материалах конференций, посвященных проблемам искусственной жизни [Langton, 1989], [Langton и др., 1992].

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

В заключение этого раздела остановимся на двух исследовательских проектах, упомянутых ранее в этой книге: проекте Родни Брукса (Rodney Brooks) из Массачусетского технологического института и Нильса Нильсона (Nils Nilsson) и его студентов из Стэнфорда. Работа Брукса упоминалась в разделе 6.3, а проект Нильсона - при описании вопросов планирования в подразделе 7.4.3. В контексте данной главы эти два описания будут рассмотрены с точки зрения искусственной жизни и феномена эмерджентности.

Родни Брукс [Brooks, 1991a, 1991б] из Массачусетского технологического института построил исследовательскую программу, основываясь на исследовании искусственной жизни, а именно - на интеллектуальном поведении, проявляющемся при взаимодействии простых автономных агентов. Подход Брукса, зачастую называемый "интеллектом без представления", предусматривает различные способы создания искусственного интеллекта. Брукс утверждает следующее.

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

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

Мы следовали такому подходу и построили группы автономных мобильных роботов. При этом мы пришли к неожиданному заключению.

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

Брукс построил серию роботов, способных обнаруживать препятствия и перемещаться вокруг офисов и зданий Массачусетского технологического института. Они могут передвигаться, исследовать и обходить другие объекты. Каждая из этих сущностей основывается на идее Брукса об архитектуре категоризации (subsumption architecture), которая "воплощает фундаментальные идеи декомпозиции поведения на уровни и постепенную структуризацию путем апробации в реальном мире". Интеллект этой системы - это артефакт простой организации и взаимодействия с окружающей средой. Брукс утверждает: "мы конфигурируем конечные автоматы, располагая их по уровням управления. Каждый уровень строится на базе существующих. Нижние уровни никогда не основываются на существовании высоких". Более подробная информация содержится в работах [Brooks, 1987, 1991], [Lewis и Luger, 2000].

Нильс Нильсон со своими студентами из Стэнфорда, в частности Скоттом Бенсоном (Scott Benson), разработал систему телео-реактивного управления агентами. По сравнению с работой

510 Часть IV. Машинное обучение

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

Нильсон и его ученики разработали телео-реактивную программу управления агентом, направляющую агента к цели с учетом постоянно изменяющихся внешних обстоятельств [Nilsson, 1994], [Benson, 1995], [Benson и Nilsson, 1995].

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

Данный подход поддерживает принцип планирования, требующий стереотипной

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

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

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

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

Более подробная информация содержится в работах [Nilsson, 1994], [Benson, 1995], [Benson и Nilsson, 1995], [Klein и др., 2000].

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

И наконец рассмотрим научные результаты, полученные в институте Санта-Фе (Santa Fe Institute).

11.3.3. Пример эмерджентности

В [Crutchfield и Mitchell, 1994] исследована возможность эволюции и взаимодействия простых систем с целью формирования взаимосвязей, обеспечивающих высокоуровневую

Глава 11. Машинное обучение на основе социальных и эмерджентных принципов 511

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

Клеточный автомат состоит из большого числа отдельных ячеек. В каждом из рассматриваемых примеров содержится по 149 клеток. Эти клетки с бинарными состояниями образуют одномерное пространство без глобальной координации. Состояние каждой клетки зависит от ее собственного состояния на предыдущем шаге и состояний двух ее ближайших соседей. В процессе эволюции клеточного автомата формируется двухмерная решетка. Изначально она состоит из N ячеек со случайно сгенерированными состояниями. На рис. 11.14 показаны 149 шагов эволюции клеточного автомата, состоящего из 149 элементов. Время и ячейки нумеруются с 0 до 148. На рис. 11.14 показаны пространственно-временные диаграммы возможного поведения клеточного автомата. На этих диаграммах единичные состояния представлены черными клетками, а нулевые - белыми. Различные правила выбора соседей приводят к различным конфигурациям пространственно-временных диаграмм клеточного автомата.

Опишем набор правил, определяющих активизацию элементов клеточного автомата. На рис. 11.15 показан одномерный клеточный автомат с бинарными состояниями, состоящий из N=11 ячеек. Там же приведены таблица вычисления состояний и правило определения ближайших соседей. Показано изменение решетки за один шаг. Эта решетка на самом деле представляет собой цилиндр, в котором крайние слева и справа ячейки в каждый момент времени считаются соседними (это важно для применения набора правил). Таблица правил реализует правило мажоритарного голосования (majority vote): если большинство из трех ячеек находится в единичном состоянии, то центральная ячейка на следующем шаге переходит в состояние 1. В противном случае она переходит в состояние 0.

512 Часть IV. Машинное обучение

Таблица правил

окрестность: 000 001 010 011 100 101 110 111

результирующее значение: 0 0 0 1 0 1 1 1

Решетка

В работе [Crutchfield и Mitchell, 1994] предпринята попытка построения клеточного автомата, выполняющего следующие коллективные вычисления, получившие название победы большинства (majority wins): если исходная решетка содержит большинство единиц, то на следующем шаге все элементы автомата переходят в состояние 1, в противном случае - в состояние 0. При этом были использованы клеточные автоматы, в которых окрестность состояла из семи ячеек (по три соседа с каждой стороны от центра). Интересным аспектом оказалось сложность построения правила, реализующего такие вычисления. На самом деле в работе [Mitchell и др., 1996] показано, что простое правило мажоритарного голосования для семи соседей не реализует правило победы большинства. Для поиска требуемого правила был использован генетический алгоритм.

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

Таким образом, со временем на основе генетического алгоритма был сформирован набор правил, обеспечивающий победу большинства. Отобранные на основе критерия качества элементы популяции случайным образом комбинировались с помощью скрещивания, а затем каждый потомок с малой вероятностью подвергался мутации. Этот процесс продолжался для ста поколений, при этом для каждого поколения вычислялся критерий качества [Crutchfield и Mitchell, 1994].

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

Глава 11. Машинное обучение на основе социальных и эмерджентных принципов 513

Иногда (как на рис. 11.14, а) эти области заметны невооруженным глазом и представляют собой инвариантные поверхности. Обозначим эти области символом ?, а затем выделим инвариантные элементы, чтобы лучше описать взаимодействия, определяемые пересечением этих областей. В табл. 11.4 описаны три ?-области: ?°, состоящая из нулей, ?1, состоящая из единиц, и ?2, содержащая повторяющиеся фрагменты 10001. На рис. 11.14, а имеются и другие ?-области, но пока они нас не интересуют.

Выделяя инвариантные элементы ?-областей, можно отследить их взаимодействие. В табл. 11.4 описано взаимодействие шести ?-областей, в том числе по границе областей ?1 и ?°. Эта граница между единичной и нулевой областями называется внедренной частицей ? (embedded particle а). В работе [Crutchfield и Mitchell, 1994] утверждается, что внедренные частицы - это основной механизм передачи информации (или сигналов) в больших пространственно-временных областях. При столкновении этих частиц реализуются соответствующие логические операции. Поэтому поведение клеточных автоматов обусловлено информационно-обрабатывающими элементами, представляющими собой наборы областей, их границ, частиц и взаимодействия.

Таблица 11.4. Каталог регулярных областей, частиц (границ областей), их скоростей (в скобках) и взаимодействий, описывающих пространственно-временное поведение клеточного автомата на рис. 11.14, а. Запись р- ?x ?y означает, что р -это частица, формирующая границу между регулярными областями ?x и ?y

На рис. 11.16 показана эмерджентная логика, представленная на рис. 11.14, а. Здесь выделены ?-области с инвариантным содержимым, а также пограничные частицы. Увеличенные фрагменты на рис. 11.16 демонстрируют логику взаимодействия двух внедренных частиц. В правом верхнем углу показано взаимодействие ?+? ® ?, реализующее логику отображения соответствующей конфигурации сигналов ? и sigma в сигнал ?. Ниже показано взаимодействие частиц ?+g® ?. Более полное описание взаимодействия частиц содержится в табл. 11.4.

Итак, важным результатом работы [Crutchfield и Mitchell, 1994] является исследование методов описания эмерджентных вычислений в пространственно распределенных системах, состоящих из локально взаимодействующих клеточных процессоров. Локальное взаимодействие элементов определяет и глобальное. Роль генетических алгоритмов сводится к изучению локальных правил взаимодействия, которые в результате приводят к обработке информации на больших пространственно-временных интервалах. В работе [Crutchfield и Mitchell, 1994] для характеристики пространственно-временных отношений использованы идеи теории формальных языков.

514 Часть IV. Машинное обучение

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

Значение работы [Crutchfield и Mitchell, 1994] состоит в том, что в ней с помощью генетических алгоритмов продемонстрировано эмерджентное высокоуровневое поведение клеточного автомата. Более того, авторы предложили вычислительные средства описания инвариантности, построенные на основе теории формальных языков. Продолжение исследований даст возможность изучить природу сложности: определить характеристики жизни и понять принципы формирования родов, видов и экосистем.

11.4. Резюме и дополнительная литература

Основоположником развития генетических алгоритмов и биологического обучения стал Джон Холланд (John Holland) [Holland, 1975,1986]. В последней работе вводится понятие системы классификации. Анализ генетических систем содержится в [Forrest, 1990], [Mitchell, 1996], [Forrest и Mitchell, 1993a, 19936]. Формальный анализ генетических алгоритмов и обучения проводится также в [Goldberg, 1989], [Mitchell, 1996], [Koza, 1992,1994].

Как отмечено выше, в работе [Holland, 1986] впервые вводится понятие системы классификации. Классификаторы позволяют определить общий подход к обучению. Аналогичные идеи развиваются в [Rosenbloom и Newell, 1987] и [Rosenbloom и др., 1993].

Джон Коза (John Koza) - это основной исследователь в области генетического программирования [Koza, 1992,1994]. Описанный в подразделе 11.2.2 пример использования генетических алгоритмов для изучения третьего закона Кеплера предложен в [Mitchell, 1996].

515

Игра "Жизнь" изначально была создана математиком Джоном Хортоном Конвеем (John Horton Conway), однако приобрела широкую популярность после ее обсуждения в журнале Scientific American. Исследование вычислительной мощности конечных автоматов уходит корнями к первым цифровым компьютерам. Большой вклад в эти исследования внес Джон фон Нейман, который фактически впервые показал, что вычислительная мощность конечного автомата соответствует универсальной машине Тьюринга. Большинство его ранних результатов представлены в работах [Burks, 1966,1970 и 1987]. Другие исследователи [Hightower, 1992], [Koza, 1992] описали, как на основе этих ранних работ по конечным автоматам строится модель искусственной жизни. Вопросы искусственной жизни исследованы также в работах [Langton, 1986], [Ackley и др., 1992]. Труды конференций, посвященных проблемам искусственной жизни, собраны в [Langton, 1989, 1990].

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

Кратко описанная в разделе 11.3 концепция агентного обучения изложена в работах [Brooks, 1986, 1987, 1991а, 19916], [Nilsson, 1994], [Benson и др., 1995]. В работах [Maes, 1989], [Maes, 1990] предложена модель распределенной обработки информации в сетях, которая получила свое дальнейшее развитие в работе [Hayes-Roth и др., 1993]. Результаты, описанные в подразделе 11.3.3, базируются на работе [Crutchfield и Mitchell, 1994].

11.5. Упражнения

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

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

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

Вернемся к задаче построения конъюнктивной нормальной формы, описанной в

подразделе 11.1.3. В чем состоит роль количества дизъюнктов, определяющих построение конъюнктивной нормальной формы в пространстве решений? Укажите другие возможные представления и генетические операторы для этой задачи. Можно ли выбрать другую меру качества?

Постройте генетический алгоритм для решения задачи представимости в конъюнктивной нормальной форме.

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

коммивояжера, описанной в подразделе 11.1.3. Определите другие возможные генетические операторы и меры качества для этой задачи.

Постройте генетический алгоритм поиска решения задачи коммивояжера.

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

Познакомьтесь с теоремой схем Холланда [Mitchell, 1996], [Koza, 1992]. Как теория

схем описывает эволюцию пространства решений при использовании генетических

516

алгоритмов? Что утверждает эта теория относительно задач, не подлежащих кодированию битовыми строками?

9. Как алгоритм "пожарной цепочки" [Holland, 1986] связан с методом обратного распространения ошибки?

Напишите программу, решающую задачу моделирования третьего закона Кеплера,

описанную в подразделе 11.2.2.

Сформулируйте ограничения (упомянутые в подразделе 11.2.2) по использованию

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

Познакомьтесь с первыми описаниями игры "Жизнь" в журнале Scientific American.

Назовите другие структуры искусственной жизни, подобные описанному в подразделе 11.3.1 планеру.

Напишите программу моделирования искусственной жизни, реализующую функциональность, показанную на рис. 11.10-11.13.

В разделе 11.3 упоминаются исследования, ориентированные на агентов. Ознакомьтесь с публикациями по этим вопросам.

Определите роль индуктивного порога в выборе представления стратегий поиска и

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

Изучите глубже вопросы эволюции и эмерджентности. Прочтите и обсудите работы

[Dennett, 1995], [Gould, 1996].

517