Упорядочивание объектов на основе парных сравнений на подмножествах критериев

Размещено на http://www.allbest.ru/

ИСА РАН

Упорядочивание объектов на основе парных сравнений на подмножествах критериев

И.В. Ашихмин iva@isa.ru

Г.В. Ройзензон, rgv@isa.ru

117312, Москва, проспект 60-летия Октября, д.9

Аннотация

В докладе^{** Работа выполнена при финансовой подержке РФФИ (проекты № 0015-96053 и № 01-01-06321)} рассматривается задача упорядочивания небольшого числа объектов. Предлагаемый подход к решению этой задачи базируется на принципах вербального анализа решений. Представлен общий алгоритм решения и примеры.

Введение

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

Вопрос о том, насколько последовательны и рациональны люди в принятии таких решений, исследовался в большом числе работ [Russo et al., 1975], [Montgomery et al., 1989], [Payne et al., 1993], [Larichev, 1992], [Korhonen et al., 1997].

Результаты дескриптивных исследований можно сформулировать следующим образом:

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

Предлагаемый подход базируется на принципах заложенных в методах вербального анализа решений [Ларичев, 1996].

Основная цель настоящей работы заключается в представлении специальной процедуры, основанной на вышеизложенных принципах, для решения задачи упорядочивания объектов, характеризующихся оценками по многим критериям. Предлагаемая процедура [Furems et al., 2001], [Ашихмин и др., 2001] имеет следующие особенности:

Все парные сравнения, осуществляемые ЛПР, имеют качественный характер ("лучше", "хуже", "одинаково");

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

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

1. Основные обозначения

A={A_i} -- множество из N объектов. Предполагается, что N -- небольшое число (5-10).

Объекты характеризуются оценками по M критериям С = {С^j} j{1,..,M}.

Множество номеров критериев K={1,…,M}.

Каждый i-й объект из A может быть представлен M-мерным набором соответствующих ему оценок по критериям из С: A_i=(a¹_i,a²_i,...,a^M_i), где a^j_i - оценка объекта A_i по критерию C^j.

Шкала оценок по критерию C^j: V^j={v^jk}, k=1,..,K^j, где K^j -- число оценок на шкале критерия С^j.

2. Подход к решению

2.1 Основная идея: декомпозиция

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

Как уже упоминалось во введении, чем больше число критериев, по которым оцениваются объекты, тем человеку сложнее их сравнивать.

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

2.2 Независимость критериев по предпочтению и транзитивность

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

Кроме того, будем считать, что, если альтернативы a, b и c находятся в следующих отношениях: a b и b c, то a c, где «» означает «лучше» (транзитивность).

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

2.3 Правило «сложения» отношений

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

E, F K -- подмножества множества номеров критериев.

H=EF -- критерии, общие для E и F.

a^E ,b^E -- наборы оценок по критериям E.

c^F ,d^F -- наборы оценок по критериям F.

Пусть a^E b^E, c^F d^F, при попарно равных оценках по критериям K\E и K\F, соответственно.

Тогда, если b^Hc^H, где `' -- равенство оценок по соответствующим критериям из H, то при условии независимости критериев по предпочтению и транзитивности отношения a^E b^E и c^F d^F можно «сложить», т.е.

(a^E b^E)(c^F d^F)( a^Ec^F\E b^E\Fd^F)

Действительно, a^Ec^F\E b^Ec^F\E=b^E\Fb^Hc^F\Eb^E\Fc^F b^E\Fd^F, т.е. a^Ec^F\E b^E\Fd^F.

Если H=, то (a^E b^E)(c^F d^F)= (a^Ec^F b^Ed^F).

Не всегда верно, что (a^E b^E)(c^F d^F) = (c^F d^F)(a^E b^E).

Заметим, что запись a^E b^E подразумевает попарно равные оценки по критериям K\E. Следовательно, если в результате сложения получаются одинаковые оценки по некоторым критериям, их можно опустить. Это можно сделать, т.к. в соответствии с предположением о независимости критериев по предпочтению можно заменить эти оценки любыми попарно равными.

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

(a^E b^E)(c^F d^F)( a^E\Qc^F\E b^E\Fd^F\Q), где QH и a^Qd^Q.

Q может быть пустым множеством.

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

2.4 Выявление противоречий

Кроме того, правило «сложения» отношений можно использовать для выявления нарушений транзитивности и/или независимости критериев по предпочтениям (противоречия). Целесообразно после каждого ответа ЛПР проверять, не стала ли совокупность отношений, полученных к данному моменту, противоречивой. Заметим, что в случае обнаружения противоречий, ошибочным необязательно является последний ответ, хотя он и участвует в противоречии, так как до него система была проверена на непротиворечивость [Гнеденко и др., 1990].

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

2.5 Транзитивное замыкание

Все трудности, связанные с выводом отношений между объектами и поиском противоречий, легко решаются с помощь построения транзитивного замыкания [Ахо и др., 2000] множества отношений, полученных на основании ответов ЛПР. Во-первых, в транзитивное замыкание попадают непосредственно спрошенные отношения. При этом, если какие-то критерии не входят в описание сравниваемых альтернатив, по ним в правой и левой частях отношения проставляются всевозможные попарно равные оценки. Далее, если на полученном в результате опроса множестве отношений можно, в предположении транзитивности предпочтений ЛПР, получить новое отношение, оно включается в транзитивное замыкание. Кроме того, если это отношение содержит одинаковые оценки в левой и правой части, то они также заменяются всевозможными комбинациями парно равных оценок. Транзитивное замыкание содержит отношения между объектами, описываемыми всеми критериями.

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

2.6 Транзитивное квазизамыкание

Отношения a^E b^E и c^F d^F будем называть пересекающимися, если EF.

Введем понятие транзитивного квазизамыкания (ТКЗ). ТКЗ строится из ответов ЛПР последовательным применением правила сложения только к пересекающимся отношениям и включает, в том числе, сами ответы. Если в результате сложения получились альтернативы с попарно одинаковыми оценками по одному или более критериям, эти критерии убираются из отношения.

Например, в транзитивное квазизамыкание множества отношений

v¹₁v²₁ v¹₂v²₂, v³₁v⁴₁ v³₂v⁴₂, v²₂v³₃ v²₃v³₁,

войдут, кроме вышеуказанных, отношения:

v¹₁v²₁v³₃ v¹₂v²₂v³₁, v²₂v³₃v⁴₁ v²₃v³₁v⁴₂.

Как мы видим, отношение v¹₁v²₁v³₁v⁴₁ v¹₂v²₂v³₂v⁴₂ не вошло в ТКЗ.

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

Правила вывода выражений.

Сумма НЭТКЗ :- ЭТКЗ.

Сумма НЭТКЗ :- Сумма НЭТКЗ ЭТКЗ | xНЭТКЗ xЭТКЗ=.

Сумма НЭТКЗ1 ЭТКЗ1 :- Сумма НЭТКЗ2 ЭТКЗ2 | xНЭТКЗ2 xЭТКЗ2, НЭТКЗ1= НЭТКЗ2\x, ЭТКЗ1=x ЭТКЗ2.

ЭТКЗ :- исходное отношение.

ЭТКЗ :- x y | xТКЗ, yТКЗ, xy.

ЭТКЗ :- (ЭТКЗ).

Сумма НЭТКЗ :- (Сумма НЭТКЗ).

Сумма НЭТКЗ - сумма непересекающихся элементов транзитивного квазизамыкания.

ЭТКЗ - элемент транзитивного квазизамыкания.

xСумма НЭТКЗ - x является слагаемым в «Сумма НЭТКЗ».

Неочевидным является преобразование 3.

Пусть Сумма НЭТКЗ1= (c^Q1₁ d^Q1₁) (c^Q2₂ d^Q2₂) ... (c^Qm_m d^Qm_m),

ЭТКЗ1= (e^Q f^Q),

где ij QiQj= и пусть QkQ.

Тогда оценки в левой части отношения ЭТКЗ2 по критериям Q\Qk не отличаются от оценок ЭТКЗ1 по этим критериям. Таким образом, результат сложения не зависит от порядка добавления элементов «Сумма НЭТКЗ1» слева к ЭТКЗ1. После применения правила 3 мы либо получим «Сумму НЭТКЗ», либо выражение, к которому можно снова применить 3. Этот процесс конечен, т.к. в результате каждого применения правила 3 НЭТКЗ1 становится на одно слагаемое меньше.

Приведенные правила вывода выражений позволяют содержимое любой пары соответствующих скобок привести к «Сумме НЭТКЗ». Из этого прямо следует приведенное выше утверждение.

2.7 Разбор противоречий с помощью транзитивного квазизамыкания

Утверждение 2. Если добавление одного ответа ЛПР делает систему противоречивой, то транзитивное замыкание множества ответов содержит отношение, обратное этому ответу.

Для доказательства используется следующая лемма.

Лемма 1. Имеются отношения a^Eb^E, c^Fd^F, e^Gf^G, причем

(a^Eb^E) (c^Fd^F) = (e^Gf^G).

Тогда (f^Ge^G) (a^Eb^E) = (d^Fc^F), (c^Fd^F) (f^Ge^G) = (b^Ea^E).

3. Общий алгоритм решения задачи

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

Назовем альтернативу "реальной", если она составляет часть набора оценок объекта из множества A.

Далее формируется перечень всех возможных "реальных" двухкритериальных альтернатив (этап 2):

Для всех j₁, j₂ K, j₂ j₁ ^j1,j2 = {(a^j1_i, a^j2_i) | i = 1,..,N}

После того как множества ^j1,j2 сформированы, ЛПР должен, в соответствии со своими предпочтениями упорядочить альтернативы, принадлежащие этим множествам (этап 3):

1)Если a^j1_i a^j1_k и a^j2_i a^j2_k (информация, полученная на первом этапе), то (a^j1_i, a^j2_i) (a^j1_k, a^j2_k);

2)Если a^j1_i a^j1_k и a^j2_i a^j2_k, то пара (a^j1_i, a^j2_i) и (a^j1_k, a^j2_k) предъявляется ЛПР для сравнения.

При этом ЛПР, имеет возможность дать следующие ответы: (1) -- (a^j1_i, a^j2_i) (a^j1_k, a^j2_k), (2) -- (a^j1_i, a^j2_i) (a^j1_k, a^j2_k), (3) -- (a^j1_i, a^j2_i) (a^j1_k, a^j2_k), (4) -- «Не знаю».

Каждый ответ ЛПР проверяется на непротиворечивость по отношению к предыдущим ответам.

На этапе 4 осуществляется вывод отношений между объектами на основе предпочтений ЛПР, выявленных на этапе 3 (правило «сложения» см. п. 3.3). Если поставленная задача решена, то окончание процедуры, в противном случае переход к этапу 5.

На следующем этапе (5) осуществляется формирование всех возможных "реальных" трехкритериальных альтернатив:

Для всех j₁, j₂, j₃ {1,..,M}, j₃ j₂ j₁ ^j1,j2,j3 = {(a^j1_i, a^j2_i, a^j3_i), i = 1,..,N}.

На этапе 6 для всех j₁, j₂, j₃ {1,..,M}, j₃ j₂ j₁ осуществляется упорядочение альтернатив из ^j1,j2,j3 в соответствии с предпочтениями ЛПР. Если поставленная задача решена, то окончание процедуры, в противном случае переход к следующему этапу. При этом формируются четырехкритериальные альтернативы и т.д.

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

Заключение

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

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

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

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

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

Список литературы

1. Ларичев, 1996 Ларичев О.И., Мошкович Е.М. Качественные методы принятия решения. - М.; Физматгиз, 1996.

2. Russo et al., 1975 Russo, J. E., L. D. Rosen: An eye fixation analysis of multiattribute choice, Memory and Cognition., 3 (1975) 267-276.

3. Montgomery et al., 1989 Montgomery, H., O. Svenson: «A think-aloud study of dominance structuring in decision processes», In: H. Montgomery, O. Svenson (eds.), Process and Structure on Human Decision Making, J. Wiley and Sons, Chichester 1989, pp. 135-150.

4. Payne et al., 1993 Payne, J. W., J. R. Bettman, E. Coupey, E. J. Johnson: «A constructive process view of decision making: multiple strategies in judgment and choice», In: O. Huber, J. Mumpower, J van der Pligt, P. Koele (Eds.), Current Themes in Psycological Decision Research, North Holland, Amsterdam 1993, pp. 107-142.

5. Larichev, 1992 Larichev, O. I.: Cognitive validity in design of decision-aiding techniques, Journal of Multi-criteria Decision Analysis, 1, 3(1992)127-138.

6. Korhonen et al., 1997 Korhonen, P., O. Larichev, H. Moshkovich, A. Mechitov, J. Wallenius: Choice behavior in a computer-aided multiattribute decision task, Journal of Multi-criteria Decision Analysis, 6 (1997) 233-246.

7. Furems et al., 2001 Furems E., Larichev O., Lotov A., Miettinen K., Roizenson G.: Human choice with individually difficult tasks, Труды 3-й Московской международной конференции по исследованию операций (ORM2001), Москва, 4-6 апреля 2001 года.

8. Ларичев, 2000 Ларичев О.И.: Теории и методы принятия решений, а также хроника событий в волшебных странах. Москва, Логос, 2000, стр. 182-183.

9. Ахо и др., 2000 Ахо А., Хопкрофт Дж., Ульман Д.: Структуры данных и алгоритмы. Издательский дом «Вильямс», Москва, 2000, стр. 194-195.

10. Гнеденко и др., 1990 Гнеденко Л.С., Фуремс Е.М.: Эффективная процедура выявления нарушений транзитивности при попарных сравнениях. Сборник трудов ВНИИСИ т. 10, Москва, 1990, стр. 46-58.

11. Ашихмин и др., 2001 Ашихмин И.В., Ройзензон Г.В. Выбор лучшего объекта на основе парных сравнений на подмножествах критериев, в «Методы поддержи принятия решений», под ред. академика Ларичева О.И., Москва, УРСС, 2001.

Размещено на Allbest.ru