Задача многокритериальной оптимизации. Multiobjectivization — различия между версиями
(→Hill-Climbers) |
(→Задача многокритериальной оптимизации) |
||
| Строка 6: | Строка 6: | ||
:<math>maximize \{f(x) = (f_1(x),\dots,f_K(x))\}</math> | :<math>maximize \{f(x) = (f_1(x),\dots,f_K(x))\}</math> | ||
:<math> x \in X</math> | :<math> x \in X</math> | ||
| − | где <math> f(x) : X \rightarrow R^K</math> | + | где <math> f(x) : X \rightarrow R^K</math> – целевая вектор-функция, где <math>K \ge 2</math> |
}} | }} | ||
Так как не существует единого решение, которое было бы максимальным для всех целевых функций, вместо него можно искать множество <math>X^* \subseteq X </math> множество Парето оптимальных значений. | Так как не существует единого решение, которое было бы максимальным для всех целевых функций, вместо него можно искать множество <math>X^* \subseteq X </math> множество Парето оптимальных значений. | ||
| Строка 23: | Строка 23: | ||
пространства, доминируемая данным решением А. Эта область «замкнута»: | пространства, доминируемая данным решением А. Эта область «замкнута»: | ||
элементы на ее границе также доминируемы А | элементы на ее границе также доминируемы А | ||
| − | [[Файл:Dogmin points.jpg|мини|200px|Рис.1 | + | [[Файл:Dogmin points.jpg|мини|200px|Рис.1 – Доминируемые решения ]] |
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Для двух решений <math>x</math> и <math>x'</math> говорят <math>x \sim x'</math> тогда и только тогда, когда <math>\exists i \in 1..K \colon f_i(x) > f_i(x') \land \exists j \in 1..K, j \ne i \colon f_j(x') > f_j(x)</math> | + | Для двух решений <math>x</math> и <math>x'</math> говорят <math>x \sim x'</math> тогда и только тогда, когда <math>\exists i \in 1..K \colon f_i(x) > f_i(x') \land \exists j \in 1..K, j \ne i \colon f_j(x') > f_j(x)</math> – такую пару решений называют '''недоминируемой''' |
}} | }} | ||
На рис. 2 показана граница Парето для | На рис. 2 показана граница Парето для | ||
возможных решений в двухкритериальном пространстве | возможных решений в двухкритериальном пространстве | ||
| − | [[Файл:Pareto_front.jpg|мини|200px|Рис.2 | + | [[Файл:Pareto_front.jpg|мини|200px|Рис.2 – Парето фронт]] |
Множество Парето оптимальных недоминируемых решений называется '''Парето фронтом.''' | Множество Парето оптимальных недоминируемых решений называется '''Парето фронтом.''' | ||
Версия 12:00, 20 июня 2012
Содержание
Задача многокритериальной оптимизации
Постановка задачи
| Определение: |
| Задача многокритериальной оптимизации:
|
Так как не существует единого решение, которое было бы максимальным для всех целевых функций, вместо него можно искать множество множество Парето оптимальных значений.
Множество Парето оптимальных значений
| Определение: |
Множество Парето оптимальных значений:
|
Выражение означает, что доминирует над .
Говорят, что доминирует над . по Парето, если не хуже по всем критериям и хотя бы по одному критерию превосходит . В таком случае в выборе нет смысла, т.к. по всем параметрам не уступает, а по каким-то и превосхожит . Если рассматривать всего два критерия то на рис. 1 показана область пространства, доминируемая данным решением А. Эта область «замкнута»: элементы на ее границе также доминируемы А
| Определение: |
| Для двух решений и говорят тогда и только тогда, когда – такую пару решений называют недоминируемой |
На рис. 2 показана граница Парето для возможных решений в двухкритериальном пространстве
Множество Парето оптимальных недоминируемых решений называется Парето фронтом.
Multi-objectivization
Суть метода мульти-объективизации заключается в разбитии сложной задачи с одной целевой функцией на несколько подзадач, найти для каждой подзадачи решение и выбрать оптимальное решение.
Для выполнения оптимизации многокритериальной задачи мы должны добавить в целевую функцию новые параметры, либо должны добавить новые целевые функции.
Сложность этой процедуры заключается в разложении проблемы на ряд мелких независимых между собой подпроблем.
Алгоритмы
Hill-Climbers
| Определение: |
| Hill-Climbers - Итеративный алгоритм, который начинается с произвольного решения проблемы, а затем пытается найти лучшее решение, постепенно изменяя его. Если изменения позволяют найти лучшее решение, алгоритм сохраняет его и повторяет и повторяет своё выполнение до тех пор, пока лучшие решения не могут быть найдены |
Псевдокод
Discrete Space Hill Climbing Algorithm
currentNode = startNode;
loop do
L = NEIGHBORS(currentNode);
nextEval = -INF;
nextNode = NULL;
for all x in L
if (EVAL(x) > nextEval)
nextNode = x;
nextEval = EVAL(x);
if nextEval <= EVAL(currentNode)
//Return current node since no better neighbors exist
return currentNode;
currentNode = nextNode;
Задачи
Задача коммивояжера (TSP)является наиболее известно из всего класса -сложных задач. Формулируется задача следующим образом:
Задано - множество городов и для каждой пары задано расстояние. Наша цель - найти цепь из городов, минимизирующую величину:
Для того, чтобы объектизировать эту задачу, нам необходимо определить подзадачи. TSP - является -сложной именно потому, что нет хорошего разложения этой задачи.
Разобьём задачу таким образом:
-
- where
- and ,
где и - два города, указанных априори.
Предполагается, что и выбраны произвольно.
