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

Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Национальный исследовательский ядерный университет

«МИФИ»

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

Тимонин Михаил Владимирович

Методы поиска экстремальных значений интеграла Шоке и их применение в задачах принятия решений

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

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

1 9 лрг ?!1|5

005561570

Москва - 2015

005561570

Работа выполнена на кафедре «Управляющие интеллектуальные системы» Федерального государственного автономного образовательного учреждения высшего профессионального образования «Национальный исследовательский ядерный университет «МИФИ».

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

Лаврентьев Валерий Сергеевич

Официальные оппоненты: к.ф.-м.н., доцент,

Аверкин Алексей Николаевич,

Федеральное государственное учреждение «Федеральный исследовательский центр «Информатика и управление» Российской академии наук», д.ф.-м.н., профессор, Лепский Александр Евгеньевич,

Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Национальный исследовательский университет «Высшая школа экономики». Ведущая организация: Федеральное государственное учреждение «Федераль-

ный исследовательский центр «Информатика и управление» Российской академии наук».

Защита состоится 26 октября 2015г. в 11:00 часов на заседании диссертационного совета Д002.086.02 при Федеральном государственном бюджетном учреждении науки «Институт системного анализа Российской академии наук» (ИСА РАН) по адресу: 117312, Москва, проспект 60-летия Октября, 9, конференц-зал, 1-й этаж. Телефон: +74991355164.

С диссертацией можно ознакомиться в библиотеке ИСА РАН.

Электронные версии диссертации и автореферата размещены на официальном сайте ИСА РАН http://www.isa.ru.

Электронная версия автореферата отправлена для размещения на официальном сайте ВАК Министерства образования и науки РФ по адресу http://vak.ed.gov.ru/dis-details?xPARAM=2 01599 6 июля 2015 года.

Отзывы и замечания по автореферату в двух экземплярах, заверенные печатью, просьба высылать по адресу 117312, Москва, проспект 60-летия Октября, 9, ИСА РАН, диссертационный совет.

Автореферат разослан 4 августа 2015г.

Ученый секретарь диссертационного совета Д002.086.02,

д.т.н., профессор Пропой А.И.

Общая характеристика работы

Актуальность темы исследования

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

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

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

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

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

Степень разработанности темы исследования. На сегодняшний день опубликовано значительное число работ, связанных с применением интеграла Шоке в многокритериальных задачах принятия решений (см. обзор литературы в [21, 22, 31]). Однако, вопросы использования интеграла Шоке в задачах многокритериальной оптимизации на данный момент момент изучены незначительно. Основные результаты в данной области представлены в работах [17-20, 25-29], а также в работах автора [12, 13]. Вопросы робастного принятия решений с помощью интеграла Шоке являются новым направлением в данной области и рассматривались, помимо публикаций автора [14, 15], в работах [16, 23, 24].

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

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

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

2. Впервые предложены методы максимизации интеграла Шоке для нелинейных функций полезности и различных типов емкости. Рассмотрены выпуклый и невыпуклый случай.

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

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

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

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

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

8. Разработано программное обеспечение, реализующее разработанные теоретические методы.

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

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

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

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

1. Задача построения информационной системы как задача многокритериальной оптимизации.

2. Методы максимизации интеграла Шоке по выпуклым и невыпуклым емкостям.

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

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

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

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

1. 14th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems. 9-13 июля 2012, Катания, Италия;

2J The 2nd International Conference on Belief Functions, 9-11 мая 2012, Компьень, Франция;

3. Общемосковский научный семинар «Математические методы анализа оптимальных решений в экономике, бизнесе и политике». Январь 2012, Высшая школа экономики, Москва;

4. 32nd Linz Seminar on Fuzzy Set Theory. Decision Theory: Qualitative and Quantitative Approaches. 1-5 февраля 2011, Линц, Австрия;

5. Научная сессия МИФИ, Москва, 2011;

6. Научная сессия МИФИ, Москва, 2010;

7. Научная сессия МИФИ, Москва, 2009;

