Поддержка выбора лучшего объекта на основе независимости критериев по предпочтениям и транзитивности

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

поддержка выбора лучшего объекта на основе независимости критериев по предпочтениям и транзитивности Работа частично поддержана грантом Президента Российской Федерации по поддержке ведущих научных школ НШ1964.2003.1, Российским фондом фундаментальных исследований (проекты 01-01-00514, 02-01-01077), Российской академией наук (программы фундаментальных исследований РАН «Математическое моделирование и интеллектуальные системы» и ОИТВС РАН «Фундаментальные основы информационных технологий и систем»).

О.И. Ларичев, И.В. Ашихмин,

Г.В. Ройзензон, Е.М. Фуремс

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

многокритериальный выбор дискретный предпочтение

Введение

Широко распространенной задачей в повседневной деятельности человека является задача выбора лучшего (наиболее предпочтительного для ЛПР) объекта из их сравнительно небольшого (3-10) набора. Практическими примерами таких задач являются выбор покупателем товара в магазине, выбор квартиры для съема или покупки, выбор университета для поступления и т.д. При этом люди, как правило, сравнивают характеристики рассматриваемых объектов по ряду важных для них аспектов (критериев), стремясь найти лучший объект. Однако в реальных ситуациях редко встречается объект, превосходящий другие по всем критериям или хотя бы не уступающий им, что, как показывают результаты дескриптивных исследований [1, 2, 3, 4, 5], делает задачу выбора весьма сложной для присущей человеку системы переработки информации, причем сложность увеличивается с ростом числа критериев. Решая такие задачи, человек совершает ошибки, а также использует различные упрощающие стратегии в желании найти компромисс между достоинствами и недостатками сравниваемых объектов. В связи с этим, представляется целесообразной разработка методов, помогающих человеку в сравнении многокритериальных объектов.

Предлагаемая система поддержки принятия решений (СППР) UNICOMBOS (Unit COMparison for the Best Object Selection) реализует новую процедуру сравнения многокритериальных объектов и выбора из них наилучшего. Эта процедура основана на принципах вербального анализа решений (BAР) [6].

Вербальный анализ решений ориентирован на так называемые слабо структурированные задачи, где качественные и субъективные факторы доминируют.

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

Подход к решению задачи выбора. Постановка задачи и основные обозначения

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

A={a_i} - множество из N объектов.

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

K={1,…,M} - номера критериев.

S^j={s^j_m}, m=1,..,m^j - шкала оценок по критерию С^j, где m^j -- число оценок на шкале критерия С^j.

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

Требуется выбрать подмножество A*A, ?aA*, ?bA, такого, что b более предпочтителен, чем a, т.е. в множестве A нет объекта, более предпочтительного для ЛПР чем какой-либо объект из A*. Кроме того, мы ставим задачу минимизировать число несравнимых объектов в A*. Однако во многих случаях не удается получить отношение предпочтения для некоторых пар исходных объектов из-за ограничений на число критериев, по которым отличаются объекты, предлагаемые ЛПР для сравнения (см. 3.2).

Информация о предпочтениях

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

Частичные описания объекта по критериям из DK будем называть D-блоком (или, для простоты, блоком).

Для некоторого объекта a=(a¹,…,a^M), aA, его D-блок, будем записывать в виде

a^D=(¹,…, ^N) iK ⁱ=aⁱ, если iD, ⁱ=, иначе,

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

Например, для объекта a=(a¹, a², a³, a⁴, a⁵, a⁶) его {2,4}-блоком будет

a^{2,4}=(, a², , a⁴, , ),

Важно отметить, что не предполагается сравнение D-блока с E-блоком, если DE.

Выражение a^Db^D означает, что ЛПР предпочитает совокупность оценок aⁱ, iD, совокупности оценкок bⁱ, iD, в предположении попарно равных оценок по критериям C^j, jD.

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

Будем считать, пока не обнаружится обратное, что предпочтения ЛПР между D-блоками не зависят от соответственно равных оценок по остальным K\D критериям, и, кроме того, что бинарные отношения между D-блоками обладают свойством транзитивности, т.е, например, если x^D y^D и y^D z^D, то x^D z^D.

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

Правило комбинирования отношений

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

Пусть a^I - I-блок, b^J - J-блок, I, J, G K, IJ=. Будем обозначать

a^Ib^J =(¹,…, ^M) iK ⁱ=aⁱ, если iI, ⁱ=bⁱ, если iJ, ⁱ=, иначе.

