Аксиоматическое построение взвешенной многокритериальной оценки и анализ альтернатив развития когнитивной системы.

Евстегнеев Д. В, Ледащева Т.Н. (tledascheva@mail.ru ) Российский Университет дружбы народов

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

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

x(k)=x(0)+p(0)(E+ А + А 2+... + А k-1). (1)

Здесь х(0) - вектор значений вершин орграфа до придания системе начального импульса, р(0) - вектор величин начальных изменений значений вершин (начальный импульс), x(k) - вектор значений вершин после k шагов прохождения импульса по системе, А - матрица смежностей вершин, составленная из весовых коэффициентов орграфа. Если система содержит N вершин, то x(k)eRN, p(0)eRN, А - матрица размера NxN. Вектор х(0) для удобства считают тривиальным. Более подробные сведения о взвешенных орграфах можно найти в [2], [3].

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

При выполнении условия устойчивости системы мы можем найти полную реакцию системы на начальный импульс, перейдя к пределу по k-oo в формуле (1). Считая, что состояние системы оценивается при помощи набора n показателей, являющихся значениями части вершин системы, для каждого начального импульса р(0)=(4ь.. .,4N) имеем, таким образом, вектор полной реакции системы ар=(ар1,...,ар ), где api = lim x :(k) .

Рассматривая единичные векторы начальных импульсов pi(0)=ei gRn, находим соответствующие векторы полной реакции системы аг=(аг-;,...,аг>г),

a-- = lim pi (0) B(k-1) = lim bk~l, где B(k 1)=(bijk 1)= Е+А+А2+...+АкЛ Нетрудно убедиться,

k-oo k-oo

что p(0) = £4-У(0), ар =£4-al .

i=1 i=1

Будем называть совокупность векторов р(0) и ар альтернативным вариантом развития орграфа или альтернативой: Ар=(р(0), ар) eRN+n, а альтернативы Ai=(pi(0), ai) - базовыми альтернативами. Из сказанного выше следует, что множество альтернатив является линейной оболочкой множества базовых альтернатив.

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

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

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

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

Пусть имеется конечное множество альтернатив, оцениваемых при помощи n факторов. Каждой альтернативе а соответствует вектор a в n-мерном пространстве, координатами которого являются значения факторов для этой альтернативы: a(a1, ,an). Факторы считаются независимыми, что позволяет рассматривать пространство факторов как евклидово пространство, и, для простоты, имеющими равную значимость для принятия решения. Для каждого фактора Pi можно построить ранжировку Pi альтернатив из множества А: будем обозначать aPib, если альтернатива a предпочтительнее альтернативы b по фактору i (т.е. значение соответствующей координаты вектора а выше в случае, если требуется максимизировать значение фактора i и ниже в противном случае). Для обозначения набора ранжировок (Pi,...,Pn) будем использовать термин профиль . Основной проблемой является определение по данному профилю наилучшей альтернативы или, что является зачастую более трудной задачей, согласованной ранжировки, т.е. упорядочения по предпочтению всех альтернатив. Правило построения согласованной ранжировки по профилю называется функцией согласования [2]. Если задана функция полезности, то правило согласования задается естественным образом: в согласованной ранжировке более предпочтительной является альтернатива с большим значением функции полезности.

В рассматриваемой нами ситуации многофакторного анализа аксиомы Эрроу принимают следующий вид.

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

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

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

Аксиома 2 (независимость несвязанных альтернатив): Пусть А - произвольное подмножество множества альтернатив А. Если при изменении профиля результаты попарных сравнений среди элементов А сохраняются, то согласованные ранжировки, получающиеся для исходного и измененного профиля, на альтернативах из А должны совпадать.

Аксиома 3 (значимость факторов): Для каждой пары альтернатив a и b существует профиль, для которого в согласованной ранжировке а предпочтительнее b.

Аксиома 4 (отсутствие доминирующего фактора): Не существует такого фактора, что если относительно него а предпочтительнее b при любых а и b из А, то и в согласованной ранжировке а предпочтительнее b, независимо от результатов сравнений по другим факторам.

Имеет место следующая теорема [2 с.382]:

Теорема Эрроу о невозможности. Пусть множество альтернатив А содержит не менее трех элементов, количество факторов n не менее двух и Pn(A) - множество всех профилей на А для n факторов. Тогда функции согласования, определенной на Pn(A) и удовлетворяющей аксиомам 1-4, не существует.

Причиной такого положения может быть недостаточная обоснованность аксиом. Рассмотрев систему аксиом более критично, мы можем убедиться, что аксиомы 1, 3, 4 представляют собой естественные условия для того, чтобы функция согласования была объективной и учитывала все факторы. Что же касается аксиомы 2, утверждающей, что результаты попарных сравнений альтернатив, не входящих в подмножество А, и их сравнений с альтернативами из А, не связаны с результатами сравнений альтернатив из А, то на первый взгляд она кажется обоснованной. Однако при более глубоком анализе оказывается, что эта аксиома ошибочна. Нетрудно привести примеры ситуаций, в которых эта аксиома оказывается противоречащей нашим представлениям о справедливости. Это связано с тем, что она исключает из рассмотрения количественные данные относительно результатов сравнения альтернатив, которые иногда называют интенсивностью предпочтения альтернатив. Введение этой информации в структуру аксиомы при качественном ранжировании альтернатив, как в теории группового принятия решений, затруднительно и может привести к значительному ее усложнению. Но применительно к нашей задаче это можно сделать, например, следующим образом.