8. 12-й Национальный форум информационной безопасности. Москва, 2009;

9. Всероссийская научно-практическая конференция «Информационная среда вуза 21 века». Петрозаводск 2008;

10. Научная сессия МИФИ, Москва, 2008.

Публикации. Материалы диссертации опубликованы в 14 печатных работах, из них 2 статьи в международных рецензируемых журналах [13, 15], 5 статей в журналах, входящих в «Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации», утвержденный ВАК [3, 7-10], и 8 статей в сборниках трудов международных и всероссийских конференций [1, 2, 4-6, 11, 12, 14].

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

Структура и объем диссертации. Диссертация состоит из введения, 3 глав, заключения и библиографии. Общий объем диссертации 144 страниц, из них 127 страниц текста, включая 25 рисунков. Библиография включает 142 наименования.

Содержание работы

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

Первая глава

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

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

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

пертных, так и статистических.

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

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

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

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

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

С{у, (/1(21),...,/„(гп))) -»шах

2 е 2о,

где С(и, (/1(21),..., /„(гп))) - интеграл Шоке по емкости и, /¿(г;) - функции ценности, г = (¿1, ■ ■ ■ ,гп), 20 с К" - замкнутое ограниченное выпуклое множество (множество допустимых альтернатив). Распространенным примером множества £0 является:

п

= В, «>()}, (2)

¿=1

где В - размер бюджетного ограничения. В случаях, когда это возможно, будем писать (7(1/,/(г)) вместо С(«/,(Л(г,),...,/„(«„))).

Второй задачей, решаемой в данной диссертации, является задача робастной оптимизации интеграла Шоке. Данная задача порождается неопределенностью, при которой предпочтения лица, принимающего решение (ЛПР), не позволяют однозначно определить модель (1). В частности, в данном случае считается, что емкость и принадлежит некоторому множеству Ы. В этом случае задача формулируется следующим образом:

шах [тахС(|/,/(г))- С(1/,/(/))] ->шп I'еЫ

О)

г е 20 гГ в 2о,

где и - множество емкостей согласующихся с предпочтениями ЛПР.

В разделе 1.7 содержатся выводы из первой главы:

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

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

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

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

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

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

Вторая глава

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

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

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

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

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

В разделе 2.1 приводятся базовые теоремы, в частности, характеризуется связь вогнутости интеграла со свойствами емкости (2-монотонностью).

Определение 1. Емкость V называется к-монотонной для некоторого к > 2, если для всех семейств из к подмножеств ... ,Ак выполняется

к

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

Определение 2. Емкость и называется к-аддитивной, если для коэффициентов ее обращения Мебиуса выполняется т"{А) := Х)всл(-1)|ЛуВЧ-в) = 0 для всех А С ./V,\А\ > к, и существует А с N,\А\ = к такое, что т"(А) ф 0.

Теорема 1. Интеграл Шоке С{и,{}1(21),... ,/„(«„))) по емкости 1> : 2Ы -)• К является выпуклым ( вогнутым ) на К", для всех возможных выпуклых (вогнутых) /¿(¿¿) тогда и только тогда, когда емкость V : 2м К является субмодулярной (супермодулярной).

В разделе 2.2 рассматривается решение задачи поиска максимума (1) для случая вогнутого интеграла Шоке. Характеризуется супердифференциал и описывается процесс вычисления суперградиента. Для нахождения максимума предлагается использование метода проекции суперградиента и доказывается его сходимость. Рассматривается численный пример.

В разделе 2.3 предлагается алгоритм поиска глобального максимума (1) для общего случая. Рассматривается метод представления произвольного интеграла в виде максимума вогнутых интегралов. Для класса 2-аддитивных емкостей доказывается минимальность получаемого разложения и характеризуется число компонентов в таком разложении для заданной емкости.

Общий случай задачи (1) является существенно более сложным ввиду невыпуклости целевой функции. Помимо применения универсальных алгоритмов глобальной оптимизации, в данной задаче возможно использовать "комбинаторный" аспект интеграла Шоке. Основной идей предлагаемого метода является разложение интеграла на вогнутые составляющие, максимум каждой из которых ищется независимо. Целью является получение следующего представления:

