Содержание к диссертации
Введение
Глава 1. Методы многокритериального выбора 16
1.1. Процесс принятия решений 16
1.2. Задачи выбора, упорядочивания и классификации многокритериальных альтернатив 25
1.3. Методы принятия решений, использующие числовые показатели 29
1.4. Методы вербального анализа решений 35
1.5. Сопоставление методов принятия решений 41
Глава 2. Снижение размерности пространства качественных при знаков 44
2.1. Проблема снижения размерности признакового пространства и методы ее решения 44
2.2. Формализация понятия составного критерия 51
2.3. Построение шкалы составного критерия 55
Глава 3. Интерактивные методы снижения размерности при- знакового-пространства г-т—r-r-т-т т-г~. -гт~~. ~гт~. Т~Т7 7 Т". 59
3.1. Метод снижения размерности ИСКРА 59
3.2. Метод порядковой классификации ПАКС 65
3.3. Способы оценки эффективности методов 70
Глава 4. Программные средства 74
4.1. Архитектура компьютерной системы 74
4.2. Режимы системы 74
4.3. Интерфейс системы 81
Глава 5. Практическое применение 85
5.1. Многокритериальная оценка результативности научных проектов 85
5.2. Многокритериальный выбор вычислительных кластеров 95
5.3. Многокритериальная оценка кредитного риска в коммерческом банке 108
Заключение 113
Приложение А. Оценка результативности целевых фундамен тальных исследований 115
Список таблиц 120
Список иллюстраций 121
Литература 123
- Задачи выбора, упорядочивания и классификации многокритериальных альтернатив
- Формализация понятия составного критерия
- Метод порядковой классификации ПАКС
- Многокритериальный выбор вычислительных кластеров
Введение к работе
Актуальность темы диссертации. Достаточно часто в задачах многокритериального принятия решений — выделении лучших вариантов, ранжировании и классификации альтернатив — необходимо сравнивать объекты, которые характеризуются разнообразными признаками: техническими, экономическими, политическими, эксплутационными и иными. Примерами таких задач служат оценка результативности научных проектов [71, 72], выбор вычислительных кластеров [83], оценка риска при выдаче банковских кредитов [49] и др.
Методы и подходы к решению задач многокритериального выбора и классификации разработаны в трудах отечественных и зарубежных ученых: С.А. Айвазяна [77], В.А. Глотова [14], Н.Г. Загоруйко [19], Л. Заде [20], Д. Канема-на [24], Э. Квейда [25], Р.Л. Кини [27], Г. Крона [31], О.И. Ларичева [37], Б.Г. Литвака [42], А.В. Лотова [30], В.Д. Ногина [59], Л.М. Местецкого [48], Дж.А. Миллера [51], Б.Г. Миркина [52], А.И. Орлова [64], В.В. Павельева [14], А.Б. Петровского [69], В.В. Подииовского [74], ДА. Поспелова [75], И. Пфанцагля [79], X. Райфы [27], А.С. Рыкова [87], Т. Саати [89], П. Словика [24], В.Л. Стефанюка [97], С.С. Стивенса [46], А. Тверски [24], В.К. Финна [100], И.Ф. Шахнова-[44] -и-другиХт-Эти-методы-различаются способами получения~об^ работки и представления информации о свойствах объектов и предпочтениях лица, принимающего решение (ЛПР).
Вместе с тем непосредственная классификация или сравнение альтернатив, описываемых большим числом признаков, и в особенности качественных признаков, является трудоемкой процедурой, которая требует значительных временных затрат ЛПР, что нередко существенно затрудняет применение на практике методов принятия решений. Когда же сравниваемых объектов мало (3-5), а их признаки различны по значениям и многочисленны (десятки и
сотни), такие объекты, как правило, оказываются формально несравнимыми по своим свойствам.
Исследования в области когнитивной психологии продемонстрировали склонность людей использовать различные способы «группировки информации» применительно к проблемам выбора, в которых объекты описываются большим числом признаков. Так, при решении задач классификации большой размерности ЛПР зачастую применяет различные упрощенные стратегии с использованием только части критериев, что облегчает построение границ классов решений, но может негативно повлиять на выработку решающих правил и дальнейший анализ полученных результатов.
Эти обстоятельства диктуют необходимость разработки специальных методов обработки информации, обеспечивающих решение задач многокритериального выбора и классификации в пространствах большой размерности.
Одним из способов преодоления указанных трудностей при сравнении многокритериальных объектов является сокращение размерности признакового пространства и использование дополнительных, психологически корректных операций получения информации от ЛПР и экспертов. Специальные исследования показали, что человеку легче сравнивать объекты по небольшому числу показателей, результаты таких сравнений более надежны и их проще анализировать. Человек более надежно и с меньшим числом ошибок оперирует с качественными, вербальными данными, нежели с количественными, числовыми.
Для упрощения процедуры сравнения и/или классификации многопризнаковых объектов по их свойствам при решении задачи выбора ЛПР должен иметь в своем распоряжении соответствующий инструментарий, который позволяет агрегировать большое число характеристик объектов в небольшое число критериев, имеющих небольшие вербальные шкалы оценок, отражающие предпочтения ЛПР. Перечисленное выше обусловливает актуальность
проведения исследований, разработку методов и процедур снижения размерности признакового пространства и их программную реализацию.
Цели и задачи исследования. Целью диссертации является разработка методов интерактивного снижения размерности пространства, образованного дискретными качественными (вербальными) признаками, которые позволяют существенно сократить трудоемкость применения на практике различных нормативных методов принятия решений (классификации, ранжирования, выбора наилучшей многокритериальной альтернативы) и предоставляют ЛПР дополнительные возможности для содержательного анализа полученных результатов решения проблемы.
Для достижения поставленной цели в диссертационной работе поставлены и решены следующие задачи:
проведен критический анализ современных методов многокритериального принятия решений, ориентированных на задачи стратегического и тактического выбора, и особенностей их применения в большом признаковом пространстве;
рассмотрены существующие методы снижения размерности признакового пространства и возможности их использования в слабо структурируемых задачах принятия решений, для которых характерно сочетание количественных и качественных зависимостей;
предложен методологический подход к снижению размерности признакового пространства, обеспечивающий решение слабо структурируемых задач многокритериальной классификации и выбора;
разработаны интерактивные методы и алгоритмы снижения размерности признакового пространства, использующие разные способы кон-
струирования шкал составных критериев более высокого уровня иерархии;
предложены процедуры анализа полученных результатов для разных способов многокритериального выбора с целью оценки качества выработанных решений;
созданы программные средства, реализующие предложенные методы и алгоритмы, проведена их апробация при решении практических задач.
Методы исследования. Методы теории принятия решений, теории множеств и мультимножеств, теории графов, теории измерений, системного анализа, искусственного интеллекта и когнитивной психологии.
Результаты, выносимые на защиту:
Методологический подход к снижению размерности признакового пространства, облегчающий и упрощающий решение слабо структурируемых задач многокритериальной классификации и выбора.
Модель формирования составного критерия и конструирования его шкалы как средство содержательного выражения предпочтений ЛПР.
-- Интерактивный^ метод~ИСКРА~~(Иёрархическая Структуризация КРи-териев и Атрибутов), обеспечивающий последовательное снижение размерности признакового пространства и сочетающий при построении шкал составных критериев разные способы ранжирования и/или классификации многомерных альтернатив исходя из предпочтений ЛПР.
Интерактивный метод ПАКС (Последовательное Агрегирование Классифицируемых Состояний) порядковой классификации альтернатив,
оцененных по многим качественным критериям с вербальными шкалами, объединяющий разные способы последовательного агрегирования исходных признаков.
Программная реализация предложенных методов, алгоритмов и про
цедур и их применение при решении практических задач поддержки
принятия решений.
Научная новизна:
Предложено понятие составного критерия, позволяющее ЛПР конструировать его шкалу с использованием комбинации различных методов принятия решений.
Предложен математический аппарат для формализации понятия составного критерия, основанный на теории графов и теории мультимножеств.
Разработан новый интерактивный метод ИСКРА снижения размерности признакового пространства, в котором различные комбинации признаков разного уровня иерархии рассматриваются как многопризнаковые объекты, последовательно агрегируемые на основе предпочтений ЛПР в составные критерии с небольшими вербальными шкалами.
Разработан новый интерактивный метод ПАКС порядковой классификации многокритериальных альтернатив, использующий последовательное снижение размерности пространства признаков с помощью разных способов построения решающих правил.
Предложены процедуры сопоставления и анализа решений задач многокритериального выбора, полученных с использованием разных способов
формирования составных критериев, которые позволяют ЛПР оценить качество полученного решения проблемы.
Обоснованность и достоверность научных положений обеспечиваются анализом современного состояния исследований в области многокритериального принятия решений, подтверждаются корректностью предложенных моделей, алгоритмов и согласованностью результатов, полученных при практической реализации этих моделей и алгоритмов, а также апробацией основных теоретических положений в печатных трудах и докладах на российских и международных научных конференциях.
Практическая ценность работы. Предложенные методы снижения размерности признакового пространства использованы при решении практических задач: многокритериальная оценка результативности научных проектов, многокритериальный выбор вычислительных кластеров, многокритериальная оценка степени риска при выдаче банковских кредитов.
Разработанный метод ИСКРА может быть использован на практике совместно с другими нормативными методами принятия решений, препятствием к применению которых служит большое число признаков, описывающих объекты. Предложенная концепция может быть применена для анализа данных в системах OLAP (OnLine Analytical Processing), при разработке различных интегральных показателей, например, индикатора благосостояния человека, индекса общественного здоровья и других социальных индикаторов.
Реализация результатов. Результаты диссертации использованы при выполнении проектов РФФИ 98-01-00086 (1998-2000 гг.), 99-01-00476 (1999-2001 гг.), 00-15-96053 (2000-02 гг.), 01-01-00514 (2001-03 гг.), 01-01-06321 (2001-03 гг.), 02-01-06286 (2002-04 гг.), 02-01-01077 (2002-04 гг.), 03-01-06441 (2003 г.), 04-01-00290 (2004-06 гг.), 05-01-00666 (2005-07 гг.), 06-07-89352 (2006-08 гг.), 07-07-13546 (с 2007 г.), 08-01-00247 (с 2008 г.); проектов по программам фун-
даментальных исследований президиума РАН «Математическое моделирование и интеллектуальные системы» (2001-05 гг.), «Фундаментальные проблемы информатики и информационных технологий» (2006-08 гг.) и ОНИТ РАН «Фундаментальные основы информационных технологий и систем» (2003-08 гг.); гранта Президента Российской Федерации для поддержки ведущих научных школ НШ1964.2003.1 (2003-05 гг.); проекта № 3 научного сотрудничества между Российской академией наук и Академией Финляндии (2000-02 гг.).
Апробация работы. Результаты, представленные в работе, обсуждались и докладывались на: 3-й Московской международной конференции по исследованию операций (Москва, 4-6 апреля, 2001 г.); международном конгрессе «Искусственный интеллект в XXI веке» (Дивноморское, Краснодарский край, 3-8 сентября 2001 г.); 4-й, 5-й, 6-й и 7-й международных научных конференциях «Интеллектуализация обработки информации» (Алушта, Украина, 17-21 июня 2002 г., 14-19 июня 2004 г., 4-11 июня 2006 г., 9-14 июня 2008 г.); 8-й, 9-й, 10-й и 11-й национальных конференциях по искусственному интеллекту с международным участием (Коломна, 7-12 октября 2002 г., Тверь, 28 сентября - 2 октября 2004 г., Обнинск, 26-28 сентября 2006 г., Дубна, 29 сентября - 3 октября, 2008 г.); международной конференции «DSS in the Uncertainty of the Internet Age» (Катовице, Польша, 13-16 июля 2003 г); международных
конференциях «Интеллектуальныесистемы» (Дивноморское,_Краснодарский—
край, 3-Ю сентября 2003 г., 3-Ю сентября 2005 г., 3-9 сентября 2007 г.); 58-й международной конференции Европейской рабочей группы «Помощь в многокритериальном принятии решений» (Москва, 9-11 октября 2003 г.); 1-й и 2-й Международных конференциях «Системный анализ и информационные технологии» (Переславль-Залесский, 12-16 сентября 2005 г., Обнинск, 10-14 сентября 2007 г.); 14-й международной конференции «Знания-Диалог-Решения» (Варна, Болгария, 23 июня - 6 июля 2008 г.); 20-й международной конференции по системным исследованиям, информатике и кибернетике (Баден-Баден,
Германия, 24-30 июля 2008 г.); научных семинарах ИСА РАН.
Во введении обосновывается актуальность диссертационной работы, формулируется ее цель, научная новизна, приводятся полученные результаты, решенные практические задачи и структура работы.
Первая глава является обзорной. Описан процесс принятия решений,
показаны роли основных участников (ЛПР, экспертов, аналитика) при реше
нии проблемы. Приведены основные типы задач принятия решений. Особо
выделены слабо структурируемые задачи, в том числе задачи стратегическо
го выбора, в которых объекты представлены большим числом количествен
ных и качественных признаков при доминировании последних. Рассмотрены
группы методов решения задач многокритериального выбора, упорядочения
и классификации, представляющие различные направления в теории приня
тия решений, в том числе использующие числовые показатели. Основное вни
мание уделено группе методов вербального анализа решений, разработанных
в ИСА РАН, ориентированных на решение слабо структурируемых задач.
Проведен критический анализ достоинств и недостатков разных групп мето
дов. Отмечено, что представленные методы неудовлетворительно работают
в большом пространстве признаков. Показано, что недостатки методов при
нятия решений при работе с объектами, характеризуемыми большим числом
признаков, мог}^бъггь устранены ситомощью самих же^методов
Во второй главе изложен методологический подход к снижению размерности признакового пространства. Дана постановка задачи снижения размерности признакового пространства. Представлены различные методы снижения размерности признакового пространства, указаны препятствия к их использованию применительно к слабо структурируемым задачам принятия решений. Предложены модель формирования составного критерия и конструирования его шкалы как средство содержательного выражения предпочтений ЛПР и математический аппарат для формализации понятия составного
критерия с использованием теории графов и теории мультимножеств. Подчеркнут многодисциплинарный характер задачи снижения размерности признакового пространства. Прослежена связь с задачами принятия решений, системного анализа, теории измерений, искусственного интеллекта и когнитивной психологии. Использование понятий графа и мультимножества позволяет выстроить единую схему формализации понятия составного критерия и по-новому решать как известные задачи, в которых есть определенные сложности (например, задачи распознавания иерархических структур), так и новые виды задач. Предложенный новый методологический подход к снижению размерности пространства качественных признаков обладает определенной универсальностью, т.к. в общем случае может оперировать как символьной (качественной), так числовой информацией. Он может быть успешно применен в сочетании с другими методами принятия решений и обработки информации.
В третьей главе описаны новые интерактивные методы: метод ИСКРА (Иерархическая Структуризация КРитериев и Атрибутов) снижения размерности признакового пространства, в котором различные комбинации признаков разного уровня иерархии рассматриваются как многопризнаковые объекты, последовательно агрегируемые в составные критерии на основе предпочтений ЛПР; метод ПАКС (Шсдадс^зат^ьнюе^^
цируемых Состояний) порядковой классификации многокритериальных альтернатив, основанный на снижении размерности пространства признаков с помощью разных способов построения решающих правил.
Схема решения задачи многокритериального выбора с использованием снижения размерности признакового пространства включает два этапа. На первом этапе проводится снижение размерности признакового пространства путем построения иерархической системы составных критериев. На втором этапе выполняется окончательное решение задачи выбора с использованием
построенных составных (агрегированных) критериев.
Агрегирование признаков базируется на предпочтениях ЛПР. Первоначально при участии ЛПР формируется базовый набор характеристик рассматриваемых объектов. В зависимости от специфики задачи эти характеристики могут быть либо заданы заранее, либо сформированы в процессе анализа проблемы. Для каждого базового показателя формируется шкала, которая может иметь числовые (точечные, интервальные) или вербальные оценки. Шкалы оценок базовых показателей могут совпадать с обычно используемыми на практике, либо конструироваться специально.
Далее, основываясь на опыте и интуиции ЛПР, базовые характеристики объединяются в критерии, обладающие вербальными порядковыми шкалами с небольшим числом градаций (3-5). ЛПР по своему усмотрению определяет число, состав и содержание критериев каждого уровня иерархии. В качестве критерия можно выбрать один из базовых показателей или несколько характеристик, объединенных в составной критерий. ЛПР устанавливает, какие базовые показатели будут считаться самостоятельными критериями, а какие будут отнесены к тому или иному составному критерию. Смысловое содержание критериев и шкал оценок определяется ЛПР. Критерии должны иметь такие шкалы оценок, которые, с одной стороны, будут отражать агре-гированнью^ачествалзбъектов, ас другой стороны, будут понятны ЛПР при окончательном выборе объекта или их классификации.
Процедура агрегирования показателей может иметь последовательный характер, т.е. полученные группы критериев могут быть, в свою очередь, объединены в новые группы (следующий уровень иерархии) и так далее. При конструировании шкал составных критериев на разных этапах могут использоваться различные подходы. Например, один из составных критериев можно сформировать при помощи метода стратификации кортежей, а другой — при помощи многокритериальной порядковой классификации.
В зависимости от специфики задачи выбора иерархическая система критериев может быть известна заранее (например, организационная структура предприятия), известна частично (например, известна только структура технических характеристик многопризнаковых объектов) и неизвестна вообще, т.е. иерархию требуется разработать «с нуля» (такая ситуация характерна, например, для задач планирования научных исследований, где присутствует высокая степень неопределенности и риска, связанная с получением нового знания). При построении системы критериев в первом случае основное внимание должно быть уделено разработке шкал составных критериев. Особенностью разработки системы критериев во втором и в третьем случаях является возможность сформировать разные наборы составных критериев различными способами (например, последовательно объединяя критерии попарно или формируя группы критериев исходя из некоторой смысловой общности). Это позволяет сравнить полученные результаты для разных вариантов классификации и выбора с целью оценки качества решения исходной проблемы.
Важной особенностью предложенного подхода к снижению размерности признакового пространства является возможность его использования практически с любым методом ранжирования или классификации многокритериальных альтернатив.
Использование метода ИСКРА при pemeimn^agaHjmoi^pj^piiaJibuo^
го выбора и классификации дает ЛПР возможность сравнить полученные решения для разных наборов составных критериев, сформированных с помощью различных подходов. В этом случае можно сравнить между собой число обращений к ЛПР, необходимых для построения полной непротиворечивой классификации для каждого набора составных критериев. Альтернативным способом оценки эффективности является сравнение распределений альтернатив по классам решений для одного и того же набора составных критериев, сформированных с помощью различных подходов. Такая методология позво-
ляет ЛПР выбрать как наиболее предпочтительный набор составных критериев, так и метод (совокупность методов) их построения в рамках решения конкретной практической задачи.
В четвертой главе описаны программные средства, реализующие предложенные методы и алгоритмы. Приведена архитектура компьютерной системы и руководство по консультирующей системе OREX. Разработанные программные средства подтверждают реализуемость предложенных методов и алгоритмов снижения размерности признакового пространства.
В пятой главе представлены практические задачи, решенные с помощью методов снижения размерности признакового пространства: многокритериальная оценка результативности научных проектов, многокритериальный выбор вычислительных кластеров и многокритериальная оценка кредитного риска. Решенные практические задачи многокритериального выбора подтверждают обоснованность, достоверность и реализуемость предложенных методов и алгоритмов снижения размерности признакового пространства.
Заключение содержит обзор основных достижений и результатов, представленных в настоящей работе.
В приложении представлены результаты оценки результативности про
ектов це лев ых _фу н д аментал ьньршсс л е д о в ан ий.
Автор считает своим долгом выразить благодарность, академику РАН, Олегу Ивановичу Ларичеву, оказавшему существенное влияние на формирование моего мировоззрения, скоропостижная смерть которого явилась невосполнимой утратой для меня лично и для научного сообщества в целом. Особую признательность хочется выразить всем моим коллегам по лабораториям «Методы и системы поддержки принятия решений» и «Компьютерные системы, основанные на знаниях» ИСА РАН за доброжелательную помощь в процессе работы над диссертацией.
Задачи выбора, упорядочивания и классификации многокритериальных альтернатив
В рамках задач многокритериального выбора выделяются две основные группы. Первая группа - это задачи стратегического выбора. Задачи стратегического выбора характеризуются следующими особенностями [37]: 1. Имеется сравнительно немного (2 V 10) вариантов решения проблемы, из которых следует выбрать один, наилучший. 2. Варианты оцениваются по многим критериям (V \К\). Среди них могут быть как количественные, так и качественные критерии, при этом последние преобладают. 3. Существует большая неопределенность в оценках вариантов по критериям, неустранимая на момент принятия решений. 4. Принимаемое решение относится к будущему и его последствия имеют долгосрочный характер. 5. Имеется лицо, принимающее решение (ЛПР), несущее основную ответственность за результат принятия решений. 6. Задачей ЛПР является выбор наилучшего варианта, соответствующего его целям. Задачи тактического выбора, представляющие вторую группу, отличаются от задач стратегического выбора, тем, что в них принимаемое решение относится к текущему моменту и рассматривать долгосрочные последствия не столь критично. Приведем конструктивную постановку задачи выбора, упорядочивания и порядковой классификации многокритериальных альтернатив [37, 49, 80]. Дано: S — целевое свойство, характеризующее специфику задачи (кредитоспособность заемщика, результативность выполнения проектов целевых фундаментальных исследований и т.п.); Задано множество альтернатив (вариантов) Vi,..., Vp, оцененных по многим критериям; Ki,..., Кт — критерии, по которым оценивается каждый объект; ХІ = {х\,... ,xf} — множество оценок (шкала) критерия КІ, упорядоченных по убыванию характерности для свойства S; \ХІ\ — 9ІІ Яг число значений оценок на шкале г-го критерия; Y = Х\ х Х2 х ... х Хт — декартово произведение шкал критериев, определяющее множество всех возможных описаний объектов, подлежащих классификации; D = {Di,. .., Dq} — множество классов решений, упорядоченных по убыванию выраженности целевого свойства S.
Требуется: Для задачи выбора определить лучшую альтернативу из Vi,..., Vp. Для задачи упорядочивания проранжировать альтернативы Vi,..., Vp. Для зада чи классификации распределить альтернативы Vi,..., Vp по классам решений Du _,Dqi Каждый объект описывается набором оценок по критериям К\,... ,Кт и представляется в виде кортежа вида yj = (2/ ,2/,2, ,Vjm), где yji Є Xit m = 1,...,УиУ = \\gi Может оказаться, что некоторые сочетания оце 2 = 1 нок по критериям являются недопустимыми, например, описывают не существующие объекты. Поэтому рассматривается множество Ya С Y кортежей оценок допустимых объектов. Обозначим множество оценок недопустимых объектов как Yb — Y\Ya, а множество оценок объектов, принадлежащих классу Dj, — через Yj. Очевидно, что - П 7 = 0, V/i 7 j. В дальнейшем множество оценок Yj для удобства отождествляется с классом Dj. Требуется, основываясь на предпочтениях ЛПР, построить отображение множества допустимых объектов Ya во множество классов D: F:Ya- D, (1.2) которое должно быть полным и непротиворечивым.
Укажем, прежде всего, что в соответствии с формальной постановкой задачи порядковой классификации многокритериальных альтернатив на каждом множестве критериальных оценок ХІ (г = 1,..., га) определено отношение порядка Qi = {{xJ x )\j fc}, а на множестве классов D — отношение порядка Qi) = {(А-, Dh)\r h}, которые являются линейными рефлексивными антисимметричными транзитивными отношениями. Введем на множестве возможных комбинаций оценок Y рефлексивное антисимметричное транзитивное отношение доминирования:
1. Методы, основанные на количественных измерениях. К этой группе относятся широко известные методы, основанные на многокритериальной теории полезности [122], а также многие эвристические методы.
2. Методы, основанные на первичных качественных измерениях, результаты которых переводятся в количественный вид. К этой группе относятся методы аналитической иерархии [89, 113], а также методы, использующие «размытые» измерения [123].
3.-Ме-тодьі,-основашіьіе-на-количественньіх-измерениях—но-использующие несколько индикаторов при сравнении альтернатив. К этой группе относятся методы сравнительного превосходства (семейство методов Электра [86, 106, 116]).
4. Методы, основанные на качественных измерениях без перехода к количественным переменным. К этой группе можно отнести ряд методов вербального анализа решений [6, 40].
Формализация понятия составного критерия
Сведем задачу снижения размерности признакового пространства к построению иерархической системы критериев, в которой различные комбинации исходных признаков (кортежи оценок) последовательно агрегируются в меньшие наборы новых признаков, имеющих для ЛПР вполне определенное содержательное значение.
Введем следующее определение. Составным критерием называется интегральный показатель, который определяет выбранное ЛПР свойство вариантов, агрегирующее исходные характеристики. Каждая градация шкалы составного критерия является комбинацией оценок исходных показателей.
Процедура агрегирования показателей является многоуровневой иерархической структурой со «слабыми» связями, в которой элемент нижележащего уровня (оценки исходных показателей) подчинен двум и более вершинам вышестоящего уровня (оценкам составных критериев). Переходя шаг за шагом на более высокий уровень иерархии, ЛПР может сконструировать приемлемые для него составные критерии вплоть до одного единственного.
Представим процедуру построения шкал составных критериев в виде однотипных блоков. Блоки содержательно выделяются ЛПР в зависимости от специфики решаемой задачи. Каждый блок классификации г-го уровня иерархии состоит из некоторого набора признаков и одного составного критерия. В качестве объектов классификации выступают все градации оценок на шкалах признаков. Классами решений г-го уровня служат градации оценок на шкале составного критерия.
В блоке классификации (г+1)-го уровня иерархии составные критерии г го уровня считаются признаками, множество градаций оценок которых представляет собой новые объекты классификации в сокращенном признаковом пространстве, а классами решений будут теперь градации оценок на шкале составного критерия (г+1)-го уровня. Процедура повторяется до тех пор, пока не останется единственный составной критерий верхнего уровня, шкала оценок которого образует искомые упорядоченные классы решений D\,..., Dq, где q — число классов.
Тем самым устанавливается соответствие между классами решений D\,..., Dq и совокупностью исходных показателей — множеством Х\,..., Хт всех возможных комбинаций градаций оценок на шкалах критериев Xi = {xj,..., xf}, і = 1,..., m, критериев Ki,... , Кт и находятся границы классов, что позволяет легко построить классификацию реальных альтернатив Vi,...,Vp, гдер — число альтернатив (вариантов), оцененных по многим критериям. Для формирования шкал оценок по составным критериям ЛПР может воспользоваться несколькими процедурами.
Рассмотрим подробнее математический аппарат оперирования иерархическими структурами. Во многом это определяется центральной ролью иерархических структур в рамках системных исследований [92]. Существует несколько форм представления иерархий: матричная, теоретико-множествен-ная (например, с использованием таксонов [19]), графическая (например, «деревья» целей, «деревья» решений [43], стратифицированные иерархии [47]), с использованием языка типологии и ряд других. Каждый блок г-го уровня иерархии представляет собой связный двудольный граф Gi = (U, -Ё1), где U — вершины графа, Е — дуги. Множеством вершин U — X U Y являются значения исходных признаков X = {Х\ U... UХт} и градации шкал составных критериев Y = {УІ U ... U У }.
Дуги Е графически выражают наборы решающих правил, на основании которых выстраиваются кортежи оценок, формирующих градации шкал со ставных критериев (фактически это одна из форм смысловой интерпретации предпочтений ЛПР). Между одними и теми же вершинами, относящимися к разным множествам, имеет место кратность дуг, т.е. граф d является муль-тиграфом (рис. 2.1). Способы построения кортежей оценок подробно рассматриваются ниже.
Размерность матрицы смежностей М для графа d равна (\Х\ х \Y\) или (S 2 9i х 5j )- Матрица смежностей М представлена на рисунке 2.2. В каж дой ячейке матрицы записывается сколько раз оценка х , где е = 1,..., г — 1,...,тп (оценка базового признака), встречается в кортежах, которые формируют комбинации оценок, образующих градацию шкалы составного критерия щ1, где fj — 1,..., hj, j = 1,..., п. Одним из очевидных свойств матрицы является то, что сумма по столбцу у-1 должна быть кратна т.
Использование понятий графа и мультимножества позволяет выстроить единую схему формализации понятия составного критерия, представленную на рисунке 2.3. Формализация иерархических структур в виде мультимножеств дает возможность по-иовому решать известные задачи [19], такие как измерение близости [81] и сопоставление, и задачи с решением которых есть определенные сложности, например, распознавание иерархических структур, за счет использования новых, недоступных ранее операций, введенных в теории мультимножеств [69].
Метод порядковой классификации ПАКС
Напомним постановку задачи многокритериальной порядковой классификации. Задано множество альтернатив (вариантов) Vi,..., Vp, оцененных по многим качественным критериям. Каждый критерий Кг имеет упорядоченную дискретную шкалу ХІ — {х\,... ,xfl}, г = 1,... , т. Градации шкалы критерия описываются развернутыми словесными формулировками, которые упорядочены ЛПР, например, от лучшей оценки к худшей, от более характерной для некоторого свойства к менее характерной. Заданы упорядоченные классы (категории) Di,...,Dq, где q — число классов. Требуется разбить исходную совокупность многопризнаковых объектов по классам, то есть построить полную классификацию кортежей оценок.
Для решения подобной задачи разработан метод ПАКС (Последовательное Агрегирование Классифицируемых Состояний), в котором используется последовательное сокращение размерности признакового пространства. В качестве классифицируемых объектов выступают комбинации оценок исходных показателей, а классами решений являются градации оценок составного критерия. Для построения шкал составных критериев применен метод ИСКРА с однотипной процедурой классификации на каждом иерархическом уровне.
Рассмотрим построение шкал составных критериев на модельном примере. Исходное множество альтернатив описывается восемью критериями (базовыми признаками) К±,... ,К$,, имеющими шкалы ХІ с двумя или тремя вербальными порядковыми оценками 0,1,2, где 0 обозначает лучшую оценку, 1 - среднюю (или худшую), 2 - худшую. Требуется разбить множество альтернатив на пять упорядоченных классов D\,..., D$ (рис. 3.3).
Например, критерий К\ характеризует «Степень выполнения заявленных задач», которая может оцениваться как 0 - задачи выполнены полностью, 1 - задачи выполнены частично, 2 - задачи не выполнены; критерий. Кз оценивает «Достижение поставленной цели в установленные сроки» как О - реальное, 1 - нереальное. Критерии К%,..., К8 имеют следующие шкалы: Xi = {0,1,2}; Х2 = {0,1,2}; Х3 = {0,1}; Х4 = {0,1,2}; Х5 = {0,1}; 6 = {0,1}; Xi = {0,1}; Х$ = {0,1,2}. Таким образом, размерность исходного признакового пространства равна 1296. Составным критерием верхнего уровня является «Результативность», градации оценок по шкале которого {высокая, хорошая, средняя, низкая, неудовлетворительная) определяют 5 упорядоченных классов решений.
Непосредственная классификация исходного множества альтернатив требует существенных трудозатрат ЛПР. Введем три составных критерия AKj, ЛК2, ЛКэ, имеющих порядковые шкалы с тремя градациями: УІ = {0,1,2}; У2 = {0,1,2}; Уз = {0) 1.2}, где значения 0,1,2 являются вербальными оценками, определяемыми содержанием соответствующих составных критериев, и выступают как классы решений первого уровня для исходных базовых при знаков (критериев).
Допустим, что ЛПР решил агрегировать исходные признаки К\, К2, К3 в составной критерий АК\\ признаки К5, KQ, K-J - соответственно в составной критерий АКч и признаки К Kg - в составной критерий АКз- Рассмотрим подробнее возможные способы построения шкал составных критериев. Пусть для формирования шкал составных критериев для примера, представленного на рис. 3.3, ЛПР воспользовался одной из указанных выше процедур — методом ОРКЛАСС, предназначенным для построения полной непротиворечивой порядковой классификации многопризнаковых объектов. В результате опроса ЛПР для шкалы Y\ получены следующие градации оценок (классы решений с границами): у\ = 0 - класс 0 (верхняя граница: 000; нижняя граница: 100,010,001); /i = l- класс 1 (верхняя граница: 200,110,020,101,011; нижняя граница: 210,120,201,111,021); у\ = 2 - класс 2 (верхняя граница: 220,211,121; нижняя граница: 221).
Для шкал составных критериев АК и АКз получены такие градации оценок: 7/2 = 0- класс 0 (верхняя граница: 000; нижняя граница: 001); yf = 1 - класс 1 (верхняя граница: 100,010; нижняя граница: 101,011); 2/1 = 2- класс 2 (верхняя граница: 110; нижняя граница: 111); у\ = 0 - класс 0 (верхняя граница: 00; нижняя граница: ОО уІ І кл&сс вщжшія-гр&нііцд Ш ОІ-,— нижняя граница: 20,11,02); 7/3 = 2 - класс 2 (верхняя граница: 21,12; нижняя граница: 22).
Рассмотрим теперь наборы всех оценок по составным критериям как объекты классификации следующего уровня, где классами решений Z?i,..., D5 являются градации оценок шкалы Z = {21,2:2,23,24,2} составного критерия верхнего уровня иерархии. Аналогичным образом, агрегируя показатели АК\, АК2, АКз, имеем: z\ - класс D\ (верхняя граница: 000; нижняя граница: 000); 22 - класс 1 (верхняя граница: 100,010,001; нижняя граница: 110,101); 2з - класс з (верхняя граница: 200,020,011,002; нижняя граница: 211,121,202,112,022); z4 - класс DA (верхняя граница: 220,212,122; нижняя граница: 221,212,122); z5 - класс / (верхняя граница: 222; нижняя граница: 222). Таким образом, реальные альтернативы, имеющие оценки по исходным критериям, будут непосредственно отнесены при классификации к сформированным классам решений.
Многокритериальный выбор вычислительных кластеров
В настоящее время существует достаточно много прикладных и научных задач, требующих для своего решения больших вычислительных мощностей, предоставляемых суперкомпьютерными технологиями. Высокопроизводительные вычисления необходимы в самых различных областях, в таких как: нанотехнологии, обработка потоков информации в распределенных базах данных [17], автоматизация проектирования [94], компьютерное управление прризводств_еііньши_пррцессами,_анализ_фондовіЗго_рьінка,_управление„сол:о вой связью, моделирование погоды, биоинформатика, биохимия, биофизика, теплофизика, динамика жидкостей и газов, электромагнетизм, исследование генома человека, исследование прочности материалов и в других.
Необходимость в разработке более дешевой аппаратной части суперкомпьютеров побудила обратить более пристальное внимание на кластерные технологии. По определению компании Digital Equipment Corporation (DEC), кластер — это группа вычислительных машин, которые связаны между собою и функционируют как один узел обработки информации [91]. Активное развитие кластерных технологий обусловлено тем, что, используя стандартные компоненты - обычные процессоры, материнские платы, сетевые компоненты и тому подобное, которыми буквально «завален» весь мировой рынок, - стало возможным создание значительно более дешевых вычислительных комплексов не только не уступающих, но и порой превосходящих по производительности продукцию известных фирм, например, таких как Cray.
Кластеры можно разделить на две большие категории. Первая категория - кластеры высокой готовности или отказоустойчивые кластеры [28]. Для таких кластерных систем на первое место выходит понятие надежности. Вторая категория - высокопроизводительные или вычислительные кластеры. Для этой категории главным является производительность. Кластеры можно также разделить на однородные (состоящие из вычислительных узлов одной и той же конфигурации) и неоднородные (состоящие из вычислительных узлов различной конфигурации). В данной работе акцент сделан на однородные вычислительные кластеры (далее ВК).
Модульная структура ВК позволяет гибко и последовательно наращивать его производительность за счет добавления новых вычислительных узлов. При этом даже морально устаревшие модули могут использоваться и в дальнейшем. Принимая во внимание многообразие процессоров, сетевых тех нологий, про_граммных_продуктрв для.выполнения расчетов,и_томудодобное, перед конечным пользователем, заинтересованным в использовании В К для решения своих конкретных вычислительных задач, стоит достаточно непростая задача выбора конфигурации ВК.
Проблема выбора ВК, предназначенных для решения прикладных задач пользователя, рассматривается как слабоструктурированная задача многокритериального стратегического выбора. Предварительно составляется перечень возможных вариантов, из которого будет выбран наиболее предпочтительный ВК. Выбор ВК зависит от следующих основных факторов.
Используемая прикладная программа предъявляет определенные требования к характеристикам аппаратной платформы, что накладывает ограничения на выбор конфигурации ВК или отдельных компонентов ВК. Прикладная программа обусловливает также выбор операционной системы и кластерного программного обеспечения. Важность этого фактора связана с тем, что для решения задачи пригодны не все, а только вполне определенные прикладные программы, стоимость которых может быть на порядок больше, чем стоимость ВК.
Размерность счетной задачи и необходимый временной выигрыш позволяют определить требуемые производительность, минимальный суммарный объем и тип оперативной памяти, суммарный объем и тип дискового пространства. Это, в свою очередь, позволяет выбрать ту или иную базовую аппаратную платформу, а также влияет на выбор типа процессора.
Точность расчетов. Чем выше требуемая точность, тем больше времени нужно для расчета. В ряде случаев этот фактор оказывает влияние на выбор типа процессора.
Интенсивность обмена данными между вычислительными узлами позволяет выбрать технологию построения сети ВК.
Особенность рассматриваемых объектов выбора (сложные технические системы, в частности, ВК) состоит в том, что они характеризуются большим числом показателей. Поскольку вариантов немного, то обычно все варианты несравнимы друг с другом по своим характеристикам. В этой ситуации известные методы решения задачи выбора лучшего объекта оказываются неэффективными. Поэтому прежде, чем применять какой-либо метод вербального анализа решений, необходимо решить еще одну вспомогательную, но крайне важную задачу: построить процедуру, которая позволяет агрегировать большое число базовых (технических, эксплуатационных, стоимостных) характеристик ВК в небольшое число критериев, имеющих порядковые шкалы оценок (количественные и качественные). Сокращенное описание объектов позволит упростить процедуру решения исходной задачи выбора.
Выбор критериев и формирование шкал оценок проводится ЛПР самостоятельно или с привлечением системного аналитика. Предлагается следующий подход формирования набора критериев [82, 83].
Первоначально составляется перечень всех базовых показателей, характеризующих отдельные компоненты кластера, кластер в целом и условия его эксплуатации. Характеристики, описывающие ВК, можно представить в виде иерархической системы, нижним уровнем которой служат выделенные базовые показатели. Например, процессор характеризуется такими базовыми по-казателями как архит_ектура тактовая_настота,-объем-кэшавторого идрет-ье-го уровня, поддерживаемая частота системной шины. Некоторые из базовых показателей удобно объединять в составные показатели, которые выступают как оценки следующего уровня иерархии. После классификации эти общие оценки наполняются конкретным содержанием.
Следующим этапом является формирование вспомогательных шкал оценок для каждого базового показателя. Шкалы могут иметь числовые точечные, интервальные или вербальные (словесные) оценки. Шкалы оценок могут совпадать с обычно используемыми на практике, либо конструироваться специально для данного критерия. Например, производительность ВК оценивается в Гфлопсах, стоимость - в млн. рублей. Для сокращения размерности описания объекта часто бывает удобно перейти от непрерывной шкалы оценки к дискретной шкале, имеющей небольшое число оценок на шкале, и от количественной шкалы к качественной шкале. Например, можно оценивать стоимость оценками «низкая», «средняя», «высокая», указав для каждой из оценок соответствующие интервалы величин. Все сформированные оценки ЛПР упорядочивает от лучшей к худшей.
Далее ЛПР по своему усмотрению определяет число и состав критериев, их содержание. В качестве критерия можно выбрать один из базовых показателей (например, производительность, стоимость) или несколько характеристик, объединенных в составной критерий. ЛПР устанавливает, какие технические и эксплуатационные показатели будут считаться самостоятельными критериями, а какие будут отнесены к тому или иному составному критерию. Шкалы простых критериев, являющихся базовыми показателями, уже построены на предыдущем этапе. Для формирования шкал оценок по составным критериям можно воспользоваться несколькими процедурами.
При формировании шкалы оценок составного критерия важно учесть, что одна часть характеристик, входящих в состав подобного критерия, может рассматриваться_как_самрстоятельная а другая часть характеристик может _ быть составной. Поэтому процедура построения шкалы составного критерия сама может состоять из нескольких этапов.
На основе анализа литературы [1, 21, 28, 83, 88, 95] был предложен список характеристик ВК, которые разделены на несколько групп. К первой отнесем технические характеристики кластера (процессор, базовая аппаратная платформа, технология построения сети, оперативная память, дисковая память). Используемая операционная система и кластерное программное обеспечение составляют вторую группу. Производными от них является третья группа показателей: производитель технических и программных средств; производительность кластера; стоимость кластера (группа «Обобщенные характеристики»). И, наконец, в последнюю группу «Эксплуатационные характеристики» входят: энергопотребление, тепловыделение, уровень шума и условия окружающей среды.
Исходя из базовых характеристик ВК, были предложены четыре критерия оценки ВК и разработаны шкалы их оценок. В качестве самостоятельных критериев для сравнения ВК были выбраны две базовые характеристики: стоимость и производительность кластера. Двумя другими являются составные критерии: возможность модернизации и сложность эксплуатации кластера, сконструированные из базовых характеристики и составных критериев нижнего уровня (рис. 5.4 и рис. 5.5). Для построения шкал составных критериев использовался метод ИСКРА. Рассмотрим особенности шкал составных критериев.
