Геловани В.А. и др. Интеллектуальные системы поддержки принятия решений в нештатных ситуациях

Подождите немного. Документ загружается.

Глава 3

Методы

поиска решений

для

динамических

баз знаний

систем

поддержки

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

3.1.

Постановка проблемы

Проблемы человеко-машинного управления техническими и органи-

зационными системами и процессами: энергетическими, транспортными,

экономическими и социальными привели к развитию нового направления

исследований в области математического и программного обеспечения

современных вычислительных систем — систем поддержхи принятия

решений.

Системы поддержки принятия решений (СППР) базируются на ин-

терактивных информационно-программных технологиях, основанных на

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

перед лицом, принимающим решения (ЛПР) и находить решение этих

проблем. СПР могут быть ориентированы и на поиск оптимального

решения. Для этого их базы знаний должны содержать описания форма-

лизмов строгих математических методов и модели оптимизации. СППР

используются при поддержке принятия решений в системах оперативного

управления сложными системами и процессами, как правило, в условиях

жестких временных ограничений.

СППР в отличие от СПР в основном ориентированы на решение пло-

хоформализуемых, слабоструктурированных задач при отсутствии полной

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

ные модели, построенные на основе знаний специалистов-экспертов

в данной проблемной области, и эвристические методы поиска. По со-

временной классификации программных средств СППР можно отнести

к классу интеллектуальных систем расчетно-логического типа. Необхо-

димость внедрения СППР обуславливается непрерывно возрастающей

сложностью управляемых объектов и процессов с одновременным со-

кращением времени, отводимого ЛПР на анализ проблемной ситуации

и принятие необходимых управляющих воздействий. Одной из основных

задач при построении СППР является выбор адекватных инструменталь-

ных средств, основанных на знаниях. Последние должны включать в себя

формальный аппарат для описания процесса принятия решений и постро-

ения на его базе адекватной (формально корректной) проблемной обла-

сти — модели принятия (поиска) решений. В качестве такого аппарата,

как правило, используются продукционные системы. Однако основные

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

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

12 Глава 3.

Методы поиска решений

для

динамических баз знаний

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

характеризующимся недетерминизмом, неполнотой, нечеткостью пред-

ставления информации. Имеющиеся на сегодня программные инструмен-

тальные средства проектирования СПР и СППР, включая системы реаль-

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

проблемные области, т.е. на ситуации, не требующие коррекции модели

принятия решений и стратегии поиска в процессе поиска решения.

Ниже рассматриваются экспертные модели принятия решений про-

дукционного типа, способные адаптироваться к специфике конкретной

проблемной области (специфике решаемой задачи), и методы поиска

решения на основе таких моделей, включая детерминированный, неде-

терминированный и параллельный поиск решения. Данные модели пред-

назначены для СППР реального времени, способных функционировать

в открытых, динамических проблемных областях при возможной коррек-

тировке и пополнении модели принятия решений в процессе поиска.

3.2. Формализация поиска решения

Рассмотрим специфику работы систем поддержки принятия реше-

ний, ориентированных на решение плохоформализуемых и слабострук-

турированных задач в статических и динамических проблемных областях.

Для формализации задачи принятия решений как задачи эвристического

поиска проанализируем возможные ее решения. В качестве основы моде-

ли принятия решений будем использовать продукционную систему. Для

анализа прюдукционной системы, с переходом как к детерминирован-

ной, так и недетерминированной схеме поиска решения, свойственной

открытым и динамическим проблемным областям, необходимо устано-

вить связь с задачей принятия решений и ввести понятие адаптивной

продукционной модели принятия решений, ориентированной на зада-

чи принятия решений в открытой форме, специфичных для открытых

и динамических проблемных областей.

3.2.1.

Специфика систем поддержки принятия решений

Системы поддержки принятия решений — направление исследова-

ний, возникшее и активно развиваемое в последние годы [6, 67, 102, 150,

152,

158, 163, 187]. СППР представляют собой человеко-машинные ком-

плексы, предназначенные для оказания помощи лицам, принимающим

решения, при решении плохоформализуемых и слабоструктурирован-

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

является:

