Лекции в печатном виде (Лекции в печатном виде)

Посмотреть архив целиком

60




Теория Принятия Решений.



Литература.

Классика:

  1. Пойя Д. “Математика и правдоподобные рассуждения.” М. Наука. 1975.

  2. Нильсон Н. “Искусственный интеллект. Методы решения задач.”

М. Мир. 1973

  1. Попов Р. “Искусство решения проблем.” М. Мир. 1982

  2. Александров “Основы теории эвристических решений.”

М. Советское радио 1975.

  1. Вагин В. Н. “Дедукция и обобщение в системах принятия решений.”

М. Наука 1988.


Современные:

  1. Еремеев А. П. “Экспертные модели и методы принятия решений.” М. МЭИ 1995

  2. Ларичев О. И. “Теория и методы принятия решений.” М. Логос 2000, 2002

  3. Тратенгерц Э. В. “Компьютерная поддержка принятия решений.” М. Синтег. 1998

  4. Башлыков А. А. Еремеев А. П. “Проектирование ЭС поддержки принятия решений в энергетике.”




























Введение.

Принятие решений (ПР). Задача принятия решений (ЗПР).

Методы теории принятия решений (ТПР).



Принятие решений



В узком смысле

- построение последовательности действий для достижения поставленной цели.

- выбор некоторой альтернативы из имеющегося множества альтернатив.


В широком смысле

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





Этапы ПР:

  1. Осмысливание проблемной ситуации.

  2. Формулировка задачи принятия решения.

Задача ПР – это любая задача, которая может быть сформулирована в терминах: цели, средства (альтернативы) и результаты.

  1. Поиск (построение) множества альтернатив.

  2. Оценка и выбор альтернатив для реализации.

  3. Применение (реализация) альтернатив.

  4. Оценка результата.

(Подключается множество критериев оценок. Если результат удовлетворяет оценке, то он принимается в качестве решения. В противном случае возможен возврат на любой из этапов ПР. Чем выше этап, тем больший объём работы необходимо выполнять заново)

- + конец



Задача ПР = T = T(G, A, R, ) , где:

G – цели, A – альтернативы, R – результат, критерии.


Задача принятия решения


В замкнутой форме

- нет необходимости в дополнительной информации в процессе решения задачи


В открытой форме

- при наличии различного типа

НЕ-факторов (неполнота знаний, нечёткость критериев и т.д.)


В замкнутой форме Оптимальное решение

ЗПР

В открытой форме Приближённое решение

(размерногсть велика, наличие НЕ-факторов)

F(x) = ext

Задача поиска в пространстве состояний.

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


С

Пример: Шахматы.

S - все состояния.

S* - разрешённые состояния.

S\S*- король под ударом.

P – мн. ходов, которые можно делать.

pi – ладья не может ходить через фигуры.


- поставить мат за минимальное количество ходов

читается, что любое состояние системы можно описать.

T = (S, S*, Sн, Sк, P, )

S - множество состояний задачи (проблемной области)

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

- множество запрещённых состояний.

- множество

преобразований состояний

pi, Spi – множество состояний, в которых

можно делать преобразования.

- множество критериев.

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

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


Задача:

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


Композиция определяется следующим образом:


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

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

Sн



S11 … S120



S21 … S220 … S21 … S220



Пример: Шахматы.

Метод перебора.

После первого хода

получаем 400 вершин


Партия длится в среднем

40 ходов и на каждом

ходу 20 возможностей.

Следовательно, полное дерево перебора будет иметь 40400 вершин.

Применение метода перебора невозможно. В этом случае вводится эвристическая функция. Как правило, она позволяет найти только приближённое решение.

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

Методы Теории Принятия Решений.



Строгие методы

Ориентированы на поиск оптимального решения.

ЗПР в замкнутой форме.

Методы математической оптимизации. (линейное, нелинейное, дискретное программированиек)



Решение оптимально


Дедуктивный вывод.

(от общего к частному)

AB

A

B

Системы Принятия Решений

(Decision Making )






















Эвристические методы

Поиск приемлемого (удовлетворяющего, допустимонго) решения.

ЗПР в открытой форме.

НЕ-факторы.


- множество возмущений.


Решение оптимально

- функция допустимости.

R - отношение допустимости.

Обычно это отношение нестрогого порядка .

Свойства:

  1. Рефлексивность a r a

  2. Транзитивность arb & brc => arc

  1. Асимметричность

a r b & b r a =>a=b


Если в силу природы задачи не возможно отыскать оптимальное решение, то ищется приближённое.

Индуктивный вывод.

(от частного)

AB

B

A

Это правдоподобные методы, следовательно необходимо оценивать степень правдоподобия.

Обобщённый modus ponens

AB

A*

B* B*=A* (AB)

AR1 A ~ a0

TR2 T ~ t0

(t - a0) (t - t0) => выбираем R1


Условия принятия решений.


1.Условия определенности.


S – состояния.

A(R) – альтернативы (частичное решение)




S  aA


2.Условия риска.


Существуют ситуации, которым соответствует ряд возможных решений и их вероятности:


а1,p1

S а2,p2

… Pi=1.0

an,pn


3.Условия неопределенности.


Неполнота или противоречивость.



Формализация цели в ЗПР.


1. Количественное задание цели ( с помощью целевой функции)


Сведение ЗПР к задаче математической оптимизации.



2. Качественное задание цели.


Выделяется 2 подзадачи:


1). Цель достигнута или цель не достигнута.

Определяется целевое множество Xц



2). С помощью отношения предпочтения () на множестве

альтернатив A .



Пример.


Задача сортировки (классы эквивалентности). Их частичный порядок можно задавать деревом или звездой.



K1 K2



Спецификация плохо формализованных ЗПР.


