«системы автоматизированного проектирования», 2008 Дисциплина: «Интеллектуальные подсистемы сапр»




Название«системы автоматизированного проектирования», 2008 Дисциплина: «Интеллектуальные подсистемы сапр»
страница3/36
Дата публикации17.01.2015
Размер2.36 Mb.
ТипДокументы
lit-yaz.ru > Информатика > Документы
1   2   3   4   5   6   7   8   9   ...   36
^

3. Представление задач в пространстве состояний. Методы поиска в пространствах состояний


Фундаментальная идея, которая появилась в результате первых опытов по применению компьютеров для решения игровых задач и головоломок, получила наименование поиск в пространстве состояний. Суть идеи в том, что множество проблем можно сформулировать в терминах 3-х важнейших ингредиентов:

  • исходное состояние проблемы, например исходное состояние головоломки;

  • тест завершения – проверка, достигнуто ли требуемое конечное состояние или найдено решение проблемы (примером может послужить правило определения, собрана ли головоломка);

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

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

В качестве примера рассмотрим задачу построения слова из некоторого множества букв (К И Т). Задавшись набором операций установки букв, можно сформировать пространство состояний.

^ Ориентированный граф (орграф) G=(V,E) состоит из множества вершин V и множества дуг E. Вершины также называются узлами, а дуги – ориентированными ребрами. Дуга представима в виде упорядоченной пары вершин (v, w), где вершина v называется началом, а w – концом дуги. Дугу (v, w) часто записывают как vw и изображают в виде



Говорят также, что дуга vw ведет от вершины v к вершине w, а вершина w смежная с вершиной v.

Вершины орграфа используют для представления объектов, а дуги – для отношений между объектами.

Путем в орграфе называется последовательность вершин v1, v2, ...vn, для которых существуют дуги v1v2, v2v3,...,v n-1vn. Этот путь начинается в вершине v1 и проходя через вершины v2, v3, ..., vn-1, заканчивается в вершине vn. Длина пути – количество дуг, составляющих путь.

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

Цикл – это простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине.

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

Неориентированный граф G=(V, E) состоит из конечного множества вершин V и множества ребер E. В отличие от ориентированного графа, здесь каждое ребро (v, w) соответствует неупорядоченной паре вершин.

Вершины v и w называются смежными, если существует ребро (v, w)

Основные методы поиска:

  • поиск в глубину,

  • поиск в ширину,

  • поиск от наилучшего,

  • метод наискорейшего подъема,

  • стратегия ветвей и границ.


Поиск в ширину



Рис. 1. Простое пространство состояний: а - стартовая вершина, f и j - целевые вершины. Применение стратегии стратегии поиска в ширину дает следующий порядок прохода по вершинам: а,Ь,с, d,e,f. Более короткое решение [а,с, t] найдено раньше, чем более длинное [a,b,e,j].

Поиск в глубину


^

4. Продукционные представления знаний в интеллектуальных системах


Продукции являются наиболее популярным средством представления знаний.

Термин «продукция» предложен американским логиком Э Постом в 1936 г. для определения языков и формальных грамматик. С 1974 г. он находит широкое применение в экспертных системах.

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

Продукционная модель или модель, основанная на правилах, позволяет представить знания в виде предложений типа «Если (условие), то (действие)».

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

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

Программные средства, реализующие продукционный подход: язык OPS 5; «оболочки» или «пустые» ЭС – EXSYS Professional, Карра, ЭКСПЕРТ и др.

В общем виде под продукцией понимают выражение следующего вида:

(i); Q; P; AB; N

где:

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

^ Qсфера применения продукции. Разделение знаний на отдельные сферы позволяет экономить время на поиск нужных знаний.

AB – ядро продукции, являющееся основным элементом продукции. Интерпретация ядра продукции может быть различной, зависит от того, что стоит слева от знака секвенции (). Обычно прочтение ядра выглядит так: ЕСЛИ A, ТО B. Более сложные конструкции ядра допускают в правой части альтернативный выбор: ЕСЛИ А, ТО В1, ИНАЧЕ В2. Секвенция может истолковываться в обычном логическом смысле как знак логического следования В из истинного А (если А не является истинным выражением, то о В-ничего сказать нельзя). Возможны и другие интерпретации ядра продукции, например А описывает некоторое условие, необходимое для того, чтобы можно было совершить действие В.

P - условие применимости ядра продукции. Обычно Р представляет собой логическое выражение (как правило, предикат). Когда Р принимает значение «истина», ядро продукции активизируется. Если Р ложно, то ядро продукции не может быть использовано. Например, если в продукции «НАЛИЧИЕ ДЕНЕГ; ЕСЛИ ХОЧЕШЬ КУПИТЬ ВЕЩЬ X, ТО ЗАПЛАТИ В КАССУ ЕЕ СТОИМОСТЬ И ОТДАЙ ЧЕК ПРОДАВЦУ» условие применимости ядра продукций ложно, т. е. денег нет, то применить ядро продукции невозможно.

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

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

В ряде ИС используются комбинации сетевых и продукционных моделей представления знаний. В таких моделях декларативные знания описываются в сетевом компоненте модели, а процедурные знания — в продукционном. В этом случае говорят о работе продукционной системы над семантической сетью.
^ Классификация ядер продукции:

Ядра продукций можно классифицировать по различным основаниям.

Все ядра делятся на два больших типа:

  • детерминированные - при актуализации ядра и при выполнимости А правая часть ядра выполняется обязательно (Если А, то B обязательно)).

  • недетерминированные - В может выполняться и не выполняться. Интерпретация ядра в этом случае может, например, выглядеть так: ЕСЛИ ^ А, ТО ВОЗМОЖНО В.

Секвенция в детерминированных ядрах реализуется с необходимостью, а в недетерминированных — с возможностью.

Возможность может определяться некоторыми оценками реализации ядра. Например, если задана вероятность выполнения В при актуализации А, то продукция (в простейшем случае продукция состоит лишь из ядра) может быть такой: ЕСЛИ ^ А, ТО С ВЕРОЯТНОСТЬЮ р РЕАЛИЗОВАТЬ В. Оценка реализации ядра может быть лингвистической, связанной с понятием терм-множества лингвистической переменной, например: ЕСЛИ ^ А, ТО С БОЛЬШОЙ ДОЛЕЙ УВЕРЕННОСТИ В. Возможны иные способы задания оценки реализации ядра.

Детерминированные продукции могут быть:

  • однозначными;

  • альтернативными - в правой части ядра указываются альтернативные возможности выбора, которые оцениваются специальными весами выбора. В качестве таких весов могут использоваться вероятностные оценки, лингвистические оценки, экспертные оценки и т. п. (например, ЕСЛИ ^ А, ТО ЧАЩЕ ВСЕГО НАДО ДЕЛАТЬ В1, РЕЖЕ В2).

Особым типом являются прогнозирующие продукции, в которых описываются последствия, ожидаемые при актуализации А, например: ЕСЛИ ^ А, ТО С ВЕРОЯТНОСТЬЮ р МОЖНО ОЖИДАТЬ В.

Графически ядро можно представить в виде дерева:



Популярность продукционных моделей определяется следующими факторами:

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

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

  • ^ Доступность чтения. Подавляющая часть человеческих знаний может быть записана в виде продукций. Человеческие знания являются модульными и поэтому продукционные системы более близки для их представления и легки для чтения.

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

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

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

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

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

^ Недостатки продукционной системы:

  • При большом числе продукций становится сложной проверка непротиворечивости системы продукций.

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

Наблюдение из практики: если число продукций > 1000, то мало шансов, что система продукций во всех случаях будет правильно функционировать.

1   2   3   4   5   6   7   8   9   ...   36

Похожие:

«системы автоматизированного проектирования», 2008 Дисциплина: «Интеллектуальные подсистемы сапр» iconМинистерство образования РФ московский энергетический институт (технический...
Сапр; методы прогнозирования развития средств автоматизированного проектирования. Организация инженерного труда

«системы автоматизированного проектирования», 2008 Дисциплина: «Интеллектуальные подсистемы сапр» iconАвтореферат разослан
Работа выполнена на кафедре "Системы автоматизированного проектирования и поискового конструирования" Волгоградского государственного...

«системы автоматизированного проектирования», 2008 Дисциплина: «Интеллектуальные подсистемы сапр» iconУчебное пособие Санкт-Петербург 2012 Общая информация о курсе Название...
Курс представляет собой руководство по применению системы автоматизированного проектирования Autocad. В книге отражены функциональные...

«системы автоматизированного проектирования», 2008 Дисциплина: «Интеллектуальные подсистемы сапр» iconРабочая программа по курсу «компас-3D»
Программа предназначена для освоения возможностей автоматизации процесса разработки проектной и конструкторской документации в системе...

«системы автоматизированного проектирования», 2008 Дисциплина: «Интеллектуальные подсистемы сапр» iconРабочая программа по курсу «Solid Works»
Программа предназначена для обучения студентов разработке конструкторской и технологической документации в системе автоматизированного...

«системы автоматизированного проектирования», 2008 Дисциплина: «Интеллектуальные подсистемы сапр» iconРабочая программа по курсу «t-flex cad»
Программа предназначена для освоения возможностей автоматизации процесса разработки проектной и конструкторской документации в системе...

«системы автоматизированного проектирования», 2008 Дисциплина: «Интеллектуальные подсистемы сапр» iconПрограмма подготовки должностных лиц и специалистов гражданской обороны...
Программа предназначена для подготовки должностных лиц и специалистов гражданской обороны и Свердловской областной подсистемы единой...

«системы автоматизированного проектирования», 2008 Дисциплина: «Интеллектуальные подсистемы сапр» iconВ семи томах том Интеллектуальные системы (Системы решения проблем)
Интеллсист, их структуры и технологии работы с инструментарием составляют центральную часть тома. Оценка возможностей Интеллсист...

«системы автоматизированного проектирования», 2008 Дисциплина: «Интеллектуальные подсистемы сапр» iconРабочая программа по курсу «компас-автопроект»
Программа предназначена для освоения возможностей автоматизации процесса разработки проектной и технологической документации в системе...

«системы автоматизированного проектирования», 2008 Дисциплина: «Интеллектуальные подсистемы сапр» iconИнтеллектуальные разминки
Они могут использоваться как на уроке, так и во внеклассной работе. Интеллектуальные разминки способствуют повышению интереса школьников...



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница