Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по базам знаний и экспертным системам - файл 1.doc


Лекции по базам знаний и экспертным системам
скачать (1259 kb.)

Доступные файлы (1):

1.doc1259kb.24.11.2011 09:16скачать

содержание
Загрузка...

1.doc

1   2   3   4   5   6   7   8   9   10
Реклама MarketGid:
Загрузка...
^

Natural Comp


  1. Генетические алгоритмы.

  2. Муравьиные алгоритмы.

  3. Эволюционное программирование.

  4. Нейронные сети.

  5. DNA Computing.

  6. Клеточные автоматы.
^

Генетические алгоритмы


Моделирование естественного отбора. Каждому объекту из аА ставится в соответствие хромосома (последовательность элементов составл., которая называется геном) (как правило – это линейный вектор).

U(a) – мера полезности состояния а (или мера близкая состоянию а к целевым состояниям).

На множестве А вводим операции, каждая описывает возможности преобразования хромосом:

  • операция кроссинговер (перекрёст)  V(a), V(b)  разбиваем на несколько частей (2 части):

V(a) V(в)




V1(a) V2(a) V1(b) V2(b)
V1(a)  V2(b) V1(b)  V2(b)


  • Мутация: выбирается случайным образом генетическое значение, каждое заменяется (0->1).

  • Инверсия: V1(a), V2(a), V3(a) ( порядок следования в средней части меняется на противоположное).

Этапы: 1. А0 – случайное множество ситуаций (строится).

2. Выбираем подмножество 0 такое что:

0 = {a| aAo, U(a)>= }




Выбираем самые полезные пары функция полезности
3. Строится S0(0) – множество позиций, каждая может быть построена с помощью операции.

4. (0) = {a| a S0(0), U(a)>= }

Получаем: А1=0 S(0).

Повторяем 1-4 до Аi=Ai-1.

Пример использования: (использование для поиска экстремумов функций для решения не полиномиальных задач).

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

I – соответствующий гамильтоновый цикл в группе.

Любой гамильтоновый путь описывается числами 1,…,n.

35214 1 3

(i, (i)) 2

[1..n] 5

[i] 4

Операция 1: 1, 2 выбираем случайным образом j (ген).

j=3

Из вектора 1 выбираем первые j элементов, которые добавляем элементам 2 отсутствующие в первых элементах из 1.

Мутация: Выбираем два гена i и j и меняем местами.

Инверсия: Выбираем i и j и часть цепочки записываем в обратном порядке.

3|521|4 i=2




31254 j=4

Частота использования мутации и инверсии ниже, чем операции 1.

U(a) – суммарный вес.

U(a)>= оставляем 20% самых хороших.

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

Функция n –переменных.

F(x1, x2,…xn), x1 – 4 байта (вещественные числа).

4n – байтов.

32n – байта.
^

Муравьиный алгоритм


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

Поведение муравьёв регулируется 4 факторами:

  1. Случайность.

  2. Многократность.

  3. Положительная обратная часть.

  4. Отрицательная обратная часть.

Задача состоит из многократных элементов по поиску муравьиного гамильтонового цикла:

dij – расстояние между городами.

ij – 1/ dij – видимость (длина дороги).

dij – каждому ребру приписывается величина: ij(t) – полезность ребра момент времени t.

Для каждого муравья задаётся массив TL (список посещённых городов).

Pijk(t) – вероятность перехода муравья k из города i в j в момент времени t.

Pijk(t) = , если jGL

+=1(коэффициент ), 0 в противном случае.

GL – список вершин, достижимых из вершин i, в которых муравей еще не бывал.

Каждый муравей находит некоторый путь длины e. Мера полезности ребра ij(t+1)=(1-p) ij(t) + e.

e = L/e, где L некая константа приблизительно равная длине наибольшего цикла в этом графе. P – коэффициент забывания (0<p<1).

Замечание

Для ускорения процесса сходимости можно использовать элитных муравьёв, которые на каждой итерации увеличивают оценки полезности рёбер, входящих в кратчайший путь на величину *e=L/emin.

Использование нескольких элитных муравьёв ускорят сходимость алгоритма к субоптимальным решениям.

Выбор оптимального количества муравьёв зависит от задачи. Если мы не используем элитных муравьёв, то мы найдем оптимальное решение, но это достаточно долго. Если 1 или 2 муравья (элитных), то найдем быстрее решение, но с недостаточной точностью. Количество муравьёв = число вершин.
^