Прежде всего, определим понятие интенсивности предпочтений.

Определение. Назовем интенсивностью сравнения значений альтернатив ao(a1, ,an) и bo- (b],...,bn) на факторе Pk инвариант группы преобразований множества альтернатив вида:

ф(а)=еш+р, а>0, p=(pb..., pn) .

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

Аксиома 2 теперь может быть заменена следующей аксиомой:

Аксиома 2 (независимость несвязанных альтернатив): Пусть А - произвольное подмножество множества альтернатив А. Если при изменении профиля интенсивности попарных сравнений среди элементов А сохраняются, то согласованные ранжировки, получающиеся для исходного и измененного профиля, на альтернативах из А должны совпадать.

Определить, совпадают ли интенсивности сравнений двух альтернатив в разных профилях, достаточно просто: это выполняется в том и только том случае, если найдутся такие числа а>0, Рpn, что векторы a, bзначений альтернатив a и b в одном профиле получены из векторов a, b в другом соответственно при помощи указанного преобразования.

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

- для каждого фактора Pk (k=1,...,n) строится матрица парных сравнений, элемент Syk принимается равным 1, если альтернатива аi предпочтительнее альтернативы аj при сравнении только по фактору Pk и 0 в противном случае;

- далее все матрицы парных сравнений суммируются;

- оценкой альтернативы аi называется сумма элементов i-й строки суммарной матрицы парных сравнений.

Заметим, что полученная оценка совпадает с оценкой по правилу Борда, известному в теории группового принятия решений. Пусть величина Bk(a) равна числу альтернатив, расположенных ниже альтернативы а в ранжировке Pk, и BfaEBa). Оценка В(а) называется числом Борда для альтернативы а. Функция согласования Борда определяется следующим образом: в согласованной ранжировке а выше b тогда и только тогда, когда В(а) больше, чем B(b).

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

Рассмотрим множество альтернатив, занимающих n-мерный параллелепипед в пространстве факторов, ограниченный гиперплоскостями Pk= Pkmin, Pk= Pkmax, k=1,..,n. Обобщая подход метода парных сравнений для оценки альтернативы a(a1, ,an), для

ТО = 2 ~k (2),

где ak - координаты вектора состояний, нормированные по формулам

k е /1

a - pk

pk - pk 1 max 1 min

P - a

pk - pk max min

(3).

k е / 2

Рассмотрим теперь две альтернативы а^ц,...,ain) и аjO(aj1, ,ajn)и сравним их оценки по полученным формулам. Теперь можно ввести в метод парных сравнений для конечного множества альтернатив веса, определяя элементы матриц парных сравнений так:

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

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

каждого фактора Pk вычислим меру множества альтернатив, которые хуже альтернативы a при сравнении только по фактору Pk - это объем n-мерного параллелепипеда:

rk (a) = (ak - pJin) -П (Pl - Pim), k е /i

l * k

rk (a) = (Pl - ak ) П (Piax - Piin), k е /2, l * k

где I1 и I2 - множества факторов, для которых предпочтительно соответственно наибольшее и наименьшее значения.

Сложив эти числа и разделив на объем исходного параллелепипеда, получаем оценку в

Утверждение. Пусть и(а) = У ak , ak = 3

pk pk 1

1 max 1 min max min

где Qk (k=1,.. .,n) - произвольные числа. Тогда оценка U(a) эквивалентна оценке W(a) (то есть приводит к такой же согласованной ранжировке на любом конечном множестве альтернатив).

Есть основания полагать, что класс оценок U(a) охватывает все возможные оценки, удовлетворяющие аксиомам 1, 3, 4, 2 с приведенным выше определением интенсивности сравнений. (Другому определению интенсивностей будет соответствовать другой класс оценок.) В таком случае определяемая этим классом оценок функция согласования в свою очередь будет обладать свойством единственности.

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

Рассмотрим множество альтернатив с ограниченным импульсом:

Q1=(Ap p = yAjp1 (0), У < 1}. Для оценки альтернатив из этого множества применим

/=1 i=1

формулы (2), (4). Оказывается, если взять в формуле (4) Qk = 0 (k=1,...,n), то оценка произвольной альтернативы Ар может быть приведена к виду линейной комбинации оценок базовых альтернатив:

и(Ар ) = улр (Ai).

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

NN и(Ар) = -U(At) max, у\Ц < 1

i=1 i=1

с ограничениями типа неравенств

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

принципиально важным для построения функции полезности по формуле (2). Более того, справедливо следующее

Литература

[1] Прангишвили И.В. Системный подход и общесистемные закономерности. М: СИНТЕГ, 2000

[2] Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука , 1986

[3] Горелов В.И., Карелова О. Л. Математическое моделирование в экологии. М.: изд. РУДН,

2000

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

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

u(A р ) = Е vJapj, j=1

где V - вес фактора P При этом все рассмотренные ранее свойства оценки сохраняются.