Задача многокритериальной оптимизации. Multiobjectivization
Содержание
Определение
Мультикритериальная оптимизация - это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения.
Задача многокритериальной оптимизации
Постановка задачи
| Определение: |
| Задача многокритериальной оптимизации:
|
Так как не существует единого решение, которое было бы максимальным для всех целевых функций, вместо него можно искать множество множество Парето оптимальных значений.
Множество Парето оптимальных значений
| Определение: |
Множество Парето оптимальных значений:
|
Выражение означает, что доминирует над . Решения в Парето оптимальном множестве также являются эффективными или допустимыми.
| Определение: |
| Для двух решений и говорят тогда и только тогда, когда - такую пару решений называют несравнимой |
Получение оптимальных по Парето решений
Для получения оптимальных по Парето решений используют методы скаляризации. Целевую функцию задачи многокритериальной оптимизации превращают в функцию со скалярным значением.
Функция скаляризации должна удовлетворять следующим условиям.
Пусть - функция скаляризации. Если для выполняется:
тогда решение , что минимизирует до , является решением по Парето. Если сохраняет отношение порядка в , то есть, если для произвольных выполняется:
тогда решение , что минимизирует до , является слабым по Парето. Если непрерывна на и единственная точка минимума на , тогда является решением по Парето.
Метод взвешенных множителей
Недостатки: невозможность охватить все оптимальные по Парето точки из множества Парето-фронта. В задачах комбинаторной многокритериальной оптимизации множество целевых значений не является выпуклым, поэтому метод взвешенных сумм не подходит для скаляризации целевых функций для этих задач.
Функция скаляризации Чебышева
Взвешенная функция скаляризации Чебышева сохраняет отношения и поэтому минимум является слабым по Парето.
Метод ограничений
В качестве решения задачи принимают компромиссное решение.
Компромиссное решение - эффективное решение, которое обеспечивает одинаковые минимальные взвешенные относительные потери по всем критериям одновременно. Если - вес нормализованного критерия , то величина , где - компромиссное решение, будет постоянна для всех критериев.
Описание алгоритма
- Задаем вектор предпочтений ;
- Заменяем все критерии одним ;
- К системе ограничений добавляем неравенства для каждого из критериев, где - вес нормализованного критерия ;
- Решаем полученную однокритериальную задачу симплекс-методом
