Часть 16.

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

234591876.

Поскольку города 4, 6, 5 и 7 не учитываются (они уже входят в состав первого потомка), получается укороченный ряд 2, 3, 9, 1, 8, который и подставляется в cl с сохранени­ем порядка следования этих городов в р2:

с1=(239|4657|18). Аналогично получим второй потомок с2=(392|1876|45).

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

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

с1=(239|4657|18)

после инвертирования его средней части примет вид с1=(239|7564|18).

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

11.1.4. Обсуждение генетического алгоритма

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

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

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

Завершая обсуждение способа представления данных, рассмотрим проблему "естественности" такого представления. В качестве простого, но несколько искусственного, примера рассмотрим задачу выделения чисел 6, 7, 8 и 9. Естественным представлением, обеспечивающим сортировку данных, является обычное целочисленное описание, поскольку среди десяти цифр каждая следующая на 1 больше предыдущей. При переходе к двоичному описанию эта естественность исчезает. Рассмотрим битовое представление чисел 6,7,8 и 9:

01100111 1000 1001.

Заметим, что числа 6 и 7, а также 8 и 9 отличаются друг от друга на один бит. Однако числа 7 и 8 не имеют между собой ничего общего! Это свойство представления может вы­звать большие проблемы при решении задач, требующих систематизации этих образов. Для решения проблемы неоднородного представления используется множество приемов, получивших общее название кодирования Грея (gray coding). Например, код Грея для первых шестнадцати двоичных чисел приводится в табл. 11.1. Заметим, что здесь каждое число от­личается от своих соседей ровно на один бит. Обычно при использовании кодирования Грея вместо обычного двоичного представления переходы между состояниями при реали­зации генетических операторов являются более естественными и гладкими.

Важным преимуществом генетических алгоритмов является параллельная природа поиска. Они реализуют одну из мощных форм поиска экстремума, поддерживающую несколько решений. На рис. 11.2, взятом из работы [Holland, 1986], показано, как

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

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

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

Еще одним отличием эвристического поиска в пространстве состояний, описанного в главе 4, от генетических алгоритмов является анализ различия между текущим и целе­вым состояниями. Такая информация учитывается в алгоритме А* (раздел 4.2), требующем оценки "усилий" для перехода из текущего состояния в целевое. Для работы генетиче­ских алгоритмов такая мера не нужна. Просто каждое поколение потенциальных решений оценивается с помощью некоторого критерия качества. Не требуется также строгая систе­матизация последующих состояний, как при поиске в пространстве состояний. Просто формируется поколение решений-кандидатов, каждое из которых может внести свой вклад в получение новых возможных решений в процессе параллельного поиска.

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

строки вида 101 #_ _ _ _. Если родительское решение не соответствует критерию качества,

то в процессе работы алгоритма не будут рассматриваться и все его потенциальные потомки.

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

Поскольку генетические алгоритмы все шире применяются для решения прикладных задач и математического моделирования, в последнее время повышается интерес к осмыслению их теоретических основ. Естественно, возникают следующие вопросы.

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

Для каких типов задач они работают плохо?

Что означает высокая и низкая эффективность генетического алгоритма для решения некоторого типа задач?

Существуют ли законы, описывающие поведение генетических алгоритмов на

макроуровне? В частности, можно ли спрогнозировать изменения значений критерия качества для элементов популяции?

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

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

Многие из этих вопросов выходят за рамки тематики данной книги. В работе [Mitchell, 1996] указано, что в теоретическом осмыслении генетических алгоритмов пока еще больше открытых вопросов, чем приемлемых ответов. Тем не менее с момента появления генетических алгоритмов исследователи пытаются понять принципы их работы [Holland, 1975]. И хотя многие вопросы, как и приведенные выше, относятся к макроуровню, их анализ начинается с микроуровня битового представления.

