Главная Контакты Добавить в избранное Авторы Вопросы и ответы
,

УДК 681.32

ФОРМАЛЬНАЯ МОДЕЛЬ ГИБРИДНОЙ СЦЕНАРНО-ПРЕЦЕДЕНТНОЙ СППР

Шерстюк В.Г.

CBR (Case-Based Reasoning), или метод рассуждения на основе прецедентов, является одним из интенсивно развиваемых направлений в исследованиях по искусственному интеллекту. По определению Р. Шенка [1] «CBR – способ решения новых проблем путем адаптации решений, которые использовались ранее в аналогичных ситуациях».

Прецедент включает проблемную ситуацию и ее решение (рис. 1).

Рис. 1 Принятие решений на основе прецедента

Как только будет выявлена проблемная ситуация и будет принято решение на основе уже имеющихся (хранимых) прецедентов, соответствующая информация упаковывается в контейнер, называемый прецедентом и сохраняется в хранилище прецедентов, в качестве которого могут использоваться традиционные средства СУБД, специализированные серверы баз знаний, многомерные базы данных и т.д., для последующего использования. Ситуация, для которой был сохранен прецедент, считается опорной, или базовой [2].

Выбор наиболее подходящего в конкретной ситуации прецедента позволяет сформировать на его основе решение в готовом виде, либо требует проведения дополнительных действий по адаптации решения с целью учета различий в контекстах сложившейся и базовой ситуации.

Если подходящий прецедент не обнаружен или процесс адаптации требует привлечения дополнительной информации, принятие решения потребует обращения к базе знаний, содержащей основные сведения о предметной области. Общие (domain knowledge) знания о предметной области являются вспомогательными, и могут представляться при помощи продукционных правил, фреймов или семантических сетей.

Метод, с помощью которого будет осуществляться вычисление меры подобия (сходства) прецедентов, задается во время создания CBR-системы разработчиками. Наиболее популярным и часто используемым методом является поиск ближайшего соседа, в основе которого лежит способ измерения степени совпадения значений атрибутов (свойств), определяющих прецедент.

Типовой прецедент представляет собой структуру, состоящую из: описания проблемы, характеризующего сложившуюся ситуацию на момент активизации прецедента, и решения, содержащего список возможных вариантов принятия решений, связанных с данной проблемой, а также описание ситуации, которая (возможно) будет иметь место после выбора прецедента. Процесс функционирования прецедентных СППР обычно представляется в виде так называемого CBR-цикла (рис. 2), состоящего из четырех основных фаз [3]:

1) получение (выбор) из хранилища наиболее уместного прецедента или множества прецедентов, обычно на основе заданного отношения подобия;

2) использование выбранных прецедентов для принятия решения поставленной задачи;

3) пересмотр и коррекция (адаптация) в случае необходимости принимавшихся ранее в выбранных прецедентах решений;

4) сохранение в хранилище принятого решения и сложившейся ситуации в качестве нового прецедента или соответствующее изменение выбранного прецедента, что может быть полезным в дальнейшем при решении аналогичных задач.

Рис. 2 Фазы CBR-цикла

Обычно CBR-цикл выполняется при непосредственном взаимодействии с ЛПР. Многие прецедентные системы только извлекают из хранилища наиболее уместные прецеденты и оставляют процесс адаптации на усмотрение ЛПР, поскольку автоматизация процесса адаптации является сложной задачей и практически не поддается обобщению, а зачастую в адаптации нет необходимости, поскольку выбранные прецеденты содержат достаточно информации для принятия решения.

Если же адаптация необходима, для ее проведения можно использовать базу знаний предметной области, содержащую набор необходимых фактов и правил, и методы индуктивного и(или) абдуктивного машинного обучения.

Основным достоинством CBR-систем является их простота и легкость реализации, что делает прецедентные системы хорошим средством для представления знаний и поддержки принятия решений, однако и прецедентным системам присущи недостатки.

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

1) сложность учета динамических факторов;

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

3) затруднительность учета ограничений по принятию решений, задаваемых множеством целевых факторов, а не состояний.

Традиционно указанные недостатки преодолевают или ослабляют, разрабатывая гибридные системы [4], когда объединяют механизм принятия решений на основе прецедентов с механизмом, основанным на правилах или ограничениях, что в свою очередь усложняет СППР.

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

Целью статьи является формирование подхода и теоретических основ создания гибридных прецедентных систем.

Для этого необходимо построить формальную модель гибридной сценарно-прецедентной СППР.

Представим формальную модель следующим образом.

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

Определение 1. Состояние системы  определяется как совокупность значений параметров (факторов) .

Обозначим множество возможных состояний системы (конечное или бесконечное) как . Тогда некоторое состояние системы можно охарактеризовать как:

 

,

(1)

 

где   – множество выполнимых действий (процедур);

        – множество объектов;

        – множество свойств объектов;

        – множество отношений между объектами.

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

Графическая интерпретация понятия состояния представлена на рис. 3.

Рис. 3 Состояния системы

Определение 2. Ситуация  есть оценка совокупности значений параметров системы и связей между ними в заданный момент времени : , где  – оценка состояния системы (значений параметров) в момент времени ,  – множество известных на момент времени  связей между факторами, .

Совокупное множество ситуаций определятся как . Существование в системе ситуации  определяется истинностным значением выражения si=Ø, .

Связи между факторами могут быть постоянными и причинно-следственными отношениями, зависящими от произошедших событий и протекающих процессов.

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

Допустим, у нас имеется:

- множество сортов переменных (тип есть множество заданных сортов);

- множество заданных констант;

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

- связки  (не),  (и),  (или).

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

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

Для корректной связи между когнитивной моделью ситуации и ее описанием в качестве предиката необходимо разделить множество предикатных символов на непересекающиеся подмножества входных факторов  и целевых факторов : .

Пусть атомарная формула имеет вид , где  – константа, литерал является атомарной формулой или ее отрицанием.

Формула строится из атомарных формул с использованием связок не, и, или.

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

Можно выделить два важных свойства ситуаций: множественность и неоднородность исходных данных. Важно отметить, что ситуация всегда представляет собой некую оценку (анализ, обобщение) множества данных, более того, эта оценка является субъективной, т.к. зависит от средств и методов обобщения конкретного ЛПР.

Определение 3. Обобщенное описание (отображение) системы с помощью ситуаций называется ситуационной моделью : .

Пусть  – пространство возможных ситуаций,  – пространство возможных решений.

Определение 4. Прецедент  есть пара , состоящая из ситуации  и связанного с ней решения .

Ситуация  задается с помощью множества формул языка .

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

Данные в СППР представлены множеством прецедентов :

 

(2)

Каждый прецедент  может рассматриваться как условная импликация вида

 

,

(3)

 

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

Более того, чем ближе ситуация  к ситуации , тем правдоподобнее, что  является решением для  [6].

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

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

Определение 5. Прецедентная система представляет собой структуру , где  – хранилище прецедентов,  – мера подобия, заданная на множестве интерпретаций  языка , описывающего входные ситуации,  – множество формул языка .

Множество формул  составляет базу знаний о предметной области, полученную экспертным путем или с помощью методов машинного обучения.

Для каждого прецедента  можно с помощью оценки подобия вычислить степень уместности решения  в ситуации, близкой к . В случае, если для этого можно также использовать имеющиеся знания о предметной области, можно утверждать, что формула

 

(4)

 

выполнима для класса ситуаций .

Хранилище прецедентов  задает экстраполяцию отношения импликации для (3), и фактически является базой знаний, содержащей приближенные импликации: . Соответственно формула

 

(5)

 

также выполнима для класса ситуаций .

Таким образом можно сказать, что прецедентная система выполняет функцию вывода по аналогии:

 

.

(6)

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

Под возможным планом будем понимать частично упорядоченную последовательность действий, направленную на достижение целевого состояния системы из некоторого заданного начального состояния [7].

Возможный план становится планом действий в результате принятия решения ЛПР. 

План действий с точки зрения прецедентного принятия решений должен включать описание списка граничных условий, целей и способов их достижения (рис. 4). Список граничных условий (список ограничений) определяет множество критических параметров системы.

Цель представляет собой желательное (целевое) состояние, которое должна достигнуть система в результате выполнения данного плана.

Список ограничений определяет начальные условия выполнения плана (предусловия выполнения), цель характеризует результат выполнения плана (постусловия).

Рис. 4 Представление плана действий

Таким образом, план действий должен состоять из тела плана, содержащего информацию о порядке его реализации, и дескриптора плана, характеризующего пред- и постусловия его выполнения.

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

Элементарным фрагментом тела плана является действие , где  – множество допустимых действий. Выполнение действия  представляет собой шаг плана и обозначается .

Тогда тело плана может быть представлено следующим образом:

.

(7)

 

Определение 6. Дескриптор плана  есть бинарное отношение вида , для которого выполняется ограничение: если , тогда .

Определение 7. Дескриптор предусловия  определяет множество ситуаций , в которых допустимо выполнение тела плана , т.е. является предусловием осуществления .

Определение 8. Дескриптор постусловия  определяет множество ситуаций , которые могут возникнуть в результате выполнения тела плана , т.е. является постусловием для .

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

Определение 9. План есть пара , , множество возможных планов есть .

Если – некоторый план, то – тело плана, – дескриптор плана, дескриптор предусловий, дескриптор постусловий.

Если , то представляет образ в , т.е.

 

.

(8)

 

Определение 10. План является релевантным [8] ситуации , если его тело начинает выполняться из ситуации , такой, что и заканчивается в некоторой ситуации , при этом .

Определение 11. Ограниченный путь (ограниченный локальный курс событий) есть временная последовательность , такая что , .

Определение 12. Полный путь  есть временная последовательность , при этом .

Если – некоторый путь и , то . Совокупное множество путей обозначим .

Процесс выполнения некоторого плана обозначим как . Тело плана выполняется на пути , ограниченном временным интервалом .

Определение 13. План является выполнимым, если выполняются следующие условия:

1) ,   ;

2),

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

Сценарий  рассматривается как кортеж, состоящий из актуального состояния системы (ситуации), целевого состояния системы (и/или значений целевых факторов) и множества планов достижения целевого состояния. Для каждого плана может быть также представлена оценка возможности его выполнения:

 

,

(9)

 

где  – исходная ситуация;

        – план;

        – конечная (целевая) ситуация в случае выполнения плана ;

       – оценка возможности достижения целевой ситуации  при выполнении плана .  

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

Таким образом, прецедентная система является «преобразователем» актуальной ситуации в сценарий решения (рис. 5), а сценарий является траекторией продвижения к необходимому и возможному будущему состоянию системы. Отличительной особенностью сценария является его многовариантность т.е. допустимость рассмотрения нескольких альтернативных вариантов развития ситуации, а соответственно и нескольких целевых состояний.

Группировка сценариев в классы даст возможность выбора наиболее рациональной стратегии воздействия на ситуацию. Получение широкого спектра вариантов развития ситуации позволяет выявить критические ситуации для принятия решений, а также возможные последствия предлагаемых альтернативных вариантов решений с целью их сопоставления и выбора наиболее эффективного.

 

Рис. 5 Схема функционирования СППР

Выводы. В результате исследования на основе комбинации сценарного и прецедентного подходов, известных из ряда работ в области искусственного интеллекта, построена формальная модель нового класса интеллектуальных систем поддержки принятия решений – сценарно-прецедентных СППР. Полученная гибридная модель дает возможность разработки интеллектуальных систем, пригодных длля работы в условиях неполноты и неопределенности информации в сложных динамичных предметных областях. Дальнейшим развитием модели может являться включение эпизодов (или элементарных последовательностей событий), обработка которых может быть выполнена с применением методов извлечения знаний.

 

The theoretical basis of a combination script and case approaches in the formal model of a new class of intelligent decision support systems – script-case system is constructed in this paper. The received hybrid model enables development of intelligent systems, suitable for works in conditions of incompleteness and uncertainty of the information in complex dynamical domains.

 

1. Джексон П. Введение в экспертные системы. – М. – Вильямс. – 2001. – 624 с.

2. Нечипоренко О.А. Использование технологии Case-Based Reasoning в проектировании программных систем // Перспективные информационные технологии и информационные среды. – Таганрог. – 2002. – № 3. – с. 27-32.

3. Aamodt A., Plaza E. Case-Based Reasoning: foundational issues, methodological variations, and system approaches // AI Communications. – 1994. – Vol. 7. – №1. – pp. 39-59.

4. Main J., Dillon T.S. A hybrid case-based reasoner for footwear design // Case-Based Reasoning Research and Development. – Lecture Notes in Artificial Intelligence. – 1999. – Vol. 1650. – pp. 499-509.

5. Plaza E., Esteva F., Garcia P., Godo L., Lopez de Mantaraz R. A logical approach to case-based reasoning using fuzzy similarity relations // Information Sciences. – 1997. – Vol. 106. –№1-2. – pp. 105-122.

6. Dubois D., Esteva F., Garcia P., Godo L., Lopez de Mantaras R., Prade H. Case-Based Reasoning: A Fuzzy Approach. – Lecture Notes in Computer Science. – Springer. – 1999. – vol. 1566. –  pp. 79–91.

7. Гладун В.П. Планирование решений. –К.: Наукова думка. – 1987. – 168 с.

8. Ходаков В.Е., Шерстюк В.Г., Степанский К.Г., Дидык А.А., Мартынов А.Н. Методы оценки релевантности информационных структур в базах знаний // Проблемы бионики. – Харьков. – 1998. – вып. 49. – с. 186-195.

 





Ответы на вопросы [_Задать вопроос_]

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

Теленик С.Ф., Ролік О.І., Букасов М.М., Андросов С.А. Генетичні алгоритми вирішення задач управління ресурсами і навантаженням центрів оброблення даних

Богушевский В.С., Сухенко В.Ю., Сергеева Е.А., Жук С.В. Реализация модели управления конвертерной плавкой в системе принятия решений

Бень А.П., Терещенкова О.В. Применение комбинированных сетевых методов планирования в судоремонтной отрасли

Цмоць І. Г., Демида Б.А., Подольський М.Р. Методи проектування спеціалізованих комп’ютерних систем управління та обробки сигналів у реально-му час

Теленик С.Ф., РолікО.І., Букасов М.М., РимарР.В., Ролік К.О. Управління навантаженням і ресурсами центрів оброблення даних при виділених серверах

Селякова С. М. Структура інтелектуальної системи управління збиральною кампанією

Еременко А.П., Передерий В.И. Принятие решений в автоматизированных системах с учетом психофункциональных характеристик оператора на основе генетических алгоритмов

Львов М.С. Алгоритм перевірки правильності границь змінення змінних у послідовних програмах

Ляшенко Е.Н. Анализ пожарной опасности сосновых насаждений в зоне Нижне-днепровских песков – самой большой пустыни в Европе

Кучеров Д.П., Копылова З.Н. Принципы построения интеллектуального автору-левого

Касаткина Н.В., Танянский С.С., Филатов В.А. Методы хранения и обработки нечетких данных в среде реляционных систем

Ходаков В.Е., Жарикова М.В., Ляшенко Е.Н. Применение когнитивного подхода для решения задачи поддержки принятия управленческих решений при ликвидации лесных пожаров

Гончаренко А.В. Моделювання впливу ентропії суб’єктивних переваг на прийняття рішень стосовно ремонту суднової енергетичної установки

Фарионова Н.А. Системный подход построения алгоритмов и моделей систем поддержки принятия решений при возникновении нештатных ситуаций

Биленко М.С., Серов А.В., Рожков С.А., Буглов О.А. Многоканальная система контроля качества текстильных материалов

Мотылев K.И., Михайлов M.В., Паслен В.В. Обработка избыточной траекторной информации в измерительно-вычислительных системах

Гончаренко А.В. Вплив суб’єктивних переваг на показники роботи суднової енергетичної установки

Гульовата Х.Г., Цмоць І.Г., Пелешко Д.Д. Архітектура автоматизованої системи моніторингу і дослідження характеристик мінеральних вод

Соломаха А.В. Разработка метода упреждающей компенсации искажений статорного напряжения ад, вносимых выходными силовыми фильтрами

ПотапенкоЕ.М., Казурова А.Е. Высокоточное управление упругой электромеханической системой с нелинейным трением.

Кузьменко А.С., Коломіц Г.В., Сушенцев О.О. Результати розробки методу еквівалентування функціональних особливостей fuzzy-контролерів

Кравчук А. Ф., Ладанюк А.П., Прокопенко Ю.В. Алгоритм ситуационного управления процессом кристаллизации сахара в вакуум-аппарате периодического действия с механическим циркулятором

Абрамов Г.С., Иванов П.И., Купавский И.С., Павленко И.Г. Разработка навигационного комплекса для автоматического наведения на цель системы груз-управляемый парашют

Литвиненко В.И., Четырин С.П. Компенсация ошибок оператора в контуре управления следящей системы на основе синтезируемых вейвелет-сетей

Бардачев Ю.Н., Дидык А.А. Использование положений теории опасности в искусственных иммунных системах

Рожков С.О., Кузьміна Т.О., Валько П.М. Інформаційна база як основа для створення асортименту лляних виробів.

Ускач А.Ф., Становский А.Л., Носов П.С. Разработка модели автоматизированной системы управления учебным процессом

Мазурок Т.Л., Тодорцев Ю.К. Актуальные направления интеллектуализации системы управления процессом обучения.

Ускач А.Ф., Гогунский В.Д., Яковенко А.Е. Модели задачи распределения в теории расписания.

Сідлецький В.М., Ельперін І.В., Ладанюк А.П. Розробка алгоритмів підсистеми підтримки прийняття рішень для контролю якості роботи дифузійного відділення.

Пономаренко Л.А., Меликов А.З., Нагиев Ф.Н. Анализ системы обслуживания с различными уровнями пространственных и временных приоритетов.

Коршевнюк Л.О. Застосування комітетами експертів системи нечіткого логічного виводу із зваженою істинністю.. – С. 73 – 79.

Кирюшатова Т.Г., Григорова А.А Влияние направленности отдельных операторов и направленности всей группы на конечный результат выполнения поставленной задачи.

Петрушенко А.М., Хохлов В.А., Петрушенко І.А. Про підключення до мови САА/Д деяких засобів паралельного програмування пакету МРІСН.

Ходаков В.Е., Граб М.В., Ляшенко Е.Н. Структура и принципы функционирования системы поддержки принятия решений при ликвидации лесных пожаров на базе новых геоинформационных технологий.

Сидорук М.В., Сидорук В.В. Информационные системы управления корпорацией в решении задач разработки бюджета.

Нагорный Ю.И. Решение задачи автоматизированного расчета надежности иасуп с использованием модифицированного метода вероятностной логики

Козак Ю.А. Колчин Р.В. Модель информационного обмена в автоматизированной системе управления запасами материальных ресурсов в двухуровневой логистической системе

Гожий А.П., Коваленко И.И. Системные технологии генерации и анализа сценариев

Вайсман В.А., Гогунский В.Д., Руденко С.В. Формирование структур организационного управления проектами

Бараненко Р.В., Шаганян С.М., Дячук М.В. Аналіз алгоритмів взаємних виключень критичних інтервалів процесів у розподілених системах

Бабенко Н.И., Бабичев С.А. Яблуновская Ю.А. Автоматизированная информационная система управления учебным заведением

Яковенко А.Е. Проектирование автоматизированных систем принятия решений в условиях адаптивного обучения с учетом требований болонского процесса

Бараненко Р.В Лінеаризація шкали і збільшення діапазону вимірювання ємностей резонансних вимірювачів

Головащенко Н.В. Математичні характеристики шумоподібно кодованих сиг-налів.

Шекета В.І. Застосування процедури Append при аналізі абстрактних типів даних модифікаційних запитів.

Цмоць І.Г. Алгоритми та матричні НВІС-структури пристроїв ділення для комп'-ютерних систем реального часу.

Кухаренко С.В., Балтовский А.А. Решение задачи календарного планирования с использованием эвристических алгоритмов.

Бараненко Р.В., Козел В.Н., Дроздова Е.А., Плотников А.О. Оптимизация рабо-ты корпоративных компьютерных сетей.

Нестеренко С.А., Бадр Яароб, Шапорин Р.О. Метод расчета сетевых транзакций абонентов локальных компьютерных сетей.

Григорова А.А., Чёрный С. Г. Формирование современной информационно-аналитической системы для поддержки принятия решений.

Шаганян С.Н., Бараненко Р.В. Реализация взаимных исключений критических интервалов как одного из видов синхронизации доступа процессов к ресурсам в ЭВМ

Орлов В.В. Оценка мощности случайного сигнала на основе корреляционной пространственной обработки

Коджа Т.И., Гогунский В.Д. Эффективность применения методов нечеткой логики в тестировании.

Головащенко Н.В., Боярчук В.П. Аппаратурный состав для улучшения свойств трактов приёма – передачи информации в системах промышленной автоматики.