Содержание к диссертации
Введение
Глава 1: Методология создания систем поддержки принятия решений для слабо структурированных ситуаций и основные концепции создания гибридных информационных интеллектуальных систем 8
1.1 Методологические проблемы создания систем поддержки принятия решений для слабо структурированных ситуаций 8
1.2 Использование нечетких множеств в СППР для слабо формализованных ситуаций 15
1.2.1. Формализация качественных знаний 16
1.2.2. Алгебраические свойства операций с нечеткими подмножествами на базе Т-норм 20
1.3 Обзор средств и методов построения систем искусственного интеллекта 22
1.3.1. Формальные модели представления знаний в интеллектуальных системах 30
1.4 Обзор существующих моделей гибридных информационных интеллектуальных
систем (ГИИС) 34
1.4.1. Классификация ГИИС 36
Глава 2: Методы и алгоритмы построения и анализа нечеткой когнитивной модели слабо структурированной ситуации; методы и алгоритмы построения и анализа нечеткой иерархической модели слабо структурированной ситуации 37
2.1 Методология нечеткого когнитивного моделирования слабо структурированной
ситуации 37
2.1.1. Понятие нечеткой когнитивной карты 37
2.1.2. Прямая задача когнитивного процесса ...45
2.1.3. Обратная задача когнитивного процесса 49
1.2 Нечеткая иерархическая модель слабо структурированной предметной области50
2.2.1. Основные этапы определения коэффициентов важности объектов в
иерархических системах 52
2.2.2. Методы определения коэффициентов важности альтернатив 60
2.2.3. Упорядочение объектов в иерархических системах на основе нечетких отношений с интенсивностью предпочтений 67
Глава 3: Методология построения гибридной модели слабо структурированной ситуации на основе интеграции нечеткой когнитивной модели и нечеткой иерархической модели представления слабо структурированной ситуации 93
3.1 Согласование шкал факторов когнитивной модели и модели иерархии 96
3.2 Описание процесса построения интегрированной модели 102
Глава 4; Описание программного комплекса интегрированной системы поддержки принятия решений в слабо структурированной ситуации 113
4.1. Основные задачи, решаемые программным комплексом 114
4.2 Работа с программным комплексом 115
Заключение 127
Список используемой литературы 129
- Использование нечетких множеств в СППР для слабо формализованных ситуаций
- Обзор средств и методов построения систем искусственного интеллекта
- Понятие нечеткой когнитивной карты
- Описание процесса построения интегрированной модели
Использование нечетких множеств в СППР для слабо формализованных ситуаций
Методы принятия решений основаны на представлении знаний в виде некоторых количественных данных, являющихся оценками предпочтений экспертов. Методы различаются способами представления и обработки предпочтений и часто приводят к разным результатам. В связи с этим возникает проблема выбора стратегии и метода решения конкретной задачи. Критерии для выбора метода в каждом случае будут зависеть от количества и качества доступной информации, от принятой постановки задачи и совокупности факторов внешней по отношению к объекту исследования среды (объект исследования определен на этапе постановки задачи), которые влияют на поведение этого объекта. Поэтому подход к принятию решений с позиции классических методов включает достаточно трудные задачи выбора метода и обоснования полученных результатов. Для решения задач многокритериального выбора в условиях неопределенности предложено множество математических методов. Методы прикладной теории принятия решений различаются способом представления и обработки экспертных знаний. Подход к проблеме выбора может основываться на отношениях порядка среди альтернатив (классическая модель принятия решений, в которой каждой альтернативе ставится в соответствие некоторое число) или на отношениях включения (поведенческая модель, основанная на принадлежности альтернатив к некоторому множеству). Среди методов классического подхода наибольшей универсальностью и теоретической обоснованностью обладают методы теории нечетких множеств и методы многокритериальной оценки. Ряд задач поддержки принятия решений, для которых классические методы не являются эффективными, могут быть решены методами нечетких множеств и систем. Основы современной теории нечетких систем заложены работами Л. Заде, А.Кофмана, Дюбуа и Прада, Негойцэ и др. Развитие теории нечетких множеств и систем, связанных с решением прикладных задач принятия решений, планирования и целевого управления, показывает, что для построения сложных математических моделей систем, моделирующих слабо структурированную ситуацию, требуются операции с нечеткими подмножествами и нечеткими отношениями. Такой класс операций может быть построен с помощью триангулярных норм.
При формализации качественных знаний, полученных в результате экспертного оценивания, может быть использована теория нечетких множеств [56], особенно те ее аспекты, которые связаны с лингвистической неопределенностью, наиболее часто возникающей при работе с экспертами на естественном языке. Под лингвистической неопределенностью подразумевается не полиморфизм слов естественного языка, который может быть преодолен на уровне понимания смысла высказываний в рамках байесовской модели, а качественные оценки естественного языка для длины, времени, интенсивности, для целей логического вывода, принятия решений, планирования.
Лингвистическая неопределенность в системах представления знаний задается с помощью лингвистических моделей основанных на теории лингвистических переменных и теории приближенных рассуждении. Эти теории опираются на понятие нечеткого множества, систему операций над нечеткими множествами и методы построения функций принадлежности.
Одним из основных понятий, используемых в лингвистических моделях, является понятие лингвистической переменной. Значениями лингвистических переменных являются не числа, а слова или предложения некоторого искусственного либо естественного языка. Множество допустимых значений лингвистической переменной называется терм-множеством.
Лингвистическая переменная задается набором из пяти компонентов: А, Т(А), U, V, М , где Л-имя лингвистической переменной; Т (А)-ее терм-множество; U-область, на которой определены значения лингвистической переменной; V -синтаксическое правило, обычно, грамматика, описывает операции по порождению производных значений лингвистической переменной на основе тех значений, которые входят в терм-множество. М — семантическое правило, которое ставит в соответствие каждой нечеткой переменной из Т (А) нечеткое подмножество универсального множества U.
Для перехода от качественных описаний к формализованным необходимо построить отображения, входящие в М, т. е. построить функции принадлежности, В таком виде подобная задача была исследована в [41]. При получении от экспертов информации о виде функций принадлежности необходимо учитывать характер измерений (первичные и производные измерения) и тип шкалы, на которую проецируются измерения и на которой будут определяться функции принадлежности. На этой шкале задается вид допустимых операторов и операций, т. е. некоторая алгебра для функций принадлежности. Кроме того, следует различать характеристики, которые можно измерять непосредственно и характеристики, которые являются качественными и требуют попарного сравнения объектов, обладающих этими характеристиками, чтобы определить их отношение к исследуемому понятию. Можно выделить две группы методов построения функций принадлежности: прямые и косвенные. В прямых методах эксперт непосредственно задает правила определения значений функции принадлежности. К прямым методам относится непосредственное задание функции принадлежности таблицей, формулой или примером [31,32, 56]. В косвенных методах значения функции принадлежности выбираются таким образом, чтобы удовлетворялись заранее сформулированные условия. Экспертная информация является только исходной для дальнейшей обработки. Дополнительные условия могут налагаться как на вид получаемой информации, так и на процедуру обработки. Примерами дополнительных условий могут служить следующие: функция принадлежности должна отражать близость к заранее выделенному эталону, объекты множества являются точками в параметрическом пространстве [41, 42], результатом процедуры обработки должна быть функция принадлежности, удовлетворяющая условиям интервальной шкалы [64, 101]; при попарном сравнении объектов, если один объект оценивается в к раз сильнее, чем другой, то второй объект оценивается в — раз сильнее, к чем первый объект [32, 90, 91] и т. д. Как правило, прямые методы используются для описания понятий, которые характеризуются измеримыми признаками (высотой, ростом, массой, объемом). В этом случае удобно непосредственное задание функции принадлежности. К прямым методам можно отнести методы, основанные на вероятностной трактовке функций принадлежности. Так как люди часто искажают оценки, например, сдвигают их в направлении концов оценочной шкалы [64, 78], то прямые измерения, основанные на непосредственном определении значений функции принадлежности, могут быть использованы только в том случае, когда такие искажения незначительны или маловероятны. Косвенные методы более трудоемки, чем прямые, но обладают стойкостью к искажениям в ответе. Результатом применения косвенных методов является интервальная шкала. В [78] выдвигается для косвенных методов "условие безоговорочного экстремума": при определении степени принадлежности множество исследуемых объектов должно содержать, по крайней мере, два объекта, численные представления которых на интервале [0, 1] - 0 и 1 соответственно. Функции принадлежности могут отражать мнение как некоторой группы экспертов, так и одного уникального эксперта. Комбинируя возможные два метода построения функций принадлежности с двумя типами экспертов (коллективным и уникальным), можно получить четыре типа экспертизы [41]. Рассмотрим далее понятие нечеткого отношения. Нечеткие отношения играют фундаментальную роль в теории нечетких систем. Аппарат нечетких отношений используется при построении теории нечетких автоматов, при моделировании структуры сложных систем, при анализе процессов принятия решений, в задачах управления и т.д. Как правило, аппарат теории отношений применяется при качественном анализе взаимосвязей между объектами исследуемой системы, когда методы количественного анализа взаимосвязей по каким-либо причинам не применимы.
Обзор средств и методов построения систем искусственного интеллекта
Функционирование многих интеллектуальных систем (ИС) носит целенаправленный характер (примером могут служить автономные интеллектуальные роботы). Типичным актом такого функционирования является решение задачи планирования пути достижения нужной цели из некоторой фиксированной начальной ситуации. Результатом решения задачи должен быть план действий - частично-упорядоченная совокупность действий. Такой план напоминает сценарий, в котором в качестве отношения между вершинами выступают отношения типа: "цель-подцель" "цель-действие", "действие-результат" и т. п. Любой путь в этом сценарии, ведущий от вершины, соответствующей текущей ситуации, в любую из целевых вершин, определяет план действий. Поиск плана действий возникает в ИС лишь тогда, когда она сталкивается с нестандартной ситуацией, для которой нет заранее известного набора действий, приводящих к нужной цели. Все задачи построения плана действий можно разбить на два типа, которым соответствуют различные модели: планирование в пространстве состояний (SS-проблема) и планирование в пространстве задач (PR-проблема).
В первом случае считается заданным некоторое пространство ситуаций. Описание ситуаций включает состояние внешнего мира и состояние ИС, характеризуемые рядом параметров. Ситуации образуют некоторые обобщенные состояния, а действия ИС или изменения во внешней среде приводят к изменению актуализированных в данный момент состояний. Среди обобщенных состояний выделены начальные состояния (обычно одно) и конечные (целевые) состояния. SS-проблема состоит в поиске пути, ведущего из начального состояния в одно из конечных. При планировании в пространстве задач ситуация иная. Пространство образуется в результате введения на множестве задач отношения типа: "часть - целое", "задача - подзадача", "общий случай - частный случай" и т. п. Другими словами, пространство задач отражает декомпозицию задач на подзадачи (цели на подцели). PR-проблема состоит в поиске декомпозиции исходной задачи на подзадачи, приводящей к задачам, решение которых системе известно. Представление задач в пространстве состояний предполагает задание ряда описаний: состояний, множества операторов и их воздействий на переходы между состояниями, целевых состояний. Описания состояний могут представлять собой строки символов, векторы, двухмерные массивы, деревья, списки и т. п. Операторы переводят одно состояние в другое. Иногда они представляются в виде продукций А В, означающих, что состояние А преобразуется в состояние В. Пространство состояний можно представить как граф, вершины которого помечены состояниями, а дуги - операторами. Таким образом, проблема поиска решения задачи А,В при планировании по состояниям представляется как проблема поиска на графе пути из А в В. Обычно графы не задаются, а генерируются по мере надобности. Различаются слепые и направленные методы поиска пути. Слепой метод имеет два вида: поиск вглубь и поиск вширь. При поиске вглубь каждая альтернатива исследуется до конца, без учета остальных альтернатив. Метод плох для "высоких" деревьев, так как легко можно проскользнуть мимо нужной ветви и затратить много усилий на исследование "пустых" альтернатив. При поиске вширь на фиксированном уровне, исследуются все альтернативы и только после этого осуществляется переход на следующий уровень. Метод может оказаться хуже метода поиска вглубь, если в графе все пути, ведущие к целевой вершине, расположены примерно на одной и той же глубине. Оба слепых метода требуют большой затраты времени и поэтому необходимы направленные методы поиска.
Метод ветвей и границ. Из формирующихся в процессе поиска неоконченных путей выбирается самый короткий и продлевается на один шаг. Полученные новые неоконченные пути (их столько, сколько ветвей в данной вершине) рассматриваются наряду со старыми, и вновь продлевается на один шаг кратчайший из них. Процесс повторяется до первого достижения целевой вершины, решение запоминается. Затем из оставшихся неоконченных путей исключаются более длинные, чем законченный путь, или равные ему, а оставшиеся продлеваются по такому же алгоритму до тех пор, пока их длина меньше законченного пути. В итоге либо все неоконченные пути исключаются, либо среди них формируется законченный путь, более короткий, чем ранее полученный. Последний путь начинает играть роль эталона и т. д. Алгоритм кратчайших путей Мура. Исходная вершина Хо помечается числом 0. Пусть в ходе работы алгоритма на текущем шаге получено множество дочерних вершин Х(х,) вершины х,. Тогда из него вычеркиваются все ранее полученные вершины, оставшиеся помечаются меткой, увеличенной на единицу по сравнению с меткой вершины х,, и от них проводятся указатели к X. Далее, на множестве помеченных вершин, еще не фигурирующих в качестве адресов указателей, выбирается вершина с наименьшей меткой и для нее строятся дочерние вершины. Разметка вершин повторяется до тех пор, пока не будет получена целевая вершина.
Алгоритм Дейкстры определения путей с минимальной стоимостью является обобщением алгоритма Мура за счет введения дуг переменной длины.
Алгоритм поиска Дорана и Мичи. Используется, когда стоимость поиска велика по сравнению со стоимостью оптимального решения. В этом случае вместо выбора вершин, наименее удаленных от начала, как в алгоритмах Мура и Дийкстры, выбирается вершина, для которой эвристическая оценка расстояния до цели наименьшая. При хорошей оценке можно быстро получить решение, но нет гарантии, что путь будем минимальным.
Алгоритм Харта, Нилъсона и Рафаэля. В алгоритме объединены оба критерия: стоимость пути до вершины g(x) и стоимость пути от вершины h(x) - в аддитивной оценочной функции// ) =g(x}-h(x). При условии h(x) hp(x), где /ipf -действительное расстояние до цели, алгоритм гарантирует нахождение оптимального пути. Алгоритмы поиска пути на графе различаются также направлением поиска. Существуют прямые, обратные и двунаправленные методы поиска. Прямой поиск идет от исходного состояния и, как правило, используется тогда, когда целевое состояние задано неявно. Обратный поиск идет от целевого состояния и используется тогда, когда исходное состояние задано неявно, а целевое явно. Двунаправленный поиск требует удовлетворительного решения двух проблем: смены направления поиска и оптимизации "точки встречи". Одним из критериев для решения первой проблемы является сравнение "ширины" поиска в обоих направлениях - выбирается то направление, которое сужает поиск. Вторая проблема вызвана тем, что прямой и обратный пути могут разойтись и чем уже поиск, тем это более вероятно.
Решение задач методом редукции. Этот метод приводит к хорошим результатам потому, что часто решение задач имеет иерархическую структуру. Однако не обязательно требовать, чтобы основная задача и все ее подзадачи решались одинаковыми методами. Редукция полезна для представления глобальных аспектов задачи, а при решении более специфичных задач предпочтителен метод планирования по состояниям. Метод планирования по состояниям можно рассматривать как частный случай метода планирования с помощью редукций, ибо каждое применение оператора в пространстве состояний означает сведение исходной задачи к двум более простым, из которых одна является элементарной. В общем случае редукция исходной задачи не сводится к формированию таких двух подзадач, из которых хотя бы одна была элементарной.
Понятие нечеткой когнитивной карты
Традиционное понятие когнитивной карты возникло и развивалось в виде знаковых орграфов. Среди этих представлений наиболее конструктивными являются представления, рассмотренные в работах [2, 58, 59] и подход Робертса [85] применительно к импульсным процессам. Эти подходы делают акцент на прогнозе ситуации по знаковому орграфу, а возможности таких моделей для использования в плане поддержки принятия решений, на самом деле, весьма ограничены.
В современных моделях используется новый подход к когнитивному моделированию ситуации, а именно, используются методы нечетких множеств в когнитивном моделировании. Такие модели называются нечеткими когнитивными картами ситуации.
Нечеткая когнитивная карта есть причинно - следственная сеть, отражающая какую-либо область знания посредством дуг и узлов положительно -отрицательной сети. В такой сети дугам соответствуют отношения (связи) из интервала [-1,1], а узлами являются атрибуты (концепты).
Под концептом в данном случае понимается понятие, объект в обобщенном смысле, признак ситуации и т.д. Концепт - основная каузальная категория или объект. Когнитивные карты задаются когнитивными графами, которые представляют собой узлы - концепты и связи - числа, лежащие в отрезке [-1,1]- Процедура построения когнитивной карты называется когнитивным отображением.
Данный процесс основан на методах адаптации семантической сети или на использовании прямых экспертных процедур опроса. Сформулируем основные этапы приобретения знаний от экспертов:
1. Интервью для определения актуальной области, в которой происходит процесс решения интересующей проблемы, и расчленение ее на автономные области.
2. Автоматизированное интервью для выявления и формирования декларативной модели предметной области.
3. Протокольный анализ к выявленным на предыдущем этапе понятиям и отношениям предметной области для пополнения модели процедурными знаниями (этапы 2 и 3 можно использовать попеременно до тех пор, пока модель не достигнет нужной полноты).
4. Протокольный анализ для пополнения декларативных знаний модели. Проверка полноты модели. Обычно протокольный анализ выявляет пустоты в модели. Имеется в виду случай, когда понятия, использованные в "мыслях вслух", недостаточно описаны. В этом случае интервью и протокольный анализ повторяются.
При построении когнитивной карты эксперту потребуется определить концепты исследуемой предметной области и далее определить, какой концепт является причиной, а какой является следствием. Затем при установлении влияния, эксперту необходимо определить, какое действие на концепт В оказывает усиление концепта А а в какой степени. «Усиление - ослабление» носит абстрактный характер, эксперту необходимо проинтерпретировать релевантную причинно - следственную связь.
Построенная нечеткая когнитивная карта представляет собой причинно - следственную сеть (или нечеткую положительно - отрицательную семантическую сеть), в которой отношения (веса связей) могут лежать в отрезке [-1,1]. Нечеткие семантические сети используются для анализа взаимовлияния концептов друг на друга. В заданном орграфе G (E, W), Е -множество факторов ситуации, W - множество дуг в орграфе, представляющих собой непосредственные связи между факторами ситуации, лежащими в вершинах орграфа.
Описание процесса построения интегрированной модели
В результате такого построения интегрированной модели, нечеткая когнитивная модель ситуации представляется как модель предметной области, в которой отражены все связи между всеми факторами ситуации, также каждый из факторов имеет некоторое значение (количественное или качественное) в каждый дискретный момент времени. Тогда как нечеткая иерархия построена таким образом, что представляет собой целевую функцию. В результате совместной работы этих двух моделей, в каждый дискретный момент времени в системе существует информация о том, как текущая ситуация влияет на оценку 102 достижимости заданной цели. То есть, в каждый дискретный момент времени существует альтернатива для оценивания в модели иерархии. Определение 3.3: Гибридную (интегрированную) модель поддержки принятия решений в неструктурированных ситуациях можно представить следующим набором: (Со,1г,Ф, W,A,0(A)), J. Со - когнитивная модель, которая определяется четверкой: {(F, W), X, Х(0)\ (F, W) - когнитивная карта ситуации, F множество факторов ситуации, W -матрица смежности орграфа; Х- {Xj}- множество шкал всех факторов ситуации; Х(0) - начальное состояние ситуации, вектор начальных значений всех факторов когнитивной модели. 2. 1г - иерархическая модель оценивания, определяется четверкой ((Z, Е), К, Y, (vj), a) (Z, Е) - иерархический орграф оценивания, Z - множество критериев оценивания разного уровня иерархии, Е - множество дуг, связывающих критерии разного уровня; b) К={к/}- листовые критерии иерархии, К zZ; c) Y={Yj} - множество шкал листовых критериев; d) {Wjj — множество весов листовых критериев К. 3. Ф - множество факторов когнитивной модели, 0czF, подобных по смыслу листовым критериям иерархической модели оценивания К, Ф=# eF: ff-kj, j-l,n}, - означает смысловое подобие факторов из множеств F и К; 4. F= {у/і} - множество отображений шкал факторов когнитивной модели X в шкалы листовых критериев модели иерархического оценивания Y, y/i .Xi— Yi; 5. А - множество альтернатив интегрированной модели поддержки принятия решений; 6. 0(A) — оценки достижимости генеральной цели альтернативой интегрированной модели поддержки принятия решений.
В определенной выше интегрированной модели множество альтернатив А является входом модели, а оценки О(А) — ее выходом. Модель иерархического оценивания Ir, когнитивного моделирования Со, а также подмножество факторов Ф и отображения шкал У образуют вычислительную часть интегрированной модели. Общая схема построения нечеткой гибридной модели: 1. Построение нечеткой положительно-отрицательной семантической сети G =(E,W), являющейся нечеткой когнитивной картой ситуации. Здесь Е 103 множество концептов, W - множество связей, W:(x)-»[-l,l], е/5е є, wie e eW. Определение когнитивной матрицы взаимовлияний факторов когнитивной модели в соответствии с алгоритмом определения матрицы взаимовлияний. 2. Построение нечеткой целевой иерархической модели в виде ориентированного графа G г без контуров с множеством вершин Z, совпадающим с множеством объектов, и множеством дуг . 3. Определение соответствия между листовыми критериями иерархической модели и факторами когнитивной модели. Достраивание и корректировка исходной нечеткой целевой иерархии, 4. Анализ и оценивание модифицированной иерархической модели: т.е. проведение элементарных экспертиз, усреднение экспертных оценок, определение весов дуг в модели по модифицированному методу анализа иерархий, определение коэффициентов важности факторов всех уровней иерархической модели относительно общей цели с учетом знаков влияния на дугах, анализ достоверности полученных весов. 5. При каждом возмущении когнитивной модели определение значения целевой функции FfAT w,). Таким образом, в результате совместной работы нечеткой когнитивной модели и нечеткой целевой иерархии, получаем оценку достижимости главной цели и всех подцелей нечеткой целевой иерархии для каждого прогноза, полученного в когнитивной модели. При этом нечеткая когнитивная модель представляет собой структурированную модель предметной области.
В построенной интегрированной модели помимо анализа текущей ситуации и оценивания текущей альтернативы относительно генеральной цели иерархической модели возможно также построение альтернатив в интегрированной модели с целью увеличения оценки достижимости цели. Для построения таких альтернатив необходимо построить ранжирование листовых критериев относительно интегрированной модели. Известно, что при построении интегрированной модели проводится сопоставление листовых критериев иерархической модели с факторами когнитивной модели по описанному выше правилу. Также, известно, что в когнитивной модели ситуации существует зависимость между всеми факторами ситуации и изменение одного из факторов когнитивной модели влечет изменение всех факторов за и шагов. Необходимо провести ранжирование листовых критериев с учетом сопоставленных им факторов когнитивной модели. С этой целью используются системные показатели нечеткой когнитивной карты.
Тогда степень влияния листового критерия к, на генеральную цель в интегрированной модели определяется по формуле: р(к,) = \\Vt\-Р, С Дф . Здесь w, -вес критерия kt в иерархической модели, такого что к, fr После упорядочивания полученных степеней влияния получаем ранжирование листовых критериев в интегрированной модели. Прогноз развития ситуации в системе когнитивного моделирования представляется парой (Р(т), С(т)). Р(т) - вектор приращений значений факторов ситуации в момент времени т, С(т) - вектор консонансов приращений значений признаков. Такое представление прогноза удобно для эксперта, анализирующего этот прогноз, поскольку дает возможность отдельно анализировать причинно-следственные цепочки увеличения и уменьшения значения любого фактора ситуации. Однако это создает проблемы при оценивании ситуации. Например, прогнозы развития ситуаций могут характеризоваться одинаковым вектором приращений состояния ситуации Р(т) и разными векторами консонанса значений факторов С(т)# С(т) . Понятно, что оценка таких состояний должна быть различна. Т.е. система иерархического оценивания должна адекватно упорядочивать оценки по предпочтительности с учетом не только значения фактора, но и его консонанса.
Похожие диссертации на Методология построения гибридных информационных интеллектуальных систем поддержки принятия решений на основе параметрических логик в слабо структурированных предметных областях