В [Holland, 1975] вводится понятие схемы (schema) как общего шаблона и строительного блока решения. Схема- это шаблон битовых строк, описываемый символами 1, О и #. Например, схема 10##01 представляет семейство шестибитовых строк, начинаю­щихся с фрагмента 10 и завершающихся символами 01. Поскольку центральный фраг­мент ## описывает четыре возможные комбинации битов, 00, 01, 10, 11, то вся схема представляет четыре битовые строки, состоящие из 1 и 0. Традиционно считается, что каждая схема описывает гиперплоскость [Goldberg, 1989]. В этом примере данная гипер­плоскость пересекает множество всех возможных шестибитовых представлений. Цен­тральным моментом традиционной теории генетических алгоритмов является утвержде­ние, что подобные схемы - это строительные блоки семейств решений. Генетические операторы скрещивания и мутации оперируют такими схемами в процессе поиска по­тенциальных решений. Эти операции описываются теоремой о схемах [Holland, 1975], [Goldberg, 1989]. По Холланду, для повышения производительности в некоторой среде адаптивная система должна идентифицировать, проверить и реализовать некоторые структурные свойства, формализуемые с помощью схем.

Анализ схем Холланда предполагает, что алгоритм выбора по критерию качества сводится к поиску подмножеств в пространстве поиска, наилучшим образом удовлетворяющих данному критерию. Следовательно, эти подмножества описываются схемами, для которых значение критерия качества выше среднего. При выполнении генетических операторов скрещивания строительные блоки с высоким показателем качества склады­ваются вместе и формируют "улучшенные" строки. Мутации позволяют гарантировать, что генетические особенности не будут утеряны в процессе поиска, т.е. эти операторы обеспечивают переход к новым областям поверхности поиска. Таким образом, генетиче­ские алгоритмы можно рассматривать как некое обобщение процесса поиска с

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

сохранением важных генетических свойств. Холланд изначально анализировал генетические ал­горитмы на битовом уровне. Более современные работы распространяют результаты это­го анализа на другие схемы представления [Goldberg, 1989]. В следующем разделе гене­тические алгоритмы будут применены к более сложным представлениям.

11.2. Системы классификации и генетическое программирование

Первые генетические алгоритмы почти целиком базировались на низкоуровневом представлении, в частности, битовых строках {0, 1, #}. Помимо того что битовые строки являются естественным представлением для реализации генетических операторов, они обеспечивают для генетических алгоритмов столь же высокую производительность, как и другие несимвольные подходы, в том числе нейросетевые. Однако существуют за­дачи, например, проблема коммивояжера, для которых естественным является кодирова­ние на более высоком уровне представления. При глубоком исследовании может возник­нуть вопрос о реализации генетических алгоритмов для таких высокоуровневых пред­ставлений, как правила вывода или фрагменты программного кода. Важным аспектом этих представлений является возможность комбинирования таких фрагментов высоко­уровневых знаний, как цепочки правил вывода или вызовы функций.

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

11.2.1. Системы классификации

В [Holland, 1986] разработаны проблемно-ориентированные архитектуры, получившие название систем классификации (classifier system), в которых генетическое обуче­ние применяется к правилам логического вывода. Система классификации включает стандартные элементы системы вывода (рис. 11.3): правила вывода (называемые здесь классификаторами), рабочую память, входные датчики (или декодеры) и выходные эле­менты (эффекторы). Отличительной особенностью системы классификации является конкурентный подход к разрешению конфликтов, применение генетических алгоритмов для обучения и алгоритма "пожарной цепочки" (bucket brigade algorithm) для распреде­ления поощрений и наказаний в процессе обучения. Обратная связь со внешней средой дает возможность оценить качество классификаторовкандидатов, что необходимо для реализации генетического обучения. Система классификации, показанная на рис. 11.3, включает следующие основные компоненты.

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

Рис. 11.3. Взаимодействие системы классификации с внешней средой

Детекторы входящих сообщений от внешней среды.

Детекторы обратных связей со внешней средой.

Эффекторы, передающие результаты применения правил во внешнюю среду.

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

Рабочая память для правил классификации, в которой результаты правил выбора

интегрированы с входной информацией.

Набор генетических операторов для модификации правил вывода.

Система для предоставления кредита правилам, участвующим в выполнении успешных действий.

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

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

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

двумя способами. Первый способ состоит в использовании системы поощрений, настраивающей меру качества правил классификации за счет усиления полезных пра­вил и ослабления действия ошибочных. Алгоритм распределения кредитов передает часть вознаграждения или штрафа каждому правилу классификации, принимавшему участие в формировании окончательного правила. Такое распределение различных вознаграждений между взаимодействующими классификаторами зачастую реализу­ется с помощью алгоритма "пожарной цепочки". Этот алгоритм решает проблему распределения кредитов и штрафов для систем, выход которых является результа­том последовательного применения набора правил. Как распределить штрафы меж­ду правилами этой цепочки в случае ошибки на выходе? Какое из правил цепочки является источником ошибки: последнее или одно из предыдущих? Алгоритм "пожарной цепочки" позволяет распределить кредиты и штрафы между правилами этой последовательности в зависимости от вклада каждого правила в окончательное решение. Аналогичное распределение поощрений и штрафов на основе ошибки на выходе обеспечивает алгоритм обратного распространения, описанный в разде­ле 10.3. Более подробная информация об этом содержится в [Holland, 1986].

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

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

Взаимодействие этих компонентов системы классификации можно продемонстрировать на простом примере. Предположим, набор подлежащих классификации объек­тов определяется шестью атрибутами (условиями с1, с2, ..., с6). Допустим также, что каждый из этих атрибутов может принимать 5 различных значений. И хотя каждый атри­бут имеет свой физический смысл (например, параметр с3 описывает цвет, а с5 - пого­ду), без потери общности допустимые значения всех атрибутов можно описать целыми числами {1, 2,..., 5}. Предположим, согласно правилам вывода объекты разбиваются на 4 класса: А1, А2, A3, АА.

Таким образом, каждый классификатор можно описать в виде соотношения

(с1, с2, сЗ, с4, с5, с6)?Ai, где i=1, 2, 3, 4,

где каждое из условий с/ принимает значение из диапазона {1, 2, ..., 5} соответствующего атрибута. Обычно условию может соответствовать и произвольное значение # каждого атрибута. В правой части соотношения выражение Ai обозначает один из клас­сов A1, А2, A3 или А4. В табл. 11.2 приводится набор классификаторов. Обратите вни­мание на то, что несколько различных условных шаблонов могут соответствовать од­ному классу, как в правилах 1 и 2, либо два одинаковых шаблона могут соответство­вать различным классам.

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

Таблица 11.2. Наборы условий для различных классов

Условие (атрибуты) Действие (класс) Номер правила

(1###1#) ?A1 1.

(2##3##) ?A1 2

(##43##) ?A2 3

(1#####) ?A2 4

(##43##) ?A3 5

Как показано выше, система классификации - это еще одна форма вездесущих систем, основанных на правилах логического вывода. Единственным отличительным свойством правил классификации, использованных в приведенном примере, является применение строк цифр и символов # для представления шаблонов условий. Такое представление условий обеспечивает применение генетических алгоритмов в правилах логического вывода. Далее будет исследован вопрос генетического обучения в системах классификации.

Чтобы упростить изложение, будем рассматривать обучение системы только для класса А\. Не принимая во внимание другие классы, присвоим шаблонам условий значение 1 или 0 в зависимости от соответствия классу A1. Заметим, что это упрощение не ограничивает общности рассуждения, поскольку эти выкладки можно распространить на случай обучения для не­скольких классов. Для этого достаточно ввести вектор, соответствующий конкретному услов­ному шаблону. Например, классификатор из табл. 11.2 можно описать в виде

(1###1#)?(1000), (2##3##)?(1000), (1#####)?(0100), (##43##)?(0110).

Последняя строка в этом примере соответствует правилам классификации для классов А2 и A3, но не А\ или А4. Заменяя 0 или 1 подобными векторными представлениями классов, можно оценить эффективность правила для классификации на несколько классов.

Для определения корректности классификации будем использовать правила из табл. 11.2. А именно, будем рассматривать их в качестве учителя для оценки качества правил в системе классификации. Как в большинстве генетических систем обучения, выберем случайным образом исходную популяцию правил. Каждому шаблону условий со­поставим параметр качества (fitness) или силы (strength) (вещественное число из диапа­зона от 0,0 до 1,0). Этот параметр силы s будем вычислять на основе качества каждого родительского правила с учетом предыстории.

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

(###21#)?1 s=0,6,

(##3##5)?0 s=0,5,

(21####)?1 s=0,4,

(#4###2)?0 s=0,23.

Допустим, из среды поступило новое входное сообщение (1 4 3 2 1 5), и учитель (на основе первого правила из табл. 11.2) классифицировал этот вектор как положительный

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

пример для класса A1. Посмотрим, что происходит при передаче этого образа в рабочую память при попытке его классификации с помощью 4 правил-кандидатов. Этот образ соответствует правилам 1 и 2. Разрешение конфликта между подходящими правилами вы­полняется на основе конкуренции. В нашем примере степень соответствия каждого пра­вила вычисляется как сумма произведений степеней соответствия каждого из атрибутов и меры качества данного правила. Неопределенному атрибуту # соответствует значение 0,5, а при точном соответствии атрибута ему присваивается степень 1,0. Для нормировки полученное значение делится на длину входного вектора. Поскольку первый классификатор для данного входного вектора дает два точных соответствия и 4 неопределенных атрибута, об­щая степень его соответствия входному вектору составляет ((4*0,5+2*1)*0,6)/6=0,4. Для второго классификатора тоже имеется 2 точных соответствия и 4 неопределенных атрибута, поэтому его степень соответствия составляет 0,33. В нашем примере по принципу кон­куренции побеждает классификатор с максимальной степенью соответствия, но в более сложных задачах желательно учитывать некоторый порог.

Таким образом, победило первое правило, в соответствии с которым предъявленный образ относится к классу А1. Поскольку это действие корректно, мера качества первого правила увеличивается и принимает новое значение, приближенное к 1. Если бы результат выполнения этого правила оказался некорректным, его мера качества была бы уменьшена. Если для получения результата в системе многократно выполняется некото­рый набор правил, то определенную долю подкрепления должны получить все правила, участвующие в получении результата. Точная процедура пересчета меры качества опре­деляется в зависимости от системы и может оказаться очень сложной. Она может стро­иться на основе алгоритма "пожарной цепочки" или другого метода распределения кре­дитов. Более подробная информация по этому вопросу содержится в [Holland, 1986].

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

(###2|1#)?1 s=0,6,

(##3#|#5)?0 s=0,5,

получим потомки

(##3#|1#)?0 s=0,53,

(###2|#5)?1 s=0,57.

Мера качества каждого потомка - это взвешенная функция показателей качества их родителей. Весовые коэффициенты определяются местоположением точки скрещивания. Первый потомок получил 1/3 информации от классификатора с мерой качества 0,6 и 2/3 - от классификатора с мерой качества 0,5. Поэтому его мера качества составляет (1/3*0,6)+(2/3*0,5)=0,53. С помощью аналогичных рассуждений выясним, что мера качества второго потомка равна 0,57. Результат выполнения правила (значение 0 или 1) оп­ределяется соответствием большинства атрибутов. В типичных системах классификации эти два новых правила, наряду с их родителями, входят в набор классификаторов, с ко­торыми работает система на следующем этапе.

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

Можно определить и оператор мутации. Простая мутация заключается в случайной замене любого значения атрибута произвольным значением из допустимого диапазона. Например, 5 можно изменить на 1, 2, 3, 4 или #. Как указывалось при описании генетических алгоритмов, операторы мутации призваны внести элемент случайности в поиск классификатора, в то время как скрещивание позволяет сохранить удачные фрагменты данных из родительских шаблонов в их потомках.

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

Описанный пример взят из работы [Holland, 1986], выполненной в университете шта­та Мичиган. Такой подход можно рассматривать как численную модель познания, в которой знания (классификаторы) обучаемой сущности формируются в процессе взаимо­действия с внешней средой и модифицируются со временем. При этом оценивается об­щая работа всей системы, а не качество отдельного классификатора. В работе [Michalski и др., 1983], выполненной в университете Питтсбурга (Pittsburg), предложен альтерна­тивный подход к построению систем классификации, в котором при создании нового по­коления классификаторов основное внимание уделяется отдельным правилам. Такой подход реализует предложенную Михальски (Michalski) модель индуктивного обучения.

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

11.2.2. Программирование с использованием генетических операторов

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

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

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

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

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

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

Итак, генетическое программирование включает следующие шесть компонентов, многие из которых напоминают составные части генетических алгоритмов.

Набор структур, подвергающихся трансформации с помощью генетических операторов.

Набор исходных структур, соответствующих предметной области.

Мера качества для оценки этих структур, выбираемая с учетом предметной области.

Набор генетических операторов для трансформации структур.

Описания параметров и состояний элементов каждого поколения.

Набор условий останова.

В следующих разделах эти компоненты будут рассмотрены более подробно.

В генетическом программировании операции выполняются над иерархически организованными программными модулями. Основным средством представления компонентов программных языков был и остается язык LISP. В [Koza, 1992] программные фрагменты представлены в виде символьных выражений на языке LISP, или s-выражений. Описание s-выражений, их естественное представление в виде структур деревьев, а также эффек­тивность такого представления более подробно рассматриваются в разделе 15.1.

Генетические операторы оперируют s-выражениями. В частности, они отображают древовидные структуры s-выражений (фрагменты программ на языке LISP) в новые деревья (другие программы на LISP). Хотя эти s-выражения появились еще в работе [Koza, 1992], другие исследователи применяли этот подход к различным парадигмам програм­мирования и в более позднее время.

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

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

некоторого множества задач, необходимо сначала проанализировать возможные конечные значе­ния составных элементов и самого решения, а также функции, необходимые для получе­ния этих конечных значений. В [Koza, 1992] отмечено, что "...при использовании генети­ческого программирования необходимо знать..., что некоторая композиция функций и конечных значений приводит к решению проблемы".

Чтобы инициализировать структуры, модифицируемые с помощью генетических операторов, необходимо создать два множества: множество функций F и множество конеч­ных значений Г, требуемых для данной предметной области. Множество F может состо­ять из простых операций {+, -, *, /} или включать более сложные функции, такие как sin(x), cos(x) и матричные операции. Множество Т может содержать целые или вещест­венные числа, матрицы или более сложные выражения. Множество символов Г должно быть замкнуто относительно функций из F.

Затем генерируется популяция исходных "программ" путем случайного выбора элементов из множеств F и Т. Например, выбирая элемент из множества Т, мы получаем вырожденное дерево, состоящее из одного корневого элемента. Более интересной является ситуация, когда сначала выбирается элемент из F, скажем, +. В этом случае получа­ется корневой узел дерева с двумя потенциальными потомками. Допустим, после этого в качестве первого потомка инициализатор выбирает из F операцию * (с двумя потенци­альными потомками), а в качестве второго - конечное значение 6 из множества Т. Сле­дующими случайно выбранными элементами могут стать конечное значение 8 и функция + из F. Допустим, процедура завершается выбором значений 5 и 7 из множества Т.

Случайно сгенерированная таким образом программа представлена на рис. 11.4. На рис. 11.4, а показано дерево после первого выбора операции +, на рис. 11.4, б- после выбора конечного значения 6, а на рис. 11.4, в - окончательная программа. Для инициализации процесса генетического программирования формируется целое поколение подоб­ных программ. Для контроля размерности этой популяции можно применять ограничения, например, на максимальную глубину программ. Описание подобных ограничений, а также различных методов генерирования исходных популяций содержится в [Koza, 1992].

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

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

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

fitness) учитывает различие между результатом выполнения программы и требуемым решением реальной задачи. Следовательно, линейный критерий качества можно рассматривать как сумму ошибок при наборе задач. Возможны также другие меры качества. Нормализованный критерий качества подразумевает деление общего критерия качества на количество всех воз­можных ошибок. Следовательно, нормализованный критерий качества может изменяться в диапазоне от 0 до 1. Преимущество нормализации проявляется при работе с большими попу­ляциями программ. Мера качества учитывает размер программы, например, можно поощрять создание компактных программ небольшого размера.

Генетические операторы в пространстве программ содержат как преобразование самого дерева, так и обмен фрагментами между различными деревьями. В [Koza, 1992] описаны основные преобразования, получившие название воспроизводства (reproduction) и скрещивания (crossover). Воспроизводство - это выбор программ текущего поколения и копирование их (без изменений) в популяцию следующего поколения. Скрещивание подразумевает обмен поддеревьев двух существующих программ. Допустим, существуют две родительские про­граммы, представленные на рис. 11.5, в которых символом | показаны точки скрещивания. Дочерние деревья, полученные в результате скрещивания, изображены на рис. 11.6. Скрещи­вание также можно использовать для преобразования одного родительского дерева путем пе­ремены мест в двух его поддеревьях. При случайном выборе точки скрещивания два иден­тичных родительских дерева могут дать различное потомство. Точкой скрещивания также может служить корневой узел программы.

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

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

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