Software & Systems

Проблемы классификации и ранжирования объектов встречаются при решении широкого круга задач. Одним из основных направлений, где данные задачи возникают наиболее часто, является теория принятия решений. При этом в последнее время при решении указанных задач часто используются эвристические алгоритмы, а именно метод анализа иерархий (МАИ), предложенный Саати [1, 2]. Однако этот метод предполагает наличие достаточно полной информации о сравниваемых при принятии решений объектах, поэтому сейчас активно развиваются его модификации, нивелирующие данный недостаток.

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

Большинство исследователей [3–5] решают задачу многокритериального принятия решений с неполной информацией, используя следующую двухшаговую процедуру. На первом шаге формируется задача многокритериального принятия решений с полной информацией путем дополнения отсутствующих значений матрицы решений, используя механизм обучения [3, 4] или эвристические правила [5]. На втором шаге применяются стандартные методы многокритериального принятия решений для выполнения задачи с полной информацией.

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

Основные понятия и определения

Приведем определения основных понятий, используемых в работе [6].

Пусть G есть произвольное множество с элементами gÎG; P(G) – класс подмножеств G, причем Æ, GÎP(G), E1 – числовая прямая.

Определение 1. Мерой возможности p называется функция множества p: P(G)®E1, обладающая свойствами p(Æ)=0, p(G)=1; , , "I, где I – любое индексное множество.

Определение 2. Триплет (G, P(G), p) называется возможностным пространством.

Введем понятие меры необходимости, двойственной мере возможности.

Определение 3. Мерой необходимости m называется функция множества m: P(G)®[0, 1], определяемая по следующей формуле: m(A)= =1–p(Ac), где Ac есть дополнение A.

При этом функцию m называют функцией доверия и обозначают Bel, а функцию  называют функцией правдоподобия и обозначают Pls.

Функции Bel(A) и Pls(A) интерпретируются как пессимистическая и оптимистическая оценки события A. Интервал [Bel(A), Pls(A)] называется доверительным интервалом.

Определение 4. Множество Q всех взаимоисключающих событий в G называется фреймом различия. Возможными гипотезами являются все возможные подмножества Q, их количество |2Q|.

Для агрегирования независимых доверий относительно одних и тех же гипотез используется правило Демпстера [7], согласно которому агрегированные доверия к гипотезам находятся посредством вычисления ортогональных сумм:

m1⊕m2(A)=,                      (1)

где  – нормировочная константа, интерпретируемая как мера конфликта при агрегировании доверий m1 и m2.

Используя свойство ассоциативности правила Демпстера (1), m1⊕(m2⊕m3)=(m1⊕m2)⊕m3, осуществляется агрегирование трех и более независимых доверий.

Формализация метода

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

Пусть А={Ai | i=1, ..., n} – множество альтернатив решений, а С={Cj | j=1, ..., q} – множество критериев решений.

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

Для этого каждую группу альтернатив решений будем сравнивать с фреймом различия (все множество альтернатив) по каждому из критериев, и эксперт определит степень «благоприятного знания» для каждой из этих групп альтернатив [8, 9]. Данный факт является принципиальным отличием от метода МАИ, в котором парные сравнения проводятся между отдельными альтернативами. Количество групп альтернатив отображает количество знаний эксперта по данному критерию. К альтернативам, находящимся в одной группе, полагается (имеет место) одинаковое доверие, то есть эксперт не обладает достаточными знаниями для их различения. Кроме того, для агрегирования весов альтернатив по множеству критериев используется правило Демпстера вместо дистрибутивного и идеального методов, применяемых в МАИ.

В итоге метод состоит из семи этапов [8, 9]:

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

2)    нахождение точечных весов критериев по методу собственного вектора МАИ;

3)    формирование групп альтернатив относительно критериев, при этом к альтернативам, находящимся в одной группе, имеется одинаковое доверие;

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

5)    нахождение значений функций базового распределения доверия mj(∙) для групп альтернатив и фрейма по каждому из критериев j=1, ..., q методом главного собственного вектора;

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

7)    расчет значений полного доверия Bel(∙) и правдоподобия Pls(∙), построение доверительных интервалов для групп альтернатив.

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

,  (2)

где di=diQ – количественное выражение степени преобладания группы альтернатив Si над фреймом Q; r – количество групп альтернатив по рассматриваемому критерию; wc – вес критерия. Записывая нули в соответствующие позиции МПП (2), полагаем, что парные сравнения между различными группами альтернатив не производятся.

Значения функции базового распределения доверия mj(∙) для групп альтернатив и фрейма вычисляются как элементы собственного вектора МПП (2), отвечающего наибольшему собственному числу этой матрицы. Используя уравнения det(Dr+1–lIr+1)=0, Dr+1w=lmaxw, нетрудно доказать следующие утверждения.

Утверждение 1. Наибольшее собственное число МПП (2) равно .

Утверждение 2. Элементы нормированного главного собственного вектора MПП (2), соответствующие ее наибольшему собственному числу lmax, равны

                        (3)

Величины wi, i=1, 2, …, r+1, вычисленные по формулам (3), являются значениями функции базового распределения доверия по критерию m(Si)=wi, i=1, 2, …, r, m(Q)=wi+1.

Определение 5. Мерой неполноты экспертной информации по критерию назовем величину m(Q) базового доверия к фрейму по рассматриваемому критерию.

Определение 6. Мерой неполноты экспертной информации по множеству критериев С={Cj | j=1, ..., q} назовем величину (m1⊕m2⊕…⊕mq)(Q) базового агрегированного доверия к фрейму.