• невозможность получения, как правило, всей объективной инфор-

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

субъективной, эвристической информации;

• данные задачи являются существенно комбинаторными, многие

из них относятся к классу NP-полных (например, задачи диагностики

и планирования, связанные с построением оптимальных решающих

деревьев [80]);

• присутствие недетерминизма в процессе поиска решения;

3.2. Формализация поиска решения 73

• необходимость коррекции и введения дополнительной информации

в процессе поиска решения, активное участие в нем ЛПР;

• необходимость получения решения в условиях временных ограниче-

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

Перечисленные факторы не позволяют успешно использовать для

решения таких задач классические алгоритмические методы и модели

теории принятия решений.

СППР, концептуально объединяя подходы и методы теории принятия

решений, теории информационных систем, искусственного интеллекта

(в области извлечения, представления знаний и организации человеко-

машинного взаимодействия) и используя объективную и субъективную

информацию, обеспечивает ЛПР средствами анализа решаемой проблемы

и направляет его в процессе принятия решений с целью повышения

эффективности принимаемых решений.

В процессе принятия решений выделяются следуюшие основные

этапы [3, 67, 87]:

1) восприятие и осмысливание проблемной ситуации;

2) определение множества допустимых преобразований над ситуациями;

3) выбор необходимого или наиболее эффективного преобразования

в данной ситуации;

4) оценка полученного или ожидаемого результата и его коррекция при

необходимости.

Отметим, что если ко второму этапу ЛПР в определенной степе-

ни может подготовиться заранее, хотя может возникнуть необходимость

в пополнении и коррекции множества преобразований непосредственно

в процессе принятия решений, то все остальные этапы выполняются

ЛПР в «реальном времени», определяемом темпом управляемого про-

цесса. А темпы эти таковы, что ЛПР, управляюший в настояшее время

все более усложняющимися объектами и процессами (энергетическими,

транспортными, производственными и т.д.), все чаще испытывает недо-

статок времени и подвергается стрессовым перегрузкам. Ответственность

же ЛПР непрерывно возрастает. Принятие неадекватных или неэффек-

тивных решений может привести, как показывает практика, к серьезным

материальным, а в ряде случаев и людским потерям.

Современный этап создания СППР для диагностики и мониторинга

основан на методах, используюшцх принципы искусственного интеллек-

та. В такие системы закладываются знания высококвалифицированных

специалистов — экспертов в области диагностики, и постановка диа-

гноза осуществляется на основе этих знаний. Интеллектуальные СППР

характеризуются способностью к накоплению опыта, адаптации к измене-

ниям и обучению. Они не только позволяют менее квалифицированному

и опытному персоналу проводить диагностирование с приемлемой надеж-

ностью, но и помогают опытным специалистам глубже и детальнее анали-

зировать ситуацию и повышать эффективность принимаемых решений.

СППР помогают ЛПР принимать правильные и эффективные реше-

ния в условиях дефицита времени, а также неполноты, неопределенности

и недостоверности информации, отображающей проблемную ситуацию.

74 Глава 3. Методы поиска решений для динамических баз знаний

По сути решаемых задач, СППР как систему искусственного интеллекта

можно отнести к классу гибридных экспертных систем расчетно-логиче-