a^G =(¹,…, ^M) iK ⁱ=aⁱ, если iIG, ⁱ=, иначе.

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

H=EF - номера критериев, общих для E и F.

u^E ,v^E -E-блоки.

x^F ,y^F -F-блоки.

QH - номера критериев, общих для E и F, по которым u^Q=y^Q.

Пусть u^E v^E, x^F y^F, при попарно равных оценках по критериям K\E и K\F, соответственно.

Тогда, если v^H=x^H, то, при условии независимости критериев по предпочтению и транзитивности, отношения u^E v^E и x^F y^F можно «скомбинировать», т.е.

(u^E v^E) (x^F y^F) (u^Ex^F\E v^E\Fy^F)

Действительно, u^Ex^F\E v^Ex^F\E=v^E\Fv^Hx^F\E=v^E\Fx^F v^E\Fy^F, т.е. u^Ex^F\E v^E\Fy^F.

Если H=, то (u^E v^E)(x^F y^F)= (u^Ex^F v^Ey^F).

Приведенное выше правило комбинирования отношений не обладает свойством коммутативности, т.е. не всегда верно, что (u^E v^E) (x^F y^F) = (x^F y^F)(u^E v^E).

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

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

(u^E v^E) (x^F y^F)(u^E\Qx^F\E v^E\Fy^F\Q), где QH и u^Qy^Q.

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

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

Возможные противоречия

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

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

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

Противоречие может возникнуть не только из-за ошибки ЛПР при сравнении объектов, но и оказаться следствием зависимости критериев по предпочтению и/или нетранзитивности предпочтений ЛПР.

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

Система поддержки принятия решений UNICOMBOS

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

Структуризация

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

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

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

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

На рис. 1 показан экран UniComBOS структуризации задачи выбора отеля для отдыха.

Рисунок 1. Структуризация проблемы

Процедура опроса

На этом этапе СППР предлагает ЛПР блоки для сравнения.

Опрос начинается с попарного сравнения блоков размерности один, а затем система приступает к попарному сравнению блоков размерности два.

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

Рисунок 2. Сравнение блока размерности 2

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

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

Напомним, что система переходит к сравнению блоков размерности три только после сравнения всех блоков размерности два и один. Следовательно, системе "известно", какие блоки размерности один и два в каждой паре блоков размерности три ЛПР считает лучшими, а какие худшими, и она может выделить их соответствующими цветами (см. Рис. 3).

Рисунок 3. Сравнение блоков размерности 3

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

Например, блок a^{{1, 2, 3}} можно декомпозировать так:

a^{1}a^{2,3}, или

a^{1,2}a^{3}, или

a^{3}a^{1,2}

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

Рисунок 4. Сравнение тех же блоков в другом представлении

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

Заметим, что пока в системе предусмотрено сравнение блоков размерности не больше трех. В дальнейшем предполагается динамически определять максимальную сложность (размерность) вопросов индивидуально для каждого ЛПР на основании того, насколько хорошо он справляется с такими вопросами (дает идентичные ответы при разном представлении блоков в паре)^** Каждая четверка может быть представлена четырьмя разными способами, пятерка - пятью и т.д..

Анализ и исправление противоречий

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

Рисунок 5. Анализ противоречия

Представление и объяснение результатов сравнения

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

Рисунок 6. Результаты

Рисунок 7. Дерево вывода

Техническая реализация системы

СППР UniComBOS имеет клиент-серверную архитектуру. Сервер обрабатывает подсоединения java-аплетов и хранит все данные о пользователях (ЛПР) и решаемых ими проблемах. Клиентское приложение предназначено для работы ЛПР с проблемой, автоматизированного опроса с целью выявления предпочтений ЛПР и анализа его предпочтений. Клиент и сервер реализованы на языке программирования JAVA с помощью среды разработки Forte^tm for Java^tm4 CE фирмы Sun Microsystems. Данные хранятся и пересылаются по сети в формате XML.

Вы можете поработать с системой, загрузив JAVA-аплет со страницы http://iva.isa.ru.

Заключение

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

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

Литература

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

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.

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.

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

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.

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

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

Льюис Р. Д., Райфа Г. Игры и решения. М.: ИЛ, 1961.

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

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

Furems E.M., Larichev O.I., Roizenson G.V., Lotov A.V., Miettinen K.: Human behavior in a multi-criteria choice problem with individual tasks of different difficalties, International Jornal of Information Technology & Decision Making Vol.2, No. 1 (March 2003).

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

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