Вопрос 24. Методы стохастической многокритериальной оптимизации

Постановка задачи:

Пусть имеются критерии . Требуется найти точку , которая в некотором смысле минимизирует все эти критерии. Критерии называют частными критериями. В совокупности они образуют векторный критерий , который и полежит оптимизации. А именно, рассматривается задача:

при условии .

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

Опр. Решение называется эффективным решением или оптимальным по Парето решением, если не существует другого решения такого, что

,

причем хотя бы для одного имеет место строгое неравенство.

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

• методы сведения задач многокритериальной оптимизации к задачам скалярной оптимизации;

• методы компенсации;

• методы порогов сравнимости.

Оптимизация основного частного критерия

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

при ограничениях

где — задаваемые допустимые значения для каждого критерия.

Метод взвешенной суммы оценок частных критериев

При таком подходе формулируется скалярный критерий как взвешенная сумма оценок частных критериев:

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

Минимаксный обобщённый критерий

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

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

Минимизация обобщённого скалярного критерия

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

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

Метод последовательных уступок

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

На первом этапе решается однокритериальная задача для первого наиболее важного критерия:

при условии .

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

А именно, на втором этапе метода последовательных уступок ищем решение, минимизирующее g⁽²⁾(x) при указанном ограничении на при указанном ограничении на и с учетом заданного множества X допустимых решений, т.е. решаем следующую однокритериальную задачу:

при ограничениях

Аналогичные процедуры реализуются на всех последующих этапах этого метода. В частности, на k-ом этапе решается соответствующая однокритериальная задача для k-го по важности частного критерия с учетом заданного множества X допустимых решений и всех ранее наложенных ограничений, к которым добавляется еще одно требование, согласно которому оценка для частного критерия, минимизируемого на предыдущем (k-1)-ом этапе не должна превышать величины где — минимальное значение целевой функции предыдущего (k-1)-гo этапа, а — соответствующая уступка ( ), которая была принята в качестве допустимой по отношению к найденному значению , чтобы перейти к рассматриваемому k-му этапу реализации метода. А именно, решается задача:

при ограничениях

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

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

Метод идеальной точки

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

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

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

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

В общем случае, метод идеальной точки может приводить к решениям, не принадлежащим границе Парето.

Методы компенсации

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

Суть такой идеи была изложена еще в 1752 г. Франклином Б. Он отмечает, что «при сравнении трудно держать в голове все достоинства и недостатки каждой из альтернатив». Поэтому он составляет два отдельных списка из достоинств и недостатков альтернативы. Затем после тщательного анализа определяет, какой недостаток (или их совокупность) можно считать эквивалентным определенному достоинству (или их совокупности). После чего такие «компромиссные» достоинства и недостатки вычеркиваются из списков.

Методы порогов сравнимости

К таким задачам относят серию методов ЭЛЕКТРА (ELECTRE). Идея такой группы методов состоит в использовании бинарных отношений между анализируемыми вариантами решений или альтернатив. Бинарные отношения соответственно определяют условия, при которых: 1) один вариант решения превосходит другой; 2) оба варианта решений эквивалентны; 3) оба варианта решений несравнимы между собой. При изменении условий меняется и количество сравниваемых альтернатив. При этом изменяется и состав так называемого ядра, состоящего из альтернатив, оказавшихся не худшими при всех сравнениях.