ского типа [36, 94, 95, 96J, сочетающих строгие математические методы

поиска решения с нестрогими, эвристическими методами, базирующими-

ся на экспертных

знаниях.

Причем главной является именно «экспертная,

эвристическая» компонента, а строгие методы имеют в основном вспо-

могательное назначение.

Основными элементами экспертных СППР являются модели пред-

ставления проблемной ситуации (состояний проблемной области) и по-

иска решений, а также средства организации диалогового взаимодействия

с пользователем (экспертом, ЛПР). Проблемная ситуация может описы-

ваться посредством некоторого вьщеленного множества признаков или

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

связи (отношения) между элементами проблемной области. В качестве

таких структур обычно используются семантические сети рши фреймы.

Модель поиска (принятия) решений (МПР) определяет допусти-

мые преобразования ситуаций и стратегию (стратегии) применения этих

преобразований. Специфика решаемых задач ориентирует СППР, как

правило, на открытые, динамические проблемные области (ПО), харак-

теризующиеся как возможностью введения новых элементов и связей

в описания ситуаций, так и возможностью изменения правил и страте-

гий функционирования объектов ПО в процессе принятия решений. Это

означает, что модели представления проблемной ситуации и поиска реше-

ния могут корректироваться непосредственно в процессе решения задачи.

По имеющимся данным [55, 57, 88, 89,90,107,164,172], подавляющее

большинство существующих экспертных систем и инструментальных про-

граммных средств их проектирования ориентированы на замкнутые'и ста-

тистические ПО, отличающиеся неизменностью средств описания про-

блемной ситуации, заранее известной логикой принятия решений и отсут-

ствием специальных механизмов реакции на внешние ситуации. Попытки

приспособления таких систем на открытые и динамические ПО с поиском

решения в реальном масштабе времени, как правило, малоэффективны.

Теоретические и прикладные вопросы конструирования экспертных си-

стем для динамических ПО и режима реального времени находятся

на начальной стадии исследований. Некоторые известные системы дан-

ного класса (см., например, [46, 159, 165, 168, 172, 184]) являются или уз-

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

Исследования по технологии создания экспертных систем реального

времени развиваются в настоящее время по двум главным направле-

ниям: поддержка принятия решений и непосредственное управление.

Соответствующие технологии и создаваемые на их базе промышленные

системы — основное направление исследований в области «реальное

время» на 1990-е годы.

Следует отметить, что большинство инструментальных средств ори-

ентировано на создание прикладных СППР, а не на непосредствен-

ное управление соответствующими процессами. Непосредственное упра-

вление критическими процессами, особенно при использовании новьпс

технологий, слишком рискованно. Переход к прямому управлению будет

3.2. Формализация поиска решения 75

возможен только в случае более изученных и освоенных технологий.

Основное же назначение СППР

—

поддержка ЛПР при управлении ггро-

цессами, выявлении и предупреждении опасностей, т. е. помощь ЛПР

в разрешении проблемных ситуаций до того, как они станут необрати-

мыми.

Создание современных высокопроизводительных СППР является

комплексной проблемой, требующей участия широкого крута специали-

стов:

психологов, когнитологов, математиков, экономистов, программи-

стов [67]. Основное внимание должно быть уделено следующим аспектам

данной проблематики:

• формализация экспертных знаний в плане построения МПР, обла-

дающих свойствами адаптации в условиях открытых и динамических

ПО;

• реализация поиска решения (включая недетерминированный и па-

раллельный поиск) в режиме реального времени в открытых и дина-

мических ПО;

• ориентация на современную и перспективную вычислительную тех-

нику с возможностью параллельной обработки информации.

Итак, основное наше внимание будет уделено конструированию се-

мантически корректных (адекватных ПО) МПР, ориентированных на от-

крытые и динамические ПО. В качестве базового формализма предста-

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

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

3.2.2.

Формализация задачи принятия решений

Задачу принятия решений будем рассматривать в известной в ис-

кусственном интеллекте постановке — поиске в пространстве состоя-

ний [81, 82]. В общем виде задача формулируется следующим образом:

задается некоторое начальное состояние или подмножество таких состоя-

ний, конечное состояние или подмножество таких состояний (возможно,

в неявном виде посредством некоторых ограничений) и множество пра-

вил преобразования состояний. Требуется найти такую последователь-

ность правил преобразований, возможно удовлетворяющую определен-

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

преобразовать начальное состояние в конечное. Если искомая последо-

вательность должна удовлетворять требованиям оптимальности, то имеем

задачу поиска оптимального решения, если требованиям допустимости

—

то задачу поиска допустимого (удовлетворительного) решения [77].

Задача принятия решений (ЗПР) определяется набором

{S,S'',S,„S^,P,Q}, (3.1)

где S — множество состояний (ситуаций), называемое универсумом,

S" С S — подмножество возможных (допустимых) состояний, соот-

ветственно S" П S — подмножество невозможных (недопустимых) со-

стояний; S„ С S — подмножество начальных состояний; S,^ С S —

подмножество конечных, или целевых состояний; Р: S

—*

S — конеч-

ное множество правил преобразований, каждое правило Р, С Р является

76 Глава 3. Методы поиска решений для динамических баз знаний

функцией, реализующей отображение Р,: S,

—^

S, где S,

—

область опре-

деления Р,. Считается, что правило Р, применимо к состоянию s С S,

если S С S,; Q — множество критериев оценки найденного решения.

Будем считать, что состояния описьшаются конечными словами (тек-

стами) некоторого языка и могут выражать как структурированные, так

и неструктурированные понятия.

Структурированное описание состояния обычно строится в виде

семантической сети.

Решением ЗПР является последовательность правил (последователь-

ность применений правил) преобразований (Р,

Р,...,

Р„), Р, Р, i =

п,

такая, что:

1) композиция РоРо... oP„(s') с 5к, где s' С S^, где под компози-

цией Р,

Pj понимается функция с областью определения {s\s С S,

и Ptis) С Sj}, где S, и Sj — области определения соответственно Р,

и Pj, значение которой есть Pj (Pi{s));

2) s'cs

(р,(/),...,

р„(...

p„-i(s')...));

3) искомая последовательность должна удовлетворять критериям

из

мно-

жества Q (например, если каждое правило Р, взвешено своей сложно-

стью,

а в качестве критерия оценки выбрана наименьшая сложность

решения, то при наличии нескольких последовательностей, удовле-

творяющих условиям 1-2), в качестве решения берется та из них,

которая имеет наименьшую суммарную сложность).

Если элементы набора (3.1) не изменяются в процессе поиска ре-

шения, то имеем ЗПР в замкнутой форме, соответствующей статической

ПО:

если же коррекция набора (3.1) допустима, например, возможно

пополнение множеств S, S", 3„, 5к, Р, или Q, то имеем ЗПР в открытой

форме, соответствующей динамической ПО.

Для решения ЗПР могут быть использованы как строгие методы тео-

рии принятия решений, так и эвристические [3, 70, 121]. Строгие методы

характеризуются точностью, определенностью и гарантируют оптималь-

ное решение (при его существовании). Данные методы обычно примени-

мы к ЗПР в замкнутой форме, когда решения принимаются в условиях

определенности и когда имеются достаточные вычислительные ресурсы.

К классу строгих методов относится дедуктивный вывод.

Эвристические методы характеризуются неточностью, неполнотой,

неопределенностью. Оптимальность или вообще решение не гарантиру-

ется. Данные методы используются для решения плохоформализуемых

и плохоструктурированных ЗПР и ЗПР в открытой форме, когда строгие

методы не применимы вообще или их применение требует слишком боль-

ших вычислительных ресурсов. Эвристические методы, базирующиеся

на учете специфики ПО, используются также в случае принятия решений

в условиях неопределенности и риска. К классу эвристических методов

относятся методы правдоподобного индуктивного и абдуктивного вывода.

Процесс поиска решения можно отобразить посредством дерева, на-

зываемого решающим деревом (деревом решений), вершины которого

соответствуют состояниям (корневой вершине соответствует начальное

3.2. Формализация поиска решения 77

состояние s' С SH), а ребра — правилам преобразований. Мы уже отме-

чали, что спецификой плохоформализуемых и слабоструктурированных

ЗПР является их комбинаторность, т. е. быстрый (лавинообразный) рост

решающих деревьев в процессе поиска. В [80] исследована проблема

построения оптимальных решающих деревьев для семи критериев опти-

мальности (среди них: общее число вершин дерева, число конечных

вершин, число пустых, или тупиковых, конечных вершин и др.), часто

употребляемых при решении прикладных задач с помощью экспертных

систем. Доказано (путем сведения к известной NP-полной задаче), что за-

дача построения решающего дерева, оптимального по любому из данных

критериев, является NP-полной.

Поэтому основой решения таких задач являются эвристические ме-

тоды, базирующиеся на учете специфики ПО, знаниях и опыте специали-

стов,

решающих подобные задачи, а ЗПР, сформулированная как поиск

в пространстве состояний, называется часто задачей эвристического по-

иска [81]. «Эвристичность» данной задачи состоит также и в том, что

в общем случае не определена стратегия поиска применимых к текуще-

му состоянию правил преобразований (по «умолчанию» предполагается

последовательный перебор правил), а также стратегия «разрешения кон-

фликта» при одновременной применимости нескольких правил.

Мы привели традиционную постановку ЗПР, соответствующую слу-

чаю,

когда явно заданы начальное и конечное состояния или подмно-

жества таких состояний, и требуется найти последовательность правил

п^)еобразований (возможно не единственную), дающую конечное состоя-

ние и удовлетворяющую критериям из множества Q (если Q определено).

Такая постановка свойственна задачам планирования, мониторинга, упра-

вления. При поиске решения могут использоваться стратегии прямого

(от начального состояния к конечному), обратного (от конечного состо-

яния к начальному) или комбинированного двунаправленного поиска.

Назовем данную постановку подходом 1.

Для рассматриваемого нами класса ЗПР возможна и другая поста-

новка (подход 2), используемая в случае, когда конечное состояние или

подмножество таких состояний 5к задаются неявно посредством следую-

щих требований:

а) найти все состояния (если число их конечно) и соответствующие

