Содержание к диссертации
Введение
Глава 1. Компьютерные системы поддержки принятия решений 6
1.1. Компьютерные системы имитационного моделирования 7
1.2. Экспертные системы 13
1.3. Методология когнитивного моделирования 16
1.3.1. Методологии структуризации проблемной ситуации 20
1.3.2. Модели представления знаний о функциональной структуре ситуации 22
1.3.3. Модели прогноза развития 23
1.3.4. Методы решения обратных задач 25
1.3.5. Методы структурного анализа 26
1.4. Принципы построения систем моделирования слабо структурированных ситуаций 28
Глава 2. Модель представления знаний эксперта о ситуации. Методология структуризации ситуации 33
2.1. Модель представления знаний о ситуации 33
2.2. Методология структуризации слабо структурированной ситуации 34
2.3. Модель ситуации в функциональной системе поля знаний 39
2.3.1. Метод шкалирования признаков ситуации 40
2.3.2. Методы извлечения предпочтений эксперта для настройки силы влияния признаков ситуации 46
2.3.3. Метод решения прямой задачи 47
2.3.4. Метод решения обратной задачи 54
2.4. Модель ситуации в понятийной системе поля знаний 61
2.4.1. Понятийный кластер в семантическом пространстве 64
2.5. Правило модификации понятий в понятийной системе поля знаний... 72
2.6. Пример 79
3. Методы поддержки интерпретации прогнозов развития ситуации и решений обратной задачи 88
3.1. Метод интерпретации прогнозов развития ситуаций 88
3.2. Метод интерпретации решений обратной задачи 91
3.3. Методика поиска структурных решений 93
3.3.1. Генерация решений 93
3.3.2. Структуризация решений в функциональной системе 94
3.3.3. Структуризация решений в понятийной системе 95
3.3.4. Методика поиска структурных решений 99
3.4. Пример 102
Глава 4. Программная реализация системы поддержки принятия решений, основанной на моделировании знаний эксперта (Система когнитивного моделирования) 115
4.1. Подсистема представления субъективной инф ормации 116
4.2. Интерфейс настройки силы влияния признаков 119
4.3. Подсистема получения прогноза развития ситуации 130
4.4. Подсистема представления результатов моделирования 131
4.5. Подсистема поддержки аналитической деятельности эксперта 133
4.5.1. Подсистема объяснения прогноза развития ситуации 133
4.5.2. Советующая подсистема 135
4.6. Подсистема поддержки сценарного исследования ситуации 138
Заключение 140
Литература 142
- Модели представления знаний о функциональной структуре ситуации
- Методология структуризации слабо структурированной ситуации
- Метод интерпретации решений обратной задачи
- Подсистема поддержки аналитической деятельности эксперта
Введение к работе
В настоящее время разработано множество различных программных систем поддержки принятия решений (СППР). Это системы интеллектуального анализа данных (Data Mining), позволяющие выявить закономерности развития ситуации; системы компьютерного имитационного моделирования, экспертные системы, основанные на знаниях и опыте принятия решений экспертов в определенных предметных областях; системы, облегчающие выбор лучшего решения из множества предложенных.
Наиболее трудными для анализа и поддержки принятия решений являются слабо структурированные уникальные ситуации, типичные для задач мониторинга и управления в административной и социально-политической сферах. В них характеристики ситуации могут быть представлены лишь качественно. Кроме того, анализу ситуаций и выработке вариантов решений должна предшествовать формализация модели ситуации, т.е. выявление основных признаков, связей между ними и силы влияния одних признаков на другие. В слабо структурированных ситуациях этот процесс должен происходить в тесном контакте с экспертами, причем для сколько-нибудь сложных предметных областей такая работа без серьезной компьютерной поддержки оказывается очень трудоемкой. Современные СППР, предназначенные для работы в таких ситуациях, помимо использования методов анализа, оценки и выработки решений, должны включать методы структуризации ситуации, развитый пользовательский интерфейс для работы с экспертами, средства редактирования и настройки моделей, а также визуализации всего процесса построения модели, анализа результатов моделирования их интерпретации и объяснения. Архитектуры систем моделирования слабо структурированных ситуаций, удовлетворяющих
5 указанным требованиям, в настоящее время находятся на этапе становления. Поэтому тематика данной работы, посвященная разработке принципов и методов построения программных систем поддержки принятия решений в слабо структурированных предметных областях, является актуальной.
Целью диссертационной работы является разработка принципов и методов построения систем моделирования, основанных на знаниях экспертов для повышения качества управленческих решений, принимаемых в слабо структурированных уникальных ситуациях.
Модели представления знаний о функциональной структуре ситуации
В настоящее время для описания процессов функционирования ситуации широко используется модель функциональной структуры в виде ориентированного знакового графа. Вершины графа - это основные факторы ситуации (характеристики), а дуги - причинно-следственные связи, отражающие известные субъекту законы и закономерности предметной области. Используются две модификации модели функциональной структуры ситуации: 1. Знаковый орграф. Здесь все дуги графа имеют вес либо +1, отражающий положительную причинную связь, либо -1, отражающий отрицательную причинную связь. 2. Взвешенный орграф. Здесь дуги имеют вес в интервале значений -1, +1, отражающий силу влияния фактора на фактор. Модель представления знаний эксперта о функциональной структуре ситуации в виде ориентированного графа понятна аналитикам и экспертам, строящим модель и удобна для специалистов, разрабатывающих методы анализа когнитивных карт. При получении прогнозов развития ситуации считается, что все факторы ситуации характеризуются некоторым начальным значением, представленным в виде вектора начальных значений Х(0)=(х](0),..., хп(0)) - это начальное состояние ситуации. Эксперт может увеличить или уменьшить начальные значения любых факторов X(l)=(xi(l),..., хп(1)). Приращение значения фактора рі(0)= Хі(1)-Х[(0) называется начальным приращением или начальным импульсом, а вектор приращений Р(0)=(рі(0),..., рп(0)) начальным вектором приращений.
Для получения прогноза развития ситуации в когнитивном моделировании записывается система конечно-разностных уравнений [31] следующего вида: где, P(t) - вектор приращений значений факторов в момент времени t (вектор импульсов); P(t+1) - вектор приращений значений факторов в момент времени t+1;, W- матрица смежности орграфа. Состояние ситуации в момент времени t+І определяется из соотношения: где, X(t) - состояние ситуации в момент времени t. Вектора приращений P(t), P(t+1), ..., P(t+n) в последовательные дискретные моменты времени называются импульсным процессом [31], а состояния ситуации X(t), X(t+1), ..., X(t+n) в последовательные моменты времени характеризуют динамику изменения ситуации, при управляющих воздействиях P(t). В настоящее время для получения прогнозов развития ситуации наибольшее распространение получили две модели: 1. Модель получения прогнозов, предложенная в работе Робертса [31]. В этой модели для вычисления элементов p(t+l) вектора прогнозных приращений P(t+1) используется соотношение: Эта модель получения прогноза используется, если значения всех факторов (х](0),..., хп(0)) могут быть точно измерены и представлены численно и, кроме этого, допускается суммирование приращений (импульсов) в вершинах графа. На основе этой модели построена система когнитивного моделирования «Ситуация» [13]. 2. Модель получения прогнозов, предложенная Б. Коско [45]. Здесь для вычисления прогнозов развития ситуаций используется так называемое правило max-product (умножение и взятие максимума).
Для вычисления элементов p(t+l) вектора прогнозных приращений P(t+1) в этом случае используется соотношение: Эта модель получения прогноза используется, если значения всех факторов (х](0),..., хп(0)) заданы качественно, в лингвистическом и нечетком виде. В этом случае суммирование приращений (импульсов) в вершинах графа недопустимо. Методы получения прогнозов развития ситуации для этой модели разрабатывались в работах Б. Коско [45], В. Занга [46], В. Силова [12] и др. Подробно этот метод получения прогноза рассматривается во второй главе. На основе этой модели вычисления прогноза построено множество систем когнитивного моделирования, в частности системы: «Космос» [12], «Компас» [41, 47, 48], «Канва» [49, 50, 51, 52, 53] и др.
Методология структуризации слабо структурированной ситуации
Методологии структуризации знаний экспертов для представления их в поле знаний рассмотрены [27]. Здесь предложен объектно-структурный подход (ОСП) структуризации знаний. Согласно этому подходу анализ и представление знаний осуществляется в следующих аспектах (стратах): стратегический; организационный; концептуальный; функциональный; пространственный; временной; каузальный; экономический. Методологической основой структуризации ситуации для представления ее в модели поля знаний является системный подход. Системный подход - это способ теоретического представления объектов или ситуаций как систем. Основными понятиями системного подхода являются понятия элемента, структуры, функции. В центре внимания системного подхода находится изучение структуры объекта или ситуации и места элементов в ней.
Специфика системного подхода определяется тем, что он ориентирует исследование на раскрытие целостности объекта и обеспечивающих ее механизмов, на выявление многообразных типов связей сложного объекта и сведение их в единую теоретическую картину. Системный подход направлен на: 1. Изучение целостности и установление состава целого и его элементов. 2. Исследование закономерностей соединения элементов в систему, т.е. структуры системы. 3. Изучение функций системы и ее составляющих, т.е. структурно-функциональный анализ системы. Методология структуризации слабо структурированной ситуации, основанная на системном подходе, заключается в описании ситуации в двух аспектах: структурном и функциональном.
Описание ситуации в структурном аспекте заключается в выделении составных частей наблюдаемой ситуации в виде иерархии «Часть-Целое», (D, 0), где, D={di} - множество элементов, характеризующих целое и составные части ситуации, 0 - отношение «Часть-Целое», заданное на множестве элементов ситуации D. При структурной декомпозиции определяются также основные факторы (в дальнейшем признаки) Fj={fy} всех элементов ситуации dt. В качестве примера структурного представления ситуации рассмотрим декомпозицию рыночной структуры. Рынок d] - это механизм регулирования хозяйственной жизни - экономики государством [64] и включает составные части рынка: производители d2, потребители d3 и государство d4. Т.е. задана структура объекта в виде иерархии «Целое-Часть»: (d{) (d2, d3, d4), рис.2.1. Рынок - это механизм обмена товаров и услуг между производителями и потребителями. Признаки F\={fu, fn, /із} понятия рынок (dj): 1. цены на товары и услуги (fn), 2. структура рынка (f12), 3. дефицит товаров или услуг (f13). Производители - это физические или юридические лица, занимающиеся производством товаров и услуг. Признаки F2={f2i, /22, /23, /24, /25} понятия «Производители» d2 следующие: 4. совокупный объем производства (f2]), 5. количество фирм производителей (f22), 6. прибыль производителей (f23), 7. совокупные затраты на сырье (f24), 8. совокупная заработная плата (f25).
Потребители - это физические или юридические лица, приобретающие товары или услуги на рынке. Признаки F3={f3i, f32J понятия «Потребители» d3\ 9. совокупный спрос (f31)\ 10. уровень доходов (f32). Государство - это регулирующий орган процессов на рынке. Признаки F4={f4h /42, /43, /44} понятия «Государство» d4 следующие: 11. уровень доходов государства (f4\)\ 12. уровень налогов (f42), 13. объем государственных инвестиций (f43) , 14. объем социальных трансфертов (f44) Описание ситуации в функциональном аспекте заключается в построении модели функционирования ситуации в виде ориентированного знакового графа - когнитивной карты ситуации. При построении когнитивной карты сложной ситуации используются результаты ее структурной декомпозиции, т.е. представление ситуации в виде иерархии «Часть-Целое», (D, 0).
В сложной ситуации когнитивные карты строятся для каждого элемента ситуации dte D. В качестве вершин орграфа используются признаки F fo} элемента dt. Экспертным путем определяются бинарные причинно-следственные отношения на множестве признаков Fh которые представляются в виде ориентированного графа (Fh W,), где Wt -матрица смежности графа, отражающая экспертные знания о законах функционирования элемента ситуации dt. Направленным дугам графа приписывается знак «+» или «-», т.е. они могут быть положительными или отрицательными. Положительная связь означает, что увеличение значения признака-причины приводит к увеличению значения признака-следствия, а отрицательная дуга означает, что увеличение значения признака-причины приводит к уменьшению значения признака-следствия. После построения когнитивных карт отдельных элементов ситуации экспертным путем определяются причинно-следственные отношения признаков разных элементов ситуации, т.е. определяется модель функционирования ситуации как целого, выраженная через модели функционирования ее отдельных элементов. Таким образом, когнитивные карты (Fh Wj) отдельных элементов ситуации объединяются в когнитивную карту сложной ситуации (F, W), где F= и Fj - множество признаков ситуации, W - матрица смежности орграфа, описывающая сложную ситуацию и включающая матрицы Wt отдельных элементов ситуации и связи между ними. Построение когнитивных карт отдельных элементов ситуации, основанное на ее структурной декомпозиции значительно проще, чем построение когнитивной карты сложной ситуации без ее предварительной структуризации. Системный прием структурной декомпозиции широко используется в науке и технике при исследовании сложных ситуаций.
Однако в когнитивном моделировании он практически не применяется по двум причинам. Во-первых, преимущество когнитивных моделей заключается в их наглядности, поэтому когнитивные модели обычно содержат небольшое число базовых факторов и связей между ними, отражающие основные законы и закономерности развития ситуации. Когнитивные карты, включающие большое число факторов теряют наглядность и, следовательно, резко падает продуктивность их анализа. Во-вторых, когнитивный подход - это подход решения проблем, т.е. когнитивная модель - это модель проблемы, которая отражает основные ее факторы и строится после возникновения проблемы. Проблемный подход решения проблем не позволяет предсказать появление проблемы или чрезвычайной ситуации. Для решения задач предсказания проблем, иначе мониторинга ситуаций, нужен системный подход при построении модели ситуации. В этом случае когнитивная модель отражает как можно более полно все известные субъекту факторы ситуации и связи между ними. Т.е. строится модель ситуации как системы. Пример когнитивной карты сложной ситуации в блочном виде показан на рис.2.2. На рисунке показаны когнитивные карты отдельных элементов ситуации и причинно-следственные связи между ними.
Метод интерпретации решений обратной задачи
Задача принятия решения в когнитивном моделировании формулируется как задача разработки стратегии перевода ситуации из текущего состояния Х(0) в целевое состояние л. Для разработки стратегии управления ситуацией можно определить два подхода: параметрический и структурный. Параметрический подход заключается в нахождении значений параметров модели ситуации (F, X, Х(0), W) (значений признаков хуєХу), изменение которых позволяет достичь желаемого состояния ситуации Xа без изменения структуры модели ситуации, определенной матрицей смежности W. В этом подходе поиск решения сводится к решению обратной задачи. При решении обратной задачи задается модель ситуации: (F, X, Х(0), W), целевое состояние ситуации л И множество RczF входных признаков, для изменения которых у субъекта имеются ресурсы. Ресурсы определены вектором ресурсов Рг=(риг, ..., рптґ). Элементы вектора р,/єҐ показывают допустимые приращения значения управляющего признака. Задача заключается в нахождении путем решения обратной задачи множества решений U-{Ui, ..., Uvj, где каждое решение Uv=(pu, ..., рпт) - это вектор приращений значений признаков для достижения целевого состояния, и выбора среди полученных решений - решения (решений), удовлетворяющих заданным ограничениям Рг. К сожалению, такие решения не всегда существуют.
В этом случае для достижения целевого состояния можно изменить структуру модели ситуации и попытаться получить новые решения уже для измененной структуры. Подход, предполагающий поиск изменений структуры модели ситуации W, позволяющих достичь целевого состояния ситуации л, рассмотрен в этой главе. Изменение структуры ситуации, позволяющее достичь целевого состояния, называется структурным решением. В настоящее время поиск структурных решений осуществляется экспертными методами. Это методы морфологического анализа, мозгового штурма. Методы мозгового штурма требуют подбора экспертов, подготовки и организации процесса мозгового штурма. Морфологический анализ сводится к решению переборной задачи -просмотру всех возможных вариантов решений, получаемых декартовым произведением шкал признаков [7,8]. В этой работе рассматривается методология поиска структурных решений, основанная на предлагаемой модели представления знаний.
Она заключается в поиске объектов-стимулов, структурная организация которых является примером структурных решений в анализируемой системе. Разработана методика поиска структурных решений, включающая ряд связанных этапов: 1. Генерация решений; 2. Структуризация решений в функциональной структуре; 3. Структуризация решений в понятийной системе; 4. Поиск объектов-стимулов для выработки структурных решений. Генерация решений заключается в решении обратной задачи для заданной цели G управления. При решении обратной задачи задана модель ситуации четверкой (F, X, Х(0), W), определено текущее Х(0)=(хц0, Хп . , хпт), желаемое состояние XG=(x]1g, xj2g . , xnmg) ситуации в функциональной системе поля знаний и, следовательно, целевой вектор приращений
Целевой вектор приращений G показывает, в каком направлении и на сколько нужно изменить значения признаков в начальном состоянии Х(0), чтобы перейти в целевое состояние Xе. Для целевого вектора G решается обратная задача. Постановка и алгоритмы решения обратной задачи подробно описаны во второй главе. Результатом решения обратной задачи является множество решений U. Решения Uh . ., Uv - это приращения значений признаков (ри, сп, ..., рпт, cnJ. Каждому решению UveU, соответствует состояние ситуации в функциональной системе поля знаний Xv=(x}i0+pjj, ... , xnj+pnj), т.е. определены состояния Xv, соответствующие решениям Uv. Для облегчения дальнейшего поиска решений все полученные решения структурируются. Осуществляется структуризация решений, полученных на модели, описанной в функциональной системе поля знаний, и их представления в понятийной системе поля знаний. Решения Uv, полученные в результате решения обратной задачи структурируются по двум критериям
Подсистема поддержки аналитической деятельности эксперта
Эта подсистема обеспечивает автоматическую генерацию объяснения, включающего описание последовательных шагов (причинно-следственных цепочек) получения прогнозного значения любого признака ситуации. Отчет включает положительную и отрицательную причинно-следственные цепочки. Положительная цепочка объясняет причину увеличения значения признака, а отрицательная - его уменьшения.
Для автоматической генерации объясняющих цепочек разработан алгоритм, основанный на выделении фронта максимальных приращений значений признаков в матрице прогноза Р .
Для выделения фронта максимальных приращений в каждой строке матрицы Р! находим максимальный положительный элемент p+Sd(t+b)max и максимальный отрицательный элемент p sd(t+b)max. Остальные элементы строки приравниваются к нулю. После выделения максимальных элементов во всех строках матрицы Р получаем матрицу Р тах с выделенным максимальными элементами.
Матрица с выделенными максимальными элементами Р тах является исходной для работы алгоритма поиска причинно-следственных цепочек, объясняющих суммарное приращение pscj(t) признака/ eF.
Для работы алгоритма определим два пустых множества L}=0YL L2=0, В которые будем добавлять элементы цепочек, объясняющих изменение признака fSd. В L] будет формироваться цепочка, объясняющая положительное p+sd(t), а в L2 отрицательное p sd(t) приращение значения признака. Описание алгоритма приводится ниже.
Шаг 1. Выбираем строку признака в матрице Хтах и находим столбец Ъ, в котором находится максимальный элемент р+sd(b)max.
Шаг 2. В столбце матрицы (Ь-1) матрицы Р тах ищем элемент pei(b-l), такой, чтобыpsd(b)lpei(b-l)= Wijei- Т.е. определяем, какой из элементов на предыдущем шаге вызвал изменениеpsd(b). Если такой элемент найден, то признаки и fe[ образуют причинно-следственную цепочку. Во множество L] записывается пара: fsd название признака и значение его приращения p+sd(b), т.е. Li=(fsd, P+sd(b);fei,Pei(b-l)).
Шаг 3. Для элемента pei(b-1) ищем элемент в столбце Ь-2, породившего это изменение. Т.е. повторяем шаг 2 для элемента pel(b-l). Повторяем шаги 2 и 3 для новых элементов до достижения первого столбца матрицы Р тах. В результате выполнения шагов 2 и 3 формируется цепочка признаков и их значений L] = (fsd, p+sdk(b); fi, РеіФ-1); ...; fp Pijk(V), объясняющая положительное приращение p+sdk(t) признака .
Шаг 4. Для определения причинно-следственной цепочки, объясняющей отрицательное приращение p sd (0 признака , находится столбец q, в котором находится это значение. Далее для элемента р sd(q)max, находящегося в строке признака fsd матрицы Р тах необходимо повторить шаги 2 и 3. Причинно-следственная цепочка при этом будет записываться во множество L2= (fsd, показана форма расшифровки падения значения признака «Тариф на транспортные услуги» падает на 35,2%. В этой форме приведено объяснение изменения значения признака «Тариф на транспортные услуги» при увеличении объема перевозок на 42,4 %. Правый список формы показывает причинно-следственную цепочку, увеличивающую (+1,6%), а левый уменьшающую (-35,2%) значение анализируемого признака.
Советующая подсистема предназначена для поддержки аналитической деятельности эксперта путем выдачи рекомендаций и советов для выбора управляющих воздействий при разработке стратегии достижения векторной целиG=(gu,g!2. -.Яш) Задача заключается в нахождении вектора управляющих воздействий U=(Un, U/2, -., w,„J В системе когнитивного моделирования выбор элементов вектора управляющих воздействий осуществляется в экспертом в диалоговом режиме с советующей подсистемой.
Работа советующей подсистемы основывается на решении обратной задачи, теория решения которой рассмотрена во второй главе.
При решении обратной задачи для заданного целевого вектора G=( gu, gi2, gnm) с помощью алгоритмов, описанных во второй главе, находятся все решения U. После получения всех решений задача эксперта заключается в определении множества реализуемых решений и решений, перспективных с точки зрения поиска структурных решений.
Общее число решений, получаемых в результате решения обратной задачи, может составлять несколько десятков или даже сотен решений.
В разработанной системе предлагается диалоговый режим поиска альтернативных решений (векторов управляющих воздействий для достижения векторной цели), что позволяет сократить трудоемкость анализа, полученных в результате решения обратной задачи решений.