1.Отсутствие явно (или количественно) выраженной целевой функции.

2.Отсутствие (априори) алгоритма поиска решения. Алгоритм строится и уточняется в процессе решения задачи.

3.Алгоритм существует, но его реализация очень сложна.

4.Существенная комбинаторность процесса поиска решения.

5.Диапазон данных и знаний, используемых в процессе решения задачи.

6.Возможность диалогового поиска решения (обращение к ЛПР в процессе решения).


Пункты 1-6 влияют на процесс решения и мешают использовать методы оптимизации.



Спецификация человеческого мышления при поиске решения.


1. Л.П.- рациональное мышление = дедукция + классическая аргументация.

(-> A, A->B, |-B).

В этом случае гипотеза принимается, если

S аргументов “за” - S аргументов “против” q,

где q – некоторое пороговое значение.

2. П.П. – образное мышление (правдоподобный вывод).=

индукция + абдукция + аргументация(justification)

A->B

B___

A?






Аргументация:

Пусть есть аргументы “за” и аргументы “против”


- веса, значения которых устанавливаются в зависимости

от важности гипотез.


3. Case-based reasoning (рассуждение на основе здравого смысла).


4. Belief (вера, убеждение(мнение)).


L - Квантор необходимости


- Квантор возможности


p Lp

Lp LLp

Mp LMp























Теоретико-игровые модели принятия решения

в конфликтных ситуациях.


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

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

Однократный розыгрыш игра от начала до конца называется парией.

Результатом партии являются платежи (выигрыши, проигрыши игроков)

Игра состоит из ходов, то есть выборов игроков из множества возможных альтернатив.

Ходы могут быть личными или случайными. Личный ход – ход, при котором игрок осуществляет сознательный выбор. Случайный ход – выбор варианта осуществляется на основе механизма случайного выбора. (бросание монеты, кости и т. п.).

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

Задача Теории Игр: нахождение оптимальных стратегий игроков (т.е. обеспечение максимизации или минимизации проигрыша) в стратегических играх.

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

Игра n лиц { A1, … , A1, H(A1 , … , An)},

где – Ai стратегия i игрока, H – платёж.


Классификация Теоретико-Игровых Моделей.

Дискретные

Конечные

Бесконечные

Непрерывные

Бесконечные


N лиц

Коалиционные (кооперативные)

Некоалиционные (некооперативные)

2-х лиц

Антагонистические (игры с нулевой суммой)

(интересы сторон противоположны)

Неантагонистические (интересы сторон не совпадают)


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

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

С нулевой суммой (суммарный платёж равен нулю)

С ненулевой суммой


Одноходовые

Многоходовые

Игровая модель для двух лиц.


Игрок A :{Ai} – множество стратегий A (i=1..m)

Игрок B :{Bj} – множество стратегий B (j=1..n)

Игра антагонистическая.


Представление игры.

- в виде дерева игры. (можно построить для любой игры)

- в виде матрицы (платёжной) игры.


Представление игры в виде дерева.

Вершины дерева – это ситуации или состояния, возможные в игре.

Корень дерева отражает начальную ситуацию.

Концевые вершины – это конечные состояния, взвешенные платежами.

Дуги – возможные переходы из состояния под действием стратегии.


Пример:

Два игрока A, B.

1 ход (личный) А выбирает цифру 1 или 2.

2 ход (случайный) Если герб, то В сообщается о выборе А, иначе – нет.

3 ход (личный) В выбирает 3 или 4.


Итог: Суммируются выборы игроков А и В, и если сумма чётная, то В выплачивает А, в противном случае А выплачивает В.

1 ход S

(Л)

1 2


2 ход

(С) Г Р Г Р


3 ход

(Л)

3 4 3 4 3 4 3 4


4 -5 4 -5 4 -5 4 -5


S1




S3


S2

S4








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

Следовательно, данная игра распадается на две игры: с полной и с неполной информацией.

Стратегии А: Стратегии В:

A1 (1), Ai (2) 8 стратегий. B = (, ,)

B1 = (3, 3, 3)

B2 = (3, 3, 4) S2 S3 S4

B8 = (4, 4, 4)

Построение дерева игры. Поиск на дереве игры.


- полный перебор (“в глубину”, “в ширину”, комбинированные методы).

- сокращённый перебор (использование оценочных функций)

- точная оценка (будет получено оптимальное решение)

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

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

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


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

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

Оценка алгоритма – это оценка временных ресурсов, требуемых для оценки вершин.


Методы сокращения перебора.

- универсальные методы (не зависят от проблемной области).

- эвристические методы (учитывают специфику задачи).


Универсальные методы

Метод максимина.

Метод заключается в максимизации выигрыша, при минимизации проигрыша.

(при отсутствии дополнительной информации). Этот метод позволяет отсекать неперспективные направления.

Игрок А: (MAX)

Игрок В: (MIN)

Идея алгоритма:

  1. Строится полное поисковое дерево на ту глубину, которую возможно позволить по затратам памяти, времени и т.д.. Число ходов должно быть чётно.

  2. Концевые вершины дерева оцениваются оценочной функцией.

  3. Совершается обратное движение по дереву от концевой к начальной вершине. Выбирается лучший ход игрока А.


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








Пример:


S0

















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

(Внизу - выигрыши А. В стремится их минимизирует.)



A

5



5

3


B





A

B

7

5

1

1

5

3

7

2

3

4

7

3

2

4

3

2

7












Метод отсечения


Идея метода была предложена Дж. Маккарти в 1961 г.

В основе метода лежит то, что процессы построения и отсечения дерева происходят одновременно.


Существуют 2 случая  отсечения:



Случайные файлы

Файл
46943.rtf
referat.doc
117415.rtf
13385-1.rtf
167666.doc




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