последовательности правил преобразований, их порождающие, которые

могут быть получены из заданного начального состояния или подмно-

жества таких состояний 5н посредством конечного множества гфавил

преобразований Р; искомое множество и будет результирующим множе-

ством S^;

б) найти хотя бы одно состояние и соответствующую последователь-

ность правил преобразований, которое может быть получено из заданного

начального состояния или подмножества 5„ посредством конечного мно-

жества правил Р;

в) и г) — являются частными случаями а и б, когда глубина по-

иска ограничивается некоторым заданным числом m (соответствующее

решающее дерево ограничивается т уровнями).

78 Глава 3. Методы поиска решений для динамических баз знаний

Данная постановка свойственна задачам прогнозирования или функ-

ционирования СППР в режиме «что будет, если задано такое-то начальное

состояние». При поиске решения используется стратегия прямого поис-

ка. Множество Q при поиске не используется. Применение критериев

возможно лишь на последующем этапе выбора из множества полученных

состояний 5к (при условии его конечности).

В рамках обоих подходов возможна также постановка вопроса о су-

шествовании и единственности решения 3I1P.

Исследуя процесс поиска решения как процесс вывода в неко-

торой формальной системе, мы установи.м, что для подхода 1, если

ЗПР имеет решение (т. е. конечное состояние выводимо из некоторо-

го начального состояния или подмножества состояш/ш S„ посредством

правил из Р), то всегда можно построить алгоритм поиска решения.

Для подхода 2 будет установлена недостаточность использования детер-

минированных алгоритмических схем с присущей им предписывающей

модальностью. Данному подходу более свойственны схемы с недетерми-

низмом, использующие модальность возможности (разрешения). Такие

схемы тоже будут рассмотрены.

Поиск решения ЗПР усложняется наличием неполноты и неопреде-

ленности как в описании состояний, так и в самих правилах преобразо-

ваний. Этот фактор также будет учитываться.

Отметим, что после или даже в процессе построения решающего

дерева может возникнуть и обратная задача — найти все (или хотя бы

одно) состояния и соответствующую последовательность правил преобра-

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

Такая постановка свойственна задаче диагностики или функционирова-

нию СППР в режиме выяснения причины (режиме объяснения) того,

откуда и каким образом произошел переход в данное состояние. Для

решения этой задачи используется стратегия обратного поиска, т. е.

просмотр решающего дерева производится в порядке, обратном его по-

строению. Если решена прямая задача и построено соответствующее

решающее дерево, то решение обратной задачи в общем затруднений

не вызывает. Но для динамических ПО (ЗПР в открытой форме), при

наличии факторов неполноты и неопределенности и жестких временных

ограничениях решение и этой задачи становится серьезной проблемой.

Рис.

3.1 иллюстрирует возможные ситуации поиска решения ЗПР.

Отметим, что рассматриваемые нами ЗПР имеют содержательную ин-