В результате применения метода каждой группе альтернатив Si (альтернативе в частном случае) ставится в соответствие доверительный интервал [Beli, Plsi] (рис. 1).

Поскольку значение полного доверия Beli показывает «точное» доверие к группе Si в отличие от значения правдоподобия Plsi, которое, в свою очередь, показывает величину максимального доверия, которое может быть по возможности назначено Si, в данной работе предлагаются следующие два метода ранжирования групп альтернатив:

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

–      ранжирование, полученное при сравнении доверительных интервалов [Beli, Plsi].

Метод ранжирования групп альтернатив по их доверительным интервалам

Пусть [Beli, Plsi] и [Belj, Plsj] – доверительные интервалы групп альтернатив Si и Sj соответственно. Введем понятие степени нестрогого преобладания интервала для Si над интервалом Sj: p(Si≥Sj)∈[0, 1]. Вычисление значений p(Si≥Sj) будем осуществлять на основе следующих аксиом:

p(Si≥Sj)= =

Матрица степеней нестрогого преобладания Р={(pij=p(Si≥Sj)) | i, j=1, …, n}, где n – количество групп альтернатив, которые необходимо ранжировать, имеет следующие свойства: pij∈[0, 1], pij+pji=1, pii=1/2.

В соответствии с введенными pij метод ранжирования состоит в следующем:

–      вычисление суммы степеней преобладания Si над всеми остальными группами альтернатив: pi=Spij,  j=1, …, n;

–      ранжирование групп альтернатив в соответствии с убыванием значений pi.

Пример

Рассмотрим модельную задачу оценивания моделей альянсов между банками и страховыми компаниями в соответствии с двумя группами критериев: финансовые (С1) и риски (С2) [10]. К финансовым, например, были отнесены такие критерии, как необходимый кредитный капитал, инвестиционные возможности, управление продажами, управление связями с клиентами, соотношение доходы–затраты, логика прибыли, источники конфликтов, экономия вследствие роста масштабов производства и портфеля услуг. Выполним ранжирование десяти альтернативных моделей альянсов M1, М2, МЗ, М4, М5, М6, М7, М8, М9, М10, используя оценки эксперта по указанным двум группам критериев (далее – критериям) (см. табл.).

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

Данные экспертные оценки доверия к каждой группе выполнены в 7-точечной шкале 1–7, где крайние значения шкалы означают соответственно «очень слабое доверие» и «абсолютное доверие».

В соответствии с методом по формулам (3) для каждого критерия вычисляются значения базового распределения доверия. Например, для критерия С1 весом w1c=0,6 эти значения равны: m1(S11)= =0,072, m2(S12)=0,360, m1(S13)=0,144, m1(S14)=0,216, m1(Θ)=0,208. Следующий этап – агрегирование maggr=m1⊕m2 доверий по критериям по правилу Демпстера (1). Затем вычисляются значения полных доверий и правдоподобий.

Доверительные интервалы групп альтернатив в данном примере равны: {M1}:[0,083, 0,359], {M2}: [0,163, 0,319], {M8}:[0,165, 0,489], {М9}:[0,033, 0,224], {M1, M8}:[0,393, 0,572], {М5, М7}:[0,053, 0,209], {М6, М8}:[0,260, 0,489], {M1, М9, М10}: [0,163, 0,452], {М2, М5, М7}:[0,288, 0,372], {МЗ, М4, М9}:[0,093, 0,224]. Вычислим матрицу P= ={(pij=p(Si>Sj)) | i, j=1, ..., n}, n=10 степеней нестрогого преобладания для этих групп альтернатив, и найдем ранжирование, которое будет следующим: {М8}>{M2}>{M1}>{М9}, {M1, М8}> >{М6, М8}>{М5, М7}, {M2, М5, М7}>{M1, М9, М10}>{МЗ, М4, М9}.

Отметим, что значение базового агрегированного доверия, равное maggr(Θ)=0,085, в соответствии с определением 3 является мерой неполноты экспертной информации по множеству критериев. Таким образом, уровень неопределенности данной задачи принятия решений составляет 8,5 %.

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

Литература

1.     Saaty T.L., Theory of the Analytic Hierarchy Process, 2003, Part 2.1, no. 1, pp. 48–72.

2.     Saaty Т.L., European Journ. of Operational Research, 2003, no. 145 (1), pp. 85–91.

3.     Fortes I., Mora-L'opez L., Morales R., Triguero F., Math. and Comp. Modelling, 2006, no. 44, pp. 790–806.

4.     Hong T.P., Tseng L.H., Wang S.L., Expert Systems with Applications, 2002, no. 22, pp. 285–293.

5.     Quinten A., Raaijmakers W., Educational and Psychological Measurement, 1999, no. 59 (5), pp. 725–748.

6.     Yazenin A.V., Wagenknecht M., BUTC-UW, 1996, Vol. 6, 143 p.

7.     Dempster A.P., Journ. of the Royal Statistical Society, Series B, 1968, no. 30, pp. 205–247.

8.     Beynon M.J., Curry B., Morgan P.H., Omega, 2000, no. 28 (1), pp. 37–50.

9.     Beynon M.J., European Journ. of Operational Research, 2002, no. 140, pp. 148–164.

10.  Korhonen P., Voutilainen R., European Journ. of Opera­tional Research, 2006, no. 175 (2006), pp. 1285–1299.

11.  Beynon M.J., Computers & Operations Research, 2005, no. 32, pp. 1881–1896.

12.  Beynon M.J., European Journ. of Operational Research, 2005, no. 163, pp. 403–417.

13.  Beynon M.J., Group Decision and Negotiation, 2006, no. 15, pp. 21–42.