Математические методы и экспертные системы для решения прикладных задач качественного характера

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

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

Математические методы и экспертные системы для решения прикладных задач качественного характера

Серов В.В.

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

Ключевые слова: математические методы; экспертные системы; прикладные задачи; исследование.

Введение

Понятие прикладных задач имеет многофункциональное и многообразные значения и определения.

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

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

Определение и обоснование понятия задач

Пойа [2] определяет задачу следующим образом: “Задача предполагает необходимость сознательного поиска соответствующего средства для достижения непосредственно недоступной цели”. Согласно Пойа существует два весьма общих типа задач: задачи на нахождение и задачи на доказательство.

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

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

В работе [3] Е. И. Ефимов предложил следующую классификацию типов задач:

Класс 1. Задачи, для которых существует формальная схема решений, представленная на неком формальном языке. Решение задач осуществляется по имеющейся схеме (детерминированной или вероятностной).

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

Класс II. Задачи, для которых не существует заранее готовой схемы решения. Для построения схемы решения задач этого класса привлекаются знания о предметной области. Обычно в этом случае человек сам формирует схему решения и в этом состоит его творческая деятельность. После того как человек построил схему решения, задачи перестают быть интеллектуальными, и дальнейший поиск их решений человеком или с помощью машины не представляет проблемы.

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

В работе [4] (Месарович) проблемы решения задач в теоретико-множественных представлениях формулируется в самом общем виде следующим образом. Пусть любая система описывается тройкой W,Y,N, где W Z область определения отображения T WY, X - множество входных сигналов, Z - множество состояний и Y - множество выходных сигналов системы. Тогда проблема заключается в том, чтобы по заданным множествам W и Y найти требуемые отображения T.

Примером конкретизации такой модели может служить система доказательства теорем, в которой W - множество правильных формул исчисления высказываний, Y - множество выводимых формул, wH - множество аксиом, используемых в доказательстве, yY, F0 - множество схем базовых правил вывода, примером которых может служить схема modus ponens, и F - множества конкретных доказательств, представляемых в виде упорядоченной совокупности базовых правил вывода (схема правила превращается в конкретное правило при подстановке в схему конкретных формул). Эта система служит для поиска доказательств j F.

Если принять, что W - множество правильно описанных ситуаций, и Р = WW представляют расширенное множество задач, F0 = М0 и F = V - множество программ в мире М0 , то рассмотренная модель может быть представлена как V. Таким образом, необходимыми компонентами решателя являются: объективный мир операций , задачи р Р, играющие роль входных сигналов, и решения vV, играющие роль выходных сигналов.

Отдельный класс практически важных систем составляют системы, характеризуемые большим числом ситуации sS и сравнительно небольшим числом схем решений bB. Основное внимание в этих системах уделялось эффективному описанию ситуаций в декларативной форме - ситуационное моделирование (Д. А. Поспелов [5, 6], Ю. И. Клыков [7]). Специфика ситуационных систем - значительное преобладание числа ситуаций над числом схем решений - позволяет сводить задачу управления объектов к задаче распознавания класса ситуаций, априори соотнесенного с известной схемой решения.

В попытках автоматизировать процессы решения задач часто использовались одноранговые модели типа N=<M1,Q,P,V>, в которых основное внимание обращалось на построение эффективных стратегий поиска решений Q в простых средах M1. Моделями указанного типа обладают такие известные решатели задач, как GPS, STRIPS, QAЗ, ПРИЗ, ППР и другие.

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

Вопросно-ответная дедуктивная система QA3 (Грин [8]) - это попытка более эффективного представления знаний и использование успехов в области автоматических доказательств теорем. Она рассчитана на произвольную предметную область и произвольные вопросы, ее действие основано на автоматическом доказательстве теорем с использованием принципа резолюции Робинсона [9].

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

Планирующая система STRIPS использует декларативно-процедуральное представление знаний в сочетании с эвристическим поиском.

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

Система ABSTRIPS представляет собой модификацию решателя STRIPS, использующую иерархию описаний мира задач.

Опыт разработок систем STRIPS и ABSTRIPS показал, что автоматическое доказательство теорем на основе метода резолюций недостаточно эффективно по причине неструктурированности знаний. Любая теорема в методе резолюций представляется отдельным утверждением без каких либо ссылок на другие вспомогательные теоремы, которые можно было бы использовать для доказательства данной теоремы.

Другой подход - задавать теорему как фрейм, содержащий в себе всю полезную информацию, необходимую для направленного поиска доказательства. Идея задавать такой фрейм в процедуральной форме, указывающей, что и в какой последовательности необходимо сделать предварительно, прежде чем доказать данную теорему, легла в основу разработок процедуральных языков высокого уровня (PLANNER, QLISP, CONNIVER).

Одной из систем процедурального представления знаний является ДИЛОС. Система обладает достаточно универсальным и гибким процедуральным языком, позволяющим представлять знания в едином формализме, пригодном для автоматизированного решения интеллектуальных задач различного класса. Для описания фактуальных знаний (состояния объектов и факты внешнего мира) используются понятия и отношения; для описания актуальных знаний (приемы, методы, умозаключения, законы действий и др.) используются закономерности, представляющие собой программы. Указанные выражения составляют структуру модельной базы данных.

Д. А.Поспелов предложил определение семиотической модели в виде семерки: W=T,H,,,X,,, в которой подсистема А=T,Н,, является формальной системой, а подсистема В=Х,, представляет индуктивную компоненту модели W, предназначенную для изменения указанной формальной системы в режимах обучения и адаптации применительно к конкретной области. Таким образом, система А выражает синтаксический аспект модели W, а система В - ее семантический и прагматический аспекты.

Примером семиотического решателя является СФИНКС - система формального интеллекта комплексных стратегий (Е. И. Ефимов, [3]).

Решатель СФИНКС представляет собой концептуальную систему эвристического поиска в иерархическом пространстве с элементами индуктивно-дедуктивного вывода и процедуральным представлением знаний в формализме системы ДИЛОС. Cистема создавалась в исследовательских целях, состоящих в изучении возможностей подобных решателей в области планирования поведения сложных систем, проектирования технологических и вычислительных процессов, синтеза машинных программ, автоматического доказательства теорем и других областей научно-технической деятельности человека.

В настоящее время продолжает успешно развиваться концепция, получившая название логического программирования. Важным практическим шагом в указанном направлении было создание языка ПРОЛОГ (PROgramming in LOGic). Основная идея этого языка состояла в том, что нужно на логическом языке описать условие задачи, а решение ее получается как результат некоего рутинного процесса, который исполняется на ЭВМ. Условие задачи представляет собой множество формул специального вида в языке логики предикатов первого порядка, одна из формул выделена и называется целью, остальные - посылками. Тогда упомянутый процесс состоит в построении доказательства цели из посылок в исчислении, единственным правилом вывода которого является правило резолюции.

Компьютерное обоснование решения задач качественного характера в экспертных системах

математический задача эспертный компьютерный

ПРОЛОГ обладает свойством алгоритмической полноты, то есть является универсальным языком, что привело Р. Ковальски к формулировке тезиса: "алгоритм = логика + управление". Он же предложил процедурную интерпретацию, согласно которой ПРОЛОГ-программа представляет собой совокупность хорновских дизъюнктов, среди которых выделен один, состоящий лишь из отрицательных литералов и называемый целью. Исполнение ПРОЛОГ-программы представляет собой процесс применения правила резолюции. При этом "хорновскость" позволяет отказаться от правила факторизации и применять правило резолюции не ко всем возможным парам дизъюнктов, а лишь к тем, которые удовлетворяют определенным условиям (эти условия обычно называют стратегиями). Например, можно требовать, чтобы один из вступающих в резолюцию дизъюнктов принадлежал исходному множеству (так называемая входная стратегия).

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

Результатом исполнения ПРОЛОГ-программы является значение, которое получает некоторая входящая в цель переменная после успешного завершения резолюционного процесса.

Для формализации предметной области в языке ПРОЛОГ используют синтаксические конструкции, которые позволяют описывать простые и составные объекты, выражения, списки, строки, что дает возможность использовать его для создания реальных экспертных систем.

Если пересмотреть принцип резолюций с точки зрения нечеткой логики, то появляется возможность построить нечеткий ПРОЛОГ c многозначной оценкой истинности решений. Такой вариант языка является весьма удобным и эффективным средством решения качественных задач при нечетком представлении знаний [10].

Заключение

Развитие математических методов представления знаний и создания современных экспертных систем для решения прикладных задач качественного характера является одним из основных направлений информатизации современного общества и требует к себе как научного так и общественного внимания.

В настоящее время для решения прикладных задач качественного характера при нечетком представлении знаний в экспертных системах наиболее перспективно применение логического программирования.

Библиографический список

1. Власов В. В. Общая теория решения задач (рациология). М.: ВЗПИ, 1990.

2. Пойя Г. Математика и правдоподобные рассуждения. М.: Наука, 1975.

3. Ефимов Е. И. Решатели интеллектуальных задач. М.: Наука, 1982.

4. Месарович М. Общая теория систем. М.: Мир, 1966.

5. Поспелов Д. А. Принципы ситуационного управления // Изв. АН СССР. Техническая кибернетика. 1971, № 2.

6. Поспелов Д. А. Ситуационное управление: теория и практика. М.: Наука, 1986.

7. Клыков Ю. И. Ситуационное управление большими системами. М.: Энергия, 1974.

8. Green C. C., Raphael B. The use of theorem-proving techniques in question-answering systems. Proc. 23rd ACM Nat. Conf., 1968.

9. Robinson J. A. Logic Programming - Past, Present and Future. New Generation Computing, 1983, vol. 1.

10. Серов В. В. Логическое представление нечетких знаний и его применение для решения прикладных задач качественного характера. М.: РосЗИТЛП, 2001.

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