ВВЕДЕНИЕ

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

1 ЭКСПЕРТНАЯ СИСТЕМА

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

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

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

•  извлечение информации из первичных данных;

•  диагностика неисправностей;

•  структурный анализ сложных объектов;

•  выбор конфигурации сложных многокомпонентных систем;

•  планирование последовательности выполнения операций, приводящих к заданной цели.

1.1 Характеристики экспертных систем

Экспертная система отличается от прочих прикладных программ наличием следующих признаков.

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

•  Система, помимо выполнения вычислительных операций, формирует определенные соображения и выводы, основываясь на тех знаниях, которыми она располагает. Знания в системе представлены, как правило, на некотором специальном языке и хранятся отдельно от собственно программного кода, который и формирует выводы и соображения. Этот компонент программы принято называть базой знаний.

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

Экспертные системы отличаются и от других видов программ из области искусственного интеллекта:

•  Экспертные системы имеют дело с предметами реального мира, операции с которыми обычно требуют наличия значительного опыта, накопленного человеком.

•  Одной из основных характеристик экспертной системы является ее производительность, т.е. скорость получения результата и его достоверность.

•  Экспертная система должна обладать способностью объяснить, почему предложено именно такое решение, и доказать его обоснованность. Пользователь должен получить информацию, необходимую ему для того, чтобы быть уверенным, что решение принято <не с потолка>.

1.2  Базовые функции экспертных систем

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

1.2.1  Приобретение знаний

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

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

1.2.2  Представление знаний

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

Основными критериями доступа к представлению знаний являются:

•  Логическая адекватность - представление должно обладать способностью распознавать все отличия, которые вы закладываете в исходную сущность.

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

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

1.2.3  Управление процессом поиска решения

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

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

1.2.4  Разъяснение принятого решения

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

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

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

2) Языки программирования высокого уровня. Инструментальные средства этой категории избавляют разработчика от необходимости углубляться в детали реализации системы - способы эффективного распределения памяти, низкоуровневые процедуры доступа и манипулирования данными. Одной из наиболее известных представителей таких языков является OPS5.

3) Среда программирования, поддерживающая несколько парадигм. Средства этой категории включают несколько программных модулей, что позволяет пользователю комбинировать в процессе разработки экспертной системы разные стили программирования. Среди первых проектов такого рода была исследовательская программа LOOP , которая допускала использование двух типов представления знаний: базирующегося на системе правил и объектно-ориентированного.

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

2.1 Оболочки экспертных систем

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

Оболочки являются программами, ориентированными на достаточно узкий класс задач, хотя и более широкий, чем та программа, на основе которой была создана та или иная оболочка.

2.2 Языки программирования высокого уровня

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

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

2.3 Среда программирования, поддерживающая несколько парадигм

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

2.4 Дополнительные модули

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

3.1 Поиск в пространстве состояний

Множество проблем можно сформулировать в терминах трех важнейших ингредиентов:

•  Исходное состояние проблемы

•  Тест завершения - проверка, достигнуто ли требуемое конечное состояние или найдено решение проблемы

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

Один из способов представления такого концептуального пространства состояний - граф, в котором состояниям соответствуют узлы, а операциям - дуги.

Метод формирования анаграмм последовательным перечислением является примером применения алгоритма, получившего наименование generate - and - test (порождение и проверка).

•  Генерировать новое состояние, модифицируя существующее.

•  Проверить, является ли образовавшееся состояние конечным. Если это так, то завершить, иначе перейти к шагу (1).

Множество решений, которые удовлетворяют условию на шаге (2), иногда называют пространством решений. Алгоритм имеет два основных варианта: поиск в глубину и поиск в ширину. Отличаются варианты порядком формирования состояний на шаге (1).

Для любого данного узла N алгоритм поиска в глубину строит потомок этого узла, т.е. формирует состояние, которое образуется в результате применения оператора к узлу N , а потом переходит к формированию узла, ближайшего к N , на этом же уровне графа, т.е. формирует состояние, которое образуется в результате применения оператора к узлу-родителю N . Алгоритм поиска в ширину действует наоборот - сначала формируются все <соседи> узла N , а потом уже строятся его потомки. Таким образом, в алгоритме поиска в ширину просматриваются последовательно состояния, представленные узлами одного и того же уровня на графе (рисунок 2.1), а в алгоритме поиска в глубину просматриваются состояния на одном пути, а затем происходит, возврат назад на один уровень и формируется следующий путь (рисунок 2.2).

Рисунок 2.1 - Граф пространства состояний при использовании алгоритма поиска в ширину.

Рисунок 2.2 - Граф пространства состояний при использовании алгоритма поиска в глубину.

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

Свойства этих алгоритмов существенно отличаются:

•  Алгоритм поиска в ширину отыскивает решение, путь к которому на графе - кратчайший, если таковое существует.

•  Алгоритм поиска в глубину может быстрее найти решение, особенно, если при его выполнении используются эвристики для выбора очередной ветви. Но этот алгоритм может никогда не закончиться, если пространство состояний бесконечно.

3.2 Эвристический поиск

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

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

Основной алгоритм, реализующий идею восхождения на гору, можно сформулировать следующим образом.

•  Находясь в данной точке пространства состояний, применить правила порождения нового множества возможных решений.

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

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

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

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

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

3.3 Машина логического вывода и база знаний

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

Рисунок 2.5 - Структура экспертной системы

ЗАКЛЮЧЕНИЕ

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

1.  работу с множеством баз знаний (модулей), ориентированных на разные предметные области;

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

•  критерия оптимизации процесса вывода;

•  отработка явных и неявных продукций;

•  типа - монотонный не монотонный;

3. организацию диалога с пользователем для ввода ТЗ.

ЛИТЕРАТУРА

1.  Питер Джексон. Введение в экспертные системы, Издательский дом <Вильямс> - 2001.

2.  Григорьев А.В. Организация вывода решений в базе знаний инструментальной оболочки для создания интеллектуальных САПР.

3.  Н.А. Алешина, А.В. Анисимов и др. Логика и компьютер / - М.: Наука, 1990