Задача многокритериальной оптимизации. Multiobjectivization — различия между версиями
(→Multi-objectivization) |
(→Алгоритмы) |
||
| Строка 59: | Строка 59: | ||
|''Termination:''||'''return Best'''<math>(P)</math> | |''Termination:''||'''return Best'''<math>(P)</math> | ||
|} | |} | ||
| + | |||
| + | == Задачи == | ||
| + | Задача коммивояжера является наиболее известно из всего класса <math>NP</math>-сложных задач. | ||
| + | Формулируется задача следующим образом: | ||
| + | |||
| + | Задано <math>C=\{c_1,c_2,\dots,c_N\} </math>- множество городов и для каждой пары <math>\{c_i,c_j\}</math> задано расстояние. Наша цель - найти цепь из городов, минимизирующую величину: | ||
| + | |||
| + | :<math></math> | ||
== Источники == | == Источники == | ||
Версия 09:50, 19 июня 2012
Содержание
Задача многокритериальной оптимизации
Постановка задачи
| Определение: |
| Задача многокритериальной оптимизации:
|
Так как не существует единого решение, которое было бы максимальным для всех целевых функций, вместо него можно искать множество множество Парето оптимальных значений.
Множество Парето оптимальных значений
| Определение: |
Множество Парето оптимальных значений:
|
Выражение означает, что доминирует над .
Говорят, что доминирует над . по Парето, если не хуже по всем критериям и хотя бы по одному критерию превосходит . В таком случае в выборе нет смысла, т.к. по всем параметрам не уступает, а по каким-то и превосхожит . Если рассматривать всего два критерия то на рис. 1 показана область пространства, доминируемая данным решением А. Эта область «замкнута»: элементы на ее границе также доминируемы А
| Определение: |
| Для двух решений и говорят тогда и только тогда, когда - такую пару решений называют недоминируемой |
На рис. 2 показана граница Парето для возможных решений в двухкритериальном пространстве
Множество Парето оптимальных недоминируемых решений называется Парето фронтом.
Multi-objectivization
Суть метода мульти-объективизации заключается в разбитии сложной задачи с одной целевой функцией на несколько подзадач, найти для каждой подзадачи решение и выбрать оптимальное решение.
Для выполнения оптимизации многокритериальной задачи мы должны добавить в целевую функцию новые параметры, либо должны добавить новые целевые функции.
Сложность этой процедуры заключается в разложении проблемы на ряд мелких независимых между собой подпроблем.
Алгоритмы
Hill-Climbers
| Initialization: | Init_pop |
| Main Loop: | Rand_mem,Rand_mem Mutate,Mutate
if if |
| Termination: | return Best |
Задачи
Задача коммивояжера является наиболее известно из всего класса -сложных задач. Формулируется задача следующим образом:
Задано - множество городов и для каждой пары задано расстояние. Наша цель - найти цепь из городов, минимизирующую величину:
