double arrow

Методы решения многокритериальных задач выбора

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

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

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

Аддитивная свертка (от англ. addition – сложение) имеет вид

, (5.3.1)

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

, (5.3.2)

т.е. наилучшим считается решение, которому соответствует максимум общего критерия на множестве альтернатив.

Мультипликативная свертка (от англ. multiplication – умножение) применяется в двух формах:

, (5.3.3)

или

, (5.3.4) где – знак произведения. Первая из этих форм используется гораздо чаще, чем вторая. Наилучшее решение определяется выражением

. (5.3.5)

Максминная свертка (выбор по наихудшему критерию) имеет вид

. (5.3.6)

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

, (5.3.7)

причем множитель не имеет значения, так как сравнение альтернатив выполняется в шкале порядка. Наилучшее решение определяется выражением (5.3.5). Подставив в (5.3.5) выражение (5.3.6), получим

, (5.3.8)

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

Метод пороговых критериев часто применяется в задачах обеспечения (удовлетворения), например при планировании и проектировании, когда ограничения задаются в виде

;,…,, (5.3.9)

где – пороговые значения критериев. Их совокупность обычно характеризует некоторый аналог (базовый уровень). Образуем свертку, (5.3.10)

тогда наилучшее решение определяется выражением вида (5.3.5).

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

, (5.3.11)

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

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

. (5.3.12)

В качестве меры расстояния используются различные функции, например, Махалобиса, Минковского. При использовании функции Минковского

(5.3.13)

или с учетом веса критериев

. (5.3.14)

При получаем расстояние Хемминга, при – евклидово расстояние, при – расстояние по максимальному различию, при – расстояние по минимальному различию. Выбор параметра зависит от условий задачи и предпочтений ЛПР. Отметим, что если в качестве идеального решения использовать не абсолютный максимум, а абсолютный минимум, то в выражении (5.3.12) операция изменится на операцию.

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

, (5.3.15)

т.е. альтернатива принадлежит множеству Парето, если она не хуже других по всем критериям и хотя бы по одному критерию лучше. Альтернативы из множества Парето называются парето-решениями, эффективными или недоминируемыми (непревосходимыми) альтернативами. При решении многокритериальных задач используется принцип Парето, заключающийся в том, что наилучшее решение следует выбирать среди альтернатив, принадлежащих множеству Парето. Этот принцип выполняется в большинстве практических ситуаций, когда альтернативы оцениваются по противоречивым критериям. Он позволяет сузить исходное множество альтернатив, причем окончательный выбор остается за ЛПР. Альтернативы, входящие в множество Парето, попарно не сравнимы друг с другом, т.е. по одним критериям лучше одна альтернатива, по другим другая и т.д., и их невозможно улучшить одновременно по всем критериям. Поэтому анализ множества Парето позволяет найти компромисс между противоречивыми требованиями и дает ЛПР возможность судить о том, какова “цена” увеличения одного из критериев и как это скажется на ухудшении остальных. Построение множества Парето является необходимым при решении многокритериальных задач выбора в системах (управление, проектирование промышленных и транспортных объектов и т.п.). Отметим еще одну важную особенность альтернатив из множества Парето: каждая из них представляет целый класс (группу) решений, превосходящих остальные по одному или нескольким критериям. Поясним это примером. Пусть имеется учебная группа (множество альтернатив), требуется выбрать наилучшего студента (альтернативу) по ряду критериев, например сообразительность, успеваемость, манера поведения, внешний вид, умение выражать свои мысли и т.п. Предположим, что студент – самый сообразительный, а по остальным критериям не выделяется. Студенты,,, имеют высокие значения остальных критериев, так, что они в среднем превосходят, причем лучше всех по успеваемости, а по остальным критериям не хуже других студентов. Тогда обязательно попадает в множество Парето, так как он уникальный (единственный) по первому критерию, а от группы студентов … в Парето попадает один представитель –, хотя остальные студенты превосходят по нескольким критериям (число критериев здесь не имеет значения).

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

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

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

, (5.3.16)

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

Подход, основанный на принципе равновесия (принципе Нэша). Часто действия окружающей среды являются целенаправленными, например, это имеет место для систем, включающих субъектов, причем каждая из систем стремится достичь своей цели. Случай несогласованности целей субъектов называется конфликтом. Такая ситуация характерна для теории игр. При анализе конфликтов со многими субъектами одна из важных проблем – это проблема коллективных решений, или компромисса. Для принятия решений в таких системах сохраняет свое значение принцип Парето. Эффективные альтернативы, принадлежащие множеству Парето, обладают тем свойством, что улучшить значение целевой функции (критерия) какого-либо субъекта можно только за счет других субъектов. Наряду с принципом Парето широко используется принцип равновесия, называемый также принципом устойчивости, или принципом Нэша. Этот принцип позволяет сузить множество альтернатив, когда речь идет о коллективном решении, принимаемом всеми взаимодействующими субъектами по договоренности, при этом каждый поступается частью своих интересов. Определим равновесное решение как такое, которое принимается всеми субъектами одновременно, по договоренности. Пусть имеется N субъектов, каждый из которых может выбирать свое решение (стратегию) так, чтобы максимизировать свой критерий. Значение критерия при этом зависит от выбора других субъектов, т.е.. Решение называется равновесным, если для любого выполняется условие

. (5.3.17)

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

Рассмотренные выше методы основаны на критериальном описании задачи выбора, при котором каждая альтернатива представлена точкой в пространстве критериев. Помимо критериального описания оптимизационной задачи используется также теоретико-множественное описание, оперирующее понятиями функции выбора и бинарного отношения. Функцией выбора на множестве альтернатив X называется оператор C, т.е. функция c областью определения X и областью значений 2 X, устанавливающая соответствие между множеством X и множеством всех его подмножеств 2 X, удовлетворяющий соотношению. Отсюда следует, что функция выбора не расширяет множество альтернатив.

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

Функция выбора по Парето определяется в виде

, (5.3.18)

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

Функция локально-экстремального выбора записывается в виде

, (5.3.19)

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

Функция оптимального выбора имеет вид

, (5.3.20)

где интерпретируется как функция полезности. Если; – выпуклая функция от, обладающая свойством при любых, то.

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

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

Существенное значение при решении многокритериальной задачи имеет обеспечение необходимых свойств аппроксимирующего отношения, что связано с выбором меры различия в факторном пространстве. Обычно используются такие свойства бинарных отношений как транзитивность, рефлексивность, симметричность, что позволяет ввести меру расстояния. Бинарное отношение транзитивно, если из и следует, что. Примерами транзитивных отношений являются отношения строгого порядка (больше, меньше, хуже и т.п.); примером нетранзитивных отношений являются отношения сходства или несходства. Отношение рефлексивно, если для всякого:. Если же ни для одного это не выполняется, то отношение называется антирефлексивным. Примерами рефлексивного отношения являются отношения нестрогого порядка (не больше, чем; не меньше, чем; не лучше, чем и т.п.), подобия, сходства, а примером антирефлексивного отношения – строгий порядок. Если для, то бинарное отношение называется симметричным. Если условие не выполняется ни для какой пары, то отношение антисимметрично. Примерами симметричного отношения являются отношения подобия, сходства, а несимметричного – строгий порядок. Отношение Парето, определенное выше, транзитивное, антирефлексивное и антисимметричное. Полезным свойством отношения является цикличность, облегчающая построение транзитивного замыкания отношения, которое само не является транзитивным, и введение подходящей меры расстояния. Отношение называется k -циклическим, если.

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

Существует значительное число модификаций ЧМ-процедур. Основными условиями при выборе той или иной процедуры являются имеющаяся у ЛПР информация о задаче и требования к точности решения. Обзор этих методов можно найти в [1, 2, 3, 4, 7].


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: