- •1.1. Методы искусственного интеллекта в прикладных системах и системах принятии решений
- •1.2. Интеллектуальные информационные технологии в прикладных системах и системах принятия решений
- •1.3. Типология задач интеллектуализации систем
- •Лекция 2. Представление знаний в интеллектуальных системах
- •2.1. Модели представления знаний
- •2.2. Системы, основанные на правилах
- •2.3. Системы, основанные на автоматическом доказательстве теорем
- •2.4. Системы, основанные на автоматическом порождении (выдвижении) гипотез
- •Лекция 3. Структура и основные компоненты прикладных интеллектуальных систем
- •3.1. Прикладные системы, основанные на знаниях
- •3.2. Структура системы управления, основанной на знаниях
- •3.3. Структура интеллектуальных систем поддержки принятия решения
- •3.4. Обобщенная структура экспертной системы
- •Лекция 4. Классификация прикладных интеллектуальных систем
- •4.1. Классификация экспертных систем
- •4.2. Примеры прикладных интеллектуальных систем
- •Лекция 5. Основные понятия и определения теории принятия решений
- •5.1. Роли людей в процессе принятия решений
- •5.2. Альтернативы
- •5.3. Критерии
- •5.4. Основные этапы процесса принятия решений
- •5.5. Математические методы теории принятия решений
- •Лекция 6. Принятие решений с помощью статистической проверки гипотез
- •6.1. Статистические решения
- •6.2. Основные задачи статистических решений
- •6.3. Статистическая проверка гипотез
- •6.4. Ошибки решения
- •6.5. Решающее правило при проверке гипотез
- •Лекция 7. Байесовская и последовательная процедуры принятия решения.
- •7.1. Байесовские процедуры принятия решения
- •7.1.1. Байесовская процедура при проверке простой гипотезы
- •7.1.2. Байесовские процедуры в задаче классификации
- •7.2. Принятие решения с помощью последовательной процедуры Вальда
- •Лекция 8. Принятие решения методом дискриминантнного анализа
- •8.1. Классификация в случае, когда распределения классов определены полностью
- •8.1.1. Модель двух нормальных распределений с общей ковариационной матрицей (модель Фишера)
- •8.1.2. Модель двух нормальных распределений с разными ковариационными матрицами
- •8.1.3. Модель нескольких нормальных распределений с общей ковариационной матрицей
- •8.2. Классификация при наличии обучающих выборок
- •8.2.1. Подстановочный алгоритм в модели Фишера
- •8.2.3. Правила классификации
- •8.3. Ошибка решающего правила
- •Лекция 9. Древообразные классификаторы
- •9.1. Назначение древообразных классификаторов
- •9.1. Структура дерева классификации
- •9.3. Вычислительные задачи древообразных классификаторов
- •9.3.1. Определение качества предсказания
- •9.3.2. Выбор разбиений
- •9.3.3. Определение правила прекращения разбиения
- •Лекция 10. Деревья решений
- •9.1. Характеристики дерева решений
- •9.2. Построение дерева решений
- •Лекция 11. Методы прогнозирования
- •11.1. Анализ временных рядов
- •11.1.1. Модель временного ряда
- •11.1.2. Тренд, сезонная и циклическая компоненты
- •11.1.3. Декомпозиция временного ряда
- •11.1.4. Экспоненциальное сглаживание
- •11.2. Каузальные методы прогнозирования
- •11.3. Качественные методы прогнозирования
- •Лекция 12. Основная задача линейного программирования
- •12.1. Математическая модель основной задачи линейного программирования
- •12.2. Задача линейного программирования с ограничениями-неравенствами
- •12.3. Примеры задач линейного программирования
- •12.3.1. Транспортная задача
- •12.3.2. Задача о назначениях
- •Лекция 13. Симплекс-метода решения задачи линейного программирования
- •13.1. Характеристика симплекс–метода
- •13.2. Табличный алгоритм замены базисных переменных
- •13.3. Отыскание опорного решения основной задачи линейного программирования
- •13.4. Отыскание оптимального решения основной задачи линейного программирования
- •Лекция 14. Многокритериальные методы принятия решений при объективных моделях
- •14.1. Объединение критериев
- •14.2. Метод главного критерия
- •14.3. Метод последовательных уступок
- •14.4. Метод целевого программирования
- •14.5. Метод, использующий принцип гарантированного результата
- •14.6. Метод равных наименьших относительных отклонений
- •14.7. Процедура STEM поиска удовлетворительных значений критериев
- •Лекция 15. Выбор Парето–оптимальных решений
- •15.1. Основные определения
- •15.2. Графическая интерпретация
- •15.3. Постановка задачи
- •Лекция 16. Оценка многокритериальных альтернатив с помощью теории полезности
- •16.1. Теория полезности
- •16.2. Принятие решения на основе значения ожидаемой полезности
- •16.3. Многокритериальная теория полезности (MAUT)
- •Лекция 17. Сравнение альтернатив методом аналитической иерархии
- •17.1. Основные этапы метода аналитической иерархии
- •17.2. Декомпозиция задачи
- •17.3. Попарное сравнение критериев и альтернатив
- •17.4. Свойства идеальной матрицы сравнений
- •Лекция 18. Приоритеты для критериев и альтернатив и выбор наилучшей альтернативы в методе анализа иерархий
- •18.1. Вычисление собственных характеристик обратно симметричной матрицы
- •18.2. Вычисление величины приоритетов
- •18.3. Определение наилучшей альтернативы
- •18.4. Проверка согласованности
- •18.5. Пример применения метода анализа иерархий
- •Лекция 19. Оценка многокритериальных альтернатив методами ELECTRE
- •19.1. Этапы подхода, направленного на разработку индексов попарного сравнения альтернатив
- •19.2. Свойства бинарных отношений
- •19.3. Метод ELECTRE I
- •19.4. Метод ELECTRE II
- •19.5. Метод ELECTRE III
- •Лекция 20. Основные понятия и математическая модель игровых методов обоснования решений
- •20.1. Основные понятия теории игр
- •20.2. Математическая модель игры
- •20.3. Нижняя и верхняя цена игры. Принцип минимакса
- •Лекция 21. Методы решения игр
- •21.1. Решение игры в чистых стратегиях
- •21.2. Решение игры в смешанных стратегиях
- •21.3. Упрощение игр
- •21.4. Решение игры 2х2
- •21.5. Графический метод решения (2х2)-игр
- •Лекция 22. Игры 2 х п
- •Лекция 23. Решение игр т х 2 и т х п
- •23.1. Решение игр т х 2
- •23.2. Решение игр т х п
- •Лекция 24. Критерии принятия решений в условиях риска и неопределенности
- •24.1. Основные понятия. Математическая модель
- •24.3. Максиминный критерий Вальда
- •24.4. Критерий минимаксного риска Сэвиджа
- •24.5. Критерий пессимизма-оптимизма Гурвица
- •Литература
|
Б |
БП |
ТР |
|
ПР |
|
w |
|
||
|
БП |
1 |
2 |
|
|
3 |
0,54 |
|||
|
ТР |
1/2 |
1 |
|
|
2 |
|
0,30 |
|
|
|
ПР |
1/3 |
1/2 |
|
|
1 |
|
0,16 |
|
|
|
|
|
|
|
||||||
|
|
|
λmax=3,01; ИС = 0,01 |
|
|
|
|
|||
Запишем полученные столбцы в виде матрицы: |
0,65 0,59 0,54 |
|
|
|||||||
|
0,230,33 0,30 |
. |
|
|||||||
|
|
|
|
|
|
0,12 0,08 0,16 |
|
|
||
|
|
|
|
|
|
|
|
Умножая эту матрицу на столбец w, находим искомый вектор-столбец приоритетов третьего уровня иерархии, представляющего потребителей энергии БП, ТР и ПР
(взвешенный согласно их общему влиянию): 0,62 . Итак, в соответствии с вычислениями
0,260,12
на бытовое потребление следует выделить 62% энергии, на транспорт – 26% и на промышленность – 12%.
Лекция 19. Оценка многокритериальных альтернатив методами ELECTRE
Одним из первых подходов к сравнению многокритериальных альтернатив является подход, основанный на определении бинарного отношения превосходства альтернатив по качеству. Этот подход реализован в виде совокупности методов ELECTRE (Elimination Et Choice Traduisant la Realite – исключение и выбор, отражающие реальность). Метод позволяет определить индексы попарного сравнения альтернатив (ИПСА). Эти индексы являются мерой согласия или несогласия с гипотезой о том, что одна альтернатива превосходит другую.
Как и методы анализа иерархий, методы ELECTRE направлены на сравнение заданной группы многокритериальных альтернатив. В отличие от АИ при подходе ELECTRE предполагается, что ЛПР осуществляет свой выбор из вариантов решения проблемы, полученных с помощью методов принятия решений, т.е. на основе решающих правил. Эти правила формируются в виде индексов попарного сравнения альтернатив.
19.1. Этапы подхода, направленного на разработку индексов попарного сравнения альтернатив
При разработке ИПСА различают два основных этапа [12]:
1)этап разработки, на котором строятся один или несколько индексов попарного сравнения альтернатив;
2)этап исследования, на котором построенные индексы используются для ранжирования (или классификации) заданного множества альтернатив.
Индексы попарного сравнения альтернатив в большинстве методов строятся на основе
принципов согласия и несогласия. В соответствии с этими принципами альтернатива Аi является, по крайней мере, не худшей, чем альтернатива Аj, если
•«достаточное большинство» критериев поддерживает это утверждение (принцип согласия);
•«возражения» по остальным критериям не слишком сильны (принцип малого несогласия).
Введем правило сравнения двух альтернатив А1 и А2 по k-му критерию Сk.
92
Обозначим А1 fА2 отношение «альтернатива А1 лучше альтернативы А2 по k-му |
|
k |
|
критерию» (Сk (А1) > Сk (А2)); |
|
отношение А1 ~k |
А2: «альтернатива А1 равноценна или эквивалентна альтернативе А2 по |
k-му критерию» (Сk (А1) = Сk (А2)); |
|
отношение А1 f~ |
А2: «альтернатива А1 не хуже альтернативы А2 по k-му критерию» |
k |
|
(Сk (А1) ≥ Сk (А2)). |
|
19.2. Свойства бинарных отношений
Разработка ИПСА основана на бинарных отношениях. Введем некоторые определения
[12].
Бинарное отношение R, определенное на конечном множестве альтернатив А, называется (при Аi, Аj А):
•полным, если Аi R Аj или Аj R Аi;
•транзитивным, если Аi R Аj, Аj R Аk Аi R Аk;
•полным порядком, если оно полное и транзитивное;
•частичным порядком, если оно транзитивное, но не полное.
Обозначим через xik , xkj оценки альтернатив А1 и А2 по k-му критерию. Отношение
предпочтения ЛПР при сравнении альтернатив по одному критерию является полным порядком.
При разработке индексов попарного сравнения альтернатив вводится понятие псевдокритерия [12]. Псевдокритерием является тройка ( xkj , p, q) функций, представляющих предпочтения ЛПР и определенных так, что:
q ( xik ) + xik > xkj , если по k-му критерию Аi имеет сильное предпочтение по сравнению
с Аj;
xik + q ( xik ) ≥ xkj > xik + p ( xik ) , если по k-му критерию Аi имеет слабое предпочтение по
сравнению с Аj.
Альтернативы А1 и А2 находятся в отношении безразличия (равноценны или эквивалентны) по k-му критерию ( xik ~ xkj ), если не выявлено сильное или слабое
предпочтение одной из альтернатив.
Функции p и q называются соответственно порогами безразличия и предпочтения. Бинарное отношение называется четким, если оно построено на основе критериев, и числовым, если оно построено на основе псевдокритериев.
Рассмотрим ряд методов, принадлежащих подходу разработки индексов попарного сравнения альтернатив.
19.3. Метод ELECTRE I
В методе ELECTRE I используются четкие бинарные отношения между альтернативами.
Индексы согласия и несогласия строятся следующим образом [12]. Каждому из т критериев ставится в соответствие целое число w, характеризующее важность критерия. Автор метода Б. Руа предложил рассматривать w как число голосов членов жюри, поданное за важность данного критерия.
93
Выдвигается гипотеза о превосходстве альтернативы Аi над альтернативой Аj. Множество I, состоящее из т критериев, разбивается на три подмножества:
I+ – подмножество критериев, по которым Аi предпочтительнее Аj; I= – подмножество критериев, по которым Аi равноценна Аj;
I– – подмножество критериев, по которым Аj предпочтительнее Аi.
Далее строится индекс согласия с гипотезой о превосходстве Аi над Аj. Индекс согласия подсчитывается на основе весов критериев. В методе ELECTRE I этот индекс определяется как отношение суммы весов критериев подмножеств I+ и I= к общей сумме весов:
|
|
|
∑pi |
|
CA A |
|
= |
i I + ,I − |
. |
j |
|
|||
i |
|
m |
||
|
|
|
∑pi |
|
|
|
|
i=1 |
Индекс несогласия dAB с гипотезой о превосходстве Аi над Аj определяется на основе
самого противоречивого критерия, по которому Аj в наибольшей степени превосходит Аi. Укажем свойства индекса согласия.
1)0 ≤ CAi Aj ≤ 1;
2)CAi Aj = 1, если подмножество пусто I– ;
3)CAi Aj сохраняет значение при замене одного критерия на несколько критериев с тем
же общим весом.
Укажем свойства индекса несогласия: 1) 0 ≤ dAi Aj ≤ 1;
2) dAi Aj сохраняет значение при введении более детальной шкалы по i-му критерию
при той же ее длине.
Введенные индексы используются при построении матриц индексов согласия и несогласия для заданных альтернатив.
Представим основные этапы метода ELECTRE I [12].
Этап разработки индексов. На основании заданных оценок двух альтернатив подсчитываются значения двух индексов: согласия и несогласия. Эти индексы определяют
согласие и несогласие с гипотезой о превосходстве альтернативы Аi над альтернативой Аj. Задаются уровни согласия и несогласия, с которыми сравниваются подсчитанные
индексы для каждой пары альтернатив. Если индекс согласия выше заданного уровня, а индекс несогласия ниже, то одна альтернатива превосходит другую. В противном случае альтернативы несравнимы.
Этап исследования множества альтернатив. Из множества альтернатив удаляются доминируемые. Оставшиеся образуют первое ядро. Альтернативы, входящие в ядро, могут быть либо эквивалентными, либо несравнимыми.
Вводятся меньшее значение уровня согласия и большее значение уровня несогласия, при которых выделяются ядра с меньшим количеством альтернатив. В последнее ядро входят наилучшие альтернативы. Последовательность ядер определяет упорядоченность альтернатив по качеству.
19.4. Метод ELECTRE II
В методе ELECTRE II, так же как в методе ELECTRE I, используются четкие бинарные отношения между альтернативами.
94
Индексы согласия подсчитываются тем же способом, что и в методе ELECTRE I. В методе ELECTRE II задаются два уровня для индекса согласия α1 > α2 и два уровня индекса несогласия (вето) γ1 ≤ γ2. Далее вводятся два отношения предпочтения δ1 и δ2 между альтернативами так, что для i = 1, 2 имеем [12]:
C(Ai Aj ) ≥ αi , ∑wi > ∑wi , dAi Aj < γi. i I + i I −
Очевидно, что δ1 δ2; δ1 называется сильным, а δ2 – слабым отношением предпочтения.
Этап исследования множества альтернатив [12]. На заданном конечном множестве альтернатив А выявляются альтернативы, находящиеся в сильном, а затем в слабом отношении предпочтения. Далее выявляется первое ядро, в которое входят недоминируемые альтернативы. Затем они удаляются из рассмотрения, и процедур а повторяется для оставшихся альтернатив и т.д.
Присваиваем ранги альтернативам, входящим в соответствующие ядра, затем строим полный порядок на множестве альтернатив. Второй полный порядок строится аналогично первому, но начиная с класса худших альтернатив (недоминирующих другие) и переходя к лучшим альтернативам. Если два построенных порядка не слишком различны по упорядочению альтернатив, то на их основе строится средний порядок, который предъявляется ЛПР.
Это построение осуществляется по следующим правилам:
•Аi Р Аj строго превосходит, если Аi имеет лучший ранг в одном из порядков и, по крайней мере не худший в другом;
•Аi I Аj (эквивалентны), если они имеют одинаковые ранги в двух полных порядках;
•Аi N Аj (несравнимы), если они имеют одно упорядочение в одном из порядков, противоположное – в другом.
19.5. Метод ELECTRE III
В методе ELECTRE III используются псевдокритерии и числовые бинарные отношения. Задано т псевдокритериев и уровень вето γj (xi) > 0.
Индексы согласия и несогласия вычисляются следующим способом [12]:
|
|
|
|
|
1 |
|
m |
|
|
|
|
|
|
|
C(Ai Aj ) = |
|
∑w jC j (Ai Aj ) ; |
|
|||||||||||
m |
|
|
||||||||||||
|
|
|
|
|
∑wi j =1 |
|
|
|
|
|
|
|
||
|
|
|
|
|
i=1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1, |
если xk + q |
k |
|
(xk ) ≥ xk ; |
|||||
|
|
|
|
|
|
|
i |
|
|
|
i |
j |
||
Ck (Ai Aj ) = 0,если xik + pk (xik ) ≤ xkj ; |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
линейно возрастает на промежуточном отрезке; |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0, |
если xk + p |
k |
(xk ) ≥ xk ; |
||||||
|
|
|
|
|
|
|
i |
|
|
|
i |
j |
||
d |
k |
(A A |
j |
) = |
1,если xk |
+ q |
k |
(xk ) ≤ xk ; |
||||||
|
i |
|
|
|
i |
|
|
i |
j |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
линейно возрастает на промежуточном отрезке. |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Для каждой пары альтернатив Аi, Аj строится числовое бинарное отношение в следующем виде:
95