терпретацию, в том смысле, что они порождены реальными проблем-

ными областями, в которых действует ЛПР. Поэтому все составляющие

набора (3.1) будем понимать как конструктивные объекты, представляе-

мые (описьщае.мые) конечными (квазиконечными) конфигурациями букв

(знаков, символов) из некоторого конечного алфавита. Известно, что

множество конструктивных объектов рекурсивно перечислимо, если

определена процедура последовательного порождения элементов этого

множества [75].

Далее объектом исследования будет ЗПР (соответственно МПР)

в открытой форме, свойственная открытым и динамическим ПО. При

3.2. Формализация поиска решения

ЗПР.

S", Sh, Sk,

Р,

Нет

решения

Р не применимо к Sh

Поиск бесконечен

PeuieiiHe

существует

Подход

Известны Sb, Sk

Поиск оптимального или допустимого

относи1ельно решения.

Поиск реп1е1шя обратной задачи

Подход 2. Известно Sh

Нахождение Sk

Всех решишй

Всех решений с

ограничением глубины

поиска

Одного (любого) репюния

Одного (любого) решения с

ограничением глубины

поиска

Решение вопроса о существовании и единственности

решения

Рис.

3.1

поиске решения предполагается возможность пополнения и коррек-

ции начального множества преобразований Р, что может повлечь также

изменение (расширение) множеств состояний S и S". Причем пополне-

ние множества Р будет производиться в ситуациях, когда ЗПР в исходной

постановке не имеет решения (Р неприменимо к начальному состоянию

80 Глава 3. Методы поиска решений для динамических баз знаний

или поиск обрывается, не достигнув состояния из S^), до тех пор, по-

ка за счет расширения множества Р не будет получено решение. Это

окажется возможным (т. е. решение будет найдено за конечное число

шагов), если в процессе расширения будет получено множество правил

преобразований, для которого искомое решение существует, или, иначе

говоря, синтезирована адекватная ПО (семантически корректная) МПР.

Рассматривая механизмы поиска решения, будем пытаться исполь-

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

числа шагов получения результата в случае его существования. В [64] рас-

смотрена возможность представления (программирования) неформаль-

ных процедур, используя концепцию трансфинитной (нефинитной) фор-

мальной системы, отличающейся от финитной тем, что в ней допустимы

правила преобразований с бесконечным числом посылок, и, следователь-

но,

допустимы бесконечные (трансфинитные) выводы Однако при этом

на решающее дерево накладывается требование фундированности [75],

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

исходить как конечное, так и бесконечное число вершин, но число шагов

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

сти решающих деревьев в определенном смысле соответствует свойству

нетеровости или конечной остановочности систем подстановок (пере-

писывания) термов (term rewriting systems) [126] и позволяет получить

решение лри его существовании за конечное число шагов.

В [25] вводятся так называемые системы алфавитных операторов,

допускающие бесконечные начальные слова (входную информацию),

бесконечные множества правил преобразований и бесконечность про-

цедуры вывода. Доказано, что класс алфавитных операторов является

более мош(ным, чем класс обычных алгоритмов, но при этом исполь-

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

хаусдорфовые топологии на множествах слов и предельные переходы.

Рассмотрение подобных неконструктивных объектов, несомненно важ-

ное в плане дальнейшей интеллектуализации компьютеров и расширения

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

Для задания множества правил преобразований, или, применительно

к СППР, модели принятия решений, будем использовать продукционные

системы.

3.2.3.

Продукционная система как средство уточнения

интуитивного понятия алгоритма и представления знаний

Интуитивного понятия алгоритма как вычислительного процесса

чисто механического характера, позволяющего вычислить по опреде-

ленным правилам и инструкциям искомую величину последовательно

из заданных исходных величин и обладающего свойствами дискретности,

детерминированности, элементарности шагов, направленности и мас-

совости [63, 71], оказалось недостаточно для решения ряда проблем,

в частности, доказательства существования алгоритмически неразреши-

мых проблем. Требовалось точное определение пон5ГГИя алгоритма.

Уточнение интуитивного понятия алгоритма происходило по двум

направлениям [71]: