автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Интеллектуальная система поддержки принятия решений на основе рассуждений по прецедентам

КАПЫШ АЛЕКСАНДР СЕРГЕЕВИЧ

На правах рукописи

/г

ИНТЕЛЛЕКТУАЛЬНАЯ СИСТЕМА ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ НА ОСНОВЕ РАССУЖДЕНИЙ ПО ПРЕЦЕДЕНТАМ (НА ПРИМЕРЕ ЗАДАЧИ УПРАВЛЕНИЯ ВОДОХОЗЯЙСТВЕННОЙ СИСТЕМОЙ)

05.13.01 - Системный анализ, управление и обработка информации (промышленность)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 9 МАЙ 2011

Волгоград - 2011

4846857

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

Научный руководитель:

доктор технических наук, профессор Дворянкин Александр Михайлович.

Официальные оппоненты:

доктор технических наук, профессор Лобейко Владимир Иванович.

доктор технических наук, профессор Заболеева-Зотова Алла Викторовна.

Ведущая организация

Астраханский государственный технический университет.

Защита состоится « 7 » июня 2011 года в 15-00 на заседании диссертационного совета Д 212.028.04 при Волгоградском государственном техническом университете по адресу: 400131, г. Волгоград, проспект Ленина 28.

С диссертацией можно ознакомиться в библиотеке Волгоградского государственного технического университета.

Автореферат разослан « <5"» мая 2011 года. Ученый секретарь

диссертационного совета

Водопьянов В. И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

рассуждений на знаниях внесли Д.А. Поспелов, В.Н. Вагин, В,М. Курейчик, Г.С. Осипов, A.A. Зенкин, Г.Д. Волкова, И.Ю. Петрова, П. Уинстон, П. Джексон, Дж. МакКарти.

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

Исследование существующих средств поддержки процесса принятия решения, в том числе в сфере экологии, на примере работ Варшавского, Сараева, Бергмана (Bergmann), Альтхоффа (Althoff), Ванга (Wang), Жанга (Zhuang), Кек-карони (Ceccaroni) показало, что существующие модели и алгоритмы не могут быть применены для поддержки рассматриваемого класса задач принятия решений, так как не учитывают их специфические свойства: наличие нескольких заинтересованных субъектов; невозможность оценить последствия принимаемых решений; описание задачи управления содержит множество качественных и количественных параметров; на разных этапах решения задачи управления эксперты используют разные типы знаний.

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

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

Для достижения данной цели были поставлены и решены следующие задачи:

I. Исследовать процесс решения многокритериальной задачи принятия решения в условиях неопределенности на примере задачи управления водохозяй-

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

2. Разработать подход к поддержке задачи принятия решения с использованием рассуждений по прецедентам, рассуждений по правилам и качественных рассуждений. Сформулировать требования к способу представления экспертных знаний, используемых в процессе поддержки принятия решения;

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

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

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

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

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

2. на основе предложенного подхода разработаны алгоритмы решения задачи принятия решения:

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

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

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

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

2. Алгоритм поиска прецедентов с использованием критерия эффективности и модели представления прецедента в виде онтологии;

3. Алгоритм адаптации прецедентов с использованием экспертных правил и вьюода по ним на онтологии;

4. Алгоритм оценки прецедентов с использованием качественной модели поведения объекта.

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

Работа была выполнена при поддержке грантов РФФИ (проект 05-08-17930-а, 2006-2008 гг.), а также совместного гранта Министерства образования и науки РФ и DAAD «Михаил Ломоносов II» с прохождением стажировки в университете г. Ганновер, Германия в 2008-2009 гг.

Предложенные модели и алгоритмы реализованы в виде автоматизированной системы интеллектуальной поддержки принятия решений при управлении водохозяйственной системой реки Эльба в границах национального заповедника земли Саксония-Ангальт. Создана тестовая база знаний. Проверена работоспособность автоматизированной системы при управлении водохозяйственной системой; проведена оценка эффективности предлагаемых алгоритмов.

На разработанную автоматизированную систему и базу знаний были получены свидетельства о регистрации в РосПатенте № 2010620572, № 2010620562, № 2010613010, № 2010613007.

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

Апробация работы. Основные результаты работы докладывались и обсуждались на: XXXIII международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе IT+SE'2006», Гурзуф, Украина, 2006, международном симпозиуме "Methods of Artificial Intelligence AI-METH 2007", Gliwice, Польша, 2007, XXXIV международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе IT+SE'2008», Гурзуф, Украина, 2008, практическом семинаре RAMWASS,

Ганновер, Германия, 2009, конференции «Информационные технологии в образовании, технике и медицине», Волгоград, 2009.

Публикации. По теме диссертации опубликовано 8 печатных работ, в том числе 4 публикаций в изданиях из перечня ведущих научных журналов ВАК, 1 статья в международном журнале, 3 тезиса докладов на конференциях, получено 4 свидетельства о государственной регистрации программ ЭВМ.

Структура и содержание диссертациоииой работы. Диссертационная работа состоит из введения, четырех глав, заключения, 3-х приложений и списка литературы. Общий объем диссертации 168 страниц, в том числе 20 рисунков, 18 таблиц, список литературы из 134 наименований.

Автор выражает глубокую благодарность проф. П. Вриггерсу и к.т.н. Кульцовой М. Б. за консультации по вопросам рассуждений по прецедентам; к.т.н. Жуковой И.Г. - за консультации по вопросам моделей и методов качественных рассуждений; д.е.н. Т. Кайнебургу за консультацию по вопросам системы управления водохозяйственной системой реки Эльба.

СОДЕРЖАНИЕ РАБОТЫ

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

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

По результатам анализа существующего бизнес-процесса, сформулирована задача принятия решения (ЗПР), решаемая в процессе управления:

ЗПР = <ОС, А, КМ,Р,П>, (1)

где ОС - описание ситуации принятия решения, состоящее из множества численных и качественных параметров: ОС = {Рць Рд2, ..., Рпь Рп2, ...}, А -множество альтернатив, каждая из которых состоит из множества управляющих воздействий: А,■ = {Аси Ас2, ...}, К - множество критериев, в виде качественных оценок ситуации с точки зрения хозяйствующих субъектов, М - модель, позволяющая для каждой альтернативы рассчитать вектор критериев; Р -

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

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

На основании изучения процесса принятия решения (ППР), а также аналогичных работ, выполненных в области экологии, проектирования ПО и автоматических систем, включая работы Варшавского, Сараева, Бергмана (Bergmann), Альтхоффа (Althoff), Филлипс-Рена (Phillips-Wren) и Ванга (Wang) были выделены основные этапы ППР, определены входные и выходные данные каждого этапа, а также модели и методы искусственного интеллекта (ИИ), используемые экспертами на каждом из этапов. Характеристики выделенных этапов ППР приведены в таблице 1, схема исследованного ППР приведена на рисунке 1.

Таблица 1. Анализ основных этапов ППР

Этапы ППР Входные данные Выходные данные Модели и методы, используемые экспертами

Формулировка задачи, критериев к целей Описание задачи принятия решений Описание ситуации, критерии, цели Метод экспертных оценок, методы построения дерева целей

Разработка и оценка альтернатив Описание задачи принятия решений Список альтернатив Метод экспертных оценок

Выбор оптимального решения и его согласование Цели, критерии, альтернативы Выбранная альтернатива Рассуждения по прецедентам, рассуждения по правилам

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

1 - Постановка ЗПР 4 - Выбранная альтернатива

2 - Описание ситуации, критерии, цели 5 - Изменение начальной ситуации

3 - Множество альтернатив б - Оценка решения ЗПР

Рисунок 1 - Схема исследованного ППР

Анализ текущего ППР, показывает, что основные знания, используемые экспертами, представлены в неявном виде как предыдущий опыт решения похожих задач, в то время как экспертные правила и качественные зависимости

используются для адаптации предыдущего решения к текущей ситуации и оценки эффективности предлагаемого решения. Таким образом, рассуждения по прецедентам (РПП) были выбраны в качестве основной технологии ИИ, используемой при интеллектуальной поддержке решения ЗПР. Анализ существующих моделей и алгоритмов РГТП на примере таких СППР, как DIAL, CCAR, SHYSTER-MYCIN, CASE-PARTNER и др. показал, что они не учитывают особенностей предметной области и имеют следующие недостатки:

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

2. отсутствует механизм оценки эффективности альтернативы с учетом множества неравнозначных критериев;

3. отсутствует механизм учета взаимного влияния компонент альтернативы (управляющих воздействий) друг на друга;

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

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

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

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

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

Существующие подходы к интеграции различных механизмов рассуждения, рассмотренные на примере работ Кинли (Kinley), Чена (Chan), Шойнауэра (Schoenauer) не позволяют использовать качественные рассуждения в силу накладываемых ограничений на модель представления прецедента. Поэтому была разработана новая схема интеграции РПП, рассуждений по правилам и качественных рассуждений на основе OWL-DL онтологии. На основе анализа форма-

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

Таблица 2. Знания, используемые на этапах РПП

Этап Тип используемых знаний Задачи

Формирование прецедента Продукционные правила Доопределение прецедента, определение неверных входных данных

Адаптация прецедентов Продукционные правила, качественные зависимости Адаптация элементов решения прецедента, генерация элементов решения

Оценка прецедентов Качественные зависимости, продукционные правила Проверка удовлетворения решения начальным ограничениям, оценка эффективности предлагаемого решения

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

В качестве модели представления знаний в предметной области была выбрана онтология OWL-DL, что позволяет задать сложную структуру прецедента, включающую данные разных типов, а также интегрировать экспертные правила и качественные рассуждения в процесс РПП с помощью правил описательной логики (ОЛ). При этом, комплексная модель прецедента представляется в виде совокупности классов, их экземпляров и отношений между ними, а вывод на продукционных правилах выполняется как операция «классификация таксономии» (taxonomy classification). Существует несколько способов использования онтологии в рамках процесса РПП. В работе предложено использование онтологии не только как средства описания модели прецедента и знаний в предметной области, но и как хранилища прецедентов, что позволяет обойтись без использования дополнительных средств для представления и хранения прецедентов.

Для описания прецедента ЗПР была предложена расширенная модель представления прецедента, включающая следующие компоненты:

- описание ситуации принятия решения;

- описание аспектов задачи принятия решения;

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

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

- оценка начальной и конечной ситуации с точки зрения различных аспектов;

- предпочтения ЛПР по отношению к различным аспектам.

С = {DI, Pref, Sol, DR.}, (2)

где С - прецедент, DI - описание начальной ситуации задачи принятия решения, то есть индекс прецедента; Pref- предпочтения ЛПР; Sol - описание альтернативы (решение прецедента); DR - описание конечной ситуации принятия решения, сложившейся после реализации альтернативы.

DI = {SI, Asi}, (3)

где SI - описание ситуации принятия решения; Así - оценка ситуации принятия решения по аспектам.

SI=fSIDe, SIPar, SRel} (4)

где SIDe - множество количественных параметров элементарного типа (строка, целое число, дробное число), SIPar - множество параметров типа «перечисление», «иерархия» или «качественная переменная»; SRel - множество отношений, областью определения и значения которых являются экземпляры SI, Отношения SRel позволяют задавать структурное описание прецедента в виде семантической сети (графа).

Asi = (AsValí, AsVal2, .... AsValNAJ (5)

где AsVali - экземпляр онтологии, принадлежащий классу значения качественной переменной Assessment и классу аспекта.

Pref={PrejValiPrefVal2,...,PrejValNpr} (6)

где PrejVak - экземпляр онтологии, принадлежащий классу значения качественной переменной Preference и классу аспекта;

Sok = {SCI, SI} (7)

где SCI - множество классов иерархии онтологии, которым принадлежит экземпляр управляющего воздействия; SI- элемент описания начальной ситуации, к которому данное управляющее воздействие применяется.

DR = (SRMR} (8)

где SR и AsR имеют такую же структуру, что и 57 и Asi соответственно. Пару дескрипторов DI и Pref подаваемых на вход системы поддержки принятия решения, будем называть запросом к системе, или PI11 I-запросом Q: Q={DI,Pref} (9)

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

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

фРг№г*пм

•с 'CJ

rencas

wltSItuBWn \ »SoJuKorítBm

MpMttalSItuaHon """"Г"! •^/«EJnJíttai

.-P / |

пмАмеитеп! л' r / ,»Р*«1А1

ч ^-г—' ' •Deealbíonlem

\ tJ ' / . □

Ti^tCwnponer» ! ' fceoflwJAl

Да »Сотрет

рфропвп!

| ДтмРвП □

Рисунок 2 - Иерархия классов и объектные отношения онтологии Фрагмент онтологии с описанием прецедента управления водохозяйственной системой представлен на рисунке 3.

Aspect:

Сельское хозяйство

>

f Критический Нормальный i Не соотаетсвует

уровень уровень

Рисунок 3 - Фрагмент прецедента

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

Шаг 1. Сформировать описание ситуации, начальную оценку ситуации и предпочтения ЛПР в виде РПП-запроса £);

Шаг 2. Провести классификацию таксономии в онтологии над сформированным описанием РПП-запроса (2;

Шаг 3. Доопределить описание О, выведенными на шаге 2 новыми свойствами и оценками; Шаг 4. Выполнять

Шаг 6.1. Выбрать прецеденты Су из базы прецедентов, наиболее близкие <2;

Шаг 6.2. Провести адаптацию решения прецедентов Ся к 0 с помощью алгоритма адаптации;

Шаг 6.3. Провести классификацию таксономии в онтологии над сформированным решением прецедента С;

Шаг 6.4. Провести качественные рассуждения над сформированным решением прецедента С;

Шаг 6.5. Проверить решения прецедента С на допустимость на основе результатов выполнения шагов 4.3 и 4.4; Шаг 5. Пока решение прецедента С не допустимо Шаг 6. Сохранить решение прецедента С в базе прецедентов; На основе разработанного алгоритма поддержки ЗПР была предложена следующая схема ППР:

' Описание

( зпр у

Описание модели прецедента, формализация

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

-и-------1-

База знаний экспертов

Рисунок 4 - Предлагаемая схема ППР.

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

Для реализации алгоритма поиска прецедентов определяется глобальная мера близости между прецедентами (а также, прецедентом и РПП-запросом): SimfCase, Query) = /Ж Sf ]'/Р, (10),

где Si - мера близости по г-щ дескриптору.

Согласно составу дескрипторов прецедента, мера близости Sim выражается следующим образом:

Sim(Case,Qm^) = [wBISa{Ca,Qay+WMSM{CM.QM,QttlfY]''' (11), где Sdi(Cdi,Qdi)— мера близости по описанию территорий начальных ситуаций прецедента и запроса, SAsI(CAs!,QAinQi,ref)~ мера близости по оценке начальных ситуаций прецедента и запроса, WDl, WAsI - весовые коэффициенты.

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

Для оценки близости двух дескрипторов интервального типа применяется следующая мера близости: 2 * Inter

Sr{C,Q) = , (12),

Lc +Lq

где Inter - длина интервала, образованного пересечением интервалов С и Q, Lc - длина интервала С, Le - длина интервала Q.

Для оценки близости дескрипторов типа «дата» используется принцип разделения календарного года на сезоны GS, короткосрочные PS и среднесрочные РМ периоды и предложена следующая мера близости: DV\, если |й/с - DIq| < PS S0(DIc,DIg) = - DV2,ec.iuI'S<\DIc-DIg\<PM (13),

DV3, если DIс uDIq eGSj

где PS - длина краткосрочного периода, РМ- длина среднесрочного периода, GSj - одни из сезонов календарного года.

Для оценки близости дескрипторов типа «перечисление» используется следующая мера близости:

il, если Dr = Dn

SEWc,De) = l с С (14)

10, если Dc * Dq

где Dc и Dq- значения дескриптора в прецеденте С и РПП-запросе О.

Для оценки близости дескрипторов вещественного типа используется формула, выражающая близость как обратную зависимость от расстояния между значениями дескрипторов, нормализованными в интервал [0; 100] и определяемая как:

^-'-Цйг1 м.

где рс - нормализованное значение дескриптора прецедента, pQ - нормализованное значение дескриптора запроса.

Для оценки меры близости дескрипторов, представляющих собой качественную переменную (формализованную в виде таксономии онтологии) или таксономию применяется модифицированный алгоритм оценки близости экземпляров онтологий на основе анализа иерархии классов онтологии CBS (Concept-based similarity):

Sc(PcPa) = CBS(pc.p0)= ^ (16)

II с\ II II сг II

Алгоритм CBS использует модель и-мерного векторного пространства, где каждый экземпляр онтологии / представлен n-мерным вектором с„ каждому компоненту v,//7 которого соответствует концепт онтологии С,. Если экземпляр i не принадлежит концепту С}, соответствующий компонент вектора ct[j] равен нулю, если принадлежит - значение с,Ц] полагается равным единице. При формировании векторов с не учитываются определенные в модели системные концепты (Action, Assessment и т.д.,).

Для оценки меры близости дескрипторов, связанных с экземпляром прецедента через объектное используется модифицированной алгоритм SBS (Slot based similarity). Если представить объектное представление каждого прецедента как граф, в котором каждая вершина является экземпляром онтологии, а каждая из дуг - отношением онтологии, то задача определения близости сводится к нахождению наибольшего общего подграфа между графами прецедента-запроса и прецедента из базы прецедентов. При этом необходимо учитывать как близость вершин графа самих по себе, так и близость вершин графа по их окружению (определяется как близость дуг и близость связанных вершин графа). Выполнение расчета 555-близости осуществляется рекурсивным обходом графа в глубину, начиная с корневой вершины объектного описания. Известный алгоритм SBS не учитывает того, что экземпляры онтологии могут быть связанны разными типами отношений (т.е. в графе присутствуют различные дуги), а также не предполагает разницы между прецедентом из базы прецедентов

15

и запросом (т.е. что граф прецедента-запроса может нарочно не содержать некоторые параметры). Поэтому был предложен модифицированный алгоритм БВБ, близость по которому определяется как:

к\ • СЩ/1, /2) + к2 ■ [ пхах (СМ(г\, г2) • 1,} 2))] /(Л' + М)

ЖЧ;'1,(2) =-^^- (17),

«1 + к2

где и Я2 - множество отношений онтологии для экземпляров и г/;',; - множество экземпляров, связанных с экземпляром г"; через отношение г/, Л' - число сопоставленных вершин, М - число несопоставленных вершин в графе запроса, А/ и ^ - весовые коэффициенты. Отличие представленного алгоритма от известного - во введении меры близости для дуг графа и отказ от учета несопоставленных вершин прецедента для повышения релевантности результатов определения близости.

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

л,

= --5--(18),

IX, 1-1

где Е(Сп,С5,дрггГ) - критерий эффективности, А, - оценка начальной ситуации по г-му аспекту, Л, - оценка конечной ситуации по г'-му аспекту, сШЛА^ А,) - разница между оценками, Шм - весовой коэффициент г'-го аспекта, N - количество аспектов.

Для представления функции сЩ{АК АС) используется формула разницы начальной и конечной оценок относительно лучшей из возможных оценок Ав:

йШ(А. А1) = СЖ(Ае1А,)~СВЯ(АЙ,А,) (19)

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

Формулы (10), (11) и (13) содержат значения коэффициентов ,

Щ, ОУ2, ПУ; и \УА,. Значения коэффициентов \УА, вычисляются исходя из предпочтений ЛПР, которые выражаются качественной переменной с монотонной равномерной шкалой, которая может быть переведена в количественную оценку в интервале [0;1]. Значения (V,- и не могут быть определены экспертами напрямую. Для их определения алгоритм поиска должен пройти этап обучения, на котором эксперты на наполненной базе прецедентов составляют множество Р неравенств вида 5(С, ,СХ)> 5(С2 ,СХ). Тогда задача определения значений Щ и сводится к нахождению максимума функции:

где <р[р,) принимает значение 1 при выполнимости неравенства Р1 при данных значениях коэффициентов и 0 иначе. (20) вместе с условиями IV0, + ¡УА11 =1 и £»К,>£)Г2 >£>К3, ввиду нелинейности (10) является задачей нелинейного программирования. Для решения данной задачи оптимизации было решено использовать метод генетического программирования с использованием линейного дискретного кроссинговера.

Исходя из определения мер 5 и Е следует, что мера Е показывает насколько решение прецедента С подходит к РПП-запросу £), а мера 5 показывает насколько сильно решение прецедента С должно быть адаптировано для того, чтобы удовлетворять начальным условиям РПП-запроса Т.к. результат адаптации во многом зависит от формализации знаний экспертов, что весьма затруднено для ЗПР в условиях неопределенности, то при сравнимом значении мер Е и 5 предпочтение должно отдаваться прецедентам с большим значением меры Е.

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

Шаг 1. Определить предпочтения ЛПР и значение весовых коэффициентов

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

(20),

Cases;

Шаг 3. Сформировать множество СР, такое, что VC е Ср: S(C, Q) > SimWf] л Е(С, Q) > Ет;

Шаг 4. Отсортировать множество СР, по возрастанию значения v;

Шаг 5. Включить в множество SC не более чем М прецедентов, значение критерия эффективности которых максимально: SC = SCu[Сj :Сj eCpAE{Cj,Q) = EUAX}-

Шаг 6. Включить в множество SC не более чем М прецедентов со значением V в интервале [Sim¡NT*v\v\,

Шаг 7. Включить в множество SC не более чем М прецедентов, значение меры близости которых максимально: SC = SCu [Cj :Cj еСр л Sim(Cj, Q) = Simíux ]

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

Задача адаптации состоит в модификации вектора управляющих воздействий Acs прецедентов SC таким образом, что при его реализации на начальной ситуации Ind. РПП-запроса Q критерий эффективности Е принимает максимально возможное значение. Т.е. задача адаптации состоит в нахождении такого вектора управляющих воздействий, который является максимально эффективным для текущего РПП-запроса Q с сформулированными предпочтениями ЛПР. Задача ограничивается условием принадлежности каждого элемента вектора решений As множеству управляющих воздействий Ас: \/Acs¡ е Ас, определенных на этапе поиска прецедентов. Таким образом, задача адаптации является задачей целочисленной (дискретной) оптимизации, которая принадлежит к классу NP-трудных задач:

E(Acs) _^max (21)

AcseAc

Особенностью функции E(Acs) является то, что ее вид не может быть описан в силу сложности формализации знаний в предметной области. Однако значение функции EfAcsJ можно оценить в любой точке с помощью рассуждений на качественной модели КМ. Результатом качественных рассуждений является оценка вектора качественных переменных А по каждому аспекту, характеризующая ситуацию прецедента после реализации вектора управляющих воздействий Acs. Имея значение вектора А как результат качественных рассуждений и значение вектора А из формулировки РПП-запроса Q можно вычислить значение меры Е по формуле (18).

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

- полученные из прецедентов, выбранных на этапе поиска;

- полученные путем применения экспертных правил на ситуации принятия решения;

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

Наличие дополнительной информации в виде таблицы взаимных влияний альтернатив Ш позволяет применить модифицированный метод ветвей и границ для решения данной задачи. Таблица М имеет размер К*К (где К=\Ас\), каждый элемент которой Шу принимает значение 1, если альтернативы Act и Acj при совместном применении дают положительный кумулятивный эффект, -1 - отрицательный кумулятивный эффект. Таким образом, функцию Е(Ас,) можно считать нижней оценкой, а функцию Е(Ас, и ACj: MIV > 0)- верхней оценкой. Отсортировав оценки по убыванию, получим на вершине списка либо одинарные действия Ас^ либо набор действия Л с, U Acj. В первом случае действие Ас, включается в решение Acs, во втором случае аналогичная оценка нижней и верхней границ производится для всех возможных пар Лс, UAcj и так далее.

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

Шаг 1. Составить массив AcSC из управляющих воздействий выбранных

прецедентов с коэффициентом уверенности va = v Шаг 2. Применить процедуру «классификация таксономии» на онтологии, занести в массив AcSC выведенные управляющие воздействия AcR с коэффициентом уверенности va = 1 Шаг 3. Если массив AcSC пуст, то для каждого управляющего воздействия

Aci: занести в массив AcSC с коэффициентом уверенности va = WS, Шаг 4. Отсортировать массив AcSC в порядке убывания коэффициента уверенности va;

Шаг 5. Для каждого управляющего воздействия Л с, удалить из массива

AcSC такие AcJ; что М1у = -1 Шаг 6. Для каждого Лс,- из AcSC провести рекурсивную процедуру оценки Шаг 6.1. Сформировать массив Хя сочетаний Ас, с Acj Шаг 6.2. Провести качественные рассуждения, рассчитать E(X[iJ), сформировать массив Еу из пар {X[i], E(X[i])} и {Ась Е(Ас^}\ Шаг 6.3. Провести качественные рассуждения, рассчитать E(Acj), занести в массив Es пару {Ась Е(Ас,)}-,

Шаг 6.4. Отсортировать массив Es по убыванию значений Е;

Шаг 6.5. Если на вершине массива Es находится пара {Ась EfAcJj, то

6.5.1. Занести Ас( в Acs Шаг 6.6. Иначе

6.6.1. Для каждой пары {X[i], E(X[i])}, таких, что E(X[i]) > E(Aci) провести рекурсивную процедуру оценки, начиная с шага 6 После выполнения этапа адаптации прецедента и составления решения Acs необходимо выполнить этап оценки нового решения РПП-запроса Q. При оценке решения могут использоваться как продукционные правила для проверки непротиворечивости и полноты решения, так и качественная модель для проверки эффективности нового решения.

Общий алгоритм оценки решения состоит из следующих шагов: Шаг 1. Сформировать новый прецедент С с описанием Ind равным описанию РПП-запроса Q и решением Acs

Шаг 2. Применить процедуру «классификация таксономии» на онтологии Шаг 3. Если прецедент С был отнесен к одному из классов, обозначающих неполное или недопустимое решение, то удалить прецедент С, перейти к шагу поиска прецедентов

Шаг 4. Провести качественные рассуждения, рассчитать по (18) Е(С) Шаг 5. Если Е(С) < 0, то перейти к шагу поиска прецедентов Шаг 6. Если Е(С) > EMN, то занести прецедент С в базу прецедентов Четвертая глава посвящена вопросам проектирования и реализации автоматизированной интеллектуальной системы поддержки принятия решений при управлении водохозяйственной системой реки Эльба в границах национального заповедника земли Саксония-Ангальт и проверке эффективности разработанных моделей и алгоритмов.

Автоматизированная интеллектуальная система под держки принятия решений (АИС 111 IP) разработана с использованием технологии объектно-ориентированного анализа и проектирования и языка моделирования UML. Система реализована как оконное приложение, функционирующее на платформе Java 1.5.

Концептуально АИС 111 IP состоит из следующих основных модулей: база знаний, подсистема работы со знаниями, подсистема интеллектуальной поддержки.

База знаний, построенная на основе библиотеки работы с онтологиями OWL-DL Protégé 3.4, реализует типовую функциональность хранения и проверки целостности данных и знаний в виде онтологии OWL-DL. Хранилище информации реализовано в виде XML документов в формате RDF, предусмотрен

интерфейс для хранилища информации: с использованием реляционной СУБД

с организацией доступа по технологии ЛЭВС. Для реализации генетического

алгоритма была использована свободно распространяемая библиотека ЮАР.

Архитектура системы приведена на рисунке 5. Уровень интерфейса

Подсистема графического интерфейса

РЛодуль редактирования прецедентов

Модуль просмотра результатов поиска

Модуль просмотра результатов адаптации

1

Подсистема поиска прецедентов!

¡"подсистема адаптации прецедентов

1,3- Множество прецедентов в формате №1 2 -Экспертные правила 4 - Прецедент а фермате ОАКРЗ 5,6 - Описание прецедентов согласно модели представления прецедента

7 - Команды СЮ-интерфейса и результаты вывода на правилах описательной логюи

8 - Результаты качественного моделирования, оцеккзАвй 16 - Новый прецедент С'

9 - Результаты вывода на правилах доопределения прецедентов

10 - Результаты вывода на правилах адаптации

11 - Результаты вывода на правилах проверки допустимости прецедентов

12 - РЛП-запрос

13 - Значения Sim и Е прецедентов

14 - Прецеденты, Еыбрзнвые для РПП-залроса 15- Решение РПВ-запроса

Рисунок 5 - Архитектура системы

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

Шаг 1. Случайным образом разделить множество прецедентов на множества М/ и М2 в отношении 60%/40%

Шаг 2. Множество M¡ занести в базу прецедентов Шаг 3. Для каждого прецедента С из множества М2 Шаг 3.1. Сформировать РПП-запрос Q

Шаг 3.2. Подать РПП-запрос Q на вход тестируемых систем, получить два прецедента C¡ и С2 - выход систем

N'

Шаг 3.3. Для C¡ и С2 подсчитать значение KS = —S2L; где NSol - коли-

^sol

чество элементов решения прецедента С, N'sol - количество элементов совпадающих элементов решения С и С,

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

В результате тестирования предложенные в исследовании алгоритмы совпадали с экспертным решением в среднем на 88%, в то время как результаты, полученные на «базовом» алгоритме совпадали в среднем на 67%. Результаты тестирования представлены на рисунке 6.

KS(Q),%

—Прадяагвемый алгоритм —S—"Базовый" алгоритм

1-1—г—г-

1 2 3 4 5 6 7 Е 9 10 11 12 13 14 прецеденты тестовой выборки

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

3. Разработаны алгоритмы адаптации и оценки результатов адаптации. Алгоритм адаптации отличается от известных тем, что в процессе адаптации используются как экспертные правила и вывод по ним на онтологии, так и качественная модель. Алгоритм оценки результатов адаптации отличается от известных тем, что использует качественную модель поведения объекта, формализованную с помощью онтологии, а также экспертные правила и вывод по ним на онтологии;

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в журналах, рекомендуемых ВАК

1. Интеграция рассуждений по прецедентам и онтологии в интеллектуальной системе поддержки инженерного анализа в области контактной механики / А.М: Дворянкин, М.Б. Сипливая, И.Г. Жукова, A.C. Капыш, А.Е. Кульцов // Изв. ВолгГТУ. Серия «Актуальные проблемы управления, вычислительной техники и информатики в тех. системах»: межвуз. сб. науч. ст. / ВолгГТУ. - Волгоград, 2008. - Вып. 4, № 2. - С. 90-94.

2. Разработка модели представления прецедента на основе онтологии и создание базы знаний для интеллектуальной системы поддержки инженерного анализа в области контактной механики / A.M. Дворянкин, М.Б. Сипливая, И.Г. Жукова, A.C. Калыш, А.Е. Кульцов // Изв. ВолгГТУ. Серия «Актуальные проблемы управления, вычислительной техники и информатики в технических системах»: межвуз. сб. науч. ст. / ВолгГТУ. - Волгоград, 2008. - Вып. 4, № 2. - С. 94-98.

3. Разработка онтологической базы знаний для интеллектуальной системы поддержки принятия решений в сфере управления водохозяйственной системой/А.М. Дворянкин, М.Б. Кульцова, И.Г. Жукова, А.Е. Кульцов, A.C. Капыш // Изв. ВолгГТУ. Серия "Актуальные проблемы управления, вычислительной техники и информатики в тех. системах". Вып. 6: межвуз. сб. науч. ст./ВолгГТУ. -Волгоград, 2009. -№ 6. -С. 95-99.

4. Метод поиска прецедентов для интеллектуальной поддержки принятия решений в сфере управления водохозяйственной системой реки Эльба / A.M. Дворянкин, М.Б. Кульцова, И.Г. Жукова, A.C. Капыш, А.Е, Кульцов // Известия ВолгГТУ. Серия "Актуальные проблемы управления, вычислительной техники и информатики в технических системах". Вып. 7 : межвуз. сб. науч. ст. / ВолгГТУ. - Волгоград, 2009. -№12.-С. 103-106.

Статьи в зарубежных журналах

5. Integration of a case-based reasoning and an ontological knowledge base in the system of intelligent support of finite element analysis / P. Wriggerrs, М.Б. Сипливая, И.Г. Жукова, A.C. Капыш, А.Е. Кульцов // Computer Assisted Mechanics and Engineering Sciences. -2007. - № 14. - C. 753-765.- Англ.

Статьи в сборниках меяедународных конференций

6. Извлечение и структурирование знаний в области управления водохозяйственной системой реки Эльба / A.M. Дворянкин, М.Б. Кульцова, И.Г. Жукова, А.Е. Кульцов, A.C. Капыш // Открытое образование: приложение к журналу [по матер, междунар. конференций, Ялта-Гурзуф, 20-30 мая 2008 г.]. - 2008. - Б/н. - С. 129-130.

7. Интеграция онтологии и рассуждений по прецедентам и правилам в системе управления водохозяйственной системой реки Эльба / A.M. Дворянкин, М.Б. Кульцова, И.Г. Жукова, A.C. Капыш, А.Е. Кульцов // Открытое образование: приложение к журналу [по матер, междунар. конференций, Ялта-Гурзуф, 20-30 мая 2008 г.]. - 2008. - Б/н. - С. 125-126.

8. Капыш, A.C. Методы адаптации для системы поддержки принятия решений на основе рассуждений по прецедентам / A.C. Капыш // Информационные технологии в образовании, технике и медицине : матер, междунар. конф., 21-24 сент. 2009 / ВолгГТУ [и др.]. - Волгоград, 2009. - С. 83.

Подписано в печать .04.2011 г. Заказ №<2^. Тираж 100 экз. Печ. л. 1,0 Формат 60x84 1/16. Бумага офсетная. Печать офсетная.

Типография ИУНЛ Волгоградского государственного технического университета. 400131, г. Волгоград, пр. им. В.И.Ленина, 28, корп. №7.

ВВЕДЕНИЕ.

ГЛАВА 1 ПОДХОДЫ К ПОДДЕРЖКЕ ПРИНЯТИЯ РЕШЕНИЙ.

1.1 Задача принятия решения в условиях неопределенности.

1.2 Модели представления знаний, применяемые для поддержки задач принятия решений.

1.3 Системы поддержки принятия решений.

1.4 Цели и задачи исследования.

ГЛАВА 2 ПОСТРОЕНИЕ ИНТЕГРИРОВАННОГО МЕХАНИЗМА РАССУЖДЕНИЙ.

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

2.2 Требования к представлению прецедента и экспертных знаний.

2.3 Описание прецедента задачи принятия решения.

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

ГЛАВА 3 АЛГОРИТМЫ ФУНКЦИОНИРОВАНИЯ

ИНТЕГРИРОВАННОГО МЕХАНИЗМА РАССУЖДЕНИЙ.

3.1 Поиск прецедентов.

3.1.1 Глобальные меры близости прецедентов.

3.1.2 Локальные меры близости прецедентов.

3.1.3 Алгоритм выборки прецедентов.

3.2 Алгоритм адаптации прецедентов.

3.3 Оценка прецедентов.

ВЫВОДЫ ПО ГЛАВЕ 3.

ГЛАВА 4 СИСТЕМА ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ В ОБЛАСТИ

УПРАВЛЕНИЯ ВОДОХОЗЯЙСТВЕННОЙ СИСТЕМОЙ.

4.1 Разработка автоматизированной системы поддержки принятия решения.

4.1.1 Функциональная структура.

4.1.2 Архитектура системы.

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

4.3 Тестовый пример.

4.4 Оценка эффективности разработанной системы.

ВЫВОДЫ ПО ГЛАВЕ 4.

Актуальность работы. Многокритериальные задачи принятия решения составляют широкий класс задач, встречающихся при планировании, управлении, инженерных разработках. Зачастую при решении данных задач необходимо учитывать интересы различных субъектов, преследующих разные цели, которые выдвигают противоречивые критерии для оценки альтернатив. Среди данных задач особым образом выделяются задачи, в которых в качестве альтернатив выступают составные наборы действий (управляющих воздействий), сложным образом влияющие на значение каждого из критериев, что делает невозможным точную оценку критериев для альтернатив [40), 46), 72), 129)].

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

В качестве примера такой задачи была рассмотрена задача управления водохозяйственной системой реки, которая представляет собой непрерывный процесс реализации управляющих воздействий (например, увеличить высоту дамбы, произвести очистку дна) с целью как обеспечения наиболее благоприятных условий хозяйствования, так и предотвращения разрушительных последствий паводков и сохранения экологического баланса реки [115)]. При этом задача выбора управляющих воздействий осложняется наличием нескольких хозяйствующих субъектов (экологи, рыболовы, туристические компании), преследующих взаимоисключающие цели и сложностью построения модели водохозяйственной системы реки для прогнозирования отклика системы на реализацию тех или иных управляющих воздействий. Данная задача сводится к многокритериальной задаче принятия решения, в которой в качестве альтернатив выступают наборы управляющих воздействий, а в ! качестве критериев — оценка ситуации с точки зрения различных хозяйствующих субъектов.

Одним из способов обеспечения более качественного и быстрого принятия решения для данного класса задач является использование специальных систем поддержки принятия решений. Реализация такой системы подра

5 j зумевает разработку формального представления знаний в предметной области и автоматизацию процесса принятия решения с использованием этих знаний. Существенный вклад в изучение проблем представления знаний и автоматизации рассуждений на знаниях внесли Д.А. Поспелов, В.Н. Вагин, В.М. Курейчик, Т.А. Гаврилова, Г.С. Осипов, A.A. Зенкин, П. Уинстон, П. Джексон, Дж. МакКарти, Б. Куйперс.

Важными особенностями рассматриваемого класса задач принятия решения являются использование экспертами как качественной, так и количе-< ственной информации, а также использование накопленного опыта — знаний о ранее решенных задачах, аналогичных данной. Анализ текущего процесса принятия решения показал, что основные знания, используемые экспертами I для выбора управляющих воздействий, сформулированы неявно в виде опыта, в то время как явные знания, сформулированные в виде экспертных правил и качественных зависимостей используются для адаптации ранее полученного решения к текущей ситуации [40)].

Исследование существующих средств поддержки процесса принятия решения, в том числе в сфере экологии, на примере работ Сливина [47)], Ванга (Wang) [129)], Денга (Deng) [77)], Кумар (Kumar) [99)], Кеккарони (Ceccaroni) [72)] показало, что существующие модели и алгоритмы не могут быть применены для поддержки рассматриваемого класса задач принятия решений, так как не учитывают их специфические свойства:

- невозможность оценить последствия принимаемых решений;

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

- на разных этапах решения задачи управления эксперты используют разные типы знаний;

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

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

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

Для достижения данной цели были поставлены и решены следующие задачи:

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

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

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

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

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

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

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

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

Положения, выносимые на защиту:

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

2) алгоритм поиска прецедентов с использованием критерия эффективности и модели представления прецедента в виде онтологии;

3) алгоритм адаптации прецедентов с использованием экспертных правил и вывода по ним на онтологии;

4) алгоритм оценки прецедентов с использованием качественной модели поведения объекта.

Практическая ценность полученных результатов. Работа была выполнена при поддержке грантов РФФИ (проект 05-08-1793 0-а, 2006-2008 гг.), а также совместного гранта Министерства образования и науки РФ и DAAD «Михаил Ломоносов II» с прохождением стажировки в университете г. Ганновер, Германия в 2008-2009 гг.

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

1) предложенные модели и алгоритмы реализованы в виде автоматизированной системы интеллектуальной поддержки принятия решений;

2) на примере задачи управления водохозяйственной системой реки Эльба в границах заповедника земли Саксония-Ангальт была создана тестовая база знаний и проверена работоспособность разработанной системы; проведена оценка эффективности предлагаемых алгоритмов;

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

На разработанную автоматизированную систему и базу знаний были получены свидетельства о регистрации в РосПатенте № 2010620572, № 2010620562, № 2010613010, № 2010613007.

Апробация работы. Основные результаты работы докладывались и обсуждались на: XXXIII международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе IT+SE"2006», Гурзуф, Украина, 2006, международном симпозиуме "Methods of Artificial Intelligence AI-METH 2007", Gliwice, Польша, 2007, XXXIV международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе IT+SE^OOS», Гурзуф, Украина, 2008, практическом семинаре RAMWASS, Ганновер, Германия, 2009, конференции «Информационные технологии в образовании, технике и медицине», Волгоград, 2009.

Публикации. По теме диссертации опубликовано 8 печатных работ, в том числе 4 публикаций в изданиях из перечня ведущих научных журналов ВАК, 1 статья в международном журнале, 3 тезиса докладов на конференциях, получено 4 свидетельства о государственной регистрации программ ЭВМ и баз данных.

Структура и содержание диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения, 3-х приложений и списка литературы. Диссертация содержит 168 страниц основного текста, в том числе 33 рисунка, 24 таблицы, список литературы из 134 наименований. Общий объем работы - 237 страниц.