Вычислительные задачи


Называется тройка: А=(B, R, F), где В – исходное множество объектов, R – множество условных зависимостей, F – множество функциональных зависимостей.

F: 2B->B, где 2B – множество всех подмножеств множества В.

Условные зависимости – это зависимости вида: если p(x) – предикат, то F(x) – функциональная зависимость.
^

Понятие вершин в графе


Последовательность вершин в гиперграфе V1,…Vn называется гиперпутём в гиперграфе Н, если существует (e1,…,ek) – линейная последовательность такая, что принадлежит {V1,…Vn}.

Разбиение (V1,…Vn) = {V11,…Vn1}{V12,…Vn22} существует гиперребро, инцидентное вершинам, как из первого, так и из второго подмножества.

Для нахождения гиперпути можно воспользоваться алгоритмом обхода в ширину.

На практике используются 3 модификации этого алгоритма:

  1. Прямая волна (X->Z)

  2. Обратная волна(Z->X)

  3. Встречная волна (минимальное пересечение прямой и обратной волны).

Для больших задач 3 алгоритм эффективнее, чем 1 и 2.

Замечание

Вычислительная модель – это компактный способ описания А (множество ситуаций). Вместо перечисления описывается схема генерации элементов.

В рекурсивной вычислительной модели число элементов множества А экспоненциально зависит от количество элементов.

Использование рекурсивных вычислительных моделей требует использования «общих знаний о мире».

Это отношение равенства
Продукционные системы.

Продукция или правило: если А, то В.

{Pi}iu – множество операндов (вместо последовательности).

Множество продукций выполняется параллельно или асинхронно.

Открытость → система пополнена асинхронно → внесение новых свойств не требует изменений предыдущих.

While Not (результат) do

Begin

P1

P2



end

Недостатки:

1. Сложность отладки.

2. Не противоречивость или верификация.

3. Эффективность.

Продукцией называется выражение следующего вида:

  1. Q; P; A->B; N, где i – имя продукции, Q – сфера примененной продукции, Р – условие применимости продукции (набор предикатов).

A->B называется ядром продукции. Как правило можно интерпретировать: если А, то В

Если А, то В иначе С

Если А, то В

Если не А, то С

А – не обязательно логическое выражение. Условие применимой продукции может быть выражена структурно. Например: наличие некоторой конструкции в предметной области.

N – пустословие. Некая последовательность действий, которая выполняется после успешного выполнения продукции. Транзакции являются частным случаем продукции.

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

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

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

С этими данными работают компоненты Q, N, P. Информационная доска объявлений позволяет процессам вывода в продукционной системе и делает наглядный процесс отладки.

Структура алгоритма отражается в доске объявлений.

управление информацией

предметная область

доска объявлений

(взаимодействие между продукцией)

ядра

(описание предметной области)

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

Использование: В системе автоматического проектирования – таблица принятия решения. Описания продукции систем являются табличной формой.

Базовой формой ТПР является следующая структура:




Условия




Операнд 1

Значение




Операнд 2










действие




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

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

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

Существуют различные виды таблиц принятия решения. По типам элементов ТПР подразделяются на:

  1. таблицы с ограниченными элементами;

  2. таблицы с расширенными элементами;

  3. таблицы со смешенными элементами.

Ограниченные элементы: да, нет, неопределенно. Действия могут также отсутствовать. Расширенные элементы исполнения числовых значений и отношений <, >, =, а так же логические операции отношения между ними.

Смешенные элементы – это объединения в одной таблице элементов двух типов.

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

Каждой ТПР соответствует дерево, и эффективность работы таблиц напрямую связана со структурой дерева.
^

Формат таблиц принятия решения


Чаще всего описания модели предметной области задаётся в виде совокупности таблиц принятия решений.

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

Иногда в описании таблицы включены компоненты p и q.

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

Как правило, действия бывают следующих 3-х видов:

  1. присвоить – изменение значения переменной соответствующей заголовку данного столбца.

  2. вычислить – результат выражения присваивается некоторому столбцу

  3. выполнить – выполняется процедура, соответствующая столбцу.

Основная область применения – это многошаговые задачи и управление сложными объектами. Существуют специальные программные решения, специализированные на обработке ТПР.
1   2   3   4   5   6   7   8   9   10



Скачать файл (1259 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru