Постановка задачи обучения по прецедентам такова. Имеется множество объектов (ситуаций) и множество возможных ответов. Между объектами и ответами существует некоторая зависимость, которая нам неизвестна. Мы располагаем совокупностью прецедентов – пар "объект, ответ", называемой обучающей выборкой. На этой основе требуется восстановить зависимость, то есть построить алгоритм, составляющими которого являются
Ниже рассматривается применение генетических алгоритмов к автоматизации вывода системы продукций, которые применяются также и в экспертных системах. Изложены классические подходы:1) Мичиганский, где в качестве особи используется отдельная
Проблема состоит в том, чтобы создать систему, которая изучит концепции, то есть, определит решающие правила для всех положительных и отрицательных примеров. Мы можем оценивать и сравнивать потенциальные решения в терминах значений ошибок и сложности построенных правил. Система должна быть способна выполнить классификацию заранее неизвестных примеров, или выполнять (возможно, более чем одну) классификацию частично определенных описаний.
При
Исторически Дж. Холландом [1], основоположником ГА, первым по времени был разработан Мичигангский подход, но в настоящее время на практике более распространен Питтсбургский подход [2,3], который мы и рассмотрим.
Здесь каждая особь в популяции представляет целый набор правил (а не отдельное правило, как в альтернативном подходе). Как обычно, особи конкурируют между собой, при этом слабые особи умирают, сильные живут и воспроизводятся. Здесь при реализации ГА часто используется пропорциональный отбор родителей, а
Рассмотрим один из возможных способов кодирования правила [4] на примере
Пусть переменная $$X$$ для определенности принимает три значения $$x_1,x_2,x_3$$, а переменная $$Y$$– два значения $$y_1,y_2$$. Тогда для кодирования значений переменной $$X$$ будем использовать три бита, соответственно для переменной $$Y$$ два бита (по одному биту для каждого возможного значения). При этом значение 1 в соответствующей позиции означает, что переменная может принимать соответствующее значение. Например, код (010) для переменной $$X$$ означает, что эта переменная имеет значение $$x_2$$. Более того, этот способ кодирования позволяет описывать ситуации, когда переменная может принимать несколько значений [4]. Так код (011) для той же переменной означает, что переменная может принимать значения $$x_2,x_3$$. Отметим, что код (111) соответствует наименьшим ограничениям, когда переменная может принимать любые (из допустимых) значения. Тогда, например, гипотеза (концепция) $$if\ (X=x_1\vee X=x_2)\ then\ C=TRUE$$ кодируется следующим образом (110 1). Данный метод кодирования позволяет легко учитывать ограничения на значения нескольких атрибутов (переменных) путем конкатенации (сцепления) двоичных кодов этих переменных. Так, например, гипотеза $$if\ (X=x_1\vee X=x_3)\(Y=y_1\vee Y=y_2)\ then\ C=TRUE$$ кодируется двоичной строкой (101 11 1). Следует отметить, что двоичная строка, представляющая некоторое правило–продукцию, содержит для каждого атрибута (переменной) соответствующую подстроку (даже в том случае, когда на ее значения не накладываются никаких ограничений – атрибут может принимать любые значения). Это определяет фиксированный размер двоичной строки для кодирования правила–продукции, в котором под кодирование значений каждого атрибута выделяется поле в определенных позициях.
Данный метод кодирования легко распространяется на множество
можно представить следующей двоичной строкой (001 11 1 111 01 0 110 10 1) в соответствии с тремя правилами $$1:x\ y\ c,\ 2:x\ y\ c,\ 3:x\ y\ c$$.
При Питтсбургском подходе одна двоичная строка представляет (как и в классическом ГА) потенциальное решение – множество продукций. В этом случае популяция, как обычно, содержит множество особей - потенциальных решений (систем продукций). Далее для представленного метода кодирования
При рекомбинации применяется двухточечный
Допустим, что для первого родителя выбраны точки кроссинговера 2, 10, что соответствует $$d_1=2$$ (номер позиции от левого края правила с первой точкой кроссинговера) и $$d_2=2$$ (номер позиции от правого края правила со второй точкой кроссинговера) – это показано ниже квадратными скобками [4]:
Тогда возможны следующие варианты выбора пар точек кроссинговера во втором родителе: (2,4), (2,10), (8,10). При этом первая точка кроссинговера попадает между вторым и третьим разрядами двоичного кода переменной $$x$$, а вторая точка – между первым и вторым разрядами кода переменной $$y$$. Для определенности возьмем пару точек (2,4), что дает
Далее, как обычно, в двухточечном кроссинговере выполняется обмен фрагментами двоичных кодов между точками кроссинговера (скобками [ и ]), что дает следующих потомков (две новых систем продукций):
Следует отметить, что в результате выполнения такого кроссинговера число правил в системе продукций может изменяться.
Далее к полученным потомкам с небольшой вероятностью применяется один из следующих
Следует особо отметить, что при Питтсбургском подходе проблема построения фитнесс-функции решается гораздо проще, чем в Мичиганском, поскольку здесь оценивается вся система продукций в целом. Одним из самых распространенных видов фитнесс-функции [2] является следующий:
$$F(h)=(y(h))^2$$где $$y(h)$$– процент правильно классифицируемых примеров обучающей выборки с помощью гипотезы (системы продукций) $$h$$. При этом каждое потенциальное решение – система продукций оценивается на обучающей выборке "естественным образом".
Здесь системы классификации используют структуру, в которой популяция правил закодирована в строки битов и развивается и совершенствуется на основе меняющихся входных данных, поступающих из внешней среды [1,2]. Система "обучается" на представленных входных данных по методу обучения с учителем, где для каждого набора входных данных известны правильные значения выходов. Правила в системе классификации формируют популяцию из особей, развивающихся во времени. Система классификации, представленная на рис. 7.1 состоит из следующих компонентов:
Среда (внешнее окружение системы классификации) посылает сообщение, которое принимается датчиками системы классификации и помещается во входной список сообщений. Датчики декодируют сообщение в одно или более (декодированных) сообщений и размещают его во внутренний список сообщений. Эти сообщения активизируют классификаторы. Наиболее сильные из активизированных классификаторов размещают сообщения в списке внутренних сообщений. Эти новые сообщения могут активизировать другие классификаторы, или послать некоторые сообщения в выходной список сообщений. В последнем случае, исполнительные элементы системы классификации кодируют их в выходные сообщения, которые возвращаются во внешнюю среду. Среда оценивает действие системы посредством обратной связи с помощью "бригадного алгоритма", который модифицирует "силу" классификаторов [1,2].
Далее рассмотрим более подробно некоторые из этих действий. Сначала определим некоторые базовые понятия. Каждый классификатор состоит из двух частей: 1-я часть условие, и 2-я сообщение. "Условная часть" правила представляет собой конечную строку символов из некоторого алфавита. Здесь алфавит включает "неопределенный" символ "*". Часть, представляющая сообщение, является конечной строкой из символов того же самого алфавита, кроме символа "*".
(рис 7.1) Система классификации.
Далее мы будем использовать (шуточный) пример классификации роботов [5]. Пусть каждый робот описывается шестью атрибутами, которые могут принимать следующие значения, представленные в таблице 7.1.
| Атрибуты | Значение Атрибутов: |
|---|---|
| Форма Головы | Округлая, Квадратная, Восьмиугольная |
| Форма Тела | Округлая, Квадратная, Восьмиугольная |
| Улыбка | Да, Нет |
| Держит в руках | Сабля, Шарик, Флаг |
| Цвет куртки | Белый, Жёлтый, Зелёный, Синий, Красный |
| Шарф | Да, Нет |
Здесь жирные буквы используются для идентификации атрибутов и их значений. Например, (Ц=Ж) означает "Цвет_Куртки = Жёлтый". Приведем примеры описаний концепций $$C_i$$ (классов или видов) роботов:
Здесь каждая концепция $$C_i$$ описана в терминах этих шести атрибутов и их значений. Формальное описание концепций представлено на языке $$VL_1$$ (упрощенная версия распространенного языка Variable Valued Logic Systems), описывающем входные события в пространстве атрибутов.
Описание концепции $$C$$ представляется в виде дизъюнкции комплексов
$$C_1\vee\dots\vee C_k\Rightarrow C$$При этом каждый комплекс $$C_i$$ выражен посредством конъюнкции селекторов, которые являются триплетами (например, (Ц=Ж) для "Цвет куртки = Желтый").
Концепции $$C_1-C_5$$ могут быть выражены следующим образом:
Каждому классификатору приписывается "сила", характеризующая его "важность"."Сила" важна в процессе "торговли", где классификаторы конкурируют за право послать сообщения. Мы можем представить решающее правило с помощью одного или более классификаторов. Каждый классификатор имеет следующую форму $$(p_1,p_2,p_3,p_4,p_5,p_6):d$$, где $$p_i$$ обозначает значение $$i$$-го атрибута $$(1\le i\le 6)$$ для областей значений, описанных выше.
Например, классификатор, (О * * * Б *):$$C_1$$ представляет следующее правило: "Если голова Округлая и куртка Белая, то робот соответствует концепции $$C_1$$". Здесь концепция фактически соответствует классу, к которому принадлежит робот.
Чтобы упростить пример, предположим, что система обучается единственной концепции $$C_1$$. Но рассматриваемый метод может быть легко обобщен для обработки множественных концепций. В случае одной концепции каждый классификатор имеет следующую форму $$(p_1,p_2,p_3,p_4,p_5,p_6):d$$, где $$d=1$$ (принадлежность к концепции $$C_1$$) или $$d=0$$ (в противном случае).
Предположим, что на некоторой стадии процесса обучения в системе имеется небольшая (случайная) популяция классификаторов $$q$$. При этом каждый классификатор имеет свою силу $$s$$. Пусть для определенности в нашем примере на текущий момент присутствуют следующие классификаторы:
Предположим далее, что из внешней среды поступает новое входное сообщение $$m:$$(ООДСБН). Оно представляет описание одного робота с округлой головой (О), округлым телом (О), который улыбается (Д), держит саблю (С) и одет в белую (Б) куртку без шарфа (Н). Очевидно, этот робот вписывается (соответствует) в концепцию $$C_1$$ из-за его округлой головы и белой куртки.
Анализ показывает, что это сообщение активизирует три классификатора: $$q_1,q_2\ и\ q_4$$. Эти классификаторы "торгуются": предложение каждого классификатора в торге пропорционально его силе $$(bid_i=b*s_i)$$. Самый сильный классификатор $$q_1$$ выигрывает и посылает свое сообщение. Так как сообщение дает правильную классификацию, этот классификатор получает премию $$r>0$$. Тогда сила классификатора становится равной:
$$s_1:=s_1-bid_1+r$$Если бы сообщение дало неправильный ответ, "премия" r была бы отрицательна. Конкретно для коэффициентов $$b = 0.2$$ и $$r = 4.0$$, новая сила классификатора $$q_1$$ составляет $$s_1 = 12.3 - 2.46 +4.0 =13.84$$.
Одним из основных параметров системы классификаторов является период ГА $$t_{ga}$$, который определяет число временных шагов (число циклов описанных выше) между запросами ГА. Конечно, $$t_{ga}$$ может быть константой, генерируемой произвольно (со средним значением, равным $$t_{ga}$$), или вообще не определенно, и этот выбор может быть сделан, исходя из характеристик работы системы. Так или иначе, предположим, что настало время для применения генетического алгоритма в классификации.
В данном подходе сила классификаторов рассматривается в качестве значений фитнесс-функции и при выборе родителей здесь используется пропорциональный отбор (колесо рулетки).
Далее используются стандартные генетические операторы: репродукция, мутация и кроссинговер. Однако их необходимо несколько модифицировать. Рассмотрим, например, первый атрибут. Его областью (форма головы) является {О, К, В, *}. Поэтому, при мутации, мы заменяем изменяемое значение на любое из трех других значений (с равной вероятностью):
После выполнения
Случайным образом генерируется номер позиции для кроссинговера (например, как показано, после третьего символа), и получаем следующий результат (особи - потомки):
При кроссинговере сила полученных классификаторов определяется как среднее значение (возможно взвешенное) от значений силы родителей.
Далее процесс обучения продолжается: принимаются новые положительные и отрицательные сообщения из внешней среды, производится "торг" и модифицируются "силы" классификаторов. Можно показать, что в конечном счете популяция классификаторов сходится к некоторому числу сильных особей (классификаторов), например,
Приведенный пример является, конечно, искусственным и предназначен для иллюстрации основных принципов обучения, используемых в Мичиганском подходе. Следует отметить, однако, что при "торге" в примере использовалась самая простая система оценок эффективности классификаторов. Существуют и более сложные (и эффективные) методы оценки классификаторов.
В настоящее время Мичиганский подход к машинному обучению, который позволяет проводить обучение в on-line режиме, получил наибольшее развитие с 1995г. [6,7] в XCS системах. Эти системы, взаимодействуют с неопределенной внешней средой и используют обратную связь в виде поощрения при правильном выборе решения. При этом они стремятся научиться точно прогнозировать размер будущих "премий".
(рис 7.2) Взаимодействие XCS систем с окружением и программой обучения
XCS система отличается от традиционных систем машинного обучения (LCS) использованием ГА и другим подходом к определению фитнесс-функции. Во-первых, вычисление фитнесс-функции для классификатора основано на
В XCS системах, как и в других машинных системах обучения (LCS), решение проблемы представляется в виде популяции классификаторов. На каждом шаге XCS система принимает конкретное событие из окружающей среды в виде значений сигналов и основываясь на текущих знаниях предлагает решение для этого случая. В зависимости от проблемной ситуации (значений входов) и предложенного решения система определяет численное значение поощрения (премии), которое характеризует качество рекомендуемого решения. В отличие от обычных систем обучения (LCS), где каждому классификатору соответствовала "сила", в XCS системе она фактически заменяется тремя параметрами: 1) (payoff) preduction, 2) prediction error, 3) fitness. Роль этих параметров рассмотрена ниже.
Для простоты мы сначала рассмотрим продукционную систему XCS как систему чистой классификации, в которой распространение поощрения (через обратную связь) необязательно. Однако следует помнить, что XCS является более общей системой обучения, которая способна обучаться итеративно (многошагово), где распространение поощрения для вывода оптимального решения проблемы является обязательным.
Описание проблемы. Рассмотрим задачу классификации на $$X=\{0,1\}^l$$- множестве двоичных наборов длины $$l$$. При этом каждая ситуация $$S\in X$$ характеризуется $$l$$ двоичными значениями. Целевая концепция приписывает каждой проблемной ситуации соответствующий класс $$A\in \{1,2,\dots ,n\}$$. Двоичные вектора $$X$$, представляющие различные проблемные ситуации, генерируются случайным образом в соответствии с некоторым распределением вероятностей $$D$$. Если не оговорено специально, то предполагается однородное распределение на всех $$2^l$$ возможных значениях. Различные ситуации (двоичные вектора $$X$$) итеративно предъявляются системе XCS. В соответствие с результатом классификации программа обучения назначает "подкрепление" $$r$$, отражающее правильность классификации. В простейшем случае нулевое поощрение показывает неправильную классификацию, а ненулевое значение (например, 1000) соответствует правильной классификации.
Представление знаний. Знания представляются популяцией $$P$$- множеством классификаторов (правил классификации) по сути в виде дизъюнктивной нормальной формы, где каждый классификатор определяется конъюнктивным термом в дизъюнкции. Таким образом, каждый классификатор можно рассматривать как эксперта в своей проблемной области, который дает в ней экспертное заключение.
Каждый классификатор состоит из пяти основных компонент и некоторых дополнительных предположений:
Условия классификаторов $$C$$ представляются строками из $$l$$ символов троичного алфавита $$[\{0,1k,\#\}\ (C\in\{0,1,\#\}^l\dots)]\ \{0,1k,\#\}\ (C\in\{0,1,\#\}^l)$$, где символ # (неопределенность) покрывает значения и 0 и 1 (это 0 или 1, но неизвестно, что именно). Отметим, что C определяет гиперплоскость в булевом $$l$$-мерном пространстве, в котором классификатор применим. Активная часть определяет одно возможное действие или классификацию. Поощрение прогноза $$R$$ итеративно изменяется в процессе обучения и обеспечивает коррекцию среднего значения "премии" для классификатора в соответствии со значением условной части $$C$$ и выбранного действия $$A$$. Аналогично выполняется коррекция ошибки прогноза поощрения $$\varepsilon$$ и фитнесса $$F$$.
Кроме указанных основных компонент, каждый классификатор имеет несколько дополнительных параметров. Размер множества действий $$as$$ оценивает среднее изменение множества акций. Он изменяется аналогично поощрению прогноза $$R$$. Временной "штамп" $$ts$$ определяет время, когда последний раз классификатор принимал участие в соревновании при выполнении ГА. Счетчик опыта $$\exp$$ подсчитывает число изменений параметров испытуемого классификатора. Параметр $$num$$ определяет число идентичных микроклассификаторов, которые представляет реально данный классификатор.
Оценка классификатора. Для текущей проблемной ситуации $$S$$ система XCS формирует множество соответствий $$(match set) [M]$$, которое состоит из всех классификаторов в популяции $$P$$, чьи условные части соответствуют $$S$$. По сути, множество соответствий $$[M]$$ представляет знания о текущей ситуации $$S$$. Это множество используется для решения проблемы классификации и формирования взвешенных фитнесс-значений поощрений прогноза для каждого варианта возможной классификации. В результате система XCS стремится сформировать полное и точное отображение $$S\times A\Rightarrow P$$ от входных воздействий и акций (действий) в стоимость прогноза, которое позволяет сделать выбор действия с максимальной стоимостью. После выполнения выбранной классификации $$A$$ и результирующего поощрения $$R$$ формируется множество действий $$[A]$$, состоящее из всех классификаторов из $$[M]$$, определяемых выбранным действием $$A$$. Основные параметры $$R$$, $$\varepsilon$$ и $$F$$ всех классификаторов в $$[A]$$ корректируются в соответствии со следующими формулами:
$$R\leftarrow R+\beta(r-R),$$ $$\varepsilon\leftarrow \varepsilon +\beta(|r-R-\varepsilon|),$$ $$k=\begin{cases}1,\text{если $\varepsilon<\varepsilon_0$}\\ \alpha\left(\frac{\varepsilon}{\varepsilon_0}\right)^{-v},\text{иначе $k'=\frac{k}{\sum_{x\in [A]} k_x}$}\end{cases}$$ $$F\leftarrow F +\beta(k'-F),$$где параметр $$\beta$$- коэффициент обучения, $$\varepsilon_0$$- коэффициент толерантности, $$\alpha$$ и $$v$$- дополнительные константы для масштабирования фитнесс-функции. Коэффициент обучения $$\beta\in [0,1]$$ определяет точность и адаптивность изменения средней ошибки поощрения прогноза. Высокое значение коэффициента $$\beta$$ ведет к меньшей зависимости от предыстории и большей адаптивности, но и большей изменчивости вследствие выбора различных значений поощрений. Отметим, что формула (7.1) соответствует коррекции поощрения в $$Q$$-обучении [8] (которое здесь фактически используется). Однако $$Q$$-значения не аппроксимируются таблицей, а определяются множеством правил, представленных в массиве прогноза $$P(A)$$.
Значения фитнесс-функции вычисляются согласно формулам (7.3) - (7.4) . Здесь $$k$$ по сути измеряет текущую абсолютную точность классификатора, используя степенную функцию с параметром $$v$$ в экспоненте для дальнейшего понижения ошибки классификаторов. Порог $$\varepsilon_0$$ означает порог максимальной толерантности ошибки. В соответствии с этим классификаторы, у которых ошибка $$\varepsilon$$ падает ниже порога $$\varepsilon_0$$, считаются точными. Отклонение точности $$k$$ относительно $$\varepsilon$$ показано на рис.7.3. Параметр $$v$$ управляет степенью падения, параметр $$\alpha$$ различает точные и неточные классификаторы.
(рис 7.3) Отклонение точности относительно текущей ошибки поощрения прогноза
Относительная точность $$k'$$ отражает относительную точность по отношению к другим классификаторам в текущем множестве действий $$A$$. В действительности каждый классификатор в $$[A]$$ соревнуется за ограниченные ресурсы фитнесса, которые распределяются в зависимости от $$k\cdot num$$.
Значение фитнесс-функции изменяется согласно формуле (7.4) относительно текущей точности $$k'$$ множества действий. Оно отражает изменение средней относительной точности классификатора.
Кроме этого, корректируется параметр $$as$$, характеризующий размер множества действий $$as\leftarrow as+\beta(|[A]|-as)$$ и чувствительность его изменения в зависимости от коэффициента обучения $$\beta$$.
Эволюция правил. В системе XCS множество правил-классификаторов эволюционирует согласно стационарному ГА с использованием ниш. При этом ниши формируются на основе множества действий классификаторов. Первоначально популяция $$[P]$$ пуста. В том случае, когда при предъявлении ситуации $$S$$ в $$[P]$$ нет соответствующих ей классификаторов, используется механизм покрытия, который генерирует классификатор для любой возможной проблемной ситуации. Такой классификатор покрывает данную ситуацию и имеет среднюю определенность $$(1-P\#)$$, где $$P\#$$ означает вероятность неопределенного символа #. Следует отметить, что если $$P\#$$ имеет значение, близкое к 1, то эволюция стартует с популяции, содержащей слишком общие классификаторы (имеющие в условной части много неопределенных символов), и затем в процессе эволюции происходит снятие неопределенности (замена # на 0 или 1) и вывод более определенных классификаторов. Такой подход чаще применяется на практике. Но возможен и другой подход, при котором эволюция стартует из начальной популяции, содержащей слишком определенные классификаторы (в условной части мало неопределенных символов #). В этом случае в процессе эволюции, наоборот, неопределенные символы вносятся в классификаторы.
В процессе эволюции ГА отбирает два родительских классификатора из текущего множества действий $$[A]$$, используя пропорциональный (или турнирный) отбор, где вероятность выбора классификатора $$cl(p_s(cl))$$ определяется значением относительной фитнесс-функции в $$[A]$$, то есть
$$p_s(cl)=\frac{F(cl)}{\sum_{c\in [A]}F(c)}.$$Далее генерируются два потомка путем выполнения
Дополнительно в процессе внедрения потомков в популяцию для усиления обобщения классификаторов применяется механизм поглощения. При этом классификаторы–потомки проверяются на возможность поглощения имеющимися классификаторами либо по логике в условной части, либо по точности (в популяции уже есть аналогичные классификаторы с лучшей точностью). Если потомок поглощается имеющимися классификаторами, то он не вносится в популяцию, но увеличивается счетчик num поглощающего классификатора.
(рис 7.4) Общая структура XCS
Далее для лучшего понимания рассмотрим простой пример решения задачи классификации для 6-входового мультиплексора.
Обучение XCS на примере мультиплексора.
Этот пример представляет интерес потому, что полное решение проблемы может быть представлено непересекающимися нишами. Функция мультиплексора определяется для двоичных строк длины $$L=k+2^k$$, где $$k>0$$ –целое число. Для мультиплексора с $$k=2$$ входом является двоичная строка из 6 бит, из которых первые две представляют индекс (адрес) а остальные биты являются информационными, один из которых (определяемый адресом) передается на выход. Например, в строке (101101) первые два бита определяют индекс 2, который соответствует предпоследнему биту входной строки и поэтому передается на выход $$y=0$$. Аналогично, строка (001000) дает значение выхода $$y=1$$, поскольку первые слева 2 бита определяют индекс 0, указывающий на следующий (третий слева) бит, который и передается на выход. Оптимальное решение для классификации мультиплексора с 6 входами представлено в табл. 7.2.
| Nr | C | A | R | $$\varepsilon$$ | F |
|---|---|---|---|---|---|
| 1 | 000### | 0 | 1000 | 0 | 1 |
| 2 | 000### | 1 | 0 | 0 | 1 |
| 3 | 001### | 1 | 0 | 0 | 1 |
| 4 | 001### | 1 | 1000 | 0 | 1 |
| 5 | 01#0## | 0 | 0 | 0 | 1 |
| 6 | 01#0## | 1 | 0 | 0 | 1 |
| 7 | 01#1## | 0 | 0 | 0 | 1 |
| 8 | 01#1## | 1 | 1000 | 0 | 1 |
| 9 | 10##0# | 0 | 1000 | 0 | 1 |
| 10 | 10##0# | 1 | 1 | 0 | 1 |
| 11 | 10##1# | 0 | 0 | 0 | 1 |
| 12 | 10##1# | 1 | 1000 | 0 | 1 |
| 13 | 11###0 | 0 | 1000 | 0 | 1 |
| 14 | 11###0 | 1 | 0 | 0 | 1 |
| 15 | 11###1 | 0 | 0 | 0 | 1 |
| 16 | 11###1 | 1 | 1000 | 0 | 1 |
Как отмечалось выше, XCS чаще стартует со множества максимально общих классификаторов (имеющих в условной части много неопределенных символов). В крайнем случае, вероятность неопределенности полагается $$P\#=1$$, что ведет к тому, что начальная популяция содержит два максимально общих классификатора $$\#\#\#\#\#\#\rightarrow 0$$ и $$\#\#\#\#\#\#\rightarrow 1$$. Далее в процессе эволюции
В целом сначала процесс эволюции способствует внесению большего числа определенных значений. Вскоре, однако, начинает преобладать внесение определенных значений в адресные биты, что способствует генерации полных и точных классификаторов.
| Nr | C | A | R | $$\varepsilon$$ |
|---|---|---|---|---|
| 1 | ###### | 0 | 500.0 | 500.0 |
| 2 | ###### | 1 | 500.0 | 500.0 |
| 3 | 1##### | 0 | 500.0 | 500.0 |
| 4 | 1##### | 1 | 500.0 | 500.0 |
| 5 | 0##### | 0 | 500.0 | 500.0 |
| 6 | 1##### | 1 | 500.0 | 500.0 |
| 7 | ##1### | 0 | 375.0 | 468.8 |
| 8 | ##1### | 1 | 625.0 | 468.8 |
| 9 | ##0### | 0 | 625.0 | 468.8 |
| 10 | ##0### | 0 | 375.0 | 468.8 |
| 11 | ##11## | 0 | 250.0 | 375.0 |
| 12 | ##11## | 1 | 750.0 | 375.0 |
| 13 | ##00## | 0 | 250.0 | 375.0 |
| 14 | ##00## | 1 | 750.0 | 375.0 |
| 15 | 0#1### | 0 | 750.0 | 375.0 |
| 16 | 0#1### | 1 | 750.0 | 375.0 |
| 17 | 0#0### | 0 | 750.0 | 375.0 |
| 18 | 0#0### | 1 | 250.0 | 375.0 |
| 19 | 0#11## | 0 | 0.0 | 0.0 |
| 20 | 0#11## | 1 | 1000.0 | 0.0 |
| 21 | 001### | 0 | 0.0 | 0.0 |
| 22 | 001### | 1 | 1000.0 | 0.0 |
| 23 | 10##1# | 0 | 0.0 | 0.0 |
| 24 | 10##1# | 1 | 1000.0 | 0.0 |
| 25 | 000### | 0 | 1000.0 | 0.0 |
| 26 | 000### | 1 | 0.0 | 0.0 |
| 27 | 01#0## | 0 | 1000.0 | 0.0 |
| 28 | 01#0## | 1 | 0.0 | 0.0 |
В [4,9] исследованы возможности применения ГА к некоторым проблемам анализа данных и
В качестве зависимой переменной используется прогнозируемая величина, например, возможный исход заболевания. В качестве зависимой может быть и векторная переменная, содержащая несколько компонент.
Таким образом, множество данных представляет набор аналогичных входных воздействий (влияющих факторов), произошедших в прошлом, в сочетании со значениями прогнозируемой величины, которые были получены в результате действия влияющих факторов.
При
где $$\wedge$$ представляет логический оператор "И". Такое условие определяет некоторое подмножество из множества данных процесса. Фактически это условие является более формализованной формой представления правил-продукций, рассмотренных выше. Переменные $$X_i$$ здесь соответствуют зависимым переменным, например, факторам риска. Таким образом, популяцию составляют множество условий на независимые переменные.
При данном подходе целью является выбор с помощью генетических алгоритмов таких наблюдений из множества данных, которые имеют сходные тенденции изменений независимых переменных, и близкие значения зависимых переменных. Эти зависимые переменные собственно и определяют прогнозируемые значения. Условие также должно однозначно удовлетворять и такому наблюдению, для которого выполняется прогноз. Таким образом, генетические алгоритмы выбирают из фактов, которые уже состоялись в прошлом, те, которые имеют достаточно много общего с фактом, который присутствует в настоящем. Это соответствует гипотезе локальной компактности. Можно предположить, что если из похожих фактов можно сделать близкие выводы, подобный же вывод можно сделать и из текущего наблюдения на основании гипотезы линейных зависимостей, допустим, простой операцией усреднения зависимой(ых) переменной(ых).
Фитнесс-функция для каждой особи (условия) вычисляется на основании всех данных наблюдений в обучающем множестве, которые удовлетворяют этому условию. Следует отметить, что с одной стороны, чем больше данных, тем лучше, но с другой, большое количество данных неизбежно приводит к большому разнообразию во множестве зависимых переменных, на основании которых, собственно, и строится прогноз.
В данном подходе обычно используется следующая фитнесс-функция:
$$f(\tilde N)=-\log\frac{\sigma}{\sigma_0}-\frac{\alpha}{N_c}+\Delta,$$где:
Как видно из приведенного выражения, фитнесс-функция имеет три составляющие (слагаемых).
Первая составляющая оценивает разброс данных, отобранных данным условием. Чем ближе между собой данные в пространстве независимых переменных, тем меньше дисперсия для условия $$C$$, и тем большее значение имеет первая составляющая.
Вторая составляющая оценивает размер выборки, которую представляет данное условие. Чем большее число наблюдений удовлетворяет данному условию, тем меньше значение этой составляющей и тем больше значение целевой функции. Таким образом, вторую составляющую можно назвать "штрафом для условий с бедной статистикой". Для того чтобы вторая составляющая была соизмерима с первой, введен масштабный коэффициент $$\alpha$$.
Третья составляющая $$\Delta$$ введена для того, чтобы существовала возможность регулирования величины фитнесс-функции относительно нуля.
Представление особи и инициализация популяции
Каждая особь популяции представляется линейной структурой (унарным деревом). Каждый узел данного дерева имеет атрибуты: "имя переменной", "левая граница", "правая граница", "потомок". Таким образом, каждый узел определяет диапазон для какой-либо одной переменной. К нему может быть присоединен (или нет) узел–потомок. Таким образом, особь представляется унарным деревом, которое имеет максимум $$N$$ узлов (которые соответствует $$N$$ независимым переменным), и для каждой из них определен диапазон изменения (верхняя и нижняя граница).
Отбор особей для размножения.
Используются стандартные оператор репродукции, например, "колесо рулетки".
В данном методе представления особи чаще всего применяется версия
Для данного представления особей возможны следующие
Использование алгоритмов такого вида по сравнению со стандартными имеет следующие преимущества:
Для решения задачи
Отбор особей для размножения
При отборе особей для размножения обычно используется стандартный оператор репродукции – "колесо рулетки", который реализует пропорциональный отбор в промежуточную популяцию. При этом особи-родители выбираются случайным образом с вероятностью, зависящей от величины их целевой функции. Для повышения эффективности целевая функция должна плавно увеличиваться от нулевого значения. Для соблюдения этого правила очень важен подбор величины смещения $$\Delta$$ для фитнесс-функции. Построенные в процессе кроссинговера потомки замещают особи, целевая функция которых хуже средней по популяции.
При получении потомства может быть использована следующая версия
Каждый ген (ограничение на значения переменной) потомка наследуется у одного из родителей с вероятностью $$P_c\approx 0,5$$. Если у родителей есть узлы с одинаковыми переменными, то они в любом случае помещаются в разные потомки. При этом добавлено правило, которое не позволяет записывать все узлы всех родителей к одному потомку, и не поощряет передачу двух узлов подряд к одному и тому же потомку. Таким образом, возможные потомки для данных родителей могут быть, например, следующие:
Здесь потомок $$C$$ имеет два гена от родителя $$A$$ и один ген от родителя $$B$$. Потомок $$D$$ имеет один ген от родителя $$A$$, и три – от родителя $$B$$.
В дополнение к
Таким образом, глобальный
В качестве критерия останова алгоритма обычно используется выполнение условие окончания: повторение лучшего результата заданное количество поколений подряд.
При сокращении промежуточной популяции применяется стратегия элитизма: особь с наилучшим значением целевой функции обязательно переходит в следующее поколение. Для замедления вырождения выборки к одной особи, все особи, которые совпадают с наилучшей, подвергаются мутации.
Определение параметров алгоритма $$\alpha$$ и $$\Delta$$.
Как указано выше, параметр $$\alpha$$ определяет размер выборки для каждого условия. Чем ниже этот фактор, тем меньшее значение имеет размер выборки, и тем большее значение имеет близость между собой значений зависимых переменных. Параметр $$\Delta$$ определяет величину смещения фитнесс-функции на положительную полуплоскость. Этот параметр должен быть таким, чтобы минимальное значение целевой функции было как можно ближе к 0, но имело положительное значение. Это способствует эффективному функционированию оператора репродукции. Для подбора параметров фитнесс-функции необходимо оценить зависимость точности результата от этих параметров. Например, для различных значений $$\alpha$$ и $$\Delta$$ можно выполнить поиск решений, среди которых найти лучшее. Затем выполнять сравнение лучшего решения с действительным, и найти погрешность результата.
Подбор размера популяции и критерия остановки программы
Аналогично предыдущему пункту производится подбор таких параметров, как размер популяции и количество поколений, в течение которых не улучшается результат (погрешность). Чем меньше размер популяции, тем быстрее выполняется программа, но тем меньше шансов найти оптимальное решение. Напротив, большое число шагов программы до остановки способствует нахождению хорошего решения, но замедляет работу программы.
Подбор вероятности мутации
После выполнения
Таким образом, в данном разделе рассмотрены возможности применения генетических алгоритмов и генетического программирования к задачам
Напомним, что основной проблемой при разработке классических экспертных систем является формирование базы знаний – множества правил-продукций. Для этого привлекаются, как правило, квалифицированные эксперты. Определенную проблему представляет также и обновление знаний в процессе эксплуатации экспертной системы. Преимуществом является, как правило, "прозрачность" правил-продукций и возможность проследить сам процесс вывода – заключения экспертной системы.
В эволюционном подходе предпринята попытка объединить преимущества обоих указанных методов создания экспертных систем – классического и нейросетевого. Фактически этот подход является развитием классического метода построения экспертных систем. Знания хранятся здесь в виде формализованных правил-продукций (почти также как и в обычных экспертных системах). Но здесь есть возможность автоматически строить эти правила-продукции по имеющейся обучающей выборке. Суть данного подхода заключается в том, что из обучающей выборки автоматически выводится множество правил-продукций, которое позволяет с минимальной (в некотором смысле) ошибкой решать поставленную задачу. Для медицинских приложений такой подход является чрезвычайно перспективным – фактически здесь из имеющихся статистических данных по некоторому заболеванию можно фактически автоматически получить методику его диагностирования и прогноза течения заболевания. Это становится возможным благодаря использованию методов эволюционных вычислений.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.