Аннотация
Васяева Т.А., Струг С.С. Получение продукционных правил на основе ГП. Рассмотрен эволюционный подход к извлечению знаний из набора данных. Предложен подход получения продукционной модели используя генетическое программирование.
Общая постановка проблемы
Продукционные модели - это наиболее распространенные на текущий день модели представления знаний, где знания описываются с помощью правил «если-то» (явление > реакция) и представляются а виде: ЕСЛИ условие (антецедент) ТО действие (консеквент) Под условием понимается некоторое предложение-образец, по которому осуществляется поиск в базе знаний, а под действием – набор действий, выполняемых при успешном исходе поиска. Внутри консеквента могут также генерироваться и добавляться в базу новые факты, которые были получены в результате вычислений или взаимодействия с пользователем.
При использовании таких моделей у систем, основанных на знаниях, имеется возможность:
- применение простого и точного механизма использования знаний;
- представления знаний с высокой однородностью, описываемых по единому синтаксису.
Эти две отличительные черты и определили широкое распространение методов представления знаний правилами.
Но вот получение таких правил является одной из наиболее трудоемких задач.
Целью данной работы является разработать математический аппарат для получения продукционных правил.
Применение генетического программирования для решения задач
Для решения поставленной задачи предложено использовать генетическое программирование (ГП).
Решение задачи на основе ГП реализуется следующей последовательностью действий.
1. Установка параметров эволюции;
2. Инициализация начальной популяции;
3. T:=0;
4. Оценка особей, входящих в популяцию;
5. T:=Т+1;
6. Отбор родителей;
7. Создание потомков выбранных пар родителей – выполнение оператор кроссинговера;
8. Мутация новых особей;
9. Расширение популяции новыми порожденными особями;
10. Сокращение расширенной популяции до исходного размера;
11. Если критерий останова алгоритма выполнен, то выбор лучшей особи в конечной популяции – результат работы алгоритма. Иначе переход на шаг 4.
Для решения задачи с помощью ГП необходимо выполнить предварительные этапы:
- определить терминальное множество;
- определить функциональное множество;
- определить фитнесс-функцию;
- определить значения параметров, такие как мощность популяции, максимальный размер особи, вероятности кроссинговера и мутации, способ отбора родителей, критерий окончания эволюции и т.п.
После этого можно разрабатывать непосредственно сам эволюционный алгоритм, реализующий ГП для конкретной задачи.
Каждое потенциальное решение в нашем случае будет представляться деревом, состоящим из функций, которые являются внутренними узлами деревьев, и терминалов, которые формируют листья деревьев.
Основная идея данного метода заключается в методе кодирования особей для генетического программирования. Каждая особь представляет собой дерево, которое соответствует синтаксическому выражению, представляющее множество правил в дизъюнктивной нормальной форме.
На рисунке 1 представлен пример дерева в дизъюнктивной нормальной форме. Дерево представлено двумя правилами. Данное представление особи значительно упрощает интерпретацию результата. В рассмотренном примере расшифровка будет следующей
ЕСЛИ правило 1 ИЛИ правило 2 ТО результат 1, ИНАЧЕ результат 2.
Определим терминальное множество.
Данные должны быть предварительно обработаны, основное назначение предобработки преобразовать входное обучающее множество в булевы переменные.
Функциональное множество состоит из логических операций: AND, OR, NOT.
Генерация начальной популяции. На данном этапе происходит генерация начальной популяции, в соответствии с заданными параметрами. Популяция состоит из набора деревьев, сгенерированных случайным образом. Генерация каждого дерева происходит рекурсивно, начиная с генерации первым функционального узла ИЛИ и его аргументов. В качестве аргументов на первом шаге может быть только узел ИЛИ. Далее для каждого дочернего узла случайным образом определяется тип и значения его аргументов по следующим принципам:
- после узла ИЛИ может быть только функциональный узел (значениями которого могут быть – ИЛИ или И);
- после узла И может быть функциональный узел (значениями которого могут быть – И или НЕ) или терминальные узлы;
- после узла НЕ может быть только терминальный узел.
Процесс выполняется по левой ветви до тех пор, пока не будет выбран дочерним терминальный узел. Затем генерируются правые ветви.
Вероятность функционального и терминального узлов меняется по следующему принципу: чем ниже вершина, тем больше вероятность терминального узла и меньше функционального. Для функционального узла на каждом последующем шаге увеличивается вероятность узла И и уменьшается вероятность узла ИЛИ.
При формировании дерева в одной ветви ИЛИ (т.е. для одного правила) не используется один и тот же терминальный символ более одного раза.
Предусмотрены методы создания деревьев: полный, растущий и комбинированный.
Применение генетических операций:
Отбор родителей. Предложено использовать отбор пропорционально значению целевой функции реализованный методом рулетки или турниром. При этом если два или более потомка имеют одинаковую фитнесс-функцию, то выбирается дерево минимальной сложности.
Кроссинговер. Для древообразной формы представления используются следующие три основных операторов кроссинговера:
- узловой кроссинговер;
- кроссинговер поддеревьев;
- смешанный.
Учитывая строго определенное представление дерева необходимо модифицировать операторы кроссинговера. Модификация заключается в выполнении оператора кроссинговера для худшего правила и в поиске оптимальной точки разрыва.
Мутация. Для деревьев используются следующие операторы мутации:
- узловая;
- усекающая;
- растущая.
Как и в случае с оператором кроссинговера оператор мутации должен быть модифицирован. Модификация заключается в определении вероятности мутации в соответствии с ошибкой обучения.
Редукция. Предлагается использовать элитную стратегию.
Критерий останова. В качестве критерия останова можно выбирать указание определенного числа итераций или указание определенного числа повторения лучшего результата.
Выводы
Разработан подход построения продукционной модели на основе ГП, данный подход позволяет извлекать знания из обучающего набора данных. Данный подход применим для любой предметной области и может быть использован для построения базы знаний в экспертных системах.
Список использованной литературы
1. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning.-Addison-Wesley, reading,MA.-1989.
2. Koza J.R. Genetic Programming.Cambridge:MA:MIT Press,1992.
3. Рутковская Д., Пилинский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И.Д. Рудинского. - М.: Горячая линия – Телеком, 2006. – 452 с. : ил.