<<
>>

2.6.2.6 МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЕКТОРНОЙ ОПТИМИЗАЦИИ Нормализация критериев

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

Поэтому в большинстве случаев в решение многокритериальной задачи требуется включение предварительного этапа - нормализации критериев.

Нормализация критериев представляет собой однозначное отображение функции fk (X),Vk е K , из RN в RN . Для нормализации критериев в векторных задачах используется линейное преобразование:

fk(X) = af'(X) + c,Vk еK (54)

или

fk (X) = (fk (X) + c)/ a,Vk е K , (55)

где f'k (X),Vk е K - первоначальное значение критерия; fk (X),Vk е K - нормализованное значение.

Такая нормализация критериев в оптимизационной задаче не влияет на результат решения. В случае, если решается выпуклая оптимизационная задача:

max F(X), X е 5 , (56)

X

то в точке оптимума

X* е5,dF(X*)/dX = 0. (57)

Если же решается оптимизационная задача:

max(aF(X) + c),X е 5 , (58)

то в точке оптимума

X* е5,d(aF(X*) + c)/dX = 0, (59)

т.е. результат идентичен.

К нормализации критериев в векторных задачах предъявляются два основных требования:

нормализованные критерии должны быть измерены в одних и тех же величинах;

в точках оптимума Xk ,Vk е K величины всех критериев должны иметь одинаковую величину.

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

Xk (X) = (fk(X) - frw; - fkmn). (60)

При этом относительная оценка Xk (X), k = 1, K на всем множестве допустимых точек лежит в пределах

0 При этом величины 1 - X k (X) называются относительными отклонениями Xk (X).

Следует заметить, что при всех достоинствах предварительной нормализации критериев у нее имеется важный недостаток (общий для всех относительных величин) - нормализованный критерий не всегда имеет столь однозначную экономическую интерпретацию, как обычный. Например, если относительная оценка критерия f9 - норматив текущей ликвидности - равна 0,9 (т.е. 90 % от максимально возможной), то трудно сказать, достаточный ли это показатель для банка. Если же знать, что в абсолютных величинах данная величина составляет 94 % (при максимуме в 106 %), а требуемое инструкцией минимальное значение составляет 70 %, то на основании этого можно сделать более определенные выводы. Поэтому в ходе решения задачи многокритериальной оптимизации необходимо пользоваться параллельно обычными и нормализованными критериями. Методика построения множества

Парето-оптимальных решений

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

Название ЛПт-последовательность появилось как сокращение фразы

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

Поэтому в качестве метода построения множества Парето был выбран приближенный графоаналитический метод Н. Н. Моисеева, который заключается в последовательном итеративном процессе решения простейших оптимизационных задач. В случае двух критериев он применяется следующим образом: сначала задаются начальными произвольными значениями критериев: f1 = с1; f2 = с2. Затем решаются две оптимизационные задач:

1) max f1, f = С2; 2) max f2, f = cb (62)

Решив эти две задачи находят точки a и b. Прямая, соединяющая эти две точки является областью Парето в первом приближении. Далее решаются две аналогичные задачи. При этом задаются значениями критериев: f = c3; f2 = c4. Затем решаются две оптимизационные задачи:

1) max f1, f = C4; 2) max f>, f = C3. (63)

Через полученные точки снова проводят прямые. После соединения точек c и d получают ломаную acdb, которая является областью Парето второго приближения. В большинстве случаев второе приближение является достаточным. В случае большего числа критериев метод теряет наглядность, но может выполняться с помощью ЭВМ. Важной проблемой является визуальное представление множества Парето. В случае двух критериев оно отображается линией на плоскости. В случае трех критериев множество Парето можно визуализовать поверхностью в пространстве, однако, в отличие от линии на плоскости сделать выбор на основании трехмерного графика достаточно трудно. Поэтому возможно применение альтернативного метода линий уровня, который можно обобщить на большее число критериев.

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

Скалярные методы решения задачи многокритериальной оптимизации

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

Метод главного критерия

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

Метод уступок

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

оптимизация по первому критерию и определяется его наибольшее значение f*. Далее эксперт оценивает величину допустимого снижения (уступки) данного критерия (f1 - А/1) и ищется оптимум второго по важности критерия и т.д. После оптимизации последнего по важности критерия при условии, что значение каждого критерия k = 1, K должно быть не меньше (fl - Afk), k = 1, K , получаемые решения считаются оптимальными.

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

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

Свертка критериев

Другая очень распространенная группа методов скаляризации векторной задачи математического программирования - свертка критериев.

Существует большое количество разных видов сверток [11, 12]. Теоретически все они базируются на подходе, связанном с понятием функции полезности лица, принимающего решение. При данном подходе предполагается, что лицо, принимающее решение, всегда имеет функцию полезности, независимо от того, может ли лицо, принимающее решение задать ее в явном виде (т.е. дать ее математическое описание). Эта функция отображает векторы критериев на действительную прямую так, что большее значение на этой прямой соответствует более предпочтительному вектору критериев. Смысл разных сверток состоит в том, чтобы из нескольких критериев получить один «коэффициент качества» (сводный критерий), приближенно моделируя таким образом неизвестную (не заданную в явном виде) функцию полезности лица, принимающего решение. Наиболее популярной сверткой является метод взвешенных сумм с точечным оцениванием весов. При этом задается вектор весовых коэффициентов критериев, характеризующий относительную важность того или иного критерия:

A = {ak ,k = 1K }. (64)

Весовые коэффициенты обычно используются в нормированном виде и удовлетворяют равенству:

K

X ak = 1, ak > 0, Vk е K , (65)

k=1

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

Получается однокритериальная (скалярная) задача математического программирования:

F0 = max X af (X). (66)

k =1

В результате решения данной задачи получается точка оптимума X0.

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

Теорема Карлина 1.

В выпуклой задаче многокритериальной оптимизации точка X0 е 5 оптимальна по Парето, если существует вектор весовых коэффициентов A0 = {a° > 0, k = 1,K}, для которого выполняется соотношение:

Xа0/ь(Х0) = тахX/ (X). (67)

о , к =1

а =1

Теорема Карлина 2.

Если в выпуклой задаче многокритериальной оптимизации точка X0 е 5 Парето-оптимальна, то существует вектор весовых коэффициентов А0 = {а° > 0, к = 1,К}, для которого выполняется соотношение:

Xа0/к°(Х°) = тахXа0/ (X). (68)

,ак!к (х ) = !хах^ ак./к'

к=1 ^ к=1 а =1

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

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

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

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

Г0 = тах П (ак/к (X))Рк . (69)

кеК

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

(7о)

Так, существует свертка вида:

тіп^ =Х| /к -/к(Х)

Наиболее широкое применение данная свертка получила при р = 2, которая трактуется как минимизация суммы квадратов относительных отклонений функционалов от своих достижимых оптимальных значений. Данная точка в случае равноценности критериев показывает решение, наиболее близкое к недостижимой «идеальной» точке (в которой все критерии принимают свое максимальное значение). Однако данной свертке также свойственен следующий распространенный недостаток: «хорошее» значение сводного критерия достигается ценой низких значений некоторых частных критериев.

Методики, основанные на гарантированном результате

Данный недостаток отсутствует в методиках, основанных на гарантированном результате (максимине, минимаксе). Данный принцип впервые был предложен Карлиным [19] в следующей постановке:

тахтіп^(X) = {/к, к = 1К}. (71)

X к

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

к =1

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

Машунин вводит понятие уровня Х-нижней из относительных оценок:

Х = тіп Х к (X) (72)

и преобразует максиминную задачу

Х0 = тахтіп Х к (X) (73)

в экстремальную задачу

Х0 = тах Х, Х < Хк (X), к = 1, К . (74)

Данная задача является формализованным представлением принципа максимальной эффективности.

Методика, основанная на принципе максимина, позволяет оценить расположение условного центра многомерного множества

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

множества Парето, так как она дает дополнительную информацию о возможностях компромисса между критериями.

<< | >>
Источник: В.В. Тен, Б.И. Герасимов. ЭКОНОМИЧЕСКИЕ ОСНОВЫ СТАБИЛЬНОСТИ БАНКОВСКОЙ СИСТЕМЫ РОССИИ. 2001

Еще по теме 2.6.2.6 МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЕКТОРНОЙ ОПТИМИЗАЦИИ Нормализация критериев:

  1. КРИТЕРИЙ ПРИНЯТИЯ РЕШЕНИЯ (критерий наблюдателя) (англ. criterion of decision-making)
  2. 7. Методы оптимизации инвестиционного портфеля
  3. КРИТЕРИЙ ПРИНЯТИЯ РЕШЕНИЯ
  4. 7.1 Метод оптимизации инвестиционного портфеля по модели Г. Марковица
  5. 2.6.2.3 ПОСТРОЕНИЕ КРИТЕРИЕВ НАДЕЖНОСТИ С ИСПОЛЬЗОВАНИЕМ СТАТИСТИЧЕСКИХ МЕТОДОВ
  6. 49. Процесс решения мыслительной задачи
  7. РЕШЕНИЕ КОМПЛЕКСНЫХ ЗАДАЧ
  8. Примеры решения задач
  9. Мышление в действии: решение задач
  10. Мышление в действии: решение задач
  11. Стратегии решения задач
  12. Стратегии решения задач
  13. Примеры решения задач