THE USE OF THE GENETIC PROGRAMMING IN THE PROBLEMOF THE AUTOMATA-BASED RESOLUTIVE DEDUCTION MODELS BUILDING

Abstract

It is considered the building of the resolutive logical deduction systems possessing effective problem-solving algo- rithms. Building of effective heuristics is based on the evolution strategy. The logical deduction system is realized as a finite state machine on the basis of the automata-based programming.

Full Text

Решение задач резолютивного вывода сводится к поиску наилучшего пути решения. При этом слож- ность поиска возрастает экспоненциально по мере продвижения по дереву вывода. Поэтому при решении задач, характеризующихся экспоненциальным ростом пространства поиска, особое значение приобретает проблема эффективности процедур поиска. Вследст- вие этого авторы предлагают использовать эволюци- онную стратегию [1] для генерации наиболее эффек- тивной эвристики для заданной выборки множества дизъюнктов. Для реализации решения задач естественноязыковой обработки научных текстов выбраны декла- ративные методы в виде систем продукций. Это обос- новывается тем, что декларативные методы можно уточнять и совершенствовать в процессе их функцио- нирования, так как модели решения задач естествен- но-языковой обработки пока еще далеки от совершен- ства. После ряда преобразований каждый метод пред- ставляется в виде множества дизъюнктов. Активация метода осуществляется по сфере применимости сис- темы продукций. Ядром аппарата активации является система логического вывода. Работа активированной системы продукций (метода естественно-языковой обработки) заключается в доказательстве входной ги- потезы d0 на множестве дизъюнктов метода. Для дока- зательства истинности или ложности гипотезы d0, описывающей входную ситуацию, используется мо- дифицированный метод линейной резолюции Лавлен- да, Ковальского и Кюнера [2]. Таким образом, имеем семейство множеств дизъ- юнктов M = {Mi|I = 1..n, n - количество методов}. На- зовем множество дизъюнктов метода выборкой. Тогда задача состоит в том, чтобы для каждой выборки Mi Î M сгенерировать конечный автомат, позволяющий осуществлять резолютивный вывод и обладающий высокой эффективностью именно для конкретной вы- борки. Модель системы резолютивного вывода. Мо- дель системы резолютивного вывода LogRezDed по- строена в виде конечного автомата Мура и определя- ется двойкой основных компонентов: А = <StaticLogRezDed, DinamicLogRezDed >. Статический компонент StaticLogRezDed описывается кортежем StaticLogRezDed = <State_S, Act_S>, где State_S и Act_S - это соответственно вектора ста- тистических состояний и действий автомата. StaticLo- gRezDed одинаков для всех реализуемых методов и проектируется сразу в инструментальной системе UniMod, поддерживающей технологии автоматного про- граммирования [3; 4]. Динамический компонент также определяется двойкой основных компонентов: DinamicLogRezDed = <State_D, Act_D>, где State_D, Act_D - генерируемые состояния и действия автомата. DinamicLogRezDed зависит от решаемой задачи (реализуемого метода), и для его построения используется эволюционная стра- тегия. Вектор статических состояний представляет собой шестерку State_S = <Select_C, Select_B, Destructor, Set_Flags, Resolution>. В каждом их этих состояний выполняются действия, принадлежащие множеству Op_S: Select_C - состояние, в котором выполняется за- грузка центрального дизъюнкта; Select_B - состояние, в котором выполняется за- грузка бокового дизъюнкта; Destructor - состояние, в котором выполняется сортировка множества контрарных пар (боковых дизъюнктов); Set_Flags - состояние, в котором выполняется сортировка множества центральных дизъюнктов; Resolution - состояние, в котором выполняется ряд действий: проверка дизъюнктов на унифицируемость; склейка дизъюнктов; обрамление литер; удаление обрамленных литер; проверка на редуцируемость и достижимость пустого дизъюнкта; проверка на вывод пустого дизъюнкта. DinamicLogRezDed строится на основании сгене- рированной модели автомата (особи популяции), со- держащей динамические состояния. В этих состояни- ях происходит оценка дизъюнктов во множествах, на основе которой выполняется выбор бокового и цен- трального дизъюнктов. На базе статических и динамических состояний формируется автомат, исполняемый в среде UniMod. Данная среда используется для проверки достижимо- сти конечного состояния и расчета Fitness-функции. Разделение автомата на статический и динамический компоненты упрощает процесс генерации эффектив- ной эвристики. Генерация динамического компонента автома- та. Основные положения генетического алгоритма. За основу взяты следующие положения: Автомат (особь) представляется в виде хромо- сомы. Хромосома состоит из динамического набора молекул ДНК двух видов X и Y, множество молекул X предназначено для выбора центрального дизъюнкта, множество Y - бокового дизъюнкта. Молекулы ДНК как первого, так и второго мно- жества должны составлять замкнутую цепочку пере- ходов. Молекулы ДНК не должны повторяться в особи. Молекула ДНК состоит из трех генов. Каждый ген представляется в виде целого числа. Первая популяция Р(0) генерируется случайным образом, при этом значения каждого гена выбирается из соответствующей области допустимых значений. Каждое новое поколение P(t) генерируется при помощи оператора кроссинговера. Родительские пары выбираются оператором репродукции по методу за- данной шкалы. В каждой новой хромосоме повторяющиеся мо- лекулы, если таковые есть, подвергаются мутации. Все повторяющиеся хромосомы из популяции удаляются. Оценивание хромосом и их ранжирование осу- ществляются на основе использования внешнего для генетического алгоритма объекта - инструментальной системы UniMod. Структура хромосомы. Хромосома состоит из ди- намического количества молекул ДНК. Структура молекулы состоит из трех генов (рис. 1): символ перехода, интервал значений которого лежит в диапазоне от 1 до 3; новое состояния, интервал значений которого для молекул вида X лежит в диапазоне от 1 до 11, а для молекул типа Y - от 12 до 21; image текущее состояние, интервал значений которого для молекул вида X лежит в диапазоне от 0 до 10, а для молекул типа Y - от 13 до 22. X XX XX Рис. 1. Структура молекулы ДНК Абстрактный пример структуры хромосомы при- веден на рис. 2. Первичные правила проверки хромосом на кор- ректность, применяемые при создании новой популя- ции следующие: во множестве молекул типа X должна присутст- вовать, по крайней мере, одна молекула, имеющая значение 2-го гена равное 11 (конечное состояние); во множестве молекул типа X должна присутст- вовать, по крайней мере, одна молекула, имеющая значение 3-го гена равное 0 (начальное состояние); во множестве молекул типа Y хромосомы должна присутствовать, по крайней мере, одна молекула, имеющая значение 2-го гена равное 22 (конечное со- стояние); во множестве молекул типа Y хромосомы должна присутствовать, по крайней мере, одна молекула, имеющая значение 2-го гена равное 13 (начальное состояние). Схема генетического алгоритма. Алгоритм вклю- чает следующие основные процессы: инициализация входного множества дизъюнктов (класс InitDis); создание начальной популяции Р(0): а) формирование особи случайным образом; б) проверка выполнения первичных правил на на- личие в хромосоме начального и конечного состояний; в) мутация некорректных молекул непосредст- венно при генерации популяции (класс Run); формирование популяции выполнимых автома- тов: а) оценка автоматов на выполнимость (класс Run); б) переход к п. 4, если все особи прошли провер- ку, иначе - к следующему пункту; в) удаление из популяции особей, не прошедших проверку; г) селекция, скрещивание и мутация автоматов, не прошедших проверку, и переход к п. 3 а); Часть Х Часть Y Ген 1 Ген 2 Ген 3 image 1 2 3 4 5 6 7 8 Рис. 2. Пример структуры хромосомы Примечание: серым цветом закрашены гены, содержащие начальное и конечные состояния. N молекулы ДНК преобразование каждой особи (модели динами- ческой части автомата) популяции в XML-описание автомата; загрузка XML-описания и прогонка автомата (класс Run RunHromosome); анализ результатов работы автоматов на вывод пустого дизъюнкта при заданной глубине (если полу- чен пустой дизъюнкт, то особь считается корректной); удаление некорректно работающих особей из популяции; расчет fitness-функции для корректных автома- тов на основе информации о количестве успешных унификаций останов, если значение fitness-функции достиг- торые верифицируют структуру автомата (наличие противоречивых переходов). Проверка достижимости конечного состояния осуществляется посредством функции getName() класса StateMachineValidator, возвращающей имя но- вого состояния. Если условие getName() = «finish» не выполнится ни разу, то построенный автомат является некорректным. Если при проверке особи обнаружена некоррект- ность, то ей назначается штраф b(а) = -1, где а - особь популяции. Если особь корректна, то b(а) = + 1. Таким образом, оценка i-й хромосомы вычисляется по сле- дующей формуле: m ( ) ( ), нет или превысит 0,9; F1 ai = åbj ai j =1 создание новой популяции выполнимых авто- матов: а) селекция, скрещивание и мутация автоматов, не прошедших проверку, и переход к п. 3 а); б) оценка автоматов на выполнимость посред- ством стандартных функций UniMod Framework (класс Run); в) удаление из популяции особей, не прошед- ших проверку; г) переход к п. 4, если все особи прошли про- верку, иначе - к п. 10 а). Оценивание. Оценивание состоит из двух этапов: оценки автоматов на выполнимость и оценки приспо- собленности особей. Оценка автоматов на выполнимость осуществляет- ся с помощью стандартных функций UniMod и заклю- чается в проверке: на наличие ошибок в объектном коде; наличие ошибок в автоматах; достижимость конечного состояния. Для проверки объектного кода применяется класс DefaultCompilationListener, объект которого создан в классе Run. В конструктор класса подается откомпи- лированная модель автомата (объект класса StateMa- chineCompiler), после чего вызывается функция getEr- rors(), которая сообщает о наличии ошибок в модели. Проверка на наличие ошибок в автоматах осуще- ствляется с помощью функций validateStructure() и getAttainableStates() класса StateMachineValidator, ко- где m - количество ошибок; ì+1, если ошибок нет, î bj (ai ) = í-1, если обнаружена ошибка. Все хромосомы, у которых F1(ai) < 0, удаляются из популяции. Оценка приспособленности особей или расчет Fit- ness-функции осуществляется по формуле оценки F2(ai) = 10(a - U(ai)) + 1/k1(ai) + 1/k2(ai) + 1/k3(ai), где ai - текущая особь; a - константа, определяющая максимально возможное количество унификаций; U(ai) - количество успешных унификаций; k1(ai) - сред- нее количество литер во множестве центральных дизъюнктов С; k2(ai) - среднее количество необрам- ленных литер во множестве С; k3(ai) - соотношение средней арности термов к количеству константных символов в них. Константа a зависит от конкретной выборки, и ее значения лежат в интервале [100, 1000]. Особи ранжи- руются в соответствии со значением F2(ai). Особи, обладающие высоким значением Fitness-функции, остаются в популяции, ранжируются в соответствии со значением F2(ai) и составляют множество, из кото- рого оператором селекции родительские хромосомы выбираются для скрещивания. image Основные генетические операторы. Оператор мутации. Используется двухточечный оператор мута- ции. Каждое значение, генерируемое оператором, должно соответствовать правилам формирования мо- лекул X, Y (рис. 3). Родительская хромосома ai Хромосома-потомок a¢i Точки мутации Рис. 3. Пример оператора мутации Оператор мутации не применяется к молекулам, содержащим начальное и конечное состояния. Из это- го следует, что в хромосоме изображенной на рис. 3 к области выбора молекул ДНК для мутации относятся 3-я и 4-я молекулы. После применения оператора му- тации в п. 2 генетического алгоритма модифицируется молекула хромосомы, а в п. 10 - создается новая хро- мосома. Оператор кроссинговера. В алгоритме использует- ся двухточечный оператор кроссинговера. У особи родителей а1 и а2, имеющей меньшую длину, случай- ным образом выбираются две позиции: одна в части молекул типа Х и вторая в части молекул типа Y. В потомок а¢1 копируются молекулы ДНК хромосомы а1 с начала до первой точки кроссинговера, затем мо- лекулы ДНК хромосомы а2 с первой точки кроссинго- вера до конца части молекул типа Х, затем молекулы ДНК хромосомы а1 с начала части молекул типа Y до второй точки кроссинговера, затем молекулы ДНК хромосомы а2 со второй точки кроссинговера до кон- ца. Потомок а¢2 формируется в инверсном порядке. Если в результате операции из хромосомы потомка выпадают гены, содержащие начальное или конечное состояния, то молекулы одного из родителей, содер- жащие их, также копируются в эту хромосому. В слу- чае если у потомка оказалось более двух генов, со- держащих начальное состояние, одна из молекул, со- держащих это состояние, удаляется. При генерации первой популяции после операции редукции выполняется оператор кроссинговера для заполнения поколения необходимым количеством особей. В том случае, если применение оператора не- возможно (после редукции осталась одна особь, или сгенерированы все возможные недублирующиеся хромосомы), используется оператор мутации. Пример модели автомата. Как было изложено выше, система LogRezDed состоит из StaticLog- RezDed, DinamicLogRezDed. Вид автомата, сформиро- ванный средой Unimod по модели автомата, сгенери- рованной генетическим алгоритмом для выборки - множества дизъюнктов по классической задаче Стим- роллер [5] показан на рис. 4. Состояния StaticLogRezDed: Select_C - состояние, в котором выполняется загрузка центрального дизъ- юнкта; Select_B - состояние, в котором выполняется загрузка бокового дизъюнкта; Destructor - состояние, в котором выполняется сортировка множества кон- трарных пар (боковых дизъюнктов); Set_Flags - со- стояние, в котором выполняется сортировка множест- ва центральных дизъюнктов; Resolution - резольвиро- вание первых дизъюнктов во множествах централь- ных и боковых дизъюнктов. Состояниям DinamicLogRezDed (генерируемые генетическим алгоритмов) соответствуют состояния s8...s15 (рис. 4). В этих состояниях происходит оценка боковых и центральных дизъюнктов. Для оценки дизъюнктов используются следующие ха- рактеристики: количество литер в дизъюнкте; количество обрамленных литер в дизъюнкте; количество констант в контрарной литере дизъ- юнкта; количество функциональных символов в кон- трарной литере дизъюнкта; соотношение мощности вершины графа контрар- ных пар к другим вершинам; соотношение средней длины дизъюнкта к сред- ней длине вершины множества; соотношение количества переменных в опреде- ленном месте предиката к среднему количеству в кон- трарном множестве в той же позиции и т. д.; способы унификации дизъюнктов (применением индексирования и без него). image Рис. 4. Диаграмма состояний автомата Алгоритмы ранжирования множеств дизъюнктов представляются в виде вложенных конечных автома- тов. Каждый автомат имеет действия в состояниях, соответствующие операциям склеивания дизъюнктов и ранжирования множеств дизъюнктов. В начальном состоянии любой автомат выполняет следующие действия: загружает и индексирует входное множество дизъюнктов; составляет граф контрарных пар; загружает дизъюнкты в соответствии с их кон- трарными парами. У автомата нет действий на переходах, но действия привязаны к каждому конкретному состоянию. Тестирование алгоритма проводилось на входном множестве дизъюнктов мощностью равной 25 [5]. При прогоне модели автомата в среде UniMod на первой популяции размером в тысячу особей было получено два автомата. Первый автомат удовлетворял всем ус- ловиям, но им не был найден пустой дизъюнкт. Вто- рой автомат вывел пустой дизъюнкт при глубине по- иска равной 5. В последующих популяциях были сге- нерированны модели автоматов, из которых можно было выбрать наиболее эффективный посредством ранжирования особей популяции по возрастанию зна- чений их fitness-функций. Таким образом, предложена модель автомата, ко- торая является универсальной по отношению к алго- ритмам резолютивного вывода. Она содержит состоя- ния, общие для всех алгоритмов и специальные для конкретных алгоритмов. Генетический алгоритм по- зволяет генерировать состояния для конкретных авто- матов. Используются такие критерии, как среднее ко- личество необрамленных и обрамленных литер в дизъюнктах, средняя арность термов аргументов пре- диката, среднее количество константных и функцио- нальных символов, количество успешных унификаций и т. д., которые способны повлиять на выбор дизъ- юнктов на определенном шаге резольвирования в раз- личных сочетаниях и различной последовательности. Это позволяет в ходе эволюции выявлять наиболее эффективные автоматы для предметной области задачи, в которой работает алгоритм резолютивного вывода.