Задача многокритериальной оптимизации. Multiobjectivization
Содержание
Задача многокритериальной оптимизации
Постановка задачи
| Определение: |
| Задача многокритериальной оптимизации:
|
Так как не существует единого решение, которое было бы максимальным для всех целевых функций, вместо него можно искать множество множество Парето оптимальных значений.
Множество Парето оптимальных значений
| Определение: |
Множество Парето оптимальных значений:
|
Выражение означает, что доминирует над .
Говорят, что доминирует над . по Парето, если не хуже по всем критериям и хотя бы по одному критерию превосходит . В таком случае в выборе нет смысла, т.к. по всем параметрам не уступает, а по каким-то и превосхожит . Если рассматривать всего два критерия то на рис. 1 показана область пространства, доминируемая данным решением А. Эта область «замкнута»: элементы на ее границе также доминируемы А
| Определение: |
| Для двух решений и говорят тогда и только тогда, когда - такую пару решений называют недоминируемой |
На рис. 2 показана граница Парето для возможных решений в двухкритериальном пространстве
Множество Парето оптимальных недоминируемых решений называется Парето фронтом.
Multi-objectivization
Суть метода мульти-объективизации заключается в разбитии сложной задачи с одной целевой функцией на несколько подзадач, найти для каждой подзадачи решение и выбрать оптимальное решение.
Для выполнения оптимизации многокритериальной задачи мы должны добавить в целевую функцию новые параметры, либо должны добавить новые целевые функции.
Сложность этой процедуры заключается в разложении проблемы на ряд мелких независимых между собой подпроблем.
Алгоритмы
Hill-Climbers
| Initialization: | Init_pop |
| Main Loop: | Rand_mem,Rand_mem Mutate,Mutate
if if |
| Termination: | return Best |
