Введение в экспертные системы
Стратегии разрешения конфликтов LEX и МЕА
В главе 5 были упомянуты стратегии разрешения конфликтов LEX и МЕА, реализованные в языке CLIPS. Ниже будет в общих чертах рассмотрена реализация стратегии МЕА, которая использована в системе R1/XCON.
Как было показано в главе 3, анализ "средство — анализ результата" является абстрактным режимом формирования цепочки обратного логического вывода в случае, когда определена некоторая цель. Этот режим позволяет выбрать операторы или правила, которые способны сократить "расстояние" между текущим и заданным целевым состоянием проблемы. Несложно показать, как этот режим можно использовать в контексте порождающей системы с обратной стратегией логического вывода, например MYCIN, когда весь процесс начинается с цели самого верхнего уровня общности (см. главу 3). В системах, использующих прямой логический вывод, которые строятся на основе языковых средств OPS5 или CLIPS, применяется стратегия разрешения конфликтов МЕА. Основанный на ней режим управления позволяет программе "продвигаться" по неявно заданному дереву целей, которые представлены специальными лексемами в рабочей памяти экспертной системы.
Алгоритм МЕА включает пять шагов. Напомним, что конфликтующее множество правил включает те конкретизированные правила, которые должны быть активизированы в течение одного и того же цикла вычислений. Конкретизация правила представляет собой совокупность обобщенной формулировки правила и значений используемых в нем переменных .
(1) Исключить из конфликтующего множества те правила, которые уже были применены в предыдущем цикле. Если после этого множество стало пустым, прекратить процесс.
(2) Сравнить "новизну" элементов в рабочей памяти, которые соответствуют первым элементам условий в конкретизированных правилах, оставшихся в конфликтующем множестве. Приоритет отдается тем правилам, которые обращаются к самым "свежим" элементам рабочей памяти,— эти правила "доминируют" над остальными. Если существует единственное такое правило, то оно выбирается для применения, после чего процесс должен быть прекращен. В противном случае, если имеется несколько доминирующих правил с
равным приоритетом, они сохраняются в конфликтующем множестве, а прочие из него удаляются. Далее выполняется переход к шагу (3).
(3) Упорядочить конкретизированные правила по "новизне" остальных элементов условий в правилах. Если доминирует единственное правило, оно применяется и затем процесс прекращается. Если же доминируют два или несколько правил, то они остаются в конфликтующем множестве, а остальные удаляются из него. Затем выполняется переход к шагу (4),
(4) Если по критерию "новизны" элементов условий отобрано несколько правил с равными показателями, то сравнивается другой показатель правил — показатель специфики. Предпочтение отдается тому правилу, применение которого требует проверки наибольшего количества условий в рабочей памяти. Если "претендентов" окажется несколько, остальные удаляются из конфликтующего множества и выполняется переход к шагу (5).
(5) Применяется правило, выбранное произвольным образом из оставшихся в конфликтующем множестве, и процесс прекращается.
Таким образом, стратегия МЕА объединяет в едином алгоритме анализ таких показателей, как повторяемость, новизна и специфика. Алгоритм LEX практически идентичен алгоритму МЕА за одним исключением — в нем отсутствует шаг 2), а на шаге 3) сравниваются все элементы условий конкретизированных правил и связанных с ними элементов рабочей памяти. Первые элементы условий, которые использовались на шаге 2), являются, как правило, лексемами задач в рабочей памяти (в главе 5 приведен пример программы, которая манипулирует такими лексемами).
