ИНТЕЛЛЕКТУАЛЬНОЕ ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ПРЕДПОЧТЕНИЙ ЭКСПЕРТОВ НА МАТРИЦАХ ПАРНЫХ СРАВНЕНИЙ С. В. Микони, И. С. Киселёв (Санкт-Петербург)
1 ИНТЕЛЛЕКТУАЛЬНОЕ ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ПРЕДПОЧТЕНИЙ ЭКСПЕРТОВ НА МАТРИЦАХ ПАРНЫХ СРАВНЕНИЙ С. В. Микони, И. С. Киселёв (Санкт-Петербург В настоящее время имитационное моделирование используется во всех сферах человеческой деятельности. В сфере информационных технологий оно нашло применение в системах поддержки принятия решений (СППР []. Одной из задач принятия решений является распределение приоритетов для некоторой совокупности сущностей. Под сущностью будем понимать любые варианты принятия решений. При определении приоритетов сущностей эксперт неявно сопоставляет их между собой. В явном виде предпочтения эксперта задаются в матрице парных сравнений (МПС. На основе её содержимого рассчитываются приоритеты сущностей. Таким образом, матрица парных сравнений может использоваться для моделирования мыслительной деятельности человека, выполняемой при количественной оценке сущностей. Относительно сферы приложения такого моделирования его следует отнести к интеллектуальному виду моделирования. Поскольку зависимость между предпочтениями и получаемыми на их основе приоритетами неоднозначна, получение приемлемых решений требует просмотра многих вариантов. Моделирование количественного оценивания сущностей с помощью МПС может преследовать следующие цели: достижение приемлемого распределения приоритетов; улучшение согласованности предпочтений эксперта [2]; определение неизвестных предпочтений в частично определённой матрице. Помимо количественных предпочтений эксперта на распределение приоритетов влияют тип предпочтений и параметры формулы, применяемой для расчёта приоритетов. Рассмотрим влияние этих факторов на значения приоритетов сущностей. Выражение предпочтений матрицами разных типов К наиболее простому типу относятся порядковые предпочтения. Именно они достаточно уверено формулируются экспертом («А лучше Б». Содержащие порядковые предпочтения МПС [3] названы матрицами фактов предпочтений А фп. Их элементы формируются по следующему правилу:, если x i >x j ; a фп ij =, если x i <x j ; (, если x i =x j. На основании соотношения a ij +a ji = значения элементов матрицы, симметричных относительно главной диагонали, вычисляются по правилу: a ji = a ij. В работе [4] дискретный диапазон значений был расширен на непрерывный случай [, ], что позволило групповые предпочтения выражать долями от. Если принять за целое, правило ( расширяется на случай задания предпочтений в долях от следующим образом. Условию x i >x j ставится в соответствие доля,<a д ij, а условию x i <x j доля a д ij. Правило вычисления элементов матрицы, симметричных относительно главной диагонали, остаётся прежним. Задание предпочтений в долях от позволяет использовать вероятностные и нечёткие оценки сопоставляемых объектов. Помимо матрицы А д в работе [4] рассматривалась матрица турнирных предпочтений А т. Значения элементов матрицы парных сравнений, отражающей результаты 82 ИММОД-27
2 турнира, формируются на основе очков, присуждаемых за результат отдельного состязания. Например, если объекту x i за победу над объектом x j даётся 2 очка, за поражение, а за ничью, элементы МПС формируются по следующему правилу: 2, если x i >x j ; a т ij =, если x i =x j ; (2, если x i <x j. Элементы матрицы, симметричные относительно главной диагонали, вычисляются по правилу a т ji=2 a т ij. Все рассмотренные типы матриц А фп, А д и А т симметричны относительно главной диагонали по модулю М: a ji =М a ij. Другой тип симметрии присущ обратно-симметричной матрице А кп, широко используемой в работе []. Её элемент выражает превосходство сущности x i над сущностью x j по правилу: 2 9, если x i >x j ; a кп ij =, если x i =x j ; (3 /2 /9, если x i <x j. По этой причине в [3] она названа матрицей кратности предпочтений А кп. Перечисленные типы матриц не исчерпывают все случаи задания предпочтений. К матрицам, не обладающим свойством симметрии, относятся МПС, которые в [6] названы матрицами выигрышей/потерь. Элемент a ij матрицы этого типа интерпретируется как сумма выигрышей/потерь, а элемент a ji как сумма потерь/выигрышей. Популярным примером такой матрицы может являться таблица чемпионата по футболу, представленная в забитых и пропущенных мячах. Естественно предположить существование изоморфизма предпочтений в матрицах типов А фп, А д и А т, что даёт основание для перехода от одного типа матрицы к другому. В [6] были предложены формулы для однозначного преобразования содержимого этих матриц. Однозначным является преобразование обратно-симметричной матрицы А кп в матрицы А фп, А д и А т. Обратный переход неоднозначен при выходе предпочтений за диапазон кратности [ 9]. Наиболее информативной из рассмотренных типов матриц является матрица выигрышей/потерь А вп. Она гомоморфна по отношению к остальным типам матриц. Из неё может быть осуществлён однозначный переход к матрицам типов А фп, А д и А т и переход с частичной потерей информации к матрице А кп (в силу ограниченного диапазона кратности [ 9]. Однако в отсутствие информации о выигрышах и потерях наиболее просто экспертом формируется матрица фактов предпочтений А фп. К недостатку матрицы А фп относится довольно резкое различие между вычисляемыми на основе её содержимого приоритетами сущностей. Сгладить это различие позволяет переход от неё к более информативным матрицам с применением переводных формул [6]. Моделирование приоритетов сущностей В [6] было показано, что вектор приоритетов сущностей w может быть получен на основе матрицы А с любым типом предпочтений возведением в k-ю степень выражения: w= (с А + Е k e т, (4 где c масштабный коэффициент (c, который можно интерпретировать, например, количеством баллов, начисляемых за победу; E единичная матрица с элементами ИММОД-27 83
3 e ii =; e т транспонированный вектор текущих приоритетов с единичными начальными значениями. Вектор, вычисляемый возведением матрицы в -ю степень (k=, отражает взаимодействие рассматриваемой сущности с n остальными сущностями (О/О. При k процесс вычисления вектора w сходится к положительному собственному вектору, отвечающему максимальному вещественному собственному числу матрицы А. Случай k гарантирует учёт взаимодействия каждой сущности с каждой (К/К. В работе [4] этот случай интерпретируется применительно к результатам турнира как вычисление приоритетов с учётом «силы команд». На рис. 3 в качестве примера приведены графики нормированных приоритетов w i =f(k, i=,2,3,4, рассчитанные по формуле (4 для матриц парных сравнений А фп, А Б3, А д, где А Б3 =c А фп при c=3. А фп = all.. А Б3 = = А. 3 д = k Рис.. График значений приоритетов для матрицы А фп (c= k Рис. 2. График значений приоритетов для матрицы А Б3 (c=3 84 ИММОД-27
4 Рис.3. График значений приоритетов для матрицы А д (c= На всех графиках значения приоритетов сходятся к компонентам собственного вектора уже при k=. На рис. и 2 иллюстрируется влияние масштабного коэффициента c на соотношение и величину приоритетов 4 оцениваемых сущностей. Увеличение коэффициента c от до 3 при переходе от матрицы А фп к матрице А Б3, увеличивает диапазон и длительность колебаний приоритетов. Источником колебаний является нетранзитивность предпочтений. Вместе с тем компоненты собственных векторов обеих матриц А фп и А Б3 имеют одинаковое значение. На рис. и 3 иллюстрируется влияние типа матрицы на значения приоритетов, вычисленных для матриц А фп и А д. При сохранении порядка приоритетов их величина в матрицах разного типа различна. Как показано в [7], участок графиков [,], соответствующий дробной степени k, позволяет определить, каким сущностям, сильным или слабым, сильные сущности обязаны своим высоким приоритетом. Достижение требуемой согласованности предпочтений Помимо вычисления приоритетов сущностей матрица парных сравнений содержит информацию о согласованности предпочтений экспертов. Она максимальна (% для сверхтранзитивных матриц [4], характеризуемых полной порядковой и количественной согласованностью. Слабая согласованность свидетельствует о слабом проникновении эксперта в предметную область, либо о примерном равенстве сил противников в турнирах. Для повышения качества экспертизы эксперту важно знать не только величину согласованности парных предпочтений, но и предпочтение, вносящее наибольший вклад в их несогласованность. При выявлении порядковой несогласованности такое предпочтение выявляется по наибольшему числу циклов, проходящих через соответствующую дугу (ребро графа предпочтений [7]. Используя результаты работы [8], эту проблему можно решить для матрицы кратных предпочтений А кп. Работа [8] посвящена автоматическому доопределению частично заполненной МПС. Оно основано на нахождении таких чисел в пустых клетках матрицы, которые доставляют максимум функции согласованности. Максимум достигается при λ max n, где λ max максимальное собственное число матрицы, а n её размерность. Таким образом, имея информацию о степени согласованности своих предпочтений и возможность обнаружения источника несогласованности, эксперт получает возможность повысить качество своей экспертизы. ИММОД-27 8
5 Выводы. Матрица парных сравнений может использоваться в качестве имитационной модели в такой плохо формализуемой области, как определение приоритетов сущностей на основе задания экспертных предпочтений. 2. Имея представления лишь о порядковых предпочтениях, эксперт имеет возможность, переходя к матрице другого типа и/или управляя степенью взаимодействия сущностей и/или масштабным коэффициентом, добиваться приемлемого соотношения приоритетов сущностей. 3. Графики приоритетов сущностей позволяют визуально определять: степень согласованности предпочтений, турбулентные участки взаимодействия сущностей на шкале k, на которых приоритеты меняются местами, каким сущностям, сильным или слабым, сильные сущности обязаны своим высоким приоритетом. 4. Имея возможность обнаружить источники порядковой и/или количественной несогласованности предпочтений в МПС, эксперт получает возможность улучшать согласованность путём изменения предпочтений в нужном направлении. Следует отметить ещё два важных обстоятельства. Инвариантность МПС относительно предметных областей делает её универсальным инструментом решения поставленных в работе задач. Все изложенные возможности анализа и моделирования реализованы в системе выбора и ранжирования СВИРЬ [9] и апробированы при решении практических задач. Литература. Лычкина Н. Н. Современные технологии имитационного моделирования и их применение в информационных бизнес-системах и системах поддержки принятия решений//сб. докладов Второй научно-практич. конференции по имитационному моделированию ИММОД-2. СПб.: ФГУП ЦНИИТС, 2. Том. С Тоценко В. Г. Методы и системы поддержки принятия решений. Киев: Наукова думка, с. 3. Микони С. В. Теория и практика рационального выбора. М.: Маршрут, 24, 462 с. 4. Миркин Б. Г. Проблема группового выбора. М.: Наука, Саати Т., Кернс К. Аналитическое планирование. Организация систем. М.: Радио и связь, 99, 224 с. 6. Микони С. В., Киселёв И. С. Универсальный алгоритм расчёта приоритета сущностей для разных типов предпочтений//сб. докладов междунар. конф. SCM 2. СПб.: СПбГЭТУ, 2. Том. С Микони С. В., Киселёв И. С. Анализ и оценивание результатов турнира//сб. докладов междунар. конф. по мягким вычислениям и измерениям SCM 26, СПб.: СПбГЭТУ. Том 2. С Микони С. В., Киселёв И. С. Приближённый метод доопределения матрицы парных сравнений с кратными предпочтениями//труды конф. IEEE AIS 7 и CAD-27, Дивноморское, М.: Наука. Физматлит, 27. Том. С ИММОД-27
МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА 2011 Математические основы интеллектуальных систем 3(13) МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ УДК 519.168 АНАЛИТИЧЕСКИЙ МЕТОД ДООПРЕДЕЛЕНИЯ КРАТНЫХ ПРЕДПОЧТЕНИЙ