ствам Т^ Эти множества образуют разбиение пространства переменных (т.е. К") такое, что интеграл является вогнутым в пределах каждого множества. Кроме того, желательным является то, чтобы число таких множеств было минимально. Основными результатами данного раздела являются:

• метод разбиения множества К" на подмножества Т1 такие, что С (и, /(г)) вогнут внутри каждого подмножества;

• метод разложения емкости и на множество емкостей /З7*, биективно соответствующих множествам Ти причем С( ^/(2)) = \1{С(0Т\ /(г)) и С (у, ¡{г)) = С{0т\Цг)) внутри каждого множества Т1;

• доказательство полной монотонности емкостей /Зт';

• доказательство минимальности разложения для класса 2-аддитивных емкостей.

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

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

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

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

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

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

Если информация о предпочтениях позволяет уникально определить емкость, проблема принятия оптимального решения имеет вид (1). Оптимальным решением является некоторый элемент допустимого множества, максимизирующий значение интеграла. Однако, в случае, если предпочтениям ЛПР соответствует более одной емкости, сформулировать задачу в виде (1) невозможно, и требуется использование дополнительных средств, позволяющих учитывать все множество допустимых емкостей. В качестве такого средства предлагается использование критерия минимаксных потерь (minimax-regret [30]). Функция потерь имеет следующий вид:

ЩигеЫ, zr) = тахС(игеа1, f(z)) - C{vTeal, f(zr)), (6)

zG-Zo

где zr - "робастное решение", а vTeai - емкость, наиболее соответствующая реальности. Поскольку ЛПР не обладает достаточной информацией для определения этой емкости задача поиска оптимального решения приобретает следующий вид:

тах [тах С(и, f{z)) — C(i>, /(¿r))j —> min veu

(RP)

2 6 20 2r 6 Zo,

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

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

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

Теорема 2. Пусть Ы - выпуклое замкнутое множество такое, что все и 6 Ы 2-моно-тонны. Тогда решение гТ„ задачи (ЯР) также является точкой глобального максимума С(уг, /(г)), г € 2о для некоторых 1/г € 1А.

Теорема 3. Пусть Ы - выпуклое замкнутое множество. Решение задачи (ЯР) также является локальным максимумом С(иг, /(г)), г £ по некоторой 1/Г е и.

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

В разделе 2.10 содержатся итоги второй главы.

1. Впервые предложены методы максимизации интеграла Шоке для различных видов функций полезности и типов емкости. Рассмотрены выпуклый и невыпуклый случай.

2. Для решения невыпуклого случая впервые предложен алгоритм представления произвольной емкости в виде максимума минимального числа тотально монотонных емкостей. Это позволило свести задачу максимизации интеграла Шоке по произвольной емкости к множеству выпуклых задач.

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

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

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

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

Результаты главы 2 опубликованы в работах [3, 7, 10, 12-15]. Третья глава

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

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

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

Защита]

[Тех, средства]

j Персопал|

ZJ7

[Оф5

—t>jОфис, сеть] [Серверы офис<

Firewall Обновления

Изолирование Журналы — NIDS Адм.

1rs да"*"

Шифрование Адм. аудит ^

Фиэ. _

защита"

Раб., станции

—^ Хостинг]

Физ.

' защита

•Сеть - Серверы

|Тех. средства"]

Упр. доступом Аудит Проверки • Обучение • Мотивация •

. Политика безо п.

_ Ограничение прав

.Учет пользователей

_ Выполнение политик

Сильная " аутепт.

.ММ система

Рис. 1. Модель многокритериальной задачи, раздел 3.3

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

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

функциями WAM (взвешенное арифметическое среднее), MIN, МАХ, OWA. Приводятся результаты анализа предпочтений для различных категорий путешественников. Выявляются следующие характеристики:

