Программные продукты и системы

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

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

В Петербургском государственном университете путей сообщения работа над системой с перечисленными свойствами ведется в течение 10 лет. За этот период было разработано и внедрено в учебном процессе и на практике несколько редакций системы выбора и ранжирования СВИРЬ [2]. В настоящей статье описываются свойства последней редакции системы, названной СВИРЬ-Р, с учетом возможности ее реконфигурации.

Модель многокритериального выбора

Модель выбора в системе, реализующей различные методы многокритериальной оптимизации и классификации, должна быть инвариантна по отношению к этим методам. Данному требованию отвечает теоретико-множественная модель [3]:

Mв=.                                    (1)

Она содержит:

·     множество оцениваемых альтернатив (объектов) X;

·     множество функций F, характеризующих различные свойства объектов;

·     области определения и значений Y функций из множества F;

·     множество целей (целевых состояний) H, задаваемых для оцениваемых признаков;

·     отношения предпочтения (предикаты) P, определяемые на множествах X, F, Y, H;

·     степень соответствия li,k альтернативы xi целевому состоянию hk.

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

При сопоставлении альтернатив xi и xk, xi, xkÎX, истинность двухместного предиката Pord(xi, xk) означает, что xixk. Если предикат Pord(xi, xk)=false(0), то имеет место либо обратное предпочтение xixk, либо равнозначность xiºxk сравниваемых альтернатив. Бинарное отношение RordÌX´X является решением задачи выбора на языке бинарных отношений. При критериальном выборе каждой альтернативе xi ставится в соответствие величина yjÎY, отражающая j-е свойство альтернативы и вычисляемая с применением функции fj: X®Y. Отношение RordÌX´X формируется на основе количественных оценок альтернатив, то есть отношения RcordÌY´Y.

Для нахождения наилучшей альтернативы выполняется ранжирование отношения Rord. Оно заключается в присвоении каждой альтернативе xiÎX целого числа из диапазона [1, N]: RnumÌX´N, Rnum={(xi,1),…,(xk,r),…,(xs,N)}, где N=çXç. Число r задает рейтинг (ранг) альтернативы – указывает ее место по предпочтению среди остальных альтернатив.

Модель (1) предоставляет всю необходимую информацию для решения задач отбора, упорядочения и классификации объектов в n-мерном пространстве признаков.

Создание и редактирование модели выбора

Отношение RисхÌX´F, которое характеризует исходные данные, представляется таблицей «Объекты/Признаки». Строки таблицы образуют объекты из множества X, а столбцы – признаки из множества F. Клетки таблицы заполняются значениями признаков yij=fj(xi). Таким образом, i-й объект, i=, характеризуется вектором значений yi=(yi1, …,yij,…,yin), поэтому второе название таблицы – «Характеристика объектов».

Таблица «Объекты/Признаки», описывающая заданную предметную область (ПрО), либо создается в системе СВИРЬ-Р с клавиатуры, либо вводится из табличного процессора MS Excel или из типовой СУБД. При создании с клавиатуры задаются размерность таблицы (число строк и столбцов), имя ПрО, имена объектов и признаков. Данные в таблицу могут заноситься с клавиатуры или из названных систем при условии совпадения имен вводимых объектов и признаков с именами, введенными в таблицу.

При формировании иерархической модели дочерние таблицы создаются на основе признаков таблиц предыдущего уровня иерархии (технология построения сверху вниз). Режим создания таблицы нижнего уровня выбирается правой кнопкой мыши. В появляющемся окне задаются число и имена детализирующих признаков. Структура модели выбора представляется деревом таблиц. Для отображения дерева иерархии в левой части главного окна системы СВИРЬ используется стандартное средство Tree-View операционной системы MS Windows.

Редактирование модели осуществляется перемещением признаков из одной таблицы в другую с помощью технологии drag-and-drop. Она же применяется для подчинения (переподчинения) одной таблицы другой в дереве иерархии.

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

Для формулирования задач выбора в системе СВИРЬ-Р используется контекстно-зависимый интерфейс. В его основу положены два класса задач: многокритериальной оптимизации и классификации. Методы оптимизации, в свою очередь, тоже делятся на два класса: методы векторной и скалярной оптимизации. Методы векторной оптимизации различаются отношением доминирования, реализуемого на векторных оценках объектов: Парето-доминирования, лексиминного и лексикографического (метод приоритета критериев). Первые два метода характеризуются минимальным использованием экспертной информации, но не гарантируют получение линейного порядка объектов при решении задачи упорядочения. Качество решения задачи упорядочения характеризуется показателями доминирования, неразличимости и несравнимости объектов, а также коэффициентом полноты порядка [3].

Методы скалярной оптимизации реализуются с применением обобщающих функций и матриц парных сравнений (МПС). Для обобщения однородных признаков, измеряемых в одной шкале, используются функции Байеса и Гурвица, а для обобщения неоднородных признаков применяются аддитивная, две мультипликативные (с прямыми и дополнительными сомножителями) и минимаксная функции.

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

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

Требования к признакам

Формирование требований к признакам зависит от решаемой задачи и глубины проникновения в предметную область. При решении задач упорядочения объектов на основе признаков формируются критерии оптимизации. Если ЛПР неизвестно пороговое значение признака, формируется целевой критерий, а если известно – ограничительный [3]. Для целевого критерия задается направление оптимизации (min или max), а для ограничительного критерия – ограничение значения признака снизу, сверху, в точке или интервале. По умолчанию этим критериям ставятся в соответствие функции полезности – линейные и кусочно-линейные. Если ЛПР известна информация о приращении полезности признака, линейные функции полезности преобразуются в нелинейные. Для выполнения нормализации признака задаются границы его шкалы. Они формируются либо ЛПР, либо автоматически, по выборке объектов.

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

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

Анализ модели и результатов выбора

В системе СВИРЬ-Р предусмотрены различные табличные и графические средства анализа. Анализ независимости критериев осуществляется с помощью корреляционной матрицы. Результаты многокритериального выбора выводятся в таблицу «Решение». В графической форме представляются: функции полезности и принадлежности классам, графы зависимости признаков и графы доминирования объектов, многокритериальные оценки полезности, вклад в них различных критериев, сравнительные оценки рейтинга объектов, полученных различным способом, деревья иерархии признаков и весовых коэффициентов в иерархии. Для пояснения результатов используются специальные таблицы, а для их различения – цветовая окраска.

Выделение ресурсов под задачи выбора

Под выделяемым ресурсом понимается одна или группа функций системы, использование которых требует специального разрешения. Ресурсы системы делятся на внешние и внутренние. Их выделение осуществляется по-разному. Внешние ресурсы, оформленные в виде динамических библиотек, включаются в комплект поставляемой программной системы. Внутренние ресурсы входят в состав исполняемой программы СВИРЬ-Р. Они делятся на следующие группы: отбор объектов, критерии оценивания, скалярная оптимизация, обобщающие функции, векторная оптимизация, классификация, критерии классификации, иерархия, сервисные функции.

Базовая конфигурация системы СВИРЬ-Р представляет собой совокупность ресурсов, требующихся для проектирования модели выбора, решения контрольной задачи и обмена информацией с процессором MS Excel. В качестве контрольной задачи принята задача нахождения рейтинга объектов относительно общей цели. Для выполнения лабораторного практикума по теории принятия решений [4] выделяются ресурсы для применения всех методов выбора с ограничением на размерность модели и на сервисные функции.

Литература

1.   Микони С.В. Теория и практика рационального выбора. М.: Маршрут, 2004. 462 с.

2.   URL: www.pgups.ru/nauka/mikoni/ (дата обращения: 10.07.2009).

3.   Микони С.В. Многокритериальный выбор на конечном множестве альтернатив: учеб. пособие. СПб: Лань, 2009. 273 с.

4.   Микони С.В., Гарина М.И. Лабораторный практикум по дисциплине «Теория принятия решений»: учеб. пособие. СПб: ПГУПС, 2009. 97 с.