Продукционная модель

Размещено на http://www.allbest.ru/

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

Продукционную систему можно определить на основе следующих категорий.

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

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

3. Цикл "распознавание-действие". Управляющая структура продукционной системы проста: рабочая память инициализируется начальным описанием задачи. Текущее состояние решения задачи представляется набором образцов в рабочей памяти. Эти образцы сопоставляются с условиями продукционных правил; что порождает подмножество правил вывода, называемое конфликтным множеством. Условия этих правил согласованы с образцами в рабочей памяти. Продукции, содержащиеся в конфликтном множестве, называют допустимыми. Выбирается и активизируется одна из продукций конфликтного множества (разрешение конфликта). Активизация правила означает выполнение его действия. При этом изменяется содержание рабочей памяти. После того как выбранное правило сработало, цикл управления повторяется для модифицированной рабочей памяти. Процесс заканчивается, если содержимое рабочей памяти не соответствует никаким условиям.

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

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

Простой пример работы продукционной системы представлен на рис. 2. Данная продукционная система сортирует строку, состоящую из символов a, b и c. В этом примере продукция является допустимой, если ее условие соответствует части строки в рабочей памяти. При выполнении правила подстрока, которая соответствовала его условию, заменяется строкой из правой части правила. Продукционная система -- это общая модель вычислений, которая может быть запрограммирована для выполнения какой-либо задачи на компьютере. Однако настоящее ее предназначение -- это реализация интеллектуальных систем.

Рис. 1. Продукционная система. Цикл выполняется до тех пор, пока образец рабочей памяти не будет более соответствовать ни одному из условий продукционных правил

Набор продукций:

1. baab

2. caac

3. cbbc

Рис. 2. Работа простой продукционной системы

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

Примеры продукционных систем

Пример 1. "8-головоломка"

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

Будем говорить о "перемещении пустой клетки". Допустимые ходы определены продукциями. Естественно, если пустая клетка находится в центре, допустимы все четыре хода. Если пустая клетка находится в одном из углов, возможны только два хода. Если начальное и целевое состояние для "8-головоломки" определены, то можно создать продукционную систему, просматривающую пространство поиска задачи.

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

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

Начальное состояние Целевое состояние

Продукционное множество

целевое состояние в рабочей памяти останов

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

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

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

пустая ячейка не возле нижней границы переместить пустую ячейку вниз

Рабочая память содержит текущее и целевое состояние игровой доски.

Режим управления

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

1. Испытать каждое правило по порядку.

2. Не допускать циклов.

3. Завершить работу при нахождении цели.

Рис. 3. Решение задачи "8-головоломки" с помощью продукционной системы, в которой поиск ограничен глубиной 5

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

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

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

Продукционные правила -- это факты перемещений move, первый параметр которых определяет условие (на доске должно быть достаточно места, чтобы сделать ход), а второй -- действие (поле, в которое конь может перейти). Цикл "распознавание-действие" реализуется с помощью рекурсивного предиката пути path. Рабочая память содержит текущее и желаемое целевое состояние. Ее можно представить параметрами предиката пути path. На данной итерации конфликтное множество -- это все выражения перемещений, которые унифицируются с целью move(X,Z). Эта программа использует простую стратегию разрешения конфликтов, состоящую в выборе и активизации первого предиката перемещения в базе знаний, который не ведет к повторному состоянию. Контроллер также осуществляет возвраты из тупиковых состояний. Эта версия определения предиката path для продукционной системы показана на рис. 4.

Таблица 1

Продукционная система для решения задачи хода конем на поле 3x3

Рис. 4. Рекурсивный алгоритм вычисления пути в продукционной системе

Размещено на Allbest.ru