• относительная важность различных факторов (таких как цена или месторасположение) с точки зрения различных групп посетителей;

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

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

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

В разделе 3.5 приводятся выводы из третьей главы.

Полученные результаты свидетельствуют о высоком уровне практической применимости разработанных методов. Результаты главы опубликованы в статьях [3, 6-11, 13].

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

Список публикаций

1. Тимонин М. В. Моделирование риска информационной безопасности с помощью теории нечеткой меры. // Научная сессия МИФИ - 2010. Сборник научных трудов. Т. 5. 2010. С. 187-190.

2. Тимонин М. В. Оптимизация стратегии инвестирования в систему защиты информации в моделях, основанных на теории нечеткой меры. Тезисы докладов конференции "Проблемы информационной безопасности в системе высшей школы" // Безопасность информационных технологий. Т. 1. 2010. С. 109-111.

3. Тимонин М. В. Пример моделирования риска информационной безопасности с помощью теории нечеткой меры // Безопасность информационных технологий. 2010. Т. 1. С. 30-35.

4. Тимонин М. В. Пример моделирования риска информационной безопасности с помощью теории нечеткой меры. // Научная сессия МИФИ - 2010. Сборник научных трудов. Т. 3. 2010. С. 130-131.

5. Тимонин М. В. Сравнительный анализ подходов к моделированию риска информационной безопасности, основанных на теории нечетких множеств и байесовых сетях. // Научная сессия МИФИ - 2010. Сборник научных трудов. Т. 3. 2010. С. 134-135.

6. Тимонин М. В. Использование интеграла шоке для оптимизации распределения ресурсов в многокритериальных задачах. // Научная сессия МИФИ - 2011. Сборник научных трудов. Т. 3. 2011. С. 109-109.

7. Тимонин М. В., Лаврентьев В. С. Использование теории нечеткой меры для агрегации составляющих риска информационной безопасности // Безопасность информационных технологий. 2009. Т. 4. С. 31-35.

8. Тимонин М. В., Лаврентьев В. С. Методика оценки целесообразности внедрения системы управления идентификационной информацией (IDM) на предприятии // Системы высокой доступности. 2009. Т. 2. С. 17-30.

9. Тимонин М. В., Лаврентьев В. С. Сравнительный анализ подходов к моделированию риска информационной безопасности, основанных на теории нечетких множеств и Байесовых сетях. // Безопасность информационных технологий. 2010. Т. 2. С. 22-27.

10. Тимонин, М. В. Проблема оптимизации распределения ресурсов при планировании стратегии информационной безопасности I. Теоретические основы. // Безопасность информационных технологий. 2011. Т. 2.

11. Timonin М. Resource Allocation Problems in Hierarchical Models Based on Multistep Choquet Integrals. // Proceedings of the 32nd Linz Seminar on Fuzzy Set Theory. Decision Theory: Qualitative and Quantitative Approaches. 2011. P. 89-97.

12. Timonin M. Choquet Integral as Maximum of Integrals with Respect to Belief Functions // Belief Functions: Theory and Applications / Ed. by T. Denoeux, M.-H. Masson. Springer Berlin / Heidelberg, 2012. Vol. 164 of Advances in Intelligent and Soft Computing. P. 117-124.

10.1007/978-3-642-29461-7_14. URL: http://dx.doi.org/10.1007/978-3-642-29461-7. 14.

13. Timonin M. Maximization of the Choquet integral over a convex set and its application to resource allocation problems // Annals of Operations Research. 2012. Vol. 196. P. 543-579. 10.1007/sl0479-012-l 147-9. URL: http://dx.doi.org/10.1007/sl0479-012-1147-9.

14. Timonin M. Minimax Regret Capacity Identification // Advances in Computational Intelligence / Ed. by S. Greco, B. Bouchon-Meunier, G. Coletti et al. Springer Berlin Heidelberg, 2012. Vol. 300 of Communications in Computer and Information Science. P. 198-207. 10.1007/978-3-642-31724-8_21. URL: http://dx.doi.org/10.1007/978-3-642-31724-8_ 21.

