УДК 519.816:004.032.26
ББК 22.18:32.818
Д30
Р е ц е н з е н т ы :
доктор техн. наук, профессор Е. А. Саксонов, кафедра «Вычислительные
системы и сети» Московского государственного института электроники
и математики (технический университет); доктор техн. наук, профессор
Е. Е. Ковшов, зав. кафедрой «Управление и информатика в технических системах»
Московского государственного университета «Станкин»
Демидова Л. А., Кираковский В. В., Пылькин А. Н.
Д30 Принятие решений в условиях неопределенности. – М.: Горячая
линия – Телеком, 2012. – 290 с.: ил.
ISBN 978-5-9912-0224-4.
Рассмотрены методы и алгоритмы принятия решений в условиях
неопределенности, основанные на комплексном использовании
инструментария теории нечётких множеств и генетических алгоритмов,
позволяющего устранить недостатки существующих аналогов,
обеспечивая при этом высокую обоснованность и адекватность принимаемых
решений. Приведены примеры, поясняющие предлагаемые
методы и алгоритмы.
Для научных работников и специалистов в области разработки
компьютерных систем, будет полезна преподавателям, студентам
и аспирантам.
ББК 22.18:32.818
Адрес издательства в Интернет WWW.TECHBOOK.RU
Научное издание
Демидова Лилия Анатольевна
Кираковский Валерий Владимирович
Пылькин Александр Николаевич
Принятие решений в условиях неопределенности
Монография
Компьютерная верстка И. А. Благодаровой
Обложка художника В. Г. Ситникова
Подписано в печать 28.09.2011. Формат 60×88/16. Уч. изд. л. 18,125. Тираж 500 экз.
ISBN 978-5-9912-0224-4
© Л. А. Демидова, В. В. Кираковский,
А. Н. Пылькин, 2011
© Издательство «Горячая линия – Телеком», 2012
Стр.2
Введение
Проблема принятия решений в условиях неопределенности
занимает важное место в общей проблеме принятия решений.
Успешное решение данной проблемы в настоящее время
невозможно без применения новых информационных технологий,
составной частью которых являются интеллектуальные средства
обработки информации. Понятие «неопределенность» трактуется
довольно неоднозначно, его смысл зависит от характера решаемой
прикладной задачи. Для описания неопределенности современная
теория принятия решений широко применяет, в частности, аппарат
теории нечетких множеств (ТНМ), основоположником которой
является Л.А. Заде (1965 г.). Проблема неопределенности присуща
всем сложным системам. К таким сложным системам относятся:
экономические и социально-экономические системы – системы
прогнозирования показателей занятости населения в экономике
страны; системы анализа инвестиционных решений и результатов
внешнеторговой деятельности регионов и др.; технические системы
– системы контроля, диагностики, классификации, кластеризации
состояний объектов различного происхождения и др.
Традиционный подход к проблеме принятия решений основан
на использовании классических методов многокритериального
анализа (А.А. Амосов, А. Вальд, Р. Кини, Р. Клемен (R. Clemen),
О.И. Ларичев, В.Д. Ногин, А.И. Орлов, Т.Л. Саати, Дж. К. Смит
(J.Q. Smith), А.Н. Тихонов, С. Ханссон (S. Hansson)) и предполагает
разработку и создание сложных, зачастую многоуровневых, систем
поддержки принятия решений, базирующихся на математических
моделях, обеспечивающих учет большого количества параметров и
критериев, и характеризуется значительными вычислительными
затратами и высокой стоимостью разработки.
Задачи поддержки принятия решений в условиях
неопределенности представляют собой слабоструктурированные
или неструктурированные задачи. Слабоструктурированные задачи
содержат неизвестные или неизмеряемые компоненты, то есть
количественно неоцениваемые компоненты. Такие задачи характеризуются
отсутствием методов решения на основе непосредственных
преобразований данных, а постановки задач предполагают
принятие решений в условиях неполной информации. Неструк
Стр.3
4
Введение
турированные задачи содержат неформализуемые процедуры,
базирующиеся на неструктурированной информации, которая
определяется высокой степенью неопределенности. Применение
ТНМ и её приложений позволяет построить формальные схемы
решения задач, характеризующихся той или иной степенью
неопределенности, которая может быть обусловлена неполнотой,
внутренней противоречивостью, неоднозначностью и размытостью
исходных данных, представляющих собой приближенные
количественные или качественные оценки параметров объектов.
Эта неопределенность является систематической, так как
обусловлена сложностью задач, дефицитом информации, лимитом
времени на принятие решений, особенностями восприятия и т.п.
Неполнота и неточность информации могут заключаться: в
принципиальной невозможности полного сбора и учета
информации об анализируемом объекте или процессе; в некоторой
недостоверности и недостаточности исходной информации об
анализируемом объекте или процессе; в возможности проявления
таких свойств анализируемого объекта или процесса,
существование которых не предполагалось. Кроме того,
неточность, неполнота и неопределенность исходных данных
могут быть вызваны недостаточными знаниями экспертов
специфики конкретной прикладной задачи. Следовательно, можно
говорить и о наличии «субъективного» человеческого фактора в
задачах поддержки принятия решений в условиях неопределенности.
В этом случае исходные данные, представленные
качественными оценками объектов, могут быть не только
несовпадающими, но и противоречивыми, что значительно
усложняет решение задачи поддержки принятия решений.
Таким образом, использование классических «жестких»
алгоритмов моделирования сложных систем, предполагающих
регламентированную постановку задачи и пошаговый процесс
получения результатов, при решении различных задач поддержки
принятия решений может оказаться малоэффективным, так как
предполагает обработку точных, полных и непротиворечивых
численных исходных данных, что может не соответствовать
высокому уровню неопределенности задачи.
Стр.4
Оглавление
Введение.................................................................................................3
Глава 1. Обзор и анализ методов и алгоритмов поддержки
принятия решений в условиях неопределенности............................9
1.1. Проблема поддержки принятия решений
в условиях неопределенности .................................................................9
1.2. Классы неопределенности информации.........................................12
1.3. Мягкие вычисления при решении задач
искусственного интеллекта ...................................................................15
1.4. Применение бионических принципов
в информационных технологиях..........................................................20
1.4.1. Генетические алгоритмы.........................................................................20
1.4.2. Искусственные нейронные сети..............................................................24
1.4.3. Искусственные иммунные системы ........................................................25
1.5. Нечеткое моделирование................................................................26
1.5.1. Классификация и преимущества нечетких моделей ...............................27
1.5.2. Сравнительный анализ нечеткого
и нейросетевого подходов к моделированию...................................................31
1.5.3. Системы нечеткого вывода в задачах поддержки принятия решений....32
1.6. Принципы анализа многокритериальных задач
принятия решений .................................................................................36
1.6.1. Принцип Эджворта-Парето .....................................................................36
1.6.2. Принцип анализа иерархий на основе метода парных сравнений...........38
1.6.3. Принцип схемы Беллмана – Заде.............................................................41
1.7. Упорядочение, классификация и кластеризация объектов ............42
1.7.1. Упорядочение объектов...........................................................................43
1.7.2. Классификация объектов.........................................................................47
1.7.3. Кластеризация объектов ..........................................................................50
1.7.4. Иерархическая кластеризация .................................................................53
1.7.5. Алгоритм четких c -средних...................................................................53
1.7.6. Алгоритмы кластеризации на основе нечетких множеств ......................57
1.8. Некоторые задачи поддержки принятия решений
в условиях неопределенности ...............................................................57
Выводы по главе 1.................................................................................58
Глава 2. Оценка объектов с использованием
нечеткого метода Дельфы..................................................................61
2.1. Нечеткий метод Дельфы согласования
экспертных оценок объектов.................................................................61
2.2. Оценка параметров на основе дефаззификации
непрерывных нечетких множеств первого типа ...................................63
Стр.285
286
Оглавление
2.3. Оценка параметров на основе центроидов интервальных
непрерывных нечетких множеств второго типа ...................................65
2.3.1. Вычисление центроида интервального
непрерывного нечеткого множества второго типа............................................66
2.3.2. Итерационный алгоритм Карника-Менделя............................................69
2.4. Применение нечеткого метода Дельфы
к задаче оценки влияния изменения состояния
окружающей среды на стоимость недвижимости
с использованием геоинформационных технологий ............................71
2.4.1. Расчет экономического эффекта с использованием
непрерывных нечетких множеств первого типа ...............................................77
2.4.2. Расчет экономического эффекта с использованием интервальных
непрерывных нечетких множеств первого типа ...............................................83
2.4.3. Сравнительный анализ результатов расчета экономического эффекта...88
Выводы по главе 2.................................................................................89
Глава 3. Методы и алгоритмы кластеризации
на основе нечетких множеств первого типа
и генетических алгоритмов ...............................................................90
3.1. Кластеризация объектов с использованием
алгоритма нечетких c -средних
на основе нечетких множеств первого типа..........................................91
3.2. Задача выбора показателя качества кластеризации .......................97
3.2.1. Показатели качества кластеризации........................................................99
3.2.2. Выбор показателя качества кластеризации............................................103
3.3. Генетические алгоритмы оптимизации результатов
кластеризации с использованием алгоритма нечетких
с-средних на основе нечетких множеств первого типа....................................106
3.3.1. Кодирование хромосомы координатами центров кластеров.................107
3.3.2. Кодирование хромосомы степенями принадлежности
объектов центрам кластеров............................................................................107
3.3.3. Генетический алгоритм для хромосомы,
закодированной координатами центров кластеров.........................................108
3.3.4. Генетический алгоритм для хромосомы, закодированной
степенями принадлежности объектов центрам кластеров...............................111
3.4. Комбинирование алгоритма нечетких с-средних на основе
нечетких множеств первого типа и генетического алгоритма............115
3.4.1. Комбинирование алгоритма нечетких с-средних на основе нечетких
множеств первого типа и генетического алгоритма при кодировании
хромосом координатами центров кластеров...................................................115
3.4.2. Комбинирование алгоритма нечетких с-средних на основе нечетких
множеств первого типа и генетического алгоритма при кодировании
хромосом степенями принадлежности объектов центрам кластеров .............117
Стр.286
Оглавление
287
3.5. Кластеризация объектов с использованием известных
модификаций алгоритма нечетких с-средних
на основе нечетких множеств первого типа........................................118
3.5.1. Кластеризация объектов с использованием
алгоритма возможностных с-средних
на основе нечетких множеств первого типа................................................... 119
3.5.2. Кластеризация объектов с использованием алгоритма нечетковозможностных
с-средних на основе нечетких множеств первого типа ........ 124
3.5.3. Кластеризация объектов с использованием алгоритма робастнонечетких
с-средних на основе нечетких множеств первого типа....................126
3.6. Генетические алгоритмы оптимизации результатов
кластеризации с использованием известных
модификаций алгоритма нечетких с-средних
на основе нечетких множеств первого типа........................................130
3.6.1. Генетический алгоритм оптимизации результатов
кластеризации с использованием алгоритма возможностных
с-средних на основе нечетких множеств первого типа................................... 133
3.6.2. Генетический алгоритм оптимизации результатов кластеризации
с использованием алгоритма возможностно-нечетких с –средних
на основе нечетких множеств первого типа ................................................... 134
3.6.3. Генетический алгоритм оптимизации результатов
кластеризации с использованием алгоритма робастно-нечетких
с –средних на основе нечетких множеств первого типа................................. 136
3.7. Проблема выбора комбинированного метода кластеризации
на основе нечетких множеств первого типа........................................137
3.8. Примеры классификации технического состояния зданий
и сооружений с использованием комбинированных методов
кластеризации на основе нечетких множеств первого типа...............138
3.8.1. Кластеризация множества объектов при реализации
комбинированного метода нечеткой кластеризации на основе нечетких
множеств первого типа с использованием генетического алгоритма............. 139
3.8.2. Кластеризация множества объектов при реализации
комбинированного метода возможностной кластеризации на основе
нечетких множеств первого типа
с использованием генетического алгоритма................................................... 154
3.8.3. Выбор комбинированного метода кластеризации
на основе нечетких множеств первого типа ................................................... 159
3.8.4. Кластеризация множества объектов при реализации
комбинированного метода возможностно-нечеткой
кластеризации на основе нечетких множеств первого типа
с использованием генетического алгоритма................................................... 160
Стр.287
288
3.8.5. Кластеризация множества объектов при реализации
комбинированного метода робастно-нечеткой кластеризации
на основе нечетких множеств первого типа
с использованием генетического алгоритма ...................................................167
Выводы по главе 3...............................................................................173
Глава 4. Методы и алгоритмы кластеризации
на основе интервальных нечетких множеств
второго типа и генетических алгоритмов......................................176
4.1. Кластеризация объектов с использованием алгоритма
нечетких c -средних на основе интервальных
нечетких множеств второго типа ........................................................176
4.1.1. Неопределенность фаззификатора в алгоритме нечетких с -средних ...177
4.1.2. Расширение множества объектов на интервальные нечеткие
множества второго типа для алгоритма нечетких с -средних..........................185
4.1.3. Итерационный алгоритм Карника – Менделя .......................................192
4.2. Задача выбора показателя качества кластеризации..................................202
4.2.1. Показатели качества кластеризации......................................................203
4.2.2. Выбор показателя качества кластеризации............................................206
4.3. Генетический алгоритм поиска оптимальной комбинации
значений фаззификаторов для алгоритма нечетких с -средних
на основе интервальных нечетких множеств второго типа ................209
4.4. Кластеризация объектов с использованием
алгоритма возможностных с -средних
на основе нечетких множеств первого типа........................................211
4.4.1. Неопределенность «ширины зоны»
в алгоритме возможностных с -средних .........................................................211
4.4.2. Расширение множества объектов на интервальные нечеткие
множества второго типа для алгоритма возможностных с -средних..............214
4.4.3. Генетический алгоритм поиска оптимальной
комбинации значения фаззификатора и значений «ширины зоны»,
реализующих управление неопределенностью, для алгоритма
возможностных с-средних на основе интервальных
нечетких множеств второго типа ....................................................................220
4.4.4. Генетический алгоритм поиска оптимальной комбинации
и значений фаззификаторов, реализующих управление неопределенностью,
значений «ширины зоны» для алгоритма возможностных с -средних
на основе интервальных нечетких множеств второго типа ........................... .224
4.5. Неопределенность в выборе целевой функции ............................227
4.5.1. Расширение множества объектов на интервальные нечеткие
множества второго типа при неопределенности выбора целевой функции ...228
4.5.2. Генетический алгоритм поиска оптимальной
комбинации значений фаззификатора и «ширины зоны»
при неопределенности выбора целевой функции ............................................231
Оглавление
Стр.288
Оглавление
289
4.6. Проблема выбора метода кластеризации на основе
интервальных нечетких множеств второго типа.................................233
4.7. Выбор метода кластеризации на основе нечетких
множеств первого типа или интервальных нечетких
множеств второго типа........................................................................234
4.8. Примеры классификации технического состояния зданий
и сооружений с использованием методов кластеризации
на основе интервальных нечетких множеств второго типа................236
4.8.1. Кластеризация множества объектов существенно
разной мощности и существенно разной плотности
при реализации метода нечеткой кластеризации на основе
интервальных нечетких множеств второго типа ............................................ 236
4.8.2. Кластеризация множества объектов существенно разной мощности
и существенно разной плотности при реализации метода возможностной
кластеризации на основе интервальных нечетких множеств второго типа
для фиксированной комбинации значений фаззификаторов, определенной
с помощью метода нечеткой кластеризации................................................... 253
4.8.3. Кластеризация множества объектов существенно разной мощности
и существенно разной плотности при реализации метода возможностной
кластеризации на основе интервальных нечетких множеств второго типа
для комбинации значений «ширины зоны».................................................... 255
4.8.4. Кластеризация множества объектов существенно разной мощности
и существенно разной плотности при неопределенности
выбора целевой функции ................................................................................ 257
4.8.5. Сравнительный анализ результатов кластеризации с использованием
методов кластеризации на основе нечетких множествпервого типа
и интервальных нечетких множеств второго типа.......................................... 258
Выводы по главе 4...............................................................................260
Список сокращений..........................................................................263
Список литературы..........................................................................264
Стр.289