Теоретическая справка к лр 2. Принцип Парето решения многокритериальных задач
 Скачать 36.06 Kb.
|
|
Принцип Парето решения многокритериальных задач Суть принципа Парето заключается в том, что он позволяет исключить неприемлемые решения из существующего множества. Это необходимо для того, чтобы сузить, как правило, большое множество в лучшем случае до единственного решения. Данный принцип основывается на наличии доминируемых и несравнимых решений. Алгоритм построения множества недоминируемых решений состоит в следующем: Этап первый. Решение х1 необходимо последовательно сравнивать с остальными альтернативами, учитывая предпочтения ЛПР. Далее в случае наличия менее предпочтительной альтернативы, доминируемая (не предпочитаемая) удаляется из имеющегося множества, а доминирующая на данный момент альтернатива сравнивается с оставшимися. Если не находится альтернативы, которая была бы доминирующей по отношению к рассмотренной выше (оставленной для дальнейшего сравнения), то она переводится в множество недоминируемых решений. Если же находится, то менее предпочитаемая удаляется. Этап второй. Он абсолютно аналогичен первому. Только сравнение начинается с другой альтернативы. Результатом этого этапа является либо удаление альтернативы, либо перемещение ее во множество недоминируемых решений, либо оставление в исходном множестве. После завершения действия алгоритма должно остаться не пустое множество потенциальных решений. Возникает вопрос о том, как сравнить два произвольных решения. Для решения этой проблемы существует аксиома Парето: для каждых двух решений х1, х2, где справедливо неравенство F(x1)>=F(x2) следует, что х1 более предпочтительно, чем х2. Неравенство F(x1)>=F(x2) означает, что должна выполняться следующая система: Fi(x1)>=Fi(x2) -- для любого критерия Fi, где i=1,2…m Fj(x1)>=Fj(x2) -- как минимум для одного критерия Проанализировав все переменные вышеуказанным способом, ЛПР получит множество Парето-оптимальных решений, из которого и делается окончательный выбор. Альтернативы, не удовлетворяющие критерию равноценности, отсеиваются с помощью критерия предпочтения альтернатив. Практика показывает, что при этом удаётся отсеять до 90-95% из числа рассматриваемых альтернатив в зависимости от количества частных критериев, образующих сравниваемые альтернативы Алгоритм построения множества Парето в общем случае состоит в выполнении следующего правила. Первая альтернатива включается в состав множества Парето автоматически. Каждая последующая альтернатива сравнивается с уже вошедшими в множестве Парето. При этом возможны три случая 1 Если в множестве Парето имеется хотя бы одна альтернатива, лучшая чем проверяемая, то проверяемая альтернатива не входит в множество Парето. 2 Если в множестве Парето есть альтернативы хуже проверяемой, то они исключаются из множества Парето и заменяются лучшей альтернативой. 3 Если в множестве Парето нет альтернатив лучше, чем проверяемая, и нет альтернатив хуже, то проверяемая альтернатива добавляется в множество Парето. В результате формируется множество равноценных альтернатив, ни одна из которых не лучше других, то есть удовлетворяет условию включения в множество Парето. Метод свертывания критериев Метод свертывания критериев предполагает преобразование набора имеющихся частных критериев в один суперкритерий.  Т.е. получаем новый суперкритерий F, который является функций  от частных критериев . В общем случае, функцию называют сверткой частных критериев.К основным этапом свертывания относятся: 1. Обоснование допустимости свертки При обосновании допустимости свертки, в первую очередь должны подтвердить, что критерии, которые сворачиваем, должны быть однородными. 2. Нормировка критериев 3. Учет приоритетов критериев Учет приоритетов обычно задается некоторым векторам весовых коэффициентов, которые отображают важность того или иного критерия для решаемой задачи. 4. Построение функции свертки Для свертывания критериев, используют такие основные типы функций: - Аддитивные функции свертки; - Мультипликативные; - Агрегированные, а также могут быть другие варианты сверток. Аддитивная свертка Аддитивную свертку критериев можно рассматривать как реализацию принципа справедливой компенсации абсолютных значений нормированных частных критериев. В этом случае, суперкритерий обычно строятся как взвешенная сумма частных критериев  Весовые коэффициенты  выбираются такими, чтобы их сумма была равна единицы . Иногда оказывается удобным подход к определению весовых коэффициентов , их определяет соответствие с таблицей:Таблица относительной важности критериев
Мультипликативная свертка Мультипликативная свертка базируется на принципе справедливой компенсации относительных изменений частных критериев. При этом, суперкритерий имеет вид:  ,произведение частных критериев  , каждый из которых возведен в степень . При этом сумма весовых коэффициентов должна быть равна единицы , а каждый из весовых коэффициентов должен быть не отрицательной величиной .Критерий расстояния до идеальной точки В этом случае обобщенный показатель вычисляются как расстояние (длина вектора) в критериальном пространстве между точкой с текущими координатами и точкой (идеальной), координаты которой задаются ЛПР. Для того, чтобы расстояния можно было измерять в одной шкале, значения показателей можно нормировать как во «взвешенной сумме». При этом, суперкритерий имеет вид:  , при этом сумма весовых коэффициентов должна быть равна единицы Методы свертывания критериев широко используются в решение задач многокритериальной оптимизации. Однако они имеют также проблемы и недостатки. В частности трудно обосновать выбор метода свертывания критериев, а от выбора метода часто зависит получаемый результат. Другим недостатком является трудность обоснование выбора весовых коэффициентов, часто для этого привлекается эксперты, проводятся опросы, потом обрабатываются полученные результаты, однако это требует много времени и затраты других ресурсов. Еще одна проблема связана с тем, что эти методы, как правила дает возможность компенсировать малые значения одних критериев большими значениями других, что часто бывает неприемлемо для конкретных решений. С математической точки зрения не существует идеального способа или метода решения многокритериальных задач оптимизации. Тем не менее, эти методы помогают подготовить всю необходимую для принятия решения информацию таким образом, чтобы помочь лицам принимающее решение максимально точно разобраться в ситуации и принять наиболее обоснованное решение. Выбор множества Парето-оптимальных решений (множества Парето) представляет собой отбор перспективных альтернатив, из которых затем отбирается одна (лучшая) альтернатива. Множество Парето представляет собой множество альтернатив, обладающих следующим свойством: любая из альтернатив, входящих во множество Парето, хотя бы по одному критерию лучше любой другой альтернативы, входящей в это множество. Выбор множества Парето производится следующим образом. Все альтернативы попарно сравниваются друг с другом по всем критериям. Если при сравнении каких-либо альтернатив (обозначим их как Ai и Aj) оказывается, что одна из них (например, Aj) Не лучше другой ни по одному критерию, то ее можно исключить из рассмотрения. Исключенную альтернативу (в данном случае — Aj) не требуется сравнивать с другими альтернативами, так как она явно неперспективна. Как правило, во множество Парето входит несколько альтернатив. Поэтому выбор множества Парето не обеспечивает принятия окончательного решения (выбора одной лучшей альтернативы), однако позволяет сократить количество рассматриваемых альтернатив, т. е. упрощает принятие решения. |