15. Timonin M. Robust optimization of the Choquet integral // Fuzzy Sets and Systems. 2013. Vol. 213, no. 0. P. 27-46. URL: http://www.sciencedirect.com/science/article/pii/ SO 165011412001856.

Цитированная литература

16. Benabbou N., Perny P., Viappiani P. Incremental Elicitation of Choquet Capacities for Mul-ticriteria Decision Making // Proceedings of ЕСАГ14. 2014.

17. Fouchal H., Gandibleux X., Le Huede F. Preferred solutions computed with a label setting algorithm based on Choquet integral for Multi-Objective Shortest Paths // 2011 IEEE Symposium on Computational Intelligence in Multicriteria Decision-Making. 2011.

18. Galand L., Lesca J., Perny P. Dominance rules for the choquet integral in multiobjective dynamic programming // Proceedings of the Twenty-Third international joint conference on Artificial Intelligence / AAAI Press. 2013. P. 538-544.

19. Galand L., Perny P., Spanjaard O. A branch and bound algorithm for Choquet optimization in multicriteria problems // Multiple Criteria Decision Making for Sustainable Energy and Transportation Systems. 2010. P. 355-365.

20. Galand L., Perny P., Spanjaard O. Choquet-based optimisation in multiobjective shortest path and spanning tree problems // European Journal of Operational Research. 2010. Vol. 204, no. 2. P. 303-315.

21. Grabisch M., Labreuche C. Fuzzy measures and integrals in MCDA // Multiple criteria decision analysis: state of the art surveys. 2005. P. 563-604.

22. Grabisch M., Labreuche C. A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid // 40R: A Quarterly Journal of Operations Research. 2008. Vol. 6, no. 1. P. 1-44.

23. Jeantet G., Perny P., Spanjaard O. Sequential Decision Making with Rank Dependent Utility: a Minimax Regret Approach // 26th AAAI Conference on Artificial Intelligence. 2012. P. 1931-1937. URL: http://wvw-desir.lip6.fr/publications/pub_1570_l_AAAI12.pdf.

24. Labreuche C., Miranda P., Le huede F. Computation of the robust preference relation combining a Choquet integral and utility functions // 5th Multidisciplinaiy Workshop on Advances in Preference Handling. Lisbon, Portugal: 2010. — Aug.

25. Lust T., Rolland A. Choquet optimal set in biobjective combinatorial optimization // Computers & Operations Research. 2013. Vol. 40, no. 10. P. 2260-2269.

26. Lust T., Rolland A. On the Computation of Choquet Optimal Solutions in Multicriteria Decision Contexts // Multi-disciplinary Trends in Artificial Intelligence. Springer, 2013. P. 131-142.

27. Lust T., Rolland A. 2-additive Choquet Optimal Solutions in Multiobjective Optimization Problems // Information Processing and Management of Uncertainty in Knowledge-Based Systems / Springer. 2014. P. 256-265.

28. MagoC T., Modave F. Optimization of the Choquet integral using genetic algorithm // Constraint Programming and Decision Making. Springer, 2014. P. 97-109.

29. Moffltt M. D., Peintner B., Yorke-smith N. Multi-criteria optimization of temporal preferences // Proceedings of CP06 Workshop on Preferences and Soft Constraints. 2006.

30. Savage L. J. The theory of statistical decision // Journal of the American Statistical Association. 1951. Vol. 46, no. 253. P. 55-67.

31. Torra V., Narukawa Y. Modeling decisions: information fusion and aggregation operators. Springer-Verlag New York Inc, 2007. ISBN: 3540687890.

Научное издание

Тимонин Михаил Владимирович

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук на тему: Методы поиска экстремальных значений интеграла Шоке и их применение в задачах

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

Подписано в печать 31.07.2015. Формат 60 х 90 1/16. Тираж 84 экз. Заказ 319.

Отпечатано в типографии «ТриумР» 125009, г. Москва, Страстной б-р, д. 6, стр. 1 +7 (965) 203-33-07