Представление знаний в информационных системах

Балтийский государственный технический университет «ВОЕНМЕХ» им. Д.Ф. Устинова Представление знаний в информационных системах Конспект лекций Для студентов заочного обучения Составитель: доц. кафедры И9 Толмачев С.Г. Санкт-Петербург 2017 Содержание 1. Модели представления знаний3 1.1. Термины и определения 3 1.2. Модели представления знаний 5 1.3. Формализация и анализ знаний 7 1.4. Формальные модели представления знаний 12 1.4.1. Логические модели 12 1.4.2. Семантические сети 20 1.4.3. Фреймы 24 1.4.4. Продукционная модель 29 2. РАЗРАБОТКА ПРОТОТИПА ЭС В СРЕДЕ CLIPS 34 2.1. Общие сведения о CLIPS 34 2.2. Программирование в CLIPS 34 2.2.1. Простые типы данных 34 2.2.2. Функции 35 2.2.3. Конструкции 36 2.2.4. Интерфейс CLIPS 43 2.3. Пример разработки учебной ЭС 44 2.3.1. Исходные данные 44 2.3.2. Сущности 45 2.3.3. Сбор информации 47 2.3.4. Диагностические правила 49 3. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ В ЛОГИЧЕСКОМ БАЗИСЕ 56 3.1 Интеллектуальные агенты 56 3.2 Постановка задачи в пространстве состояний среды 61 3.2.1 Неформальная постановка задачи 61 3.2.1 Формальная постановка задачи 65 3.3 СТРАТЕГИИ ПОИСКА. 76 3.3.1 Локальный поиск 78 3.3.2 Муравьиные алгоритмы 81 3.2.3 Поиск на графе 87 3.4 ПОИСК НА ИГРОВЫХ ДЕРЕВЬЯХ 96 1. Модели представления знаний 1.1. Термины и определения Предметная область (ПрО) — это область человеческой деятельности, для решению задач которой используется интеллектуальная информационная система (ИС). Например, если проектируется интеллектуальная система управления противокорабельным ракетным оружием, то предметная область охватывает теорию управления летательными аппаратами, радиолокацию, навигацию и т.д. Создание ИС требует глубокого понимания специфики, присущей каждой предметной области. Специфика выражается в большей степени в наличии набора эвристических, выработанных годами правил разрешения стереотипных ситуаций. Проблема состоит в том, чтобы формализовать эти правила. Для этого нужно определить важные понятия ПрО, состояния в которых они могут находиться и отношения между ними. Например, понятие «вода» - может иметь несколько состояний: «тихая», «взволнованная» и ряд других. Понятия «подводная лодка» и «вода» могут находиться в отношении «погружена в». Формализованное описание ПрО осуществляется в форме онтологий. Онтология. С формальной точки зрения это упорядоченная тройка вида: О = < А, В, С >, где А- конечное множество концептов (понятий, терминов) ПрО, которую представляет онтолоrия О; В - конечное множество отношений между концептами (понятиями, терминами) заданной ПрО; С- конечное множество функций интерпретации (аксиоматизация), заданных на А и В. Можно сказать, что онтологии - это базы знаний специального типа, которые могут «читаться», «пониматься», «отчуждаться» от их разработчика Состояние. Каждая информационная единица ПрО, как и вся система в целом, может находиться в одном из возможных состояний. Например, лампочка может находиться в одном из состояний: включена – выключена. Есть системы, для которых пространство состояний бесконечно. Пространство состояний удобно представлять в виде графа или таблицы переходов. Цель. Интеллектуальная ИС характеризуется свойством целеустремленности, т.е. содержит в себе цель, которую нужно достичь, и правила движения к этой цели. Целевые установки в интеллектуальных системах чаще всего задаются в форме требования перехода системы из начального в заданное (целевое) состояние, а в качестве критерия эффективности выбирается условная стоимость переходов из начального состояния в целевое. Например, в интеллектуальной системе управления ракетным оружием (РО) начальное состояние характеризуется координатами атакуемой цели, средств поражения, средств противодействия РО, а целевое состояние - совпадением координат цели и атакующей ракеты. В шахматной программе начальное состояние характеризуется изначально заданным расположением фигур на доске, а целевое (целевые) состояние – расположением фигур, при котором обеспечивается выигрыш одного из игроков. Знания. В качестве рабочего определения можно принять следующее. Знания - это закономерности ПрО (понятия, связи, законы), полученные в результате практической деятельности и профессионального опыта, позволяющие специалистам ставить и решать задачи в данной области. Модель представления знаний – это способ формализованного представления знаний. Реализация конкретных систем ИИ, основанных на знаниях, происходит в рамках одной из моделей преставления знаний или языка представления знаний. Таких моделей немного, наиболее полезные из них называют эвристиками. Эвристика – неформальная (теоретически не обоснованная) модель, базирующаяся на опыте экспертов. 1.2. Модели представления знаний Знания – ключевой термин интеллектуальных ИС. Знания получаются в результате применения к исходным данным некоторых методов обработки, подключения внешних процедур. Работа программы ИС заключается в выводе на знаниях или выводе новых знаний. Знания базируются на исходных данных, накопленных в ПрО и являются их обобщением. Специфические признаки знаний, позволяющие охарактеризовать их отличие от данных, можно сформулировать следующим образом. 1. Более сложная, чем у данных, структура знаний. 2. Возможность задавать знания как экстенсионально (т.е. через набор конкретных фактов, соответствующих данному понятию), так и интенсионально (т.е. через свойства понятий). Данные задаются только экстенсионально. Экстенсионал – множество объектов, способных именоваться данной языковой единицей. Интенсионал – совокупность признаков обозначаемого понятием предмета или явления. 3. Внутренняя интерпретируемость знаний. В отличие от данных в памяти совместно с элементами данных хранится система имен. 4. Рекурсивная структурированность знаний, т.е. возможность их декомпозиции и объединения по иерархическому принципу. 5. Взаимосвязь (связанность) единиц знаний, т.е. возможность установления различных отношений, отражающих семантику связей отдельных фактов, а также отношений, отражающих смысл системы в целом. 6. Наличие у знаний семантического пространства с метрикой, т.е. возможность определять близость/удаленность информационных единиц. 7. Активность знаний, т.е. возможность ставить и достигать цели, формировать мотивы поведения, строить процедуры решения задач. 8. Функциональная целостность знаний, т.е. возможность выбора средств достижения цели. При выявлении и формализации человеческих знаний возникает ряд типичных проблем, связанных с так называемыми НЕ-факторами знаний. Знаниям, полученным от экспертов, как правило, присущи элементы нечеткости, неопределенности, неточности, и неполноты. Можно выделить две основные группы НЕ-факторов знаний, первая группа – недостоверные знания включает НЕ-факторы, проявляющиеся в эксплицитном (явно выраженном) виде, а вторая включает НЕ-факторы, выделить которые в явном виде не представляется возможным. Нечеткость есть свойство количественной оценки качественных понятий и отношений, когда по количественной оценке элемента x невозможно однозначно сказать, принадлежит он множеству A или нет. Например, x=70км/ч, A–«большая скорость». Формализация нечетких знаний связана с определением функций принадлежности (ФП) множеств типа A-нечетких множеств. Неопределенность - это степень неуверенности, которую эксперт приписывает своим высказываниям, Т.е. некоторый субъективный коэффициент неполной уверенности в высказывании , который может иметь вид интервала уверенности. Неопределенность отличается от нечеткости тем, что коэффициент уверенности приписывается не каждому элементу х некоторого множества (как в случае нечеткости), а только к конкретному высказыванию. Неточность проявляется тогда, когда оперируют параметрами, полученными при помощи каких-либо измерительных приборов, каждый из которых имеет известную относительную погрешность измерения, т.е. когда значение х известно с точностью до некоторого множества Х. Неполнота означает, что неизвестен либо элемент х, либо множество А. Неполнота связана, как правило, с тем, что эксперт не знает (не сообщил) какого-либо факта или правила необходимого для решения задачи. Для обработки НЕ-факторов знаний используются: теория Байеса, теория Демпстера-Шеффера, теория нечетких множеств, факторы уверенности, пороги достоверности и другие инструменты. 1.3. Формализация и анализ знаний Решение задач создания интеллектуальных ИС в первую очередь наталкивается на проблему формализации знаний об объекте, среде его функционирования, целях функционирования и т.д. Одной из важнейших задач, которые необходимо решить при формализации знаний является их классификация. Можно выделить несколько классификаций знаний, построенных на основе разных признаков: 1. По жесткости : • «Жесткие» знания (позволяют получать однозначные четкие решения и рекомендации при заданных начальных условиях); • «Мягкие» знания (допускают несколько решений, нечеткие решения и т. п.). 2. По типам. В настоящее время принято выделять восемь типов знаний: • базовые элементы – объекты реального мира, которые связаны с непосредственным восприятием, не требуют обсуждения, вводятся в базу знаний как факты в том виде, в котором они получены. • утверждения и определения – базовые элементы, являющиеся их продуктами, и заранее рассматривающиеся, как достоверные. • концепции – перегруппировки и обобщения, представляющие собой продукты базовых объектов, получаемые на основе примеров, частных случаев и т.д. • отношения – элементарные свойства, которые представляют собой атрибуты базовых элементов, или отношения между концепциями, т.е. как атрибуты продуктов. • теоремы и правила перезаписи – частный случай продукционных правил с вполне определенными свойствами. • алгоритмы, необходимые для выполнения определенных задач – они связаны с со знаниями особого типа, поскольку определяемая ими последовательность действий оформляется в блок в строго необходимом порядке, в отличие от других типов знаний, где элементы могут появляться и располагаться без связи друг с другом. • стратегии и эвристики – врожденные или приобретенные правила поведения, позволяющие в данной конкретной ситуации принять решение о необходимых действиях. При формализации используют информацию в порядке, обратном тому, в котором она была получена изначально. Например, вначале была информация: какое-либо действие приводит к такому-то желаемому результату в такой-то ситуации (знание типа 4). Из этого следует, что, если необходимо в этой ситуации получить желаемый результат, то можно использовать известное из первой информации действие (знание типа 7). • метазнания – знание о знаниях всех уровней. Определяют коэффициент доверия к каждому знанию и важность каждой элементарной информации по отношению ко всему множеству знаний, вопросы организации каждого типа знаний и указания, когда и как они могут быть использованы. 3. По уровню «теоретичности» знаний о ПрО: Уровень 1. Знания о конкретных сущностях и фактах. Эти знания обычно называют данными, они хранятся в базах данных и в терминах реляционной модели называются кортежами. Например, множество эмпирических замеров двух величин, представляемых таблично. С накопления фактов или данных начинается любая система знаний. Уровень 2. Описания классов в виде правил. По мере обобщения и анализа данных выявляются эмпирические зависимости и корреляции, которые позволяют разбить множество кортежей (фактов) на классы и каждому классу сопоставить содержательное описание зависимостей и корреляций, выражаемых в виде правил вида «ЕСЛИ класс N, ТО …». Например, «ЕСЛИ у больного повышена температура, ТО вероятен воспалительный процесс». Уровень 3. Формулы, отношения, алгоритмы. Дальнейшее обобщение и формализация позволяют построить и описать единой формулой зависимость между переменными (например, написать «y=f(x)» для таблицы эмпирических замеров x и y). Формулы могут выражаться в виде алгоритмов вычисления одних величин по известным значениям других величин. Там, где нет формулы, применяется известная в реляционной модели данных схема отношения. Уровень 4. Теория, позволяющая вывести все формулы и алгоритмы уровня 3, правила уровня 2 и описать все факты уровня 1, в том числе и неизвестные факты. Теория обычно выражается совокупностью утверждений (аксиом) и правил вывода. Теория является законченным компактным описанием проблемной области, позволяющим решать в ней практические задачи. Взаимодействие уровней модели происходит следующим образом. Решение практической задачи требует знаний уровня 3, поскольку на основе теории строятся конкретные процедуры решения, в которые уже подставляются исходные данные задачи и производятся необходимые вычисления, после которых уже получается результат – факт уровня 1. В качестве иллюстрации оперирования уровнями модели знаний можно привести школьников и решаемые ими задачи. Двоечник помнит только отдельные факты (уровень 1) и новые задачи решить не может. Троечник помнит несколько правил (уровень2) и пытается подогнать их под новую задачу. Хорошист быстро вспоминает «сценарий», определяет тип задачи, получает алгоритм решения, подставляет в него исходные данные и вычисляет ответ. Это особенно ярко видно на задачах по физике, где сначала требуется вывести формулу (получить алгоритм), а потом произвести по ней вычисления. При этом физические законы играют роль «теории», а вводимая формула является процедурой уровня 3. Компетентность специалиста определяет владение в полной мере теорией, выраженной множеством эффективных сценариев. Они позволяют при минимальных вычислениях получить нужный алгоритм и произвести действия. Отличник способен решить задачу, для которой у него нет готового сценария. Этот сценарий он выводит из теории. Обучение специалистов происходит по схеме восхождения от уровня 1 до уровня 4. При этом, даже если теория в данной области отсутствует и нет четких процедур уровня 3, у экспертов формируется совокупность правил уровня 2 набор сценариев для решения классов задач (например, диагностики). Значительной долей компетенции эксперта зачастую является множество сценариев и правил, которые он формирует и применяет подсознательно, интуитивно, и не способен четко сформулировать или объяснить. Предположительно правила вида «ЕСЛИ … ТО» появляются только при попытке вербализации знаний, при объяснении и обосновании своих действий. Здесь язык мозга и язык модели знаний могут существенно различаться. Знания уровня 4 называют декларативными. Декларативные знания сами по себе мертвы, они актуализируются только при выводе из них алгоритма решения конкретных задач, т.е. при дедуктивном спуске с уровня 4. В ИС способ представления знаний характеризуется моделью представления знаний, выбор которой осуществляется инженером по знаниям на этапе построения формализованного представления Все многообразие моделей представления знаний, используемых в современной теории интеллектуальных ИС, можно разбить на два типа (рис. 2.1): логические (в основе их лежит понятие формальной системы) и эвристические (сетевые, продукционные, фреймы, нейросетевые). В логических моделях отношения, существующие между отдельными единицами знаний, выражаются только с помощью тех средств, которые представляются синтаксическими правилами используемой формальной системой. В отличие от формальных моделей эвристические модели имеют разнообразный набор средств, передающих специфические особенности той или иной ПрО. Рис. 2.1 Классификация моделей представления знаний Продукционная модель позволяет осуществлять эвристические методы вывода на правилах и может обрабатывать неопределенности в виде условных вероятностей или коэффициентов уверенности, а также выполнять монотонный или немонотонный вывод. Семантическая сеть отображает разнообразные отношения объектов. Фреймовая модель, как частный случай семантической сети, использует для реализации операционного знания присоединенные процедуры. Объектно-ориентированная модель, как развитие фреймовой модели, реализуя обмен сообщениями между объектами, в большей степени ориентирована на решение динамических задач и отражение поведенческой модели. Логическая модель предполагает унифицированное описание объектов и действий в виде предикатов первого порядка. Под предикатом понимается логическая функция на N-аргументах (признаках), которая принимает истинное или ложное значение в зависимости от значений аргументов. Отличие заключается в том, что для объектов соответствующие реляционные отношения задаются явно в виде фактов, а действия описываются как правила, определяющие логическую формулу вывода фактов из других фактов. Механизм вывода осуществляет дедуктивный перебор фактов, относящихся к правилу по принципу «сверху» - «вниз», «слева» - «направо» или обратный вывод методом поиска в глубину. Продукционные модели используются для решения более сложных задач, которые основаны на применении эвристических методов представления знаний, позволяющих настраивать механизм вывода на особенности ПрО и учитывать неопределенность знаний. Для обработки неопределенностей знаний продукционная модель использует, как правило, либо методы обработки условных вероятностей (байесовский подход), либо методы нечеткой логики. 1.4. Формальные модели представления знаний 1.4.1. Логические модели Традиционно в представлении знаний выделяют формальные логические модели, когда ПрО область или задача описывается в виде набора аксиом. Сама по себе модель неоднородна и включает в себя несколько существенно разных подходов. Некоторые из них перечислены на схеме (рис.2.2). Рис. 2.2 Формальные логические модели, используемые в системах ИИ Смысл построения любой формальной теории состоит в том, чтобы выразить мыслительные процессы формально (т. е. записать формулами). При этом необходимо, чтобы система уравнений, образуемая такими формулами, решалась так, чтобы результаты вычислений совпадали с картиной, которую мы наблюдали бы в реальном мире при практическом осуществлении тех действий, которые моделируем. Если применительно к какой-либо ПрО удастся сформулировать такие формулы и правила, то мы сможем предсказывать последствия тех или иных действий в данной ПрО без практического осуществления самих этих действий. Важно, что в процессе вычислений мы не будем думать о предметном смысле преобразований над переменными и формулами, а только о точном соблюдении формальных правил. Интерпретировать мы будем только конечные результаты. Следовательно, сам процесс формального логического вывода можно будет поручить машине. За человеком же останутся интерпретация и оценка полезности результатов. Для того чтобы задать формальную логическую теорию, необходимо определить алфавит (множество символов, используемых для записи), правила синтаксиса (правила записи формул), аксиоматику (особое подмножество формул) и правила вывода (множество отношений на множестве формул). Правила вывода должны быть заданы так, чтобы на любых исходных данных обеспечить правильность логических заключений. Алфавит и аксиоматика должны быть заданы так, чтобы гарантированно обеспечить осмысленность (семантику) получаемых заключений и промежуточных следствий. Разные логические теории имеют свои преимущества при реализации моделей в разных микромирах. Так, например, семантика силлогистики Аристотеля очень близка к естественному языку, поэтому результаты формального вывода легко интерпретировать. Выводы, получаемые на основе исчисления предикатов, уже не в полной мере совпадают с семантикой естественного языка, их труднее интерпретировать, однако модели на основе исчисления предикатов получаются гораздо более компактными. Модели на основе нечеткой логики позволяют оперировать размытыми понятиями, однако такие результаты и интерпретировать труднее. Среди формальных логических моделей логика предикатов наиболее широко используется в качестве модели представления знаний. Удобство ее использования заключается в том, что свойственный ей механизм вывода, во-первых, допускает высокую степень формализации и обладает привычными математическими свойствами и, во-вторых, может быть непосредственно запрограммирован. Логика предикатов является обобщением и расширением логики высказываний, и высказывание является центральной категорией логики предикатов. Высказыванием называют предложение, которое может принимать одно из двух значений: истина, ложь. Например, высказываниями являются предложения «скорость ветра увеличивается», «угол сноса увеличивается», «угол сноса остается неизменным» и т. п. Из нескольких высказываний можно составить более сложные, или составные, высказывания С точки зрения логики высказываний, интересен не смысл, или семантика, элементарных высказываний, а их истинность или ложность. Поэтому элементарные высказывания играют роль переменных, принимающих одно из двух значений: истина, ложь. Если известны значения элементарных высказываний (т.е. их истинность или ложность), входящих в состав какого-либо высказывания, то можно установить значение и этого высказывания. Логика предикатов имеет свой синтаксис и алфавит. Обычно алфавит состоит из символов шести типов: переменные, константы, функциональные символы, предикативные символы, логические символы (, , , , , ), вспомогательные символы (запятые, скобки и др.) Предикативные символы служат для описания свойств объектов предметной области и отношений между ними. Логические символы играют роль, аналогичную роли знаков математических действий. Четыре первых символа называют логическими, или позиционными, связками. Они имеют следующий смысл:  — «и» (конъюнкция),  — «или» (дизъюнкция),  — «не» (отрицание),  — «если..., то...» (импликация). Два последних символа являются знаками кванторов:  — квантора существования и  — квантора общности. В простейшем случае составное высказывание состоит из двух элементарных (обозначим их A и В). Из них можно составить следующие высказывания: AВ (A и B), AB (A или B), AВ (если A, то B). Высказывание AB истинно только тогда, когда истинны и А, и B. Высказывание AB истинно всегда, кроме случая, когда и А, и B — ложь. Высказывание AB истинно всегда, кроме случая, когда A — истинно, а B — ложь. Высказываниями являются выражения A и B, которые истинны при ложных исходных высказываниях, и наоборот. Зная эти правила, можно устанавливать значения более сложных высказываний. Центральной задачей логики предикатов является вывод заключения из предпосылок. Пусть, например, в качестве предпосылок используются следующие факты. 1. Угол измеряется в градусах. 2. Тангаж является углом. Из этих предпосылок следует заключение, что тангаж измеряется в градусах. Для получения этого заключения применяется логический метод представления знаний. Как видно, предпосылки являются элементарными высказываниями, и между ними нет никакой логической связи. В рамках логики высказываний заключение получить нельзя. Однако его можно получить, если разбить элементарные высказывания на еще более мелкие элементы. Рассмотрим, например, второе высказывание. Его можно разложить на части, при этом «тангаж» играет роль субъекта, а «угол» — роль свойства этого субъекта. Таким образом, «угол» является предикатом, и это обстоятельство можно передать посредством следующей записи: угол(тангаж), где «тангаж» является именем угла. Но углов много, «тангаж» — это только одно из возможных имен, в скобках могут стоять и другие имена, например, крен, снос, скольжение, курс. А это значит, что запись угол(тангаж) является частным случаем более общей записи угол(х), где х — переменная (использован символ первого типа). Первичную запись угол(тангаж) можно рассматривать как результат подстановки вместо х одного из его конкретных значений — «тангаж». Используя введенные обозначения, первую предпосылку можно записать через импликацию в следующем виде:  х(угол(х)  измеряется в градусах(х)). Выражение во внешних скобках читается следующим образом: если х угол, то х измеряется в градусах. Стоящий впереди квантор общности обобщает это свойство на все углы. «Тангаж» представляет собой одно из значений переменной х. Обозначим его через а (символ второго типа). «Угол» как предикат обозначим через р (символ четвертого типа). Еще одним предикатом является свойство «измеряется в градусах»; обозначим его через q. Тогда первая предпосылка примет вид:  х(р(х)  q(x)), а вторая предпосылка — вид р(а). Подставляя значение х=а и последнее выражение в предыдущее, получаем  х(р(а)  q(a)), откуда следует искомое заключение q(a), что означает «тангаж измеряется в градусах». Классическая логическая модель имеет ограниченное применение, так как предъявляет очень высокие требования к ПрО, заключающиеся в точном определении значений всех ее параметров. Это не всегда возможно, поскольку нечеткость представляет собой всеобщее свойство реального мира в отличие от строгой четкости абстрактных построений классической математики. Источниками неопределенности могу являться: невозможность сколь угодно точного измерения физических величин; невозможность полного и четкого описания многих физических объектов и ситуаций; неточность исполнительских действий, которые зачастую не достигают цели; недостаточность размерности модели, не позволяющая отразить все значимые свойства ПрО и т.п. Рассмотренное свойство объективной нечеткости реального мира необходимо дополнить еще и наличием субъективности оценок различных его явлений, даваемых различными экспертами. Вместе с тем, поразительным свойством человеческого интеллекта является, способность принимать рациональные решения в обстановке неполной и нечеткой информации. Все эти обстоятельства и обусловили использование в качестве модели представления знаний аппарат теории так называемых нечетких (размытых) множеств и нечеткой (fuzzy) логики. Связь между интеллектуальной ИС и теорией нечетких множеств (НМ) является вполне естественной, если принять гипотезу о том, что «человек мыслит не числами, а нечеткими понятиями». В действительности, большинство понятий, которые используют люди в повседневной жизни, являются нечеткими. Когда в соответствии с инструкцией по использованию клея мы сильно прижимаем друг к другу склеиваемые детали или согласно рецепту ставим варить блюдо на медленный огонь – мы выполняем нечеткие инструкции, сформулированные с помощью естественного языка. Удобным способом математического описания неформальных понятий, подобных упомянутым выше, являются нечеткие множества. Нечетким множеством А на множестве U называется совокупность пар вида A={(u, A(u))}, где uU, а A(u) –функция принадлежности НМ A, A: U[0,1], U – обычное (универсальное) множество (УМ), uU A(u) определяет степень принадлежности u множеству A. Например, поименованное НМ A – «день» (в смысле светлое время суток) может быть представлено функцией принадлежности (рис. 2.3), определенной на УМ, представляющем временной интервал T=[0,24], выраженный в часах. Полагая, что день начинается в 8 часов утра и заканчивается в 18 часов, присвоим для этого временного интервала постоянное значение функции принадлежности A(t)=1, где tT. Положим также, что ночь начинается в 20 часов и заканчивается в 6 часов утра. Другими словами, на временных интервалах от 0 до до 6 часов и от 20 до 24 часов A(t)=0. От 6 до 8 часов утра и от 18 до 20 часов значения функции принадлежности соответствующих моментов времени к множеству "день" будут лежать в интервале 0 < A(t) < 1. Рис. 2.3 Функция принадлежности НМ «день» Нечеткое множество А называется нормальным, если верхняя граница функции принадлежности НМ А sup(A(u))=1. В противном случае оно называется субнормальным. В данном примере НМ «день» - нормальное. Носителем suppА НМ A называется обычное множество вида suppA:={uU | A(u) > 0}. В рассматриваемом примере носитель НМ «день» представляет интервал - suppA=[8, 18]. Нечетким отношением (бинарным) R на УМ U=U1xU2 называется нечеткое подмножество декартова произведения U1xU2, которое характеризуется функцией принадлежности R(x,y), что U1xU2[0,1], где xU1, yU2. Значение R(x,y) принимается как субъективная мера выполнения отношения xRy. Например, нечеткое отношение R: , при достаточно больших k можно интерпретировать как «x и y близкие друг к другу числа». Целью введения НМ чаще всего является формализация неточных, расплывчатых понятий, выражаемых на естественном языке. Например, понятие «скорость» может характеризоваться несколькими расплывчатыми категориями (термами) – «медленная», «средняя», «большая». Эту формализацию можно реализовать, воспользовавшись конструкцией лингвистической переменной. Лингвистической переменной (ЛП) называется кортеж вида <,U,T,G,M>, где  - наименование ЛП; T – множество значений ЛП (терм-множество), представляющее собой названия нечетких переменных, областью определения которых является УМ U, T называется базовым терм-множеством ЛП; G – синтаксическая процедура, позволяющая оперировать элементами терм-множества Т, в частности генерировать новые термы; M – семантическая процедура, позволяющая превратить, каждое новое значение ЛП, образуемое процедурой G, в нечёткую переменную, т.е. сформировать соответствующее НМ. Нечеткими высказываниями называются высказывания вида <β есть α>, где β – наименование ЛП, отражающей некоторый объект или параметр ПрО, а α – наименование нечеткой переменной, которая является нечеткой оценкой β. Например, «скорость есть медленная». Логическая модель знаний, базирующаяся на логико-лингвистических методах, предполагает, что ПрО описывается на близком к естественному языке в терминах ЛП. Переменные ПрО рассматриваются как ЛП, а качественное описание процессов задается совокупностью высказываний и правил следующего вида: Li: Если Ai1 и/или Аi2 и/или …. и/или Aim то Bi1 и/или … и/или Bin, где Aij, i=1,…k, j=1,…m – нечеткие высказывания, определенные на значениях входных ЛП, а Bij, i=1…k, j=1…n нечеткие высказывания, определенные на значениях выходных ЛП. Например, Если «скорость есть большая» и «дистанция до препятствия есть малая» то «торможение есть резкое». Нечетким логическим выводом называется получение заключения в виде нечеткого множества, соответствующего текущим значениям входных переменных с использованием нечеткой базы знаний. Модель знаний на основе ЛП, нечетких правил и нечеткого логического вывода позволяет учесть объективные и субъективные неопределенности описания ПрО, она проще для понимания, чем формальная математическая модель на базе исчисления предикатов, дифференциальных уравнений или разностных уравнений. 1.4.2. Семантические сети Термин семантическая означает «смысловая», а семантика – это наука, устанавливающая отношения между символами и объектами, которые они обозначают, т.е. наука, определяющая смысл знаков. Семантическая сеть (СС), – это ориентированный граф, вершины которого – понятия, а дуги – отношения между ними. Любую ПрО можно характеризовать совокупностью объектов, их свойств и отношений между ними. Постигая окружающий мир, осуществляя свою деятельность в нем, человек должен уметь моделировать и описывать этот мир. При отображении внешнего мира, при его описании человек выделяет в нем конечный набор отношений. Эти отношения связывают между собой отдельные элементы модели внешнего мира. Важным шагом на пути выявления структуры, присущей знаниям, является построение моделей, в которых в явной форме выделены объекты, образующие эту структуру. В основе этих моделей лежит понятие сети, состоящей из вершин, или узлов, соединенных дугами. С вершинами этой сети сопоставляются понятия (объекты, события, процессы, явления и др.), а с дугами – связи, или отношения, существующие между этими понятиями. В качестве понятий обычно выступают абстрактные или конкретные объекты, а отношения – это связи типа: «это» (AKO – «A Kind Of», «Is»), «имеет частью» (has part), «принадлежит» и др. СС с одной стороны, имитируют естественное понимание языка человеком, а с другой стороны, придают фактическим знаниям графовую структурированную организацию, они представляют собой так называемые ориентированные графы. Построение СС как графа помогает процессу осмысления знаний, способствует их конкретизации, выявлению противоречий, обнаружению недостающей информации и т.п. Вначале СС и использовались в психологии для моделирования долговременной памяти человека. И только затем они перешли в инженерию знаний в качестве одного из основных методов представления знаний в системах ИИ. Характерной особенностью СС является обязательное наличие трех типов отношений: • класс – элемент класса (корабль – фрегат) • свойство – значение (полное водоизмещение – 4035т) • пример элемент класса (фрегат – «Адмирал Григорович») Первоначально СС были разработаны для анализа естественных языков и построения психологических моделей человеческой памяти (задача автоматического перевода — положение Аристотеля о том, что «человек мыслит на языке», задача подбора синонимов к заданному слову и др.). На этом этапе считалось, что в предложении есть некая «центральная тема», «раскрутив» которую, машина может «понять» смысл (семантику) предложения. Любой фрагмент сети, например, одна вершина, две вершины и соединяющие их дуги, называют подсетью (рис. 2.4). Логический вывод (поиск решения) на СС заключается как раз в том, чтобы найти или сконструировать подсеть, удовлетворяющую некоторым условиям. Для того чтобы формализовать этот процесс, вводят типизацию СС и затем разрабатывают методы решения для сетей конкретного вида (на основе анализа математических свойств отношений, входящих в сеть). Рис. 2.4 Семантическая сеть «корабль» и подсеть «двигатель передает усилие на гребной винт» Классификацию СС проводят по типам отношений между понятиями. По количеству типов отношений: • Однородные (с единственным типом отношений); • Неоднородные (с различными типами отношений). По типам отношений: • Бинарные (в которых отношения связывают два объекта); • N-арные (в которых есть специальные отношения, связывающие более двух понятий). Наиболее часто в СС используются следующие отношения: • связи типа «часть-целое» («класс-подкласс», «элемент-множество» и т.п.); • функциональные связи (определяются обычно глаголами «производит», «влияет» и т.п.); • количественные (больше, меньше, равно и т.п.); • пространственные (далеко от, близко от, за, под и т.п.); • временные (раньше, позже, в течение и т.п.); • атрибутивные связи (имеет свойство, иметь значение и т.п.); • логические связи (И, ИЛИ, НЕ) и др. В качестве примера рассмотрим, как с помощью СС представить следующее определение: «Угловая скорость разворота  в горизонтальной плоскости – это кинематическая величина, равная производной от угла курса  летательного аппарата, отсчитываемого от оси х, по времени». Соответствующая сеть показана на рис. 2.5. В этом примере передаются отношения «абстрактное – конкретное», свойства объектов, их функциональные связи. Рис. 2.5 Определения угловой скорости с помощью СС. В общем случае СС должна обеспечивать следующие функции: хранение сведений о понятиях и связях между ними; возможность поиска понятий по заданным характеристикам (по связям с другими понятиями); возможность пополнения и корректировки знаний системы в процессе обучения (ввод новых понятий, установление новых связей, удаление существующих понятий и связей); возможность осуществления процедуры обобщения и конкретизации знаний; отражение иерархичности предметных знаний; понятность для эксперта – специалиста в ПрО. Одним из достоинств СС является возможность отображения структуры, присущей знаниям. Особенностью СС является наглядность знаний как системы. Каждый отдельный элемент знания рассматривается как некое отношение между понятиями, и существующие внутри системы структуры, или модули, знаний можно наращивать независимо, с сохранением их модульности. В то же время, все знания, отвечающие одному понятию, могут быть изображены в виде отношений между различными вершинами, относящимися к его пирамиде. Это дает основание говорить о легкости понимания такого представления. Однако при увеличении номенклатуры понятий (объектов) СС, увеличении объема знаний снижается ее однородность и исчезает основное преимущество СС – наглядность. Еще одним недостатком этой модели является сложность организации процедуры вывода на СС. Известны примеры использования СС в качестве языка представления знаний в экспертных системах, таких как PROSPECTOR, CASNET, TORUS. 1.4.3. Фреймы Фрейм (frame (англ.) – каркас, рамка) – это абстрактный образ для представления некоего стереотипа восприятия. Этот термин предложил американский ученый Марвин Минский для обозначения структуры знаний для восприятия пространственных сцен. В психологии и философии используется понятие абстрактного образа. Любое представление о предмете, объекте, стереотипной ситуации у человека всегда обрамлено (отсюда — «рамка») характеристиками и свойствами объекта или ситуации. Например, слово «комната» порождает у слушателя образ «жилого помещения с четырьмя стенами, полом, потолком, окнами и дверью». Из этого описания ничего нельзя убрать, не изменив самого образа (убрав окна получим другой фрейм – чулан). В этом описании есть незаполненные поля (слоты) – это значения некоторых атрибутов – количество окон и дверей, высота потолка, цвет стен, покрытие пола и др. В теории фреймов такой образ называется фреймом комнаты – формализованная модель для отображения образа. Модель фрейма является достаточно универсальной и позволяет отобразить все многообразие знаний о мире через: • фреймы- структуры, используемые для отображения объектов и понятий (корабль, шторм, дождь); • фреймы- роли (командир, старпом, матрос); • фреймы-сценарии (поход, тревога, торпедная атака) и др. Традиционно структура фрейма может быть представлена списком свойств: N [, ,…, ], где N — имя фрейма; тройка — его i-й слот, ni — имя слота, gi — его тело, pi – имя процедуры. Эту же запись можно представить в виде таблицы 2.1: Таблица 2.1 Имя фрейма имя слота указатель наследования указатель атрибутов слота тип данных значение слота присоединенная процедура Слот 1 Слот 2 … Слот n Именем фрейма может быть любой идентификатор, и оно должно быть единственным в данной системе фреймов. Имя слота — также идентификатор, но единственный в данном фрейме. Таким образом, по сути дела, фрейм — это имеющий имя набор слотов, которые и содержат все необходимые знания. В общем случае слот имеет указанную выше структуру, в частных случаях некоторые элементы этой структуры могут быть опущены. Указатель наследования служит для передачи иерархических отношений (по вертикали), как отношений последовательности, так и отношений «абстрактное - конкретное», и содержит имя фрейма, находящегося в иерархической структуре на следующем верхнем уровне. Фрейм, расположенный на более высоком уровне, называют фреймом-родителем. В свою очередь, фрейм, расположенный на более низком уровне, называют дочерним фреймом. Слоты фреймов раскрывают их содержание. В качестве атрибутов слотов могут выступать тексты, числа, процедуры, указатели (метки) на определенные блоки информации из общей базы знаний системы (т.е. компьютерной программы) и т.п. Атрибуты слота образуют базу знаний о ПрО. Указатели типа данных описывают типы переменных, используемых в слоте. Обязательной компонентой слота является его значение. Как правило, значение слота — это предметное знание, ради которого данный слот присутствует в данном фрейме. В качестве значения слотов могут выступать ссылки на другие фреймы или на другие слоты того же самого фрейма, а также система имен слотов фреймов более низкого иерархического уровня, что называют свойством вложенности. Указание на другие фреймы устанавливает тем самым связь между двумя фреймами; так образуются сети фреймов. Значение слота — единственный его элемент, который может изменяться в процессе работы системы. С каждым слотом фрейма можно связать любое число присоединенных процедур. Они могут работать как безусловно, так и по какому-либо условию. Безусловную процедуру называют демон, она выполняется всегда, когда слот становится активным, т.е. когда при работе системы на этот слот передается управление. Т.е. с каждым фреймом ассоциирована информация разных видов. Одна ее часть указывает, каким образом следует использовать данный фрейм, другая — что предположительно может повлечь за собой его выполнение, третья — что следует предпринять, если эти ожидания не подтвердятся. На практике наибольшее распространение модель, основанная на фреймах, получила в объектно-ориентированном программировании и теории объектных баз данных. Современное понятие объекта языка программирования довольно точно соответствует классическому понятию фрейма. Основными свойствами фреймов, используемыми в современных языках, являются: инкапсуляция, наследование и полиморфизм объектов. Инкапсуляция — единство данных и методов в рамках объекта. Наследование — способность объекта пользоваться методами и данными, определенными в рамках одного из его предков. Полиморфизм — способность объекта в разные моменты времени вести себя по-разному, то как объект своего типа, то как объект типа любого из предков. Различают фреймы-образцы (прототипы, абстрактные классы), хранящиеся в базе знаний, и фреймы-экземпляры (объекты), которые создаются для отображения реальных ситуаций на основе поступающих данных. Таблица 2.2 Имя фрейма: подвижный технический объект Имя слота Значение слота Присоединенная процедура Тип слота Предок объект нет АКО Тип объекта технический нет Назначение перемещение в пространстве Таблица 2.3 Имя фрейма: абстрактный корабль Имя слота Значение слота Присоединенная процедура Тип слота Предок подвижный технический объект нет АКО Назначение перемещение экипажа и вооружения в пространстве нет Положение x, y, z плыть Ограничения скорости 50 км/ч нет В сети фреймов понятие «абстрактный корабль» наследует свойства фреймов «подвижный технический объект», который находятся на более высоком уровне иерархии. На вопрос: «Способен ли корабль перемещаться в пространстве?» следует ответ: «Да», так как этим свойством обладает класс-предок. Наследование свойств может быть частичным, как свойство «назначение». Свойство вложенности означает возможность иметь в качестве значений слотов ссылки на другие фреймы и на другие слоты того же самого фрейма, Это свойство обеспечивает фреймовому методу представления знаний структурированность и связность знаний. Наличие имен фреймов и имен слотов означает, что знания, хранимые во фреймах, имеют характер отсылок и тем самым внутренне интерпретированы. Возможность размещения в слотах либо указателей процедур (значение слота), либо присоединенных процедур обеспечивает отсылку к этим процедурам и позволяет активизировать программы на основе имеющихся знаний. Таким образом, фреймы удовлетворяют четырем основным признакам знаний — интерпретируемости, структурированности, связности и активности. В системах, основанных на фреймовом представлении знаний, основной операцией является поиск по образцу [3]. Образец представляет собой фрейм-прототип, в котором заполнены не все структурные единицы, а только те, по которым среди фреймов, хранящихся в памяти компьютера, будут отыскиваться нужные фреймы. Образец может, например, содержать имя фрейма, а также имя некоторого слота во фрейме с указанием значения слота. Процедура поиска по образцу должна обеспечить выборку из памяти компьютера всех фреймов, в которых содержится слот с таким именем и таким значением слота, как у образца. Основными преимуществами фреймов как модели представления знаний является ее гибкость и наглядность, а также то, что она отражает концептуальную основу организации памяти человека. Использование фреймов в фундаментальных науках дает возможность формирования более строгого понятийного аппарата. Для описательных наук фреймы — это один из немногих способов их формализации, создания понятийного аппарата. В общем случае, модель представления знаний в интерпретации фреймов строится в виде сети, то есть системы определенным образом взаимосвязанных фреймов. Тип связи имеет характер переходов, подобен гипертексту. С помощью иерархических сетей можно представить любые сущности и отношения без какого-либо ограничения на их количество. Фреймовая модель позволяет наглядно систематизировать иерархию объектов ПрО. Модель реализована во многих языках программирования и специальных языках представления знаний (FRL — Frame Representation Language), успешно использована в ряде известных экспертных систем: ANALYST, МОДИС и др. К недостаткам модели следует отнести, по-видимому, некоторые затруднения, возникающие при обмене большими порциями данных между двумя объектами. Собственно, фрейм в изначальном классическом виде вообще не предполагает никакого обмена данными. 1.4.4. Продукционная модель Для того чтобы реализовать механизм логического вывода в базах знаний необходим специальный машинно-ориентированный язык. Одним из наиболее простых и эффективных машинно-ориентированных языков для описания знаний являются правила продукций. Полная форма продукционного правила имеет вид : (i); Q; P; A→B; N, где • i – имя продукции (идентификатор правила); • Q – сфера применения продукции; • P – условие применимости ядра продукции (предикат); • A→B – ядро продукции (Если А <предпосылка> то В <заключение>); • N – постусловие продукции; Под предпосылкой (антецедентом) понимается некоторое предложение-образец, по которому осуществляется поиск в базе знаний, а под заключением (консеквентом) — действия, выполняемые при успешном исходе поиска. Они могут быть промежуточными, выступающими как условия, и целевыми (терминальными), завершающими работу системы. Постусловие описывает действия и процедуры, которые необходимо выполнить после реализации действия. Например, после покупки некоторой вещи в магазине необходимо в описи товаров уменьшить количество вещей такого типа на единицу. Продукционная система, таким образом, представляет собой базу знаний (правил продукций) и машину вывода — специальную программу «сопоставления по образцу». В зависимости от того, какие использованы продукции и каковы правила вывода, получаются различные продукционные системы. Чаще всего вывод на базе знаний бывает прямой (от данных к поиску цели) или обратный (от цели для ее подтверждения – к данным). Данные – это исходные факты, хранящиеся в базе фактов, на основании которых запускается машина вывода (интерпретатор правил), перебирающий правила из продукционной базы знаний. Ядра продукций можно классифицировать по различным признакам. Прежде всего различают детерминированные и недетерминированные ядра. При актуализации детерминированного ядра и выполнимости условия правая часть (действие) выполняется с неизбежностью (и степенью уверенности), в недетерминированных ядрах — с некоторой вероятностью. Если А, то, возможно, В с вероятностью а. Если А, то В с коэффициентом уверенности а (детерминированная продукция). Продукции также могут быть однозначными и альтернативными. Для альтернативных правил в правой части ядра указываются «альтернативные возможности выбора», которые оцениваются весами выбора — (а1,. . . , аn). Если А, то «чаще всего» надо делать B1, «реже» В2 (вероятностные оценки). Если А то В1 с уверенностью а1, В2 с уверенностью а2, … Вi с уверенностью аi …. В качестве а1,..ai,., аn используются вероятностные оценки, лингвистические оценки, экспертные оценки и т. п. При выполнении условия применимости ядер продукции для группы продукций возникает дилемма выбора той продукции, которая в данной ситуации будет активизирована. Решение этой задачи возлагается на систему управления системой продукций. Если ИС реализована на ЭВМ с параллельной архитектурой, то из фронта готовых продукций может выбираться не одна продукция, а столько, сколько параллельных ветвей может одновременно в данной ситуации выполнять ЭВМ. Рис. 2.6. Схема ЭС на основе продукционных правил. Продукционная модель чаще других применяется в промышленных экспертных системах (ЭС). Она привлекает разработчиков своей наглядностью, высокой модульностью, легкостью внесения дополнений и изменений и простотой механизма логического вывода. Имеется большое число программных средств, позволяющих реализовать продукционный подход: языки Prolog, Lisp14, LOGO15, OPS; оболочки ЭС – CLIPS и др. Типичная схема ЭС на базе продукционных правил приведена на рис.2.6. Продукционные модели имеют, по крайней мере, два серьезных недостатка. При большом числе продукций становится сложной проверка непротиворечивости системы продукций. Это заставляет при добавлении новых продукций тратить много времени на проверку их непротиворечивости уже имеющимся правилам. Системе присуща недетерминированность (неоднозначность выбора выполняемой продукции из фронта активизируемых продукций), возникают принципиальные трудности при проверке корректности работы системы. Рассмотрим простейший пример вывода на продукционных правилах с помощью интерпретатора правил. Допустим, что в нашем распоряжении имеется база данных (фактов), содержащая 8 фактов и база знаний, содержащая 5 правил: ФАКТЫ Ф1: «есть рукоятка» Ф2: «забиваем гвозди» Ф3: «колем дрова» Ф4: «ремонтируем» Ф5: «топим баню» Ф6: «инструмент» Ф7: «молоток» Ф8: «колун» ПРАВИЛА Правило 1: Если «есть рукоятка» и «забиваем гвозди» то «молоток» Правило 2: Если «есть рукоятка»и «колем дрова» то «колун» Правило 3: Если «ремонтируем» то «забиваем гвозди» Правило 4: Если «топим баню» то «колем дрова» Правило 5: Если «инструмент» то «есть рукоятка» Начальные факты (интерпретация вопроса: «какой инструмент нужен для того, чтобы истопить баню»): Ф6: «инструмент» Ф5: «топим баню» Интерпретатор правил (циклический перебор правил) Первый цикл перебора правил: Правило 1: предпосылка – false (отсутствие необходимых фактов) Правило 2: предпосылка – false Правило 3: предпосылка – false Правило 4: предпосылка – true, Вывод – новый факт Ф3: «колем дрова» Правило 5: предпосылка – true, Вывод – новый факт Ф1: «есть рукоятка» Второй цикл перебора правил: Правило 1: предпосылка – false Правило 2: предпосылка – true, Вывод – новый факт Ф8: «колун» Правило 3: предпосылка – false Третий цикл перебора правил: Правило 1: предпосылка – false Правило 3: предпосылка – false Окончание работы интерпретатора правил, ввиду отсутствия новых фактов после окончания третьего цикла перебора правил. Результат: (новые факты): Ф1: «есть рукоятка» Ф3: «колем дрова» Ф8: «колун» Объяснение ответа: «для того, чтобы истопить баню нужно наколоть дрова с помощью колуна». 2. РАЗРАБОТКА ПРОТОТИПА ЭС В СРЕДЕ CLIPS 2.1. Общие сведения о CLIPS CLIPS (C Language Integrated Production System) – программная среда для разработки экспертных систем (ЭС). CLIPS использует продукционную модель представления знаний и поэтому содержит три основных элемента: список фактов, базу знаний, блок вывода. В CLIPS используется оригинальный LISP-подобный язык программирования, ориентированный на разработку ЭС. В настоящее время CLIPS представляет собой современный инструмент, предназначенный для создания ЭС (expert system tool). CLIPS состоит из интерактивной среды — экспертной оболочки со своим способом представления знаний, гибкого и мощного языка и нескольких вспомогательных инструментов. Благодаря доброй воле своих создателей, CLIPS является абсолютно свободно распространяемым программным продуктом (страница проекта в Internet: clipsrules.sourceforge.net). 2.2. Программирование в CLIPS CLIPS предоставляет три основных элемента для написания программ: простые типы данных; функции для манипулирования данными; конструкции для пополнения базы знаний. 2.2.1. Простые типы данных Для представления информации в CLIPS предусмотрено восемь простых типов данных: float, integer, symbol, string, external-address, fact-address, instance-name и instance-address. Для представления числовой информации используются типы float и integer, символьной - symbol и string. При записи числа могут использоваться только цифры (0-9), десятичная точка (.), знак (+) или (-) и (е) при экспоненциальном представлении. Число сохраняется либо как целое, либо как действительное. Любое число, состоящее только из цифр, перед которыми может стоять знак, сохраняется как целое (тип integer представляется внутри CLIPS как тип языка С long integer). Все остальные числа сохраняются как действительные (float - С double float). Количество значащих цифр зависит от аппаратной реализации. В этой же связи могут возникать ошибки округления. Как в любом языке программирования, особенную осторожность необходимо проявлять при сравнении чисел с плавающей точкой, а также при сравнении с ними целых чисел. Примеры целых чисел: 237 15 +12 -32 Примеры чисел с плавающей точкой: 237е3 15.09 +12.0 -32.3е-7 Последовательность символов, которая не удовлетворяет числовым типам, обрабатывается как тип данных symbol. Тип данных symbol в CLIPS - последовательность символов, состоящая из одного или нескольких любых печатных символов кода ASCII. Как только в последовательности символов встречается символ-разделитель, symbol заканчивается. Следующие символы служат разделителями: любой непечатный ASCII символ (включая пробел, символ табуляции, CR, LF), двойные кавычки,"(",")". "&". "I". "<",Символы-разделители не могут включаться в symbol за исключением символа "<", который может быть первым символом в symbol. Кроме того, symbol не может начинаться с символа "?" или последовательности символов "S?", по­скольку эти символы зарезервированы для переменных. Заметим, что CLIPS раз­личает регистр символов. Ниже приведены примеры выражений символьного типа: Foo Hello B76-HI bad_value 127А 742-42-42 @+=-% Search Тип данных string - это последовательность символов, состоящая из нуля и более печатных символов и заключенная в двойные кавычки. Если внутри строки встречаются двойные кавычки, то перед ними необходимо поместить символ (\). То же справедливо и для самого (\). Несколько примеров: "foo" "a and b" "1 number" "a\"quote" Отметим, что строка "abed" не тоже самое, что abed. Они содержат одинаковые наборы символов, но являются экземплярами различного типа. 2.2.2. Функции Под функцией в CLIPS понимается фрагмент исполняемого кода, с которым связано уникальное имя и который возвращает полезное значение или имеет полезный побочный эффект (например, вывод информации на экран). Существует несколько типов функций. Пользовательские и системные функции - это фрагменты кода, написанные на внешних языках (например, на С) и связанные со средой CLIPS. Системными называются те функции, которые были определены изначально внутри среды CLIPS. Пользовательскими называются функции, которые были определены вне CLIPS. Хотя CLIPS и не ориентирован на численные вычисления, в нем предусмотрен ряд стандартных арифметических и математических функций. Среди них: Таблица 5.1 + Сложение - Вычитание * Умножение / Деление * * Возведение в степень Abs Определение абсолютного значения Sqrt Вычисление квадратного корня Mod Взятие по модулю Min Нахождение минимума Max Нахождение максимума Конструкция deffunction позволяет пользователю определять новые функции непосредственно в среде CLIPS с использованием синтаксиса CLIPS. Функции, определенные таким образом, выглядят и работают подобно остальным функциям, однако они выполняются не напрямую, а интерпретируются средой CLIPS. Вызовы функций в CLIPS имеют префиксную форму: аргументы функции могут стоять только после ее названия. Вызов функции начинается с открывающейся скобки, за которой следует имя функции, затем идут аргументы, каждый из которых отделен одним или несколькими пробелами. Аргументами функции могут быть данные простых типов, переменные или вызовы других функций. В конце вызова ставится закрывающаяся скобка. Ниже приведены примеры вызовов функций: (+ 3 4 5) (* 5 6.0 2) (* 8 (+ 3 (* 2 3 4) 9) (* 3 4)) 2.2.3. Конструкции В CLIPS существует несколько описывающих конструкций: defmodule, defrule, deffacts, deftemplate, defglobal, deffunction, defclass, definstances, defmessage-handler, defgeneric. При записи все они заключаются в скобки. Определение конструкции отличается от вызова функции главным образом по производимому эффекту. Обычно вызов функции оставляет состояние среды CLIPS без изменений (за рядом исключений, когда речь идет о функциях сброса, очистки, открытия файла и т.п.). Определение конструкции, напротив, в точности направлено на изменение состояния среды путем внесения изменений в базу знаний CLIPS. В отличие от функций конструкции никогда не возвращают значений. Все конструкции (за исключением defglobal) позволяют размещать комментарии сразу вслед за именем конструкции. Кроме того, комментарии могут вставляться в код CLIPS при помощи точки с запятой (;). Все, что следует за (;) до конца строки, будет игнорироваться CLIPS. Если (;) стоит первым символом в строке, то вся строка считается комментарием. 5.2.3.1. Факты Факты являются одной из основных форм представления информации в системе CLIPS. Каждый факт представляет фрагмент информации, который был помещен в текущий список фактов, называемый fact-list. Факт представляет собой основную единицу данных, используемую правилами. Количество фактов в списке и объем информации, который может быть сохранен в факте, ограничивается только размером памяти компьютера. Если при добавлении нового факта к списку обнаруживается, что он полностью совпадает с одним из уже включенных в список фактов, то эта операция игнорируется (хотя такое поведение можно изменить). Факт может описываться индексом или адресом. Всякий раз, когда факт добавляется (изменяется), ему присваивается уникальный целочисленный индекс. Индексы фактов начинаются с нуля и для каждого нового или измененного факта увеличиваются на единицу. Каждый раз после выполнения команд reset и clear выделение индексов начинается с нуля. Факт также может задаваться при помощи адреса. Адрес факта может быть получен путем сохранения возвращаемого значения команд, которые возвращают в качестве результата адрес факта (таких как assert, modify и duplicate), или путем связывания переменной с адресом факта в левой части правила (см. далее). Идентификатор факта - это короткая запись для отображения факта на экране. Она состоит из символа f и записанного через тире индекса факта. На­пример, запись f-10 служит для обозначения факта с индексом 10. Существует два формата представления фактов: позиционный и непозиционный. Позиционные факты состоят из выражения символьного типа, за которым следует последовательность (возможно, пустая) из полей, разделенных пробелами. Вся запись заключается в скобки. Обычно первое поле определяет "отношение", которое применяется к оставшимся полям. Например: (the pump is on) (altitude is 10000 feet) (grocery_list bread milk eggs) Поля в позиционных фактах могут быть любого простого типа (за исключением первого поля, которое всегда должно быть типа symbol), на порядок полей также не накладывается никаких ограничений. Следующие символьные выражения зарезервированы и не должны использоваться как первое поле любого факта (позиционного или нет): test, and, or, not, declare, logical, object, exists и for all. Для того чтобы обратиться к информации, содержащейся в позиционном факте, пользователь должен знать не только какие данные содержатся в факте, но и то, в каком поле они хранятся. Непозиционные (шаблонные) факты дают возможность пользователю абстрагироваться от структуры факта, задавая имена каждому из полей факта. Для задания шаблона, который затем может использоваться при доступе к полям по именам, используется конструкция deftemplate. Эта конструкция подобна структуре или записи в языках программирования С и Паскаль. Конструкция deftemplate позволяет наряду с определением именованных полей, или слотов, вводить имя шаблона. В отличие от позиционных фактов слоты шаблонного факта могут быть ограничены по типу, значению, числовому диапазону. Кроме того, для любого слота можно определить значения по умолчанию. Слот состоит из открывающейся скобки, за которой следует имя слота, полей (могут отсутствовать) и закрывающейся скобки. Заметим, что слоты не могут использоваться в позиционных фактах, так же как позиционные поля не могут использоваться в шаблонных фактах. Общая структура конструкции deftemplate такова: (deftemplate ) (slot-1) (slot-2) … (slot-N) Далее приведен пример шаблона с заданными для слотов значениями по умолчанию: (deftemplate prospect) (slot name (default ?DERIVE) (slot assets (default rich) (slot age (default 80))) Шаблонные факты отличаются от позиционных по первому полю в факте. Первое поле всех фактов должно быть типа symbol, но если это символьное выражение соответствует имени шаблона, то этот факт - шаблонный. За первым полем шаблонного факта следует список из нуля или более слотов. Как и позиционные, шаблонные факты заключаются в скобки. Порядок следования слотов в шаблонном факте не важен. Далее приведено несколько примеров шаблонных фактов: (client (name "Joe Brown") (id X9345A)) (point-mass (x-velocity 100) (y-velocity -200)) (class (teacher "Martha Jones") (#-students 30) (room "37A")) (grocery-list (#-of-items 3) (items bread milk eggs)) Факты могут добавляться к списку фактов (с помощью команды assert), удаляться из него (с помощью команды retract), изменяться (с помощью команды modify) и дублироваться (с помощью команды duplicate) самим пользователем или программой. Например: (assert (light green)) Кроме того, конструкция deffacts позволяет определить множество ис­ходных или априорных знаний в виде набора фактов. Например: (deffacts walk "Some facts about walking" (status walking) (walk-sign walk)) Когда производится сброс состояния среды CLIPS (с помощью команды reset) все факты, описанные в конструкции deffacts, добавляются к списку фактов. Кроме того, по этой команде в список фактов заносится исходный факт (initial-fact). Этот факт включается в список фактов всегда с идентифи­катором f-0. Его назначение будет рассмотрено в следующем пункте. 5.2.3.2. Правила Одним из основных методов представления знаний в CLIPS являются правила. Правила используются для представления эвристик, определяющих ряд действий, которые необходимо выполнить в определенной ситуации. Разработчик ЭС определяет совокупность правил, которые используются совместно для решения проблемы. Правило состоит из двух частей: антецедента (условия), который является аналогом условия в if-then операторе и записывается слева, и консеквента (заключения), который является аналогом then части этого оператора и записывается справа. Левая часть правила представляет собой ряд условий, которые должны выполняться, чтобы правило было применимо. В CLIPS принято считать, что условие выполняется, если соответствующий ему факт присутствует в списке фактов. Одним из типов условных элементов может быть образец. Образцы состоят из набора ограничений, которые используются для описания того, ка­кие факты удовлетворяют условию, определяемому образцом. Процесс сопоставления фактов и образцов выполняется блоком вывода CLIPS, который автоматически сопоставляет образцы, исходя из текущего состояния списка фактов, и определяет, какие из правил являются применимыми. Если все условия правила выполняются, то оно активируется и помещается в список активированных правил. Если левая часть правила пуста, то для его активации необходимо наличие в списке фактов исходного факта (initial-fact). Такие безусловные правила часто используются для того, чтобы инициировать работу программы. Поэтому перед запуском таких программ необходимо произвести сброс состояния среды CLIPS. Правая часть правила представляет собой совокупность действий, которые должны быть выполнены, если правило применимо. Действия, описанные в применимых правилах, выполняются тогда, когда блок вывода CLIPS получает команду начать выполнение применимых правил. Если существует множество применимых правил, то для того, чтобы выбрать правило, действия которого должны быть выполнены, блок вывода использует стратегию разрешения конфликтов. Действия, описанные в выбранном правиле, выполняются (при этом список применимых правил может измениться), а затем блок вывода выбирает другое правило и т.д. Этот процесс продолжается до тех пор, пока не остается ни одного применимого правила, т.е. пока список активированных правил не окажется пуст. Во многом правила похожи на операторы типа if-then процедурных языков программирования. Однако условие if-then оператора в процедурном языке проверяется только тогда, когда программа передает ему управление. С правилами ситуация иная. Блок вывода постоянно отслеживает все правила, условия которых выполняются, и, таким образом, правило может быть выполнено в любой момент, как только оно становится применимым. В этом смысле правила подобны обработчикам исключительных ситуаций в процедурных языках. Для определения правил используется конструкция defrule: (defrule rule_name "optional_comment" (patten_1) (patten_2) . . . (patten_N) => (action_1) (action_2) . . . (action_M)) Например: (defrule take-a-vacation (work done) (money plenty) (reservations made) => (printout t "Let's go!" crlf)) 5.2.3.3. Переменные Как и в других языках программирования, в CLIPS для хранения значений используются переменные. В отличие от фактов, которые являются статическими, или неизменными, содержание переменной динамично и изменяется по мере того, как изменяется присвоенное ей значение. Идентификатор переменной всегда начинается с вопросительного знака, за которым следует ее имя. В общем случае формат переменной выглядит следующим образом: ? Примеры переменных: ?х ?sensor ?noun ?color Перед использованием переменной ей необходимо присвоить значение. Все переменные, кроме глобальных, считаются локальными и могут использоваться только в рамках описания конструкции. К этим локальным переменным можно обращаться внутри описания, но они не определены вне него. Чаще всего переменные описываются и получают значения в левой части правила. Например: (defrule make-quack (duck-sound ?sound) => (assert (sound-is ?sound)) Получив значение, переменная сохраняет его неизменным при использовании как в левой, так и в правой части правила, если только это значение не изменяется в правой части при помощи функции bind. (defrule addition (numbers ?х ?у) => (assert (answer (+ ?х ?у))) (bind ?answer ( + ?х ?у)) (printout t "answer is " ?answer crlf)) Кроме значения самого факта, переменной может быть присвоено значение адреса факта. Это может оказаться удобным при необходимости манипулировать фактами непосредственно из правила. Для такого присвоения используется комбинация "<-". Следующий пример иллюстрирует присвоение переменной значения адреса факта и ее последующее использование: (defrule get-married ?duck <- (bachelor Dopey) => (retract ?duck)) Для определения глобальных переменных, которые видны всюду в среде CLIPS, используется конструкция defglobal. К глобальной переменной можно обратиться в любом месте, и ее значение остается независимым от других конструкций. Глобальные переменные CLIPS подобны глобальным переменным в процедурных языках программирования, но они значительно слабее типизированы (на них не налагается ограничения хранения данных только одного типа). 5.2.3.4. Дополнительные средства CLIPS предоставляет ряд дополнительных средств, необходимых при на­писании программ. Основными из них являются: • ограничения на значения полей; • оператор проверки условия test; • использование функций в правилах; • использование процедурных знаний. Использование ограничений на значения полей позволяет ограничить значения, принимаемые образцами в левой части правила. Рассмотрим три вида ограничений: ~, | и &. Ограничение первого типа действует на следующее прямо за ним значение и говорит о том, что поле не может принимать это значение. Например: (defrule walk (light ~green) => (printout t "Don't walk" crlf)) Ограничение второго типа указывает на то, что поле может принимать одно из следующих значений. Например: (defrule cautious (light yellow | blinking-yellow) => (printout t "Be cautious" crlf)) Ограничение третьего типа используется только вместе с ограничениями первых двух типов и указывает на то, что должны удовлетворяться оба соединяемых при его помощи ограничения. Например: (defrule cautious (light ?color syellow | blinking-yellow) => (printout t "Be cautious because light is " ?color crlf)) Оператор проверки условия test представляет собой мощное средство, при помощи которого можно сравнивать числа, переменные и строки в левой части правила. Он записывается точно так же, как и образцы. Правило может выполниться только тогда, когда наряду с совпадением всех образцов, записанных в левой части правила, справедливо и условие, описываемое в test. Функция test имеет следующий синтаксис: (test (аргумент_сравнения аргумент_1 аргумент_2)), где аргумент сравнения - это тот параметр, по которому сравниваются два следующих аргумента. В CLIPS существует ряд предопределенных аргументов сравнения: Таблица 5.2 eq Равно (сравнивает тип и значение) neq Не равно = Равно (сравнивает только значение) <> Не равно >= Больше или равно > Больше <= Меньше или равно < Меньше Все аргументы, кроме eq и neq, используются только для сравнения чисел. При интерпретации выражения сравнения считается что аргумент_1 стоит слева от аргумента_сравнения, а аргумент_2 - справа. При использовании функций в правилах их можно использовать как в левой, так и в правой части правила. Например: (defrule addition (numbers ?х ?у) => (assert (answer (+ ?х ?у)))) При использовании функции в левой части правила перед ней должен стоять знак " = ", показывающий CLIPS, что следующее выражение необходимо вычислить, а не использовать буквально. Например: (defrule addition (numbers ?х ?у) (stock ?ID = (sqrt (+ (** ?x 2) (** у 2)))) => (printout t "stock ID = " ?ID crlf)) CLIPS поддерживает также процедурную парадигму представления знаний, подобную принятой в обычных языках программирования (С, Паскаль). Конструкция deffunction позволяет пользователю определять новые функции. Эти новые функции могут вызываться точно так же, как и встроенные функции CLIPS. Конструкция defmodule позволяет разбивать базу знаний на части. 2.2.4. Интерфейс CLIPS CLIPS использует GUI-интерфейс. В таблице 5.3 приведено краткое описание основных пунктов меню. Разделы меню перечислены слева направо, т.е. так, как они написаны в строке меню. Команды внутри каждого меню также перечислены в порядке, в котором они находятся в меню. Таблица 5.3. Краткое описание GUI-интерфейса CLIPS Меню Пункт Назначение File Load Constructs... (Ctrl-L) Загрузка конструкций CLIPS из текстового файла. Эквивалентен команде (load <имя файла>). Load Batch... Загрузка командного файла. Эквивалентен команде (batch <имя файла>). Load Binary Image... Загрузка конструкций CLIPS, сохраненных в двоичном виде. Эквивалентен команде (bload <имя файла>). Turn Dribble On... Начало записи протокола работы с CLIPS в текстовый файл. Эквивалентен команде (dribble-on <имя файла>). После активации изменяется на Turn Dribble Off. Turn Dribble Off... Завершение записи протокола работы с CLIPS в текстовый файл. Эквивалентен команде CLIPS (dribble-off). Save Binary... Сохранение конструкций CLIPS в двоичном виде. Эквивалентен команде (bsave <имя файла>). Editor... Запуск встроенного редактора. Quit CLIPS (Ctrl-Q) Выход из CLIPS. Edit Paste (Ctrl-V) Копировать содержимое буфера обмена в диалоговое окно (вставляемый текст всегда помещается в конце окна). Complete... (Ctrl-J) "Завершение" символа, вводимого в данный момент в диалоговом окне. Если не существует никакого возможного продолжения, подается звуковой сигнал. Если существует только одно возможное продолжение, то символ автоматически завершается. Если существует больше чем одно завершение, то список всех возможных продолжений выводится в диалоговом окне. Нажмите кнопку ОК, чтобы завершить символ текущим выделением. Нажмите кнопку Cancel, чтобы закрыть диалоговое окно без завершения команды. Execution Reset (Ctrl-U) Сброс. Эквивалентен команде CLIPS (reset). При сбросе сначала очищаются списки фактов и активированных правил, затем в список фактов заносятся исходный факт (initial-fact) и факты, описанные конструкциях (deffacts). Run (Ctrl-R) Запуск. Эквивалентен команде (run) CLIPS. В ходе выполнения программы изменяется на Halt. Halt (Ctrl-C) Останов. Step (Ctrl-T) Пошаговое выполнение. Эквивалентен команде CLIPS (run количество_шагов>). Количество шагов задается в поле Step Rule Firing Increment панели настройки параметров CLIPS. Watch... (Ctrl-W) Смена режимов просмотра. Preferences... Настройка параметров CLIPS. Clear CLIPS Очистка CLIPS. Эквивалентна команде CLIPS (clear). Система приводится к начальному состоянию. Browse Module Переключение между модулями программы. По умолчанию создается лишь один модуль - MAIN. Defrule Manager Просмотр и редактирование базы знаний. Deffacts Manager Просмотр и редактирование списка фактов. Agenda Manager Просмотр и редактирование списка активированных в данный момент правил. Window Facts Window Просмотр списка фактов. Agenda Window Просмотр списка активированных в данный момент правил. Globals Window Просмотр всех глобальных переменных и их значений. All Above Отображение всех окон из данного меню. None Закрытие всех окон. Clear Dialog Window Очистка диалогового окна. 2.3. Пример разработки учебной ЭС Рассмотрим учебный пример создания простой ЭС, проводящей диагностику неисправности мотора автомобиля по внешним признакам. Помимо этого, диагностическая ЭС должна также предоставлять пользователю соответствующие рекомендации по устранению неисправности. В реализации данной ЭС будут использоваться управляющие команды CLIPS, такие как if-then-else и while, присутствующие в большинстве процедурных языков программирования. 2.3.1. Исходные данные Разработку любой ЭС следует начинать с выделения основных сущностей ПрО, имеющих значение при решении конкретной задачи и законов, скорее всего эмпирических, характерных для данной ПрО. В подавляющем большинстве случаев эту информацию получают от эксперта, человека хорошо знающего и давно работающего в этой области. Для решения нашей конкретной задачи предположим, что в результате бесед с экспертом в области установления неисправностей и ремонта автомобилей были установлены следующие эмпирические правила: 1 Двигатель обычно находится в одном из 3-х состояний: он может работать нормально, работать неудовлетворительно или не заводиться. 2 Если двигатель работает нормально, то это означает, что он нормально вращается, система зажигания и аккумулятор находятся в норме и никакого ремонта не требуется. 3 Если двигатель запускается, но работает ненормально, то это говорит, по крайней мере, о том, что аккумулятор в порядке. 4 Если двигатель не запускается, то нужно узнать, пытается ли он вращаться. Если двигатель вращается, но при этом не заводится, то это может говорить о наличии плохой искры в системе зажигания. Если двигатель даже не пытается заводиться, то это говорит о том, что искры нет в принципе. 5 Если двигатель не заводится, но вращается, нужно проверить наличие топлива. Если топлива нет - то, скорей всего, для ремонта машины нужно просто заправиться. 6 Если двигатель не заводится, нужно также проверить, заряжен ли аккумулятор, если нет, то его следует зарядить. 7 Если двигатель не заводится, и существует вероятность плохой искры в системе зажигания, то необходимо проверить контакты. Контакты могут быть в одном из трех состояний - чистые, опаленные и грязные, в случае опаленных контактов их необходимо заменить, в случае если контакты грязные, их достаточно просто почистить. 8 Если двигатель не заводится, искры нет и аккумулятор заряжен, то нужно проверить катушку зажигания на электрическую проводимость. В случае если ток не проходит через катушку, то ее необходимо заменить. Если катушка зажигания в порядке, значит необходимо заменить распределительные провода. 9 Если двигатель запускается, но при этом ведет себя инертно, не сразу реагирует на подачу топлива, то необходимо прочистить топливную систему. 10 Если двигатель запускается, но происходят перебои с зажиганием, то это говорит о наличии плохой искры в системе зажигания, для устранения данной неисправности необходимо отрегулировать зазоры между контактами. 11 Если двигатель запускается и стучит, то необходимо отрегулировать зажигание. 12 Если двигатель запускается, но не развивает нормальной мощности, то это может говорить об опаленных или загрязненных контактах (см. правило 7). 13 Возможны ситуации, когда состояние двигателя нельзя описать приведенными выше факторами и машине может потребоваться более детальный анализ состояния. Имея эти данные, можно приступить к решению поставленной задачи. 2.3.2. Сущности Из приведенных выше правил можно выделить следующие сущности, имеющие значение при решении задачи. Во-первых, для решения задачи ЭС необходимо знать, в каком состоянии находится машина, диагностика которой производится. Эксперт выделил три возможных состояния: нормальная работа двигателя, двигатель работает неудовлетворительно, не заводится (см. правило 1). Во-вторых, большинство приведенных правил помимо состояния двигателя в целом используют понятие состояния вращения двигателя. Согласно этим правилам двигатель может находиться в одном из двух состояний, которые определяются в зависимости от того, способен он вращаться (работать) или нет. В-третьих, в некоторых правилах (см. правила 4, 7, 8, 10) используется понятие состояния системы зажигания. Система зажигания может быть в одном из трех состояний: нормальное состояние, не регулярная работа и нерабочее состояние. В-четвертых, в правилах 6 и 8 используется понятие - состояние аккумулятора. Аккумулятор может быть в одном из двух состояний: заряженным и разряженным. Для представления всех перечисленных выше данных воспользуемся упорядоченными фактами CLIPS. 2.3.2.1. Факты, описывающие состояние автомобиля и его узлов Факты, описывающие состояние машины • working-state engine normal ; нормальная работа • working-state engine unsatisfactory ; неудовлетворительная работа • working-state engine does-not-start ; не заводится Факты, описывающие состояние двигателя • rotation-state engine rotates ; двигатель вращается • rotation-state engine does-not-rotate ; двигатель не вращается Факты, описывающие состояние системы зажигания • spark-state engine normal ; зажигание в порядке • spark-state engine irregular-spark ; искра не регулярна • spark-state engine does-not-spark ; искры нет Факты, описывающие состояние системы питания • charge-state battery charged ; аккумулятор заряжен • charge-state battery dead ; аккумулятор разряжен Следует иметь в виду, что факты, входящие в одну группу (содержат одинаковое первое поле), являются взаимоисключающими, т. е. наличие в системе сразу двух фактов из одной группы лишено смысла. Из постановки задачи следует, что ЭС должна предоставлять пользователю рекомендации, позволяющие устранить найденную неисправность. Из приведенных выше правил можно выделить следующие рекомендации: добавить топливо (правило 5); зарядить аккумулятор (правило 6); заменить или почистить контакты (правило 7 или правило 12); заменить катушку зажигания или распределительные провода (правило 8); прочистить топливную систему (правило 9); отрегулировать зазоры между контактами (правило 10); отрегулировать зажигание (правило 11). Необходимо помнить также о двух крайних случаях: ремонт не требуется в принципе; ЭС не смогла поставить диагноз. Для представления всех этих рекомендаций будем использовать следующие факты. 2.3.2.2. Факты, описывающие рекомендации по ремонту • repair "Add gas." ; добавить топливо • repair "Charge the battery." ; зарядить аккумулятор • repair "Replace the points." ; заменить контакты • repair "Clean the points." ; почистить контакты • repair "Replace the ignition coil."; заменить катушку зажигания • repair "Repair the distributor lead wire."; заменить распределительные провода • repair "Clean the fuel line." ; прочистить топливную систему • repair "Point gap adjustment." ;отрегулировать зазоры между контактами • repair "Timing adjustment." ; отрегулировать зажигание • repair "No repair needed." ; ремонт не требуется • repair "Take your car to a mechanic."; диагноз не поставлен, обратиться к специалисту Все приведенные факты, использующиеся для предоставления пользователю рекомендаций, во втором поле содержат текстовое значение с конкретной рекомендацией по ремонту. Следует обратить внимание, что одни и те же рекомендации могут выводиться как правилом 7, так и правилом 12. Однако состояние машины при этой поломке отличается. Для того чтобы иметь возможность обрабатывать эту ситуацию с помощью одного правила CLIPS, введем еще два до факта. 2.3.2.3. Факты, описывающие мощность работы двигателя • symptom engine low-output ; низкая мощность • symptom engine not-low-output ; нормальная мощность Приведенный выше список фактов вполне достаточен для решения поставленной задачи. Следующий этап - сбор исходной информации для диагностики. 2.3.3. Сбор информации Для работы ЭС можно заставить пользователя вручную вводить факты, описывающие проявление возникшей неисправности. Однако такой метод имеет ряд серьезных недостатков: пользователь может забыть о каких-нибудь существенных деталях или, наоборот, указать слишком много информации, что может помешать нормальной работе системы. Кроме того, факты, описывающие проявление неисправности, должны были бы иметь строго определенный формат, и система не смогла бы их обработать в случае ошибки со стороны пользователя. В ЭС будут реализованы правила диагностики, которые в зависимости от той или иной ситуации будут задавать пользователю необходимые вопросы и получать ответ в строго заданной форме. Дальнейшая диагностика будет производиться с учетом предыдущих ответов на вопросы, заданные пользователю. Эти ответы будут формировать описание текущей ситуации с помощью фактов, приведенных выше. Для реализации подобной архитектуры будет необходимо реализовать функцию, задающую пользователю произвольный вопрос и получающую ответ из заданного набора корректных ответов. В примере 4 приведена одна из возможных реализаций такой функции. 2.3.3.1. Функция ask-question (deffunction ask-question (?question $?allowed-values) (printout t ?question) (bind ?answer (read)) (if (lexemep ?answer) then (bind ?answer (lowcase ?answer))) (while (not (member ?answer ?allowed-values)) do (printout t ?question) (bind ?answer (read)) (if (lexemep ?answer) then (bind ?answer (lowcase ?answer)))) ?answer ) Функция принимает два аргумента: простую переменную question, которая содержит текст вопроса, и составную переменную allowed-values с набором допустимых ответов. Сразу после своего вызова функция выводит на экран соответствующий вопрос и читает ответ пользователя в переменную answer. Если переменная answer содержит текст, то она будет принудительно приведена к прописному алфавиту. После этого функция проверяет, является ли полученный ответ одним из заданных корректных ответов. Если нет, то процесс повторится до получения корректного ответа, иначе функция вернет ответ, введенный пользователем. Будет также очень полезно определить функцию, задающую пользователю вопрос и допускающий ответ в виде да/нет, т. к. это один из самых распространенных типов вопросов. С учетом реализации функции ask-question эта функция примет вид, представленный в примере 5. 2.3.3.2. Функция yes-or-no-p (deffunction yes-or-no-p (?question) (bind ?response (ask-question ?question yes no у n)) (if (or (eq ?response yes) (eq ?response y)) then TRUE else FALSE) ) Функция yes-or-no-p вызывает функцию ask-question с постоянным набором допустимых ответов: yes, no, у и n. В случае если пользователь ввел ответ yes или у, функция возвращает значение true, иначе - false. Поскольку функция yes-or-no-p использует функцию ask-question, то она должна быть определена после нее. 2.3.4. Диагностические правила Для упрощения реализации ЭС введем следующее ограничение: за один запуск система может предоставить пользователю только одну рекомендацию по исправлению неисправности. В случае если в машине несколько неисправностей, то систему нужно будет последовательно вызывать несколько раз, удаляя обнаруженную на каждом новом шаге неисправность. Таким образом, одним из образцов всех диагностических правил будет (not (repair ?)), гарантирующий, что диагноз еще не поставлен. Первым реализуем правило, определяющее общее состояние двигателя (см. правило 1). 2.3.4.1. Правило determine-engine-state (defrule determine-engine-state "" (not (working-state engine ?)) (not (repair ?)) => (if (yes-or-no-p "Does the engine start (yes/no)? ") then (if (yes-or-no-p "Does the engine run normally (yes/no)? ") then (assert (working-state engine normal)) else (assert (working-state engine unsatisfactory))) else (assert (working-state engine does-not-start))) ) Условный элемент (not (working-state engine ?)) гарантирует, что общее состояние двигателя еще не определено. Если это так, то пользователю за­даются соответствующие вопросы и в систему добавляется факт, описы­вающий текущее общее состояние двигателя. Теперь реализуем правило, определяющее, пытается ли двигатель вращаться, в случае если он не заводится. 2.3.4.2. Правило determine-rotation-state (defrule determine-rotation-state "" (working-state engine does-not-start) (not (rotation-state engine ?)) (not (repair ?)) => (if (yes-or-no-p "Does the engine rotate (yes/no)? ") then (assert (rotation-state engine rotates)) (assert (spark-state engine irregular-spark)) else (assert (rotation-state engine does-not-rotate)) (assert (spark-state engine does-not-spark))) ) Это правило выполняется, в случае если общее состояние двигателя определено и известно, что он не заводится. Кроме того, условный элемент (not (rotation-state engine ?)) гарантирует, что это правило еще не вызывалось. В зависимости от того или иного ответа пользователя правило добавляет соответствующий набор фактов (см. правило 4). Далее реализуются довольно простые правила 5 и 6. Выполняемые ими действия можно понять без дополнительных комментариев. 2.3.4.3. Правила determine-gas-level и determine-battery-state (defrule determine-gas-level "" (working-state engine does-not-start) (rotation-state engine rotates) (not (repair ?)) => (if (not (yes-or-no-p "Does the tank have any gas in it (yes/no)? ")) then (assert (repair "Add gas."))) ) (defrule determine-battery-state "" (rotation-state engine does-not-rotate) (not (charge-state battery ?)) (not (repair ?)) => (if (yes-or-no-p "Is the battery charged (yes/no)? ") then (assert (charge-state battery charged)) else (assert (repair "Charge the battery.")) (assert (charge-state battery dead))) ) Правило determine-battery-state, помимо определения возможной неисправности, также применяется для добавления в систему факта, описывающего текущее состояние аккумулятора, который может быть использован другими правилами. При реализации правила 7 необходимо обратить внимание на то, что рекомендации, предоставляемые этим правилом, подходят для двух в корне отличающихся ситуаций. Во-первых, в случае если двигатель не заводится, и существует вероятность плохой искры в системе зажигания (правило 7). Во-вторых, в случае если двигатель запускается, но не развивает нормальной мощности (правило 12). 2.3.4.4. Правила determine-low-output и determine-point-surface-state (defrule determine-low-output "" (working-state engine unsatisfactory) (not (symptom engine low-output | not-low-output)) (not (repair ?)) => (if (yes-or-no-p "Is the output of the engine low (yes/no)? ") then (assert (symptom engine low-output)) else (assert (symptom engine not-low-output))) ) (defrule determine-point-surface-state "" (or (and (working-state engine does-not-start) (spark-state engine irregular-spark)) (symptom engine low-output)) (not (repair ?)) => (bind ?response (ask-question "What is the surface state of the points (normal /burned /contaminated)?" normal burned contaminated)) (if (eq ?response burned) then (assert (repair "Replace the points.")) else (if (eq ?response contaminated) then (assert (repair "Clean the points.")))) ) Правило determine-low-output определяет, имеет ли место низкая мощность двигателя или нет. Правило determine-point-surface-state адекватно реагирует на условия, заданные в правилах 7 и 12. Обратите внимание на использование условных элементов or и and, которые обеспечивают одинаковое поведение правила в двух абсолютно разных ситуациях. Кроме того, правило determine-point-surface-state отличается от приведенных ранее правил тем, что непосредственно использует функцию ask-question, вместо yes-or-no-p, т.к. в данный момент пользователю задается вопрос, подразумевающий три варианта ответа. Реализация оставшихся диагностических правил (8-11) также не должна вызвать затруднений. 2.3.4.5. Оставшиеся диагностические правила (defrule determine-conductivity-test "" (working-state engine does-not-start) (spark-state engine does-not-spark) (charge-state battery charged) (not (repair ?)) => (if (yes-or-no-p "Is the conductivity test for the ignition coil positive(yes/no) ? ") then (assert (repair "Repair the distributor lead wire.")) else (assert (repair "Replace the ignition coil."))) ) (defrule determine-sluggishness "" (working-state engine unsatisfactory) (not (repair ?)) => (if (yes-or-no-p "Is the engine sluggish (yes/no)? ") then (assert (repair "Clean the fuel line."))) ) (defrule determine-misfiring "" (working-state engine unsatisfactory) (not (repair ?)) => (if (yes-or-no-p "Does the engine misfire (yes/no)? ") then (assert (repair "Point gap adjustment.")) (assert (spark-state engine irregular-spark))) ) (defrule determine-knocking "" (working-state engine unsatisfactory) (not (repair ?)) => (if (yes-or-no-p "Does the engine knock (yes/no)? ") then (assert (repair "Timing adjustment."))) ) 2.3.4.6. Последние замечания Проанализировав список правил, можно заметить, что некоторые правила (2, 3 и 13) остались до сих пор не реализованными. В качестве реализации правила 13 используем правило no-repairs, приведенное в примере 11. 2.3.4.7. Правило no-repairs (defrule no-repairs "" (declare (salience -10)) (not (repair ?)) => (assert (repair "Take your car to a mechanic.")) ) Следует обратить внимание на использование приоритета при определении этого правила. Все правила, приведенные в предыдущем разделе, определялись с приоритетом, по умолчанию равным нулю. Использование для правила no-repairs приоритета, равного -10, гарантирует, что правило не будет выполнено, пока в плане решения задачи находится, по крайней мере, одно из диагностических правил. Если все активированные диагностические правила отработали, и ни одно из них не смогло подобрать подходящую рекомендацию по устранению неисправности, то CLIPS запустит правило no-repairs, которое просто порекомендует пользователю обратиться к более опытному механику. Реализация правил 2 и 3 приведена ниже. 2.3.4.8. Правила normal-engine-state-conclusions и unsatisfactory-engine-state-conclusions (defrule normal-engine-state-conclusions "" (declare (salience 10)) (working-state engine normal) => (assert (repair "No repair needed.")) (assert (spark-state engine normal)) (assert (charge-state battery charged)) (assert (rotation-state engine rotates)) ) (defrule unsatisfactory-engine-state-conclusions " (declare (salience 10)) (working-state engine unsatisfactory) => (assert (charge-state battery charged)) (assert (rotation-state engine rotates)) ) В этих правилах, наоборот, используется более высокий приоритет, что гарантирует их выполнение до выполнения любого диагностического правила (естественно, только в случае удовлетворения условий, заданных в левой части правил). Это избавит систему от лишних проверок, а пользователя от лишних вопросов. ЭС фактически готова. Единственное, чего ей не хватает, — это метода вывода итоговой информации и правила, сообщающего пользователю о начале работы. Ниже приведена реализация этих правил. 2.3.4.9. Правила system-banner и print-repair (defrule system-banner "" (declare (salience 10)) => (printout t crlf crlf) (printout t "***************************************" crlf) (printout t "* The Engine Diagnosis Expert System *" crlf) (printout t "***************************************" crlf) (printout t crlf crlf) ) (defrule print-repair "" (declare (salience 10)) (repair ?item) => (printout t crlf crlf) (printout t "Suggested Repair:") (printout t crlf crlf) (format t " % s% n % n % n" ?item) ) 3. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ В ЛОГИЧЕСКОМ БАЗИСЕ 3.1 Интеллектуальные агенты Агент (рис. 1.1) воспринимает значения параметров внешней среды (α1, α2, … αm) с помощью сенсоров (x1, x2, … xm) и воздействует на нее посредством исполнительных органов (z1, z2, … zn) изменяя в общем случае некоторые параметры среды (γ1, γ2, … γm). В понятия сенсоров и исполнительных органов закладывают самый широкий смысл. Робот, выполняющий функции агента, в качестве сенсоров может иметь видеокамеру и лазерные дальномеры, а его исполнительными органами могут являться различные двигатели. Программное обеспечение, выступающее в роли агента, в качестве входных сенсорных данных получает коды нажатия клавиш, содержимое файлов и сетевые пакеты, а его воздействие на среду выражается в том, что программное обеспечение выводит на данные экран, записывает файлы, передает сетевые пакеты. Рис 3.1 Взаимодействие агента со средой Не существует общепринятой классификации агентов. В зависимости от сложности решаемых задач можно выделить четыре типа агентов: • комбинационные, • последовательные, • целенаправленные, • целевыбирающие. Комбинационные агенты. В определенный момент времени комбинационный агент получает с датчиков восприятие состояния среды. На основании только этого восприятия и неизменяемой в процессе всего существования агента базы знаний, он в этот же момент времени с помощью исполнительных органов формирует реакцию. Комбинационный агент не порождает новые знания. Каждый раз, когда надо вырабатывать очередную реакцию по вновь поступившему восприятию, он использует одни и те же знания, хранящиеся в его памяти. Примером такого агента может служить известная «мышка» К.Шеннона, осуществляющая поиск выхода из лабиринта. Последовательные агенты. Агенты, которые используют запомненную в предыдущие моменты времени информацию и используют ее для выработки реакции, называют последовательностными. Эти агенты не также не порождают новых знаний. Целенаправленный агент заранее планируют свои реакции прежде, чем принять решение, на основании известной ему цели и имеющихся у него правил. Иными словами, до того, как агент начнет действовать, он пытается построить план, гарантирующий ему достижение цели, или обнаруживает, что такого плана не существует. В случае обнаружения недостижимости цели он может запросить дополнительные правила и продолжить процесс поиска. План является последовательностью пар восприятие — реакция ведущих к цели. Для каждой вновь возникающей цели порождает свой план достижения именно этой цели. Если план найден, то целенаправленный агент его выполняет и достигает цели. Примером может служить поражение цели выстрелом из артиллерийского орудия. Целенаправленный агент не порождают новых знаний. Целевыбирающий агент при наличии одной цели может строить множество конкурирующих планов достижения цели и выбирать из них наилучший. При наличии нескольких конкурирующих целей, достижение каждой из которых заранее нельзя оценить с полной уверенностью, он способен определить степень успеха достижения каждой цели, в зависимости от ее важности. На основании предшествующего опыта, он может обучаться и корректировать или пополнять свою базу знаний. Примером может служить самонаводящаяся ракета, атакующая групповую цель. Среды Агент всегда функционирует в некоторой проблемной среде, по сути представляющей собой некоторую «проблему», для которой рациональный агент служит «решением». От свойств конкретной среды зависит выбор типа агента и всего, что ему необходимо для функционирования в этой среде. Разнообразие вариантов проблемных сред весьма велико. Тем не менее, существует возможность определить относительно небольшое количество признаков, по которым могут быть классифицированы варианты проблемной среды. Дискретные и непрерывные среды Различие между дискретными и непрерывными вариантами среды может относиться к состояниям среды, восприятиям и реакциям агента. В дискретных средах число различных восприятий и реакций, которые требуются агенту при функционировании в среде, конечно, хотя и может быть очень велико. Непрерывные среды могут порождать бесконечное число состояний, восприятий, реакций. Например, такая среда с дискретными состояниями, как игра в шахматы, имеет конечное количество различных состояний, восприятий и реакций. Вождение автомобиля – это проблема с непрерывно меняющимся состоянием и непрерывно текущим временем, поскольку скорость и местонахождение самого автомобиля и других транспортных средств изменяются в определенном диапазоне непрерывных значений. Реакция агента, управляющего автомобилем, также является непрерывной (непрерывная регулировка угла поворота руля, изменения скорости и т.д.). Статические и динамические среды Среда является статической, если за время, протекающее между получением агентом любого восприятия и выработкой им реакции, в среде ничего не изменяется. В противном случае среда называется динамической. В статической среде агенту не нужно наблюдать за состояниями среды в процессе выработки решения о выполнении следующего действия. Агент может не контролировать время, затрачиваемое на принятие решения. В динамической среде от агента требуется постоянная реакция, и если решение не вырабатывается, то это рассматривается как отказ действия. Среда вождения автомобиля является динамической, поскольку агент-водитель и другие транспортные средства продолжают движение и в ходе того, как алгоритм вождения определяет, что делать дальше. Задача решения кроссворда и игра в шахматы без контроля времени являются примерами статических сред. Детерминированные и стохастические среды Среда называется детерминированной, если следующее состояние среды полностью определяется ее текущим состоянием и действием, выполненным агентом. В противном случае среда является стохастической. С точки зрения агента, среда вождения автомобиля является стохастической, поскольку агент не может точно предсказать поведение других транспортных средств. Более того, в любом автомобиле неожиданно может возникнуть неисправность – произойти прокол шины или остановка двигателя. Среда игры в шахматы является детерминированной. Эпизодические и последовательные среды В эпизодической среде каждый эпизод включает в себя восприятие агентом среды, а затем выполнение одного действия. При этом важно то, что следующий эпизод не зависит от действий, предпринятых в предыдущих эпизодах. Эпизодическими являются многие задачи классификации. Например, агент, который должен распознавать дефектные детали на сборочной линии, формирует каждое решение применительно к текущей детали, независимо от предыдущих решений. От текущего решения не зависит то, как будет классифицирована следующая деталь. В последовательных средах текущее решение может повлиять на все будущие решения. Игра в шахматы и вождение автомобиля являются примерами последовательных сред. В обоих случаях каждое действие агента может иметь долговременные последствия. Одноагентные и мультиагентные среды Если в среде действует несколько сущностей, которые следует отнести к агентам, то такая среда называется мультиагентной. Чтобы классифицировать среду как мультиагентную, нужно определить, должен ли агент А (например, агент-водитель автомобиля) считать агентом объект В (другой автомобиль), или его можно рассматривать как стохастически действующий объект среды. Ключевым признаком, отличающим агента от объекта среды, является его поведение, максимизирующее личные показатели качества, значения которых зависят от поведения агента А. Например, в шахматах соперничающая сущность В пытается максимизировать свои показатели качества, что в свою очередь приводит к минимизации показателей качества агента А. Таким образом, шахматы – это конкурентная мультиагентная среда. В среде вождения предотвращение столкновений максимизирует показатели производительности всех агентов, поэтому она может служить примером частично кооперативной мультиагентной среды. Одним из признаков рационального поведения в мультиагентной среде часто бывает поддержка связи. Примеры проблемных сред Наиболее сложными вариантами среды являются стохастические, последовательные, динамические, непрерывные, мультиагентные среды. Например, проблемная среда вождения автомобиля является сложной во всех указанных отношениях. В Таблице 1.1 перечислены свойства некоторых вариантов проблемных сред. Таблица 1.1. Примеры проблемных сред и их характеристики. Среда Решение кроссворда Игра в шахматы без контроля времени Вождение автомобиля Анализ изображений Робот сортировщик Дискретная(Дс) / непрерывная (Нп) Дс Дс Нп Нп Нп Статическая (Ст) / динамическая (Дн) Ст Ст Дн Ст Дн Детерминированная (Дт) / стохастическая (Ст) Дт Дт Ст Дт Ст Эпизодическая (Эп) / последовательная (Пс) Пс Пс Пс Эп Эп Одноагентная (Од) / мультиагентная (Мл) Од Мл Мл Од Од 3.2 Постановка задачи в пространстве состояний среды 3.2.1 Неформальная постановка задачи Формулировка задачи Рассмотрим постановку задачи создания целенаправленного агента, имеющего дело с дискретной средой. Для иллюстрации воспользуемся очень простым примером. Рассмотрим среду, показанную на рис.2.1, в которой работает интеллектуальный агент - пылесос. Эта среда настолько проста, что можно описать все ее состояния и возможные реакции агента. Это искусственная среда, созданная человеком, поэтому можно предложить любой вариант ее организации. В этой среде есть только два условных местонахождения агента: комнаты А и В. Пылесос воспринимает с помощью датчиков информацию о том в какой комнате он находится и есть ли мусор в этой комнате. Агент может выбрать такие действия, как переход влево (в комнату А), переход вправо (в комнату В), всасывание мусора или бездействие. Задача пылесоса убрать мусор во всех комнатах. Рис. 2.1. Среда пылесоса Рассмотрим процесс постановки задачи для интеллектуального агента в рассматриваемой среде. Множество всех состояний среды можно представить в табличном виде. В столбцах табл.2.1 указаны местонахождение пылесоса (комната А или В), наличие или отсутствие мусора в соответствующей комнате. Например, состояние b1 означает, что пылесос находится в левой комнате А и мусор есть в обеих комнатах, состояние b2 – пылесос находится в правой комнате В и в обеих комнатах также есть мусор и т.д. Таблица 2.1. Состояния среды Состояние среды Местонахождение агента Наличие мусора В комнате А В комнате В b1 Комната А Есть Есть b2 Комната В Есть Есть b3 Комната А Есть Нет b4 Комната В Есть Нет b5 Комната А Нет Есть b6 Комната В Нет Есть b7 Комната А Нет Нет b8 Комната В Нет Нет Пылесос может совершать в один и тот же момент времени только одно из следующих действий: переходить в комнату А (идти влево), переходить в комнату В (идти вправо) и всасывать мусор в той комнате, где он находится. Эти действия можно обозначить с1 = «идти влево», с2= «идти направо», с3= «всасывать мусор» соответственно. Если среда находится в одном из состояний, перечисленных в табл.2.1., и пылесос совершает одно из указанных действий, то легко можно определить, в какое состояние после выполнения действий перейдет среда. Полагаем, что известно состояние среды, называемое начальным, которое будет изменяться в результате действий агента. Пусть это будет состояние b1. Можно представить это состояние в виде вершины графа (рис.2.2). Переход из одного состояния в другое, происходящее в результате действий агента, можно представить ребром направленного графа. Ребро помечено соответствующим действием и ведет в вершину, соответствующую новому состоянию среды. На рис.2.2 изображены все переходы из состояния b1 в результате действий с1, с2, с3. Рис. 2.2 Переходы из начального состояния среды На рис.2.3 показано дерево всех возможных переходов в рассматриваемой среде. Построение каждой ветви дерева прекращено на тех состояниях, которые встречается на дереве повторно. Рис 2.3.Дерево всех переходов между состояниями среды Постановка задачи в терминах состояний среды Цель пылесоса – не оставить мусора ни в одной комнате. В терминах состояния среды целью агента является перевод ее с помощью своих действий (реакций) в одно из состояний b7 или b8. Состояния, в которые с помощью набора допустимых действий необходимо перевести среду, называются целевыми. Процесс определения этих состояний называется формулировкой цели. Будем считать, что каждое восприятие агентом среды совпадает с одним из ее состояний. Тогда задачей агента является нахождение последовательности пар восприятие-действие, ведущих на дереве переходов из начального состояния в целевые. Процесс нахождения этих последовательностей называется поиском, выводом или рассуждением. Поиск осуществляется на основе некоторой стратегии поиска. Прежде чем приступить собственно к поиску целевых состояний, необходимо поставить задачу и формализовать ее, т.е. описать ее на одном из формальных языков. Для того, чтобы поставить задачу необходимо: • задать (описать) все состояния среды; • задать начальное состояние среды; • задать целевые состояния среды; • задать все действия, которые может совершать агент в процессе решения задачи; • задать все допустимые переходы между состояниями среды (описать возможные ограничения на действия агента в среде). Для среды пылесоса такая постановка задачи уже фактически сделана. Все состояния среды перечислены в табл.2.1. Начальным состоянием будем считать b1. Целевыми состояниями являются состояния b7 и b8. Все три допустимых действия агента заданы – c1, c2, c3. Все допустимые переходы между состояниями среды показаны на дереве переходов – рис.2.3. Анализ дерева переходов показывает, что решениями задачи является последовательность пар состояние среды – действие агена (b1-c2), (b2-c3), (b4-c1), (b3-c3) в результате выполнения которой агент (пылесос) переведет среду в состояние b7, или последовательность (b1-c3), (b5-c2), (b6-c3) в результате выполнения которой среда будет переведена в целевое состояние b8. Решения задачи для среды пылесоса практически очевидны, когда построено дерево переходов состояний среды, по которому легко проследить пути, ведущие в целевые состояния из начального. В реальных задачах это дерево может быть очень большим, поэтому не всегда целесообразно использовать стратегию поиска, согласно которой необходимо сначала получить дерево целиком. Известны другие более эффективные стратегии поиска. Вместе с тем, элементарный шаг поиска в любой стратегии представляет переход из одного состояния среды в другое и анализ нового состояния на принадлежность к списку целевых. Каждый разрешенный переход из состояния bi после совершения действия cj в состояние bk можно описать правилом перехода: «если среда находится в состоянии bi и совершается действие cj, то она должна перейти в состояние bk. Иначе говоря, каждый шаг состоит в проверке агентом истинности левой части правила, и в случае ее истинности признании факта перехода в новое состоянии bk. 3.2.1 Формальная постановка задачи Постановка задачи на языке логики высказываний Для поиска решения необходим математический аппарат, позволяющий формализовать постановку задачи. Формализация постановки задачи предполагает наличие формального языка, на котором можно описать все знания о среде. Формальный язык включает две неотъемлемые части: синтаксис и семантику. Синтаксис языка описывает допустимые в языке предложения, состоящие из последовательностей символов, принадлежащих алфавиту. Синтаксические правила позволяют отличать предложения, принадлежащие языку от предложений, ему не принадлежащих. Семантика языка определяет смысл этих предложений, соотнося символы языка с объектами среды, а предложения – с отношениями между объектами. Для рассматриваемой дискретной среды таким языком может быть математическая логика, в частности, логика высказываний. Семантика логики высказываний позволяет подразделять все множество допустимых предложений на истинные и ложные. Истинные предложения соответствуют имеющим место фактам или отношениям, а ложные предложения – не имеющим. Решить задачу формально – это значит иметь множество правил и стратегию их использования, которые позволяют осуществить вывод одних синтаксически правильных истинных предложений из других синтаксически правильных истинных предложений. Синтаксис логики высказываний прост. Символами языка логики, составляющими ее алфавит, являются: • логические константы «Истина» («И») и «Ложь» («Л»); • логические переменные x, y, z, … (значениями логических переменных являются логические константы); • логические связки: И (), ИЛИ (), НЕ (), ЭВИВАЛЕНТНО (), ВЛЕЧЕТ (); • круглые скобки. Предложения языка логики высказываний называются формулами (правильно построенными формулами) и составляются по определенным правилам. Семантика логики высказываний поясняется смысловой интерпретацией ее формул, под которой обычно понимают процесс установления соответствия: • между логическими переменными и изменяющимися свойствами объектов среды; • между значениями переменных и конкретными значениями свойств объектов; • между формулами и отношениями свойств объектов. В примере со средой пылесоса – это соответствие между логической переменной xp и свойствами пылесоса находиться слева (в комнате А) или справа (в комнате В) и значениями логической переменной xp=«И» (пылесос слева) или xp=«Л» (пылесос справа). Также наличие мусора в комнате А определяется значением логической переменной xa=«И», а отсутствие мусора xa=«Л». Аналогично для комнаты B xb=«И» (мусор есть) или xb=«Л» (мусор отсутствует). Истинное значение формулы определяет наличие отношения свойств объектов среды, а ложное – его отсутствие. Например, состояние среды b1 характеризуется отношением следующих свойств среды пылесос слева (xp=«И»), мусор есть в комнате A и в комнате B (xа=«И», xb=«И»). Тогда состояние среды b1 описывается формулой . По значению формулы (истинному или ложному), после подстановки в нее конкретных значений переменных, можно судить о наличии или отсутствии у среды тех или иных совокупных свойств или отношений. Подстановка в формулу констант вместо ее переменных называется конкретизацией. Таким образом, конкретизация является результатом интерпретации. Семантику формул можно всегда задать таблицами истинности, состоящими из двух частей: в левой части таблиц перечислены все наборы значений аргументов, а в правой - соответствующие им значения формул. Введенные обозначения позволяют формализовать описание всех состояний среды, т.е. заменить табл.2.1 на табл.2.2. Каждое состояние среды можно рассматривать как комбинацию (отношение) простейших свойств объектов, задаваемых значениями отдельных логических переменных. Так, например, состояние b2 соответствует комбинации свойств пылесоса и мусора, состоящей в том, что пылесос находится в комнате В, и при этом в обеих комнатах присутствует мусор. В соответствии с уже приведенной интерпретацией логических переменных xp, xa, xb это утверждение можно представить формулой , которая истинна в единственном случае – xp=«Л», xa=«И», xb=«И», т.е. среда находится в состоянии b2. Формулы такого типа являющиеся конъюнкцией переменных с отрицанием или без него, называются элементарными конъюнкциями. Элементарную конъюнкцию, в которую входит по одному разу каждая переменная, определяющую состояние среды, называют полной конъюнкцией или конституентой. Таблица 2.2. Состояния среды Состояние Переменные Формула, описывающая состояние b1 И И И b2 Л И И b3 И И Л b4 Л И Л b5 И Л И b6 Л Л И b7 И Л Л b8 Л Л Л Формулы, истинные на всех наборах значений своих аргументов называются общезначимыми формулами. Большое значение для формализации поиска в логике высказываний имеют общезначимые формулы вида . Они называются импликативными формулами или просто импликациями и используются для формального задания переходов между состояниями среды. Важным свойством импликаций является возможность получения заключения об истинности формулы β, называемой заключением, при истинности формулы α, называемой посылкой. Правило вывода заключений, используемое в классическом исчислении высказываний, формулируется следующим образом. Из истинности условия импликации и истинности самой импликации следует истинность следствия импликации: ├ Рассмотрим теперь, как могут быть выражены в виде формул переходы среды из одного состояния в другое при совершении агентом того или иного действия. Введем логические переменные z1, z2, z3 для действий пылесоса «идти влево», «идти вправо», «всасывать мусор». Переменная zi принимает истинное значение, если выполняется соответствующее ей действие. В противном случае она принимает ложное значение. Полагаем, что пылесос не может одновременно выполнять более одного действия, т.е. действие с1.описывается формулой и т.д. Если пылесос находился в состоянии b1 и выполнил действие c2 – «идти вправо», то среда перейдет в состояние b2. Совокупность свойств – нахождение агента в состоянии b1 и выполнения им в это время действия c2 означает истинность формулы . Факт перехода из состояния b1, при выполнения действия с2, в состояние b2 можно интерпретировать как истинность формулы . Это позволяет, при истинности предпосылки , сделать заключение об истинности заключения . Точно также можно выразить в виде аналогичных формул все остальные переходы, показанные на дереве (рис.2.3). Представим их в виде табл.2.3. Таблица.2.3. Переходы между состояниями среды Переход Импликация, соответствующая переходу Исходное состояние Действие Результирующее состояние b1 c1 b1 b1 c2 b2 b1 c3 b5 . . . . . . . . . . . . b6 c3 b8 Таким образом, формальня постановка задачи для рассматриваемого примера состоит в следующем: • начальное состояние среды представлено истинной формулой ; • все состояния среды представлены множеством формул (табл.2.2); • - множество допустимых действий агента описывается формулами , , ; • - множество целевых состояний представлено формулами и ; • - множество допустимых переходов представлено импликациями в табл.2.3. Решение задачи состоит в нахождении последовательности переходов, ведущих из начального состояния в одно из целевых. Примеры постановок задач поиска Рассмотрим некоторые из наиболее известных примеров задач поиска, подразделив их на два типа – упрощенные и реальные задачи. Упрощенная задача предназначена для иллюстрации или проверки различных методов решения задач. Ей может быть дано краткое, точное описание. Такая задача может быть использована для сравнения производительности различных алгоритмов. Реальная задача стоит перед специалистами в области ИИ и ее решение действительно требуется людям. Как правило, такие задачи не имеют единого описания, но можно привести их упрощенные формулировки. Упрощенные задачи Задача игры в «восемь». Задача решается на доске 3х3 с восемью пронумерованными фишками и с одним пустым полем (рис. 2.4). Любая фишка, смежная с пустым полем может быть передвинута на этот участок.Путем последовательных действий (передвижения фишек) требуется достичь целевого состояния, например состояния, изображенного на рис.2.4. Рис. 2.4 Стандартная постановка задачи для игры в «восемь»: • Состояния среды. Описание состояния определяется местонахождением каждой из восьми фишек и пустого поля на одном из девяти квадратов. • Начальное состояние среды. В качестве начального состояния может быть определено любое состояние среды. • Целевое состояние среды. Целевым состоянием может быть любое упорядоченное расположение фишек на доске. • Действия агента. Действия агента заключаются в перемещении за один ход одной фишки на пустую клетку доски. Формально эти действия могут быть заданы в виде перемещения пустого поля на каждом шаге поиска в четырех возможных направлениях Вверх, Вниз, Направо, Налево. • Стоимость пути. Каждое действие агента имеет единичную стоимость, поэтому стоимость пути равна количеству действий (ребер на графе переходов). Задача игры в «восемь» относится к семейству задач со скользящими фишками, которые часто используются в искусственном интеллекте для проверки алгоритмов поиска. Этот общий класс задач на доске nxn клеток является NP-полным. Задача игры в восемь на доске 3х3 имеет 181440 состояний. Задача игры в «пятнадцать» на доске 4х4 имеет 1,3 триллиона состояний и достаточно легко решается. Задача игры в «двадцать четыре» на доске 5х5 имеет около 1025 состояний и для случайно выбранных начальные положений достаточно трудно найти оптимальные решения с применением известных алгоритмов поиска. Задача с восемью ферзями. Задача состоит в размещении восьми ферзей на шахматной доске таким образом, чтобы ни один ферзь не угрожал любому другому. (Ферзь атакует любую фигуру, находящуюся на одной и той же с ним горизонтали, вертикали или диагонали.) Задача представляет интерес с т.з. проверки различных алгоритмов поиска, несмотря на наличие эффективных специализированных алгоритмов ее решения и всего семейства задач с n ферзями. Формулировка задачи возможна в инкрементном виде или в виде полного состояния среды. В инкрементной формулировке начальное состояние среды представляет пустую игровую доску. На каждом шаге процедуры поиска происходит добавление к этому состоянию еще одного ферзя. В формулировке полного состояния в начальном положении на доске установлены все восемь ферзей и предусматривается их дальнейшее перемещение. В том и другом случае стоимость пути не представляет интереса, поскольку важно лишь достигнуть конечного состояния. Рис. 2.5. Рассмотрим инкрементную постановку задачи. • Состояния среды. Состоянием является любое расположение ферзей на доске в количестве от 0 до 8. • Начальное состояние. Отсутствие ферзей на доске. • Целевое состояние. На доске находится 8 ферзей, ни один из них не атакует любого другого ферзя. • Действия агента. Установка ферзя на любой пустой клетке. Для сокращения числа возможных состояний можно запретить помещать ферзя на любую клетку, которая уже атакована. • Состояния среды. Состояниями являются расположения c n ферзями (0≤n≤8), по одному ферзю в каждой из находящихся слева n вертикалей, при условии, что ни один ферзь не атакует любого другого. • Действия агента. Установка ферзя на любой клетке в находящейся слева пустой вертикали таким образом, чтобы он не был атакован каким-либо другим ферзем. Реальные задачи. Задача поиска маршрута. Эту задачу можно определить в терминах заданных местонахождений (состояний) и переходов по связям между ними. Алгоритмы поиска маршрута используются в самых разных приложениях, таких как системы маршрутизации в компьютерных сетях, системы планирования операций и т.п. Процесс постановки таких задач является трудоемким, его можно проиллюстрировать на упрощенном примере задачи планирования авиапутешествий. • Состояния среды. Каждое состояние представлено местонахождением агента и текущим временем. • Начальное состояние. Определяется текущим местонахождением агента и начальным отсчетом времени. • Целевое состояние. Задается требуемым местонахождением агента и временем достижения цели. • Действия агента. Задаются функцией, которая возвращает состояния, которые следуют из выполнения любого рейса, указанного в расписании, отправляющегося позднее текущего времени с учетом ограничений на продолжительность внутренних перемещений между пунктами вылета. • Стоимость пути. Определяется стоимостью билета, затратами времени на перелет, ожидания, перемещения, дополнительные процедуры и т.п. В реальных системах планирования путешествий используется формулировка задачи подобного типа со многими дополнительными усложнениями, такими как резервирование альтернативных рейсов и т.п. Задача планирования обхода. Задача тесно связана с задачами поиска маршрута, но с одним важным исключением. Действия агента соответствуют перемещениям из одного пункта в другой, но пространство состояний является другим. Каждое состояние должно включать не только текущее местонахождение, но и последовательность пунктов, которые посетил агент. Цель заключается в посещении всех заданных пунктов. Одной из задач планирования обхода является задача коммивояжера (Traveling Salespersons Problem – TSP). По условию задачи каждый пункт маршрута должен быть посещен один раз, начало и конец маршрута совпадают. Цель состоит в нахождении самого короткого маршрута обхода. Задача является NP-полной и на повышение эффективности алгоритмов ее решения затрачены колоссальные усилия. Практически баз существенного изменения формулировки она может быть применена к задачам обслуживания удаленных буровых, планирования перемещений автоматических сверл при отработке печатных плат, организации средств снабжения в производственных цехах и т.п. Задача компоновки СБИС (сверхбольших интегральных схем). Задача состоит в позиционировании миллионов компонентов и соединений на микросхеме для минимизации площади, паразитных емкостей и максимизации выхода готовой продукции. Задача компоновки обычно подразделяется на две части: компоновка ячеек и маршрутизация каналов. При компоновке ячеек простейшие компоненты схемы группируются по ячейкам, каждая из которых выполняет некоторую известную функцию. каждая ячейка имеет постоянную форму (размеры и площадь) и требует создания определенного количества соединений с каждой из остальных ячеек. Требуется разместить ячейки на микросхеме таким образом, чтобы они не перекрывались и оставалось место для прокладки соединений между ячейками. При маршрутизации каналов происходит поиск конкретного маршрута для каждого проводника через зазоры между ячейками. Эти задачи поиска являются чрезвычайно сложными и требуют разработки эффективных алгоритмов поиска решений. Задача управления навигацией робота. Задача представляет обобщение задачи поиска маршрута. В этой задаче вместо дискретного множества маршрутов рассматривается ситуация, в которой робот может перемещаться в непрерывном пространстве с бесконечным множеством состояний и возможных действий. Пространство состояний может быть двумерным при перемещении робота по плоской поверхности, или трехмерным, если робот оборудован верхними и нижними конечностями, которыми необходимо управлять. Сложность задачи усугубляется тем, что необходимо учитывать погрешности датчиков и ошибки отработки управляющих воздействий исполнительными органами. Задача поиска информации в сети Интернет. Задача состоит в создании программных агентов, которые осуществляют поиск, находя ответы на вопросы или совершая торговые сделки. Задачи этого типа являются хорошим приложением для методов поиска, поскольку сеть Интернет может быть представлена в виде графа, состоящего из вершин (страниц), соединенных ссылками. Перечисленные формулировки задач иллюстрируют обший подход к задачам поиска, смысл которого состоит в достижении цели в пространстве состояний среды. 3.3 СТРАТЕГИИ ПОИСКА. При постановке задачи в пространстве состояний среды используется понятие вывода для нахождения целевых состояний. Вывод не является однозначным и после очередного шага приходится определять, какой следующий шаг целесообразно сделать, чтобы достичь цели. Очередной шаг зависит от выбранной стратегии поиска. Введем ряд понятий. Процедура нахождения целевого состояния (состояний) называется стратегией поиска цели. Процесс нахождения целевых состояний называется поиском. Агент, реализующий ту или иную стратегию, стремится максимизировать свой показатель качества, характеризующий успешность достижения цели. Успех поиска целевых состояний может оцениваться по следующим критериям: • Возможность достижения цели. Например, максимальное значение при достижимости цели и минимальная оценка в противном случае. • Стоимость пути. Вычисляется с помощью функции стоимости пути. • Цена поиска. Характеризуется необходимыми для поиска затратами вычислительных ресурсов и времени. Стратегии поиска различаются последовательностью просмотра состояний в пространстве всех состояний среды. Стратегии поиска обычно сравнивают по ряду критериев. Основными критериями являются: • Полнота. Стратегия является полной при условии, что она всегда обеспечивает нахождение решения (целевых состояний), если оно существует в данном пространстве состояний среды. • Сложность по времени. Определяется временем, необходимым для нахождения решения. • Сложность по памяти. Определяется объемом памяти, необходимым для решения задачи. • Оптимальность. Стратегию называют оптимальной при условии, что она обеспечивает нахождение решения, которое удовлетворяет некоторому условию – критерию оптимальности. Если среди оптимальных решений можно выделить наилучшее, то оно называется минимальным решением. Принято различать стратегии неинформированного или слепого поиска и стратегии информированного или эвристического поиска. В стратегиях неинформированного поиска не используется дополнительная информация о состояниях среды кроме той, которая представлена в формулировке задачи. Они способны вырабатывать преемников текущих состояний и отличать целевое состояние от нецелевого. Стратегии информированного поиска позволяют определить, является ли одно промежуточное нецелевое состояние среды «более перспективным» по сравнению с другим состоянием. Все стратегии поиска различаются порядком развертывания узлов (порождения состояний среды). Стратегии слепого поиска, как правило, не относят к интеллектуальным стратегиям, ввиду их неэффективности. Наиболее известными стратегиями этого типа являются поиск «в ширину» и поиск «в глубину». Предметом нашего рассмотрения будут информированные стратегии, обеспечивающие более эффективный поиск решения. Различают стратегии локального поиска и стратегии поиска, минимизирующие стоимость пути. Алгоритмы локального поиска оценивают и модифицируют одно или несколько текущих состояний вместо систематического исследования путей из начального состояния. Эти алгоритмы применимы для решения задач, в которых стоимость пути не представляет интереса и требуется лишь найти состояние, соответствующее решению. 3.3.1 Локальный поиск Рассматриваемый подход к информированному поиску называется «поиском по первому наилучшему совпадению». В рамках этого подхода на каждом шаге поиска следующее состояние среды выбирается на основе эвристической функции оценки состояний f(n). По традиции выбирается состояние с наименьшей оценкой, поскольку такая оценка эквивалентна расстоянию до цели. Поиск по первому наилучшему совпадению может быть реализован с помощью очереди состояний среды, упорядоченной по приоритету – в порядке возрастания f(n). Если функция оценки действительно является точной, то на каждом шаге поиска выбирается наилучшее состояние (ближайшее к цели) и решение представляет собой прямое шествие к цели. Если же фактически функция оценки оказывается малопригодной, то поиск заходит в тупик. Поэтому правильнее называть рассматриваемый подход поиском «по первому совпадению, которое можно считать наилучшим». Алгоритмы локального поиска учитывают информацию единственно о текущем состоянии среды и обычно предусматривают только переход в состояние, соседнее по отношению к текущему состоянию. Как правило, информация о путях, пройденных в процессе такого поиска, не сохраняется. Алгоритмы локального поиска обладают важными преимуществами: они используют небольшой объем памяти и позволяют находить приемлемые решения в больших пространствах состояний. Локальный поиск применяется при решении многих задач, когда стоимость пути к цели не представляет интереса. К этому классу задач относятся многие важные приложения, такие как проектирование интегральных схем, составление производственных расписаний, оптимизация сетей связи, управление портфелем акций и т.д. Суть локального поиска можно проиллюстрировать на примере понятия ландшафта пространства состояний. Этот ландшафт характеризуется «рельефом» - рис.4.1. Если возвышение соответствует расстоянию до цели, то задача состоит в движении к самой глубокой впадине. Алгоритм полного локального поиска всегда находит цель. Рис.4.1. Функция оценки состояний. Рассмотрим алгоритм локального поиска на примере игры «восемь». Целью этой игры является поиск целевого состояния (заданной упорядоченной комбинации фишек) путем их последовательного перемещения на единственное пустое место на игровом поле (рис. 4.2) Рис. 4.2. Игра в «восемь» Пусть в качестве эвристической функции оценки текущего состояния f(n) используется число фишек, находящихся не на своем месте. Тогда выбор действия, уменьшающего значение f(n), в некоторых случаях прямо ведет к цели. Рассмотрим следующую последовательность состояний игры (рис.4.3): Рис. 4.3 Локальный поиск целевого состояния в игре в «восемь» Цифры сверху соответствуют значениям эвристической функции f(n). За исключением состояний n=1 и n=2, для которых f(n)=3, во всех остальных случаях значения f(n) уменьшаются. График изменения функции f(n) будет иметь вид (рис. 4.4). Рис. 4.5. Данная стратегия соответствует процессу спуска к единственному глобальному минимуму функции f(n). Однако применимость данного метода ограничена наличием локальных минимумов, а также областей типа "плато" или "хребет". Попав в локальный минимум, стратегия теряет ориентир, т.к. любые действия агента не уменьшают, а увеличивают значение эвристики. Например, любой способ перемещения фишек при переходе от состояния, показанного на рис.4.6, к целевому ведет не к уменьшению, а к увеличению удаленности от цели и увеличению значения f(n). Рис. 4.6. Локальный минимум целевой функции Алгоритм поиска рассматриваемого типа еще называется «восхождением к вершине» (в данном случае это спуск во впадину). Работа этого алгоритма заканчивается после достижения «пика», в котором ни одно из соседних состояний не имеет более высокого значения. В этом алгоритме не осуществляется прогнозирование за пределами тех состояний, которые являются ближайшими по отношению к текущему состоянию среды. Поиск с восхождением к вершине еще называется жадным локальным поиском, поскольку в процессе его выполнения происходит выбор самого хорошего соседнего состояния. Жадность считается одним из семи смертных грехов, но жадные алгоритмы часто показывают весьма высокую производительность. 3.3.2 Муравьиные алгоритмы Алгоритмы «природных вычислений» В последние годы интенсивно разрабатывается научное направление Natural Computing — «Природные вычисления», объединяющее математические методы, в которых заложены принципы природных механизмов принятия решений. Эти механизмы обеспечивают эффективную адаптацию флоры и фауны к окружающей среде на протяжении миллионов лет. К этому направлению относятся методы роевого интеллекта (муравьиные, пчелиные) и методы эволюционной оптимизации (генетические). Имитация самоорганизации муравьиной колонии составляет основу муравьиных алгоритмов — нового перспективного метода оптимизации. Колония муравьев может рассматриваться как мультиагентная среда, в которой каждый агент (муравей) функционирует автономно по очень простым правилам. В противовес почти примитивному поведению агентов, поведение всей системы получается на удивление разумным. Коллективная система способна решать сложные динамические задачи по выполнению совместной работы, которая не могла бы выполняться каждым элементом системы в отдельности в разнообразных средах без внешнего управления, контроля или координации. В таких случаях говорят о роевом интеллекте (swarm intelligence), как о способах кооперативного поведения, то есть стратегии выживания. Поведение муравьев при транспортировании пищи, преодолении препятствий, строительстве муравейника и других действиях зачастую приближается к теоретически оптимальному. Основу «социального» поведения муравьев составляет самоорганизация — множество динамических механизмов, обеспечивающих достижение системой глобальной цели в результате низкоуровневого взаимодействия ее элементов. Принципиальной особенностью такого взаимодействия является использование элементами системы только локальной информации. Самоорганизация является результатом взаимодействия следующих компонентов: • случайность; • многократность; • положительная и отрицательная обратные связи; Муравьи используют два способа передачи информации: • прямой (обмен пищей и т.п.); • непрямой, т.н. стигмержи (stigmergy). Стигмержи — это разнесенный во времени тип взаимодействия, когда один агент взаимодействия изменяет некоторую часть окружающей среды, а остальные используют эту информацию позже, когда находятся в ее окрестности. Биологически непрямой обмен информациеей осуществляется через феромон (pheromone) — специальный секрет, откладываемый как след при перемещении муравья. Феромон — достаточно стойкое вещество, он может восприниматься муравьями несколько суток. Чем выше концентрация феромона на тропе, тем больше муравьев будет по ней двигаться. Со временем феромон испаряется, что позволяет муравьям адаптировать свое поведение под изменения внешней среды. Распределение феромона по пространству передвижения муравьев является своего рода динамически изменяемой глобальной памятью муравейника. Любой муравей в фиксированный момент времени может воспринимать и изменять лишь одну локальную ячейку этой глобальной памяти. Таким образом, в общем случае рассматриваются слепые муравьи, не способные чувствовать близость пищи, но ориентирующиеся по запаху феромона. Концепция муравьиных алгоритмов Муравьиные алгоритмы представляют собой вероятностную жадную эвристику, где вероятности устанавливаются, исходя из информации о качестве решения, полученной из предыдущих решений. Идея муравьиного алгоритма заключается в моделировании способности муравьев быстро находить кратчайший путь от муравейника к источнику пищи и адаптироваться к изменяющимся условиям, находя новый кратчайший путь. Муравей метит путь феромоном, и эта информация используется другими муравьями для выбора пути. Это элементарное правило поведения и определяет способность муравьёв находить новый путь, если старый оказывается недоступным. В качестве примера рассмотрим случай, показанный на рис. 5.1, когда на оптимальном пути возникает преграда. В этом случае необходимо определение нового оптимального пути. Дойдя до преграды, муравьи с равной вероятностью будут обходить её справа и слева. Однако, те муравьи, которые случайно выберут кратчайший путь, будут быстрее его проходить, и за несколько циклов передвижений он будет более обогащён феромоном. Поскольку движение муравьёв определяется концентрацией феромона, то следующие муравьи будут предпочитать именно этот путь, продолжая обогащать его феромоном. Рис. 5.1. Пример нахождения муравьями нового пути Положительная обратная связь быстро приведёт к тому, что кратчайший путь станет единственным маршрутом движения большинства муравьёв. Испарения феромона – отрицательная обратная связь – гарантирует, что найденные неоптимальные решения будут терять свою привлекательность и муравьи будут искать другие пути. Допустим, что мы моделируем процесс такого поведения на некотором графе. Рёбра графа представляют собой возможные пути перемещения муравьёв в течение определённого времени. Тогда наиболее обогащённый феромоном путь по рёбрам графа и будет являться решением задачи, полученным с помощью муравьиного алгоритма. Обобщенный муравьиный алгоритм Любой муравьиный алгоритм, независимо от модификаций, представим в следующем виде Циклическое выполнение этапов поиска (пока условия выхода не выполнены): • Формирование колонии муравьёв; • Поиск целевых вершин; • Обновление феромона; Рассмотрим последовательно каждый этап алгоритма: 0. Задание начальных условий поиска. Задаём начальный одинаковый уровень феромона на ребрах графа. Он инициализируется небольшим положительным числом τ0 для того, чтобы на начальном шаге вероятности перехода в следующую вершину не были нулевыми. 1. Формирование колонии муравьёв. Создаем колонию из N муравьев и помещаем их в начальную вершину графа – b0. 2. Поиск целевых вершин. Вероятность перехода из вершины bi в вершину bj определяется по следующей формуле , (5.1) где τij - уровень феромона на ребре ij на итерации t, Ji- множество потомков вершины i. Выражение (5.1) определяет лишь вероятности выбора того или иного ребра. Выбор для любого муравья каждый раз осуществляется по принципу «колеса рулетки». Если муравей находится в вершине bi, то выбор следующей вершины происходит случайным образом. Например, каждому ребру графа (рис. 5.2) назначается сектор на рулетке единичной площади. Площадь сектора пропорциональна вероятности (5.1) перехода по этому ребру. Для каждого муравья, находящегося в вершине bi формируется случайное число из диапазона (0,1), выпадающее на один из секторов. Муравей направляется по тому ребру, которое соответствует выпавшему сектору. Рис. 5.2 Выбор вершины в муравьином алгоритме. 3. Обновление феромона. Только после достижения целевой вершины каждый муравей k, прошедший по ребру ij откладывает на нем некоторое количество феромона: где Lk(t) — длина маршрута, пройденного муравьем k на итерации t; Q=const – запас феромона одного муравья на один маршрут. Если муравей не достигает целевой вершины, а заканчивает маршрут в «тупиковой» вершине, то он не откладывает феромон на пройденных ребрах. Для исследования всего пространства решений необходимо обеспечить испарение феромона — уменьшение во времени количества отложенного на предыдущих итерациях феромона. Обозначим коэффициент испарения феромона через . Тогда правило обновления феромона на следующей итерации поиска примет вид: , где , Kij – множество муравьев, прошедших по ребру ij на итерации t. После завершения цикла поиска – t вся колония из N муравьев помещается вновь в начальную вершину b0, (шаг 1), откуда начинается следующий цикл поиска t+1. Общее количество муравьев в колонии остается постоянным на протяжении выполнения алгоритма. Многочисленная колония муравьев приводит к быстрому усилению субоптимальных маршрутов, а когда муравьев мало, возникает опасность потери кооперативности поведения из-за их ограниченного взаимодействия и быстрого испарения феромона. Поскольку в основе муравьиного алгоритма лежит моделирование передвижения муравьёв по некоторым путям, то такой подход может стать эффективным способом поиска рациональных решений для задач оптимизации, допускающих графовую интерпретацию. Эффективность муравьиных алгоритмов растёт с ростом размерности решаемых задач оптимизации. На основе применения муравьиных алгоритмов получены хорошие результаты для таких сложных оптимизационных задач, как задача коммивояжёра, транспортная задача, задача календарного планирования, задача раскраски графа, квадратичная задача о назначениях, задача оптимизации сетевых трафиков и ряд других. 3.2.3 Поиск на графе Графы и деревья Особенность стратегии локального поиска состоит в том, что состояния среды, полученные на предыдущих шагах, забываются. Поэтому часто приходится заново порождать те состояния, которые встречались раньше. С целью устранения этого недостатка в стратегиях поиска применяют графовые структуры, сохраняющие информацию о всех получаемых состояниях. Стратегия поиска в данном случае создает граф, вершинами которого являются порожденные ею состояния bi (i=0,1,2,...,ц), а связи между вершинами определяются выполненными действиями агента. Суть решения задачи при этом сводится к поиску пути на графе от начальной вершины b0 к целевой вершине bц. Как известно, граф представляет собой непустое множество вершин вместе с множеством соединяющих их ребер (дуг). Вершины с ненаправленными связями образуют неориентированный граф, а с направленными - ориентированный или орграф (рис.6.1). В этом графе b1 - родительская вершина для вершин b2, b3; b2 - вершина-преемник (потомок), или дочерняя вершина для b1 и вершина-родитель для b3; b3 - вершина-преемник (потомок), или дочерняя вершина для b1 и b2. У ориентированных графов отношения родства между вершинами могут быть неоднозначными. Например, вершина b3 одновременно дочерняя и «внучатая» по отношению к b1. Рис. 6.1 Граф Дерево - частный случай графа, в котором каждая вершина имеет не более одного родителя (рис. 6.2). Вершина, не имеющая родителя, называется корневой, а вершины, не имеющая потомков – концевыми (листьями дерева): Рис. 6.2 Дерево Глубина корневой вершины, как правило, принимается равной нулю. Глубина любой другой вершины равна глубине родительской вершины плюс единица. Путь на дереве глубиной m от b0 до bk есть последовательность таких вершин, для которых каждая последующая вершина bj+1 является преемником предыдущей вершины bj. Иногда дугам или ребрам приписывают положительные числа, соответствующие стоимостям соответствующих действий (цена связи между вершинами). Стоимость пути между вершинами b0 и bk равна сумме стоимостей всех дуг, лежащих на пути между ними. При наличии нескольких путей между b0 и bk часто приходится искать путь минимальной стоимости. Если концевая вершина bk является элементом некоторого множества {bk} концевых вершин, удовлетворяющих целевым условиям, то множество {bk} называется целевым, а любой его элемент bk называется целевой вершиной. Граф может быть определен явно и неявно. При явном определении граф задается таблицей вершин, дуг и их стоимостей. Однако при больших размерностях графов возникают трудности их явного задания. Поэтому часто используют неявное определение графов. При неявном определении задается начальная вершина b0 и перечень возможных действий агента (операторов построения преемников). Процедура поиска раскрывает вершины с помощью операторов и порождает явное представление графа (например, граф игры в «восемь», в шашки, шахматы и т.п.). Иными словами, стратегия поиска на графе одновременно с поиском пути между вершинами b0 и bk порождает явно заданный подграф поиска на основе неявно определенного графа решения задачи в пространстве состояний среды. Общая процедура поиска на графе Рассмотрим общую процедуру поиска по графе. Процесс явного порождения части неявно заданного графа можно неформально определить следующим образом. Процедура ГРАФ 1. Организовать список, называемый ОТКРЫТ (СпО), и занести в него начальное состояние среды b0 (b0 -> СпО). 2. Создать список, называемый ЗАКРЫТ (СпЗ), и обнулить его (Сп3=O). 3. Если список ОТКРЫТ пуст, то выдать сигнал НЕУДАЧА и перейти на конец (метка 10), иначе следующий шаг. 4. Выбрать первую вершину в списке ОТКРЫТ, удалить ее из этого списка и поместить в список ЗАКРЫТ, обозначив через bk . 5. Если bk = bЦ , то зафиксировать УСПЕХ, выдать путь, ведущий от b0 к bЦ и перейти на конец (метка 10), иначе следующий шаг. 6. Раскрыть вершину bk , порождая множество {bМ}k преемников, не являющихся предками bk и поместить их в список ОТКРЫТ, если они ранее не были в него записаны. 7. Ввести указатели от введенных в СпО вершин bМ из множества {bМ}k к вершине - предку bk, т.е. bМ(bk). При необходимости произвести переориентацию указателей уже имеющихся в списке вершин. 8. Переупорядочить список ОТКРЫТ в соответствии с эвристической значимостью вершин. 9. Перейти на метку 3. 10. КОНЕЦ Процедура имеет достаточно общий характер и заключает в себе большое разнообразие отдельных алгоритмов поиска на графе. Процедура порождает в явной форме граф G, называемый графом поиска и подмножество T графа G, называемое деревом поиска. Каждая вершина из G содержится также и в Т. Дерево поиска определено указателями, которые устанавливаются на шаге 7. Каждая вершина (за исключением начальной b0) имеет указатель, направленный только к одному из родителей в G, который определяет ее единственного родителя в T. Каждый возможный путь к какой-либо вершине, найденный этим алгоритмом хранится в явном виде в G. Один выделенный путь к любой вершине определен на дереве Т. На шаге 3 процедуры ГРАФ вершины в списке ОТКРЫТ являются теми (концевыми) вершинами дерева поиска, которые еще не выбирались для раскрытия. Вершины в списке ЗАКРЫТ являются либо неконцевыми вершинами дерева поиска, либо концевыми, уже выбранными для раскрытия и не породившими преемников в графе поиска. На шаге 8 процедура ГРАФ упорядочивает вершины в списке ОТКРЫТ так, чтобы «лучшая» из них была выбрана для раскрытия на шаге 4. Это упорядочение может основываться на эвристических функциях оценки состояний или на произвольных критериях. Всякий раз, когда вершиной, выбранной для раскрытия, оказывается целевая вершина, процесс успешно завершается. Решающий путь от исходной вершины к целевой можно затем восстановить, прослеживая (в обратном порядке) указатели от целевой вершины к b0. Процесс заканчивается неудачей, когда на дереве поиска не остается концевых вершин, еще не выбранных для раскрытия. Если процесс завершается неудачей, то целевая вершина не может быть достижима из начальной. Шаг 7 процедуры ГРАФ нуждается в дополнительном пояснении. Если бы неявно заданный граф, на котором ведется поиск, был деревом, мы могли бы быть уверены, что никакой из преемников, порожденных на шаге 6, не порождался бы ранее. Каждая вершина дерева является преемником только одной вершины и поэтому порождается один раз – когда раскрывается его единственная вершина - родитель. Граф G в этом случае совпадает с деревом T и нет необходимости менять родителей вершин в подмножестве Т. Если же рассматриваемый неявно заданный граф не является деревом, то возможно, что некоторые вершины, порожденные на шаге 6, уже порождались, т.е. они уже могут быть в списке ОТКРЫТ или ЗАКРЫТ. Когда процесс поиска порождает вершину, уже возникавшую ранее, он находит к ней другой путь (возможно лучший). Желательно, чтобы дерево поиска сохраняло тот из найденных путей от b0 к любой другой его вершине bk, стоимость которого минимальна. Если вновь найденный путь короче (дешевле) прежнего, дерево поиска преобразуется – родительские функции утверждаются за последним родителем вновь порожденной вершины (рис.6.3). Рис. 6.3 Граф G и дерево T поиска до раскрытия вершины b5 Рис. 6.4 Граф G и дерево T поиска после раскрытия вершины b5 Вершины, закрашенные темной заливкой на рис 6.3 находятся в списке ЗАКРЫТ, а вершины закрашенные светлой заливкой – в списке ОТКРЫТ. До раскрытия вершины b5 вершина b12 была преемником вершины b8, потому что из двух путей от b12 до начальной вершины b0 более коротким (4 ребра) является путь (b12-b8-b4-b1-b0). Второй путь (b12-b9-b10-b6-b2-b0) более длинный (5 ребер). После раскрытия вершины b5 вновь порождается потомок b9, который уже находится в списке ЗАКРЫТ, но при этом алгоритм находит новый более короткий путь (3 ребра) между b12 и b0 – (b12-b9-b5-b0). Происходит переориентация указателей на родителей у вершин b12 и b9. Рядом показаны деревья поиска Т, соответствующие на каждом этапе графу поиска G. На графе G отображены все пути между любой вершиной графа и начальной вершиной, а на дереве Т только кратчайшие пути. При отсутствии эвристической информации, можно произвольно устанавливать очередность раскрываемых вершин. Различают неинформированные стратегии поиска в глубину и стратегию полного перебора (поиск в ширину). Первый тип неинформированного поиска располагает вершины списка ОТКРЫТ в порядке убывания их глубины в дереве поиска. Наиболее глубокие вершины помещаются в списке на первое место. Вершины, расположенные на одинаковой глубине, упорядочиваются произвольно. Процесс поиска, являющийся результатом такого упорядочения, называется поиском в глубину, поскольку для раскрытия всегда выбирается наиболее глубоко расположенная вершина дерева поиска. Для предупреждения неограниченного ухода процесса поиска по бесперспективному пути вводится ограничение на глубину. Вершины, глубина которых на данном дереве поиска превышает эту границу, вообще не порождаются. Второй тип неинформированной процедуры поиска располагает вершины списка ОТКРЫТ в порядке возрастания их глубины в дереве поиска. Процесс поиска, являющийся результатом такого упорядочения, называется поиском в ширину, поскольку раскрытие вершины в дереве поиска происходит вдоль "уровня" на одинаковой глубине. Эвристические процедуры поиска на графе Для многих задач имеется возможность использовать некоторую информацию, относящуюся к рассматриваемой задаче, чтобы содействовать сокращению поиска. Информацию такого рода обычно называют эвристической. Некоторые эвристики существенно уменьшают затраты на поиск, но не гарантируют нахождения пути минимальной стоимости. В большинстве практических задач ИИ стремятся к тому, чтобы минимизировать некоторую комбинацию стоимости пути к цели и стоимости поиска, необходимого для нахождения этого пути. Более того, наиболее интересны такие методы поиска, которые минимизируют эту комбинацию, усредненную по всем ожидаемым задачам. Если усредненная стоимость комбинации для первого метода поиска меньше, чем для второго, то говорят, что первый метод поиска имеет большую эвристическую силу, чем второй. Усредненные стоимости комбинаций в действительности никогда не вычисляются. Во-первых, потому, что трудно принять решение, каким образом комбинировать стоимость пути и стоимость поиска. Во-вторых, потому, что трудно определить распределение вероятностей на множестве задач, с которыми придется столкнуться. Поэтому вопрос о том, обладает ли один метод поиска большей эвристической силой по сравнению с другим, обычно решается на основе интуиции, накопленной в процессе работы с этими методами. Частным случаем эвристического поиска является поиск с использованием оценочных функций. Эвристическую информацию можно использовать для упорядочения вершин в списке ОТКРЫТ на шаге 8 процедуры ГРАФ таким образом, чтобы процесс поиска распространялся по тем участкам графа, которые представляются наиболее перспективными. Чтобы применить такую процедуру упорядочения, нужен метод вычисления "перспективности" вершины. Один из таких методов предусматривает использование функции, называемой оценочной и принимающей на вершинах действительные значения. В основе оценочных функций лежат самые разнообразные идеи: • определить вероятность того, что некоторая вершина принадлежит наилучшему пути; • предложить меры расстояния или различия между произвольной вершиной и целевым множеством; • в настольных играх или головоломках для рассматриваемой конфигурации подсчитать число очков на основании тех особенностей, которые связаны с перспективностью этой конфигурации. Используем функцию некоторую f(bi) для упорядочения вершин в списке ОТКРЫТ на шаге 8 процедуры ГРАФ. Условимся, что вершины в списке ОТКРЫТ расположены в порядке возрастания соответствующих значений функции f(bi). При совпадении значений f(bi) упорядочение осуществляется произвольно, но целевым вершинам bц всегда отдается предпочтение. Считаем, что вершина, имеющая меньшую оценку, с большей вероятностью окажется на оптимальном пути. Способ, с помощью которого оценочная функция используется в процедуре ГРАФ для упорядочения вершин, можно пояснить, вновь рассмотрев пример игры в «восемь». Возьмем простую оценочную функцию f(bi)= d(bi) + w(bi), (6.1) где d(bi) - глубина вершины bi на дереве поиска и w(bi) - число находящихся не на нужном месте клеток в состоянии, связанном с вершиной bi . Таким образом, конфигурация исходной вершины имеет f(b0) = 0+4=4. Результаты применения процедуры ГРАФ к игре в «восемь» с использованием такой оценочной функции приведены на рис 6.5. Значения f(bi) для каждой вершины обведены прямоугольником; отдельно выписанные числа указывают на порядок, в котором раскрываются вершины. Здесь найден тот же решающий путь, что и помощью других методов поиска, но использование оценочной функции позволило раскрыть значительно меньше вершин. Если применить оценочную функцию, равную просто f(bi)= d(bi), то получаем процесс поиска в ширину. Рис 6.5 Поиск с применением оценочной функции Выбор оценочной функции в значительной степени определяет результаты поиска. Использование оценочной функции, которая не может различить среди нескольких вершин действительно перспективную, может дать пути, стоимости которых превышают минимальную; в то же время использование функции, переоценивающей перспективность всех вершин, приводит к раскрытию слишком многих вершин. 3.4 ПОИСК НА ИГРОВЫХ ДЕРЕВЬЯХ Игры с полной информацией В интеллектуальных играх соревнование между участниками заключается в том, что они поочередно принимают решения, не зная, какое следующее решение принимает противник. Нас будут интересовать те игры, в которых либо один игрок выигрывает (а другой проигрывает), либо между ними заключается ничья. Таковы игры в шашки, крестики-нолики, шахматы и им подобные. Классический подход, реализуемый интеллектуальным агентом для решения этой задачи, состоит в прогнозировании последующих своих ходов и ответных ходов противника: если я сделаю такой ход, тогда противник может ответить тем или иным ходом, на каждый из этих ходов в моем распоряжении имеются такие-то ответы и т.д. В итоге можно построить дерево (или граф) допустимых ходов и возможных игровых позиций. В результате анализа, взвесив все «за» и «против» той или иной позиции, агент делает ход (ход первого уровня), который ему представляется наилучшим. Эти идеи можно проиллюстрировать на примере следующей игры типа «ним». Перед двумя игроками в одну кучку сложены некоторые предметы, допустим, что это монеты. Первый игрок делит исходную кучку на две обязательно неравные части. Далее игроки по очереди делят на неравные части одну из получающихся кучек (выбирая ее каждый раз по своему усмотрению). Игра продолжается до тех пор, пока во всех кучках не окажется по одной или по две монеты, после чего продолжение игры станет невозможным. Проигрывает тот, кто первым не сможет сделать свой ход. Назовем наших игроков (агентов) MAX и MIN, и пусть первый ход делает MАХ. Рассмотрим ситуацию, когда в кучке 7 монет. Для этой игры состояния среды можно представить неупорядоченной последовательностью чисел, представляющих число монет в разных кучках, а также указанием на то, чей ход следующий. Так (7,MАХ)-это исходная конфигурация. В ней MАХ имеет три различных хода, приводящих к конфигурации (6,1 MIN), (5,2 MIN) или(4,3 MIN). Полный граф этой игры, полученный применением ко всем состояниям среды всех возможных действий агентов, показан на рис.7.1. Рис. 7.1 Полный граф игры Все концевые вершины соответствуют позициям, проигрышным для игрока, делающего следующий ход. С помощью этого игрового графа можно показать, что независимо от поведения игрока MАХ игрок MIN всегда может выиграть. На рис.7.1 выигрышная стратегия показана жирными линиями. Из рисунка видно, что для игровых деревьев (графов) не обязательно указывать чей следующий ход. Каждый уровень соответствует ходу одного из игроков. В нашем примере четные уровни это ходы игрока MАХ, а нечетные уровни - ходы игрока MIN (самая верхняя, исходная вершина лежит на нулевом, т.е. четном уровне). Минимаксная процедура Поиск на графе выигрышной стратегии в сложных играх, таких как шахматы или шашки, для целиком взятой партии является совершенно нереальной задачей. Из-за большой комбинаторной сложности этих игр примитивный алгоритм поиска, который останавливается только в заключительных (окончательных) позициях игры, становится полностью непригодным. Известны оценки, утверждающие, что игровое дерево партии в шашки содержит 1040 вершин, а в шахматы – 10120. Эти оценки основаны на предположении, что из любой шахматной позиции может быть сделано приблизительно 30 допустимых ходов, а заключительные позиции возникают на глубине 40 ходов. Каждый ход состоит из двух полуходов (по одному полуходу на каждого участника игры). Рис. 7.2 Оценка дерева игры в шахматы Естественно, в различных местах дерева, показанного на рис.7.2, встречаются одинаковые позиции. Тем не менее, доказано, что количество различных позиций на шахматной доске намного превосходит возможности любых компьютеров, которые могут быть созданы в обозримом будущем. Для порождения полного дерева игры потребуется время, измеряемое столетиями. Применение методов эвристического поиска, использующих оценочные функции вершин не спасает ситуацию – коэффициент ветвления не снижается до приемлемого уровня. Однако, цель поиска на игровом дереве может быть просто в отыскании хорошего первого хода. После этого можно сделать найденный ход, подождать ответного хода противника и снова начать поиск хорошего первого хода. Можно применить или поиск в ширину, или поиск в глубину, или эвристические методы. Надо лишь ввести несколько искусственных условий остановки, основанных на таких факторах, как ограничение на время и объем памяти или наибольшая допустимая глубина вершин в дереве поиска. По окончании поиска нужно выделить на графе поиска претендента на «наилучший» первый ход. Претендента можно найти, применив к концевым вершинам графа поиска оценочную функцию. Эта функция измеряет «ценность» позиции, представленной концевой вершиной. Выбор оценочной функции основан на учете свойств игровых позиций. Например, для шашек это может быть: • относительный перевес в фигурах; • контроль над центром; • контроль дамок над центром. При анализе игровых деревьев обычно используют соглашение, по которому позиции, выгодные для игрока МАХ, оцениваются положительными значениями, а позиции выгодные MIN – отрицательными. Значения оценочной функции, близкие к 0, соответствуют тем «ничейным» позициям, которые не особенно выгодны ни MAX, ни MIN. Хороший первый ход может быть найден с помощью процедуры, называемой МИНИМАКСНОЙ. Будем считать, что если бы игроку MAX был бы представлен выбор концевых вершин, то он бы выбрал ту, на которой значение оценочной функции – наибольшее. Следовательно, родителю концевых вершин MIN-вершин (который сам является MAX-вершиной) присваивается возвращенное значение, равное максимальному значению оценочной функции на концевых вершинах. С другой стороны, если игроку MIN надо выбирать среди концевых вершин, то он скорее всего выберет ту, на которой значение оценочной функции наименьшее (т.е. наибольшее по модулю отрицательное число). Следовательно, родителю концевых MAX-вершин (который сам является MIN-вершиной) присваивается возвращенное значение, равное минимальному значению оценочной функции на концевых вершинах. После присвоения возвращенных значений всех концевых вершин строятся возвращенные значения на следующем уровне, причем считается, что игрок MAX предпочитает выбирать вершины с наибольшим возвращенными значениями, а игрок MIN – с наименьшими. Так, уровень за уровнем значения «возвращаются» до тех пор, пока возвращенные значения не будут присвоены непосредственным потомкам корневой вершины. Если эта вершина соответствует ходу игрока MAX, то он должен выбирать в качестве первого хода тот, который соответствует дочерней вершине с наибольшим возвращенным значением. Пример минимаксного дерева приведен на рис. 7.3. Рис. 7.3 Минимаксное дерево На этом рисунке уровни позиций, в которых должен ходить игрок MAX, чередуются с позициями, в которых право сделать ход передается игроку MIN. Значения позиций нижнего уровня определяются с помощью функции оценки. Стоимость внутренних вершин можно вычислить, поднимаясь снизу вверх, от одного уровня к другому до тех пор, пока не будет достигнута корневая вершина. Тогда возвращенная оценка (стоимость) вершины d будет определяться максимальной оценкой дочерних вершин - max(-2, 7, 0)=7, т.к. право выбора хода из позиции d передано игроку MAX. При этом возвращенная оценка (стоимость) вершины b будет определяться как минимальной оценкой дочерних вершин - min(7,9)=7, т.к. право выбора хода из позиции b находится у игрока MIN. На рис. 7.3 результирующая возвращенная оценка корневого узла равна 7, поэтому наилучшим ходом для игрока MAX в позиции a является a-b, наилучшим ответом для игрока MIN является b-d, и т.д. Такая последовательность позиций в игре называется основным вариантом. Основной вариант определяет для обоих участников игру, оптимальную в соответствии с принципом минимакса. Оценка позиций на основном варианте не изменяется. Полезность этой процедуры, в целом основана на предположении, что возвращенные значения для потомков корневой вершины более надежны в качестве оценок окончательной относительной ценности соответствующих им позиций, нежели значения, которые можно было бы получить непосредственным применением к этим позициям оценочной функции. В конечном итоге, возвращенные значения основаны на «просмотре вперед» по игровому дереву и поэтому зависят от свойств, проявляющихся ближе к окончанию игры. Пример использования минимаксной процедуры Рассмотрим простой пример игры в «крестики-нолики» на поле 3х3. Известно, что MAX ставит «крестик» (x), MIN ставит нолик (o), первый ход делает MAX. Проведем «поиск в ширину», пока не получим все вершины второго уровня, а затем к позициям, соответствующим этим вершинам, применим оценочную функцию. Пусть для позиции bi оценочная функция f(bi) задается следующими условиями: 1. Если в позиции bi не выигрывает ни один из игроков, то f(bi) = (число строк + число столбцов + число диагоналей, на данный момент целиком свободных для игрока MAX) – (число строк + число столбцов + число диагоналей, на данный момент целиком свободных для игрока MIN). 2. Если в позиции bi выигрыш получает игрок MAX, то f(bi) = ∞ ( или большое положительное число). 3. Если в позиции bi выигрыш получает игрок MIN, то f(bi) = - ∞ ( или большое отрицательное число). Пример: позиция bi имеет вид (рис.7.4), тогда для нее значение оценочной функции f(bi) = 6 – 4 = 2. Рис. 7.4 При порождении дочерних вершин (позиций) используется свойство симметрии игрового поля относительно главных диагоналей, средней строки и среднего столбца. Поэтому следующие позиции (рис. 7.5) будут считаться идентичными: рис. 7.5 Симметрия позволяет уменьшить коэффициент ветвления игрового дерева на начальной стадии игры, а на более поздних стадиях игры он остается малым вследствие уменьшения числа свободных клеток на доске. На рис. 7.6 показано дерево, полученное в результате поиска на глубину 2. Под концевыми вершинами указаны значения оценочной функции, а рядом с вершинами второго уровня показаны возвращенные значения. рис. 7.6 Дерево игры на глубину в два полухода Поскольку наибольшим возвращенным значением обладает позиция с оценкой f(bi) =1, то она и выбирается в качестве первого хода (это наилучший первый ход игрока MAX). Предположим, что MAX сделал этот ход, а MIN в ответ поставил «нолик» в одну из свободных клеток (это плохой ход для MIN, но он может придерживаться любой стратегии поиска). Затем из новой позиции игрок MAX осуществляет поиск на два уровня вниз. Получается новое дерево поиска (рис.7.7), МАХ выбирает наилучший ход из двух возможных и т.д. до окончания игры. Рис. 7.7 Дерево игры на глубину в два полухода (второй этап). Альфа-бета отсечение. В минимаксной процедуре поиска на игровом дереве с оценочной функцией процесс порождения дерева поиска и процесс оценки позиции полностью отделены друг от друга. Оценка позиции может начаться только после завершения порождения дерева поиска. В некоторых случаях такое разделение приводит к реализации крайне неэффективной стратегии. Если же оценивать концевые вершины и вычислять возвращенные значения по мере порождения дерева, то для нахождения столь же хорошего хода длительность требующегося на это поиска можно существенно сократить. Основная идея метода состоит в сравнении наилучших оценок, полученных для полностью изученных ветвей, с наилучшими предполагаемыми оценками для оставшихся ветвей. Можно показать, что при определенных условиях некоторые вычисления являются лишними. В отличие от метода минимакса, который заключается в построении пространства ходов путем их прямого перебора, в методе отсечений значительная часть ходов подвергается неявному перебору, проводимому с помощью процедуры отбрасывания частей дерева. Пусть вершина S соответствует позиции (рис.7.8), в которой ход принадлежит игроку MAX. При этом в распоряжении игрока MAX несколько возможных ходов, два из которых показаны на рисунке. В результате одного из них будет получена позиция A, в результате другого – позиция Y. Пусть позиция A уже полностью проанализирована и найдено ее значение оценки - . Перейдем к анализу позиции Y. Допустим, что один ход из этой позиции приведет к позиции Z, оценка которой по методу минимакса равна z. Пусть z< , а y – оценка вершины Y, тогда в любом случае выполняется неравенство yβ. В этом случае процедура называется бета-отсечением (рис.7.9). Рис. 7.9 Бета-отсечение Применив эту процедуру к ветвям анализируемого дерева, находящимся на большей глубине, можно показать, что они также могут быть отброшены, при условии, что вершины дерева принадлежат уровням хода одного игрока. Пусть игрок MAX должен сделать ход из позиции S (рис. 7.10) и имеет две возможности выбора позиций A или U. Положим, что полный анализ A завершен и получена возвращенная оценка  Рис. 7.10.Глубокое альфа-отсечение Анализируя позицию U, можно заметить, что после нечетного числа промежуточных полуходов, в данном случае трех, возникает позиция Z с оценкой z. Снова допустим, что z<. Для вершины Y, расположенной на более высоком уровне, непосредственно следующим за Z, найдем оценку y, которая удовлетворяет условию y≤z, так как ход из позиции Y принадлежит игроку MIN. И в данном случае результат анализа остальных позиций, вытекающих из Y, не может изменить конечного результата оценки s. Покажем это. Для оценки позиции V справедливо неравенство v≥y, так как право хода из этой позиции принадлежит игроку MAX. Если v>y, то результаты анализа других ходов не могут привести к изменению значения оценки v, так как y≤z, и величина y может быть только уменьшена. Если v=y, тогда справедливо неравенство v=y≤z<, то есть вершина V получает оценку меньшую, чем вершина A. Эта ситуация уже рассмотрена выше. Следовательно, в обоих случаях оценка s вершины S не зависит от других ветвей дерева, выходящих из узла Y и анализ последних можно не производить. Такая ситуация называется глубоким альфа-отсечением. Рассуждая аналогично, можно рекуррентно спуститься до вершины Z, лежащей на уровне произвольной глубины, принадлежащем тому же игроку, что и уровень S. Процедура отсечения может быть применена только начиная с того момента, когда получены оценки по крайней мере двух конечных узлов. На рис. 7.11 показан пример игрового дерева к которому применена минимаксная процедура возвращения оценок позиций путем восхождения по ветвям. На рис 7.12 показано применение процедуры альфа-бета отсечения к тому же игровому дереву. рис. 7.11 Пример применения минимаксной процедуры. Рис. 7.12 Пример применения процедуры альфа-бета отсечений. Процедура отсечений дает тот же результат, что и метод минимакса, но выполняется быстрее. С ее помощью можно получить хорошие результаты при удачно составленной оценочной функции и достаточно большой глубине анализа, что требует большого объема вычислений. Процедура отсечений является тем более производительной, чем более упорядоченно расположены вершины при отыскании каждого хода. В идеальном случае, недостижимом на практике, вершины на каждом уровне должны располагаться по монотонно убывающим значениям оценки. Рассмотренные процедуры систематического перебора допустимых ходов обладают рядом существенных недостатков. Первый недостаток заключается в полном отсутствии игровой стратегии. Каждая новая позиция рассматривается в отрыве от всех остальных. Процедуры указанного типа не ведут игру, а анализируют последовательность позиций, полностью независимых друг от друга. Минимакс не позволяет действовать в соответствии с заранее выбранным планм. Все принимаемые решения определяются оценочной функцией. Второй недостаток состоит в так называемом эффекте горизонта. Процедура не может оценить последствия хода, которые проявляются на глубине, превышающей предельную глубину анализа дерева.