Определение 4

Множество , состоящее из эффективных решений называется множеством

решений, оптимальных по Парето.

Пример.

	K1	K2	K3
M1	1	5	3
M2	2	4	4
M3	1	4	3
M4	4	5	2

- множество Парето

2. Критерии сравнимы.

1. Метод выделения главного критерия

Пусть имеется главный критерий . Тогда решаем задачу

В этом случае может оказаться, что решения не существует. Тогда нужно

ослабить требования -

2. Метод последовательных уступок.

1 шаг

- получим решение

2 шаг

………………………

n шаг

Если решение существует, то возможны 2 случая:

a). Решение устраивает ЛПР

b). Решение не устраивает ЛПР:

- решение единственное

- решение не единственное

Проблема сокращения поискового пространства

1). Сочетание точных и грубых методов.

Грубые методы - сокращают область поиска решения

Точные методы - ищут оптимальное решение.

2). Использование эвристических функций.

3). Человеко-машинные процедуры поиска оптимального решения.

1). ЛПР задает начальное значение опорного плана и весовых коэффициентов

- скорость изменения решения по i-му критерию.

2). Коректир.

Поиск решения в пространстве состояний на основе эвристической функции

Задача эвристического поиска

, где

S – множество состояний;

- множество допустимых состояний;

- множество начальных состояний;

- множество конечных состояний;

- множество преобразований.

Задача: нахождение последовательности преобразований :

Система поиска

Недетерминированный выбор

Оценка альтернатив и выбор альтернативы

Реализация

+

U-ветвление. Вводится предикат P, определенный на множестве , который имеет значение истина, если это ветвление может быть применено.

U- ветвление корректно 

Способы сокращения поискового пространства

1). Укрупнение пространства поиска. Переход от элементарных состояний к

макросостояниям.

Проблема поиска решается в укрупненном пространстве.

2). Использрвание эвристик.

3). Изменение представления задачи.

Пример

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

1	2	3
4	5	6
7	8	9

Ответ: 16 ходов (4 – если разрешить им передвигаться || )

Поиск решения на основе эвристической функции.

Допустимый алгоритм – это тот алгоритм, который гарантирует отыскание решения.

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

f(s) = f₁(s) + f₂(s) -> min

f₁(s) – оценка пройденного пути.

f₂(s) – оценка оставшегося пути.

_ _ _

f(s) = f₁(s) + f₂(s) -> min

_ _

f₂(s) f₂(s)

Теорема.

_ _

f₂ ^А1(s) f₂ ^А2(s)

Чтобы алгоритм, построенный на основе эвристической функций f был допустим, необходимо и достаточно, что .

Алгоритм А1 более информирован, чем А2 

Критерий эффективности алгоритма поиска.

1. Стоимость решающего пути. S -> min. (допустимый алгоритм)

2. К

   _

   f₂(s)

   оличество раскрываемых при поиске вершин. (оптимальный алгоритм)

3. Объём вычислений, требуемых для получения оценки V -> min.

4. Интегральная оценочная функция.

_S + _N + _V -> min

Критерии оценки эффективности эвристических алгоритмов.

1. Критерий направленности. P

L – длина найденного пути в числе раскрываемых вершин.

T – общее число раскрываемых вершин.

P = 1 => минимальное число вершин.

1. Критерий эффективности ветвлений. B

1. Оценка качества приближённого решения. K

K = 0 => оптимальное решение.

Базовые эвристики сокращения поискового пространства.

1. Перебор этапами (метод maxmin).

2. Ограничение числа дочерних вершин ( отсечение)

3. Упорядочение преобразований P_i ( )

Пример:

	Полный перебор	_ _ f(s) = f1(s) + W(s)	_ _ f(s) = f1(s) + (P(s) + 3Q(s))
P	0.108	0.385	0.419
B	1.86	1.31	1.08

P(s) – сумма расстояний каждой фишки от своего места.

Q(s) – Если фишка нецентральная, то за неё даётся 2 очка, когда за ней следует целевая (фишка на своём месте);

Если фишка центральная, то за неё даётся 1 очка, когда за ней следует целевая (фишка на своём месте);

Задача эвристического поиска

Задача эвристического поиска

, где

S – множество состояний;

- множество допустимых состояний;

- множество начальных состояний;

- множество конечных состояний;

- множество преобразований.

Правила преобразований (P: SS) могут быть заданы в виде продукционных правил:

Пусть на вход поступает . Возможны следующие ситуации:

1). P не применимо к ( ). Возможны два случая:

a). Нет применимых правил (база правил P не полна).

b). Процесс поиска бесконечен.

2). P применимо к ( ). Возможны два случая:

a). Результат конечен:

- единственный;

- неединственный (можно говорить о поиске оптимального (наилучшего)

решения относительно критерия Q).

b). Результат бесконечен.

Допускается бесконечное ветвление, при том условии, что

если был выбран какой-то путь, то до конца добираемся

за конечное число шагов.

Типы задач

1. Задача планирования.

известны: и .

найти: последовательность преобразований

2. Задача прогнозирования.

известно:

найти:

3. Задача диагностики.

известно:

найти:

Поиск в системе продукций

PS=<БП(БЗ), РП(БД),I> , где

БП – база правил

РП – рабочая память (база данных)

I - интерпретатор, реализующий стратегии поиска.

Продукционный цикл

1 этап. Сопоставление и множества продукций из P.

Получаем конфликтное множество CS= ; CS - множество тех правил, левые части которых сопоставимы с .

2 этап. Разрешение конфликтов.

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

AS= ; AS - активное множество.

3 этап. Выполнение правил из AS.

В результате получаем множество . Если , то STOP. Иначе – goto 1.( )

Реализация выбора правил

Детерминированный выбор Параллельное выполнение

Недетерминированный выбор

Детерминированный выбор

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

Могут быть использованы:

1. НАМ (нормальные алгоритмы Маркова).

2. Приоритет (частного перед общим).

3. Рейтинги.

Условия корректности детерминированного выбора

1). Условие коммутативности

2).

Недетерминированный выбор

Возможны два случая:

- мягкий недетерминизм (потом, на каком-то этапе узнаем, какой был сделан выбор)

- жесткий приоритет (не узнаем, что было выбрано)

Условия корректности недетерминированного выбора

1). Условие коммутативности

2). Условие идемпотентности

3). Условие ассоциативности

4). Условие дистрибутивности

5).

Параллельное выполнение

Условия корректности параллельного выполнения

1). Условие коммутативности

2). Условие ассоциативности

3). Условие дистрибутивности

4). Условие останова

5).

(6). Условие идемпотентности

Эффект интерференции

Это означает, что результат параллельного выполнения правил

Пример

Правила

, где {0,0} и {1,1} – не ожидаемые состояния

- если в универсум входит подструктура , то она заменяется на

Зависимости и :

1). По входу:

2). По выходу:

3). По входу / выходу:

В каких случаях параллельное выполнение будет корректно или возможно?

Есть P={ }

1). Матрица параллелизма

Q=|| ||

= =

2). После нахождения активного множества AS= для каждого правила определяем || множество.

Поиск решений в пространстве целей.

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

Z