Задача многокритериальной оптимизации. Multiobjectivization — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Hill-Climbers)
(→‎Hill-Climbers)
Строка 45: Строка 45:
  
 
=== Hill-Climbers ===
 
=== Hill-Climbers ===
 +
{{Определение
 +
|definition=
 +
'''Hill-Climbers''' - Итеративный алгоритм, который начинается с произвольного решения проблемы, а затем пытается найти лучшее решение, постепенно изменяя его. Если изменения позволяют найти лучшее решение, алгоритм сохраняет его и повторяет и повторяет своё выполнение до тех пор, пока лучшие решения не могут быть найдены
 +
}}
  
−
'''Hill-Climbers''' - Итеративный алгоритм, который начинается с произвольного решения проблемы, а затем пытается найти лучшее решение, постепенно изменяя его. Если изменения позволяют найти лучшее решение, алгоритм сохраняет его и повторяет и повторяет своё выполнение до тех пор, пока лучшие решения не могут быть найдены
+
====Псевдокод====
−
{|
+
<pre>
−
|''Initialization:''||<math>P \leftarrow \emptyset </math><br/>'''Init_pop'''<math>(P)</math>
+
Discrete Space Hill Climbing Algorithm
−
|-
+
  currentNode = startNode;
−
|''Main Loop:''||<math>x_1 \leftarrow </math>'''Rand_mem'''<math>(P)</math>,<math>x'_2 \leftarrow </math>'''Rand_mem'''<math>(P)</math><br/>
+
  loop do
−
<math>x'_1 \leftarrow </math>'''Mutate'''<math>(P)</math>,<math>x_2 \leftarrow </math>'''Mutate'''<math>(P)</math><br/>
+
      L = NEIGHBORS(currentNode);
−
'''if'''<math>(H(x_1,x'_1)+H(x_2,x'_2) > H(x_1,x'_2)+H(x_2,x'_1))</math><br/>
+
      nextEval = -INF;
−
:'''Swap'''<math>(x_1,x'_2)</math><br/>
+
      nextNode = NULL;
−
'''if''' <math>f(x'_1) > f(x_1)</math><br/>
+
      for all x in L
−
: <math>P \leftarrow P \cup x'_1 \setminus x_1</math><br/>
+
        if (EVAL(x) > nextEval)
−
'''if''' <math>f(x'_2) > f(x_2)</math><br/>
+
              nextNode = x;
−
: <math>P \leftarrow P \cup x'_2 \setminus x_2</math>
+
              nextEval = EVAL(x);
−
|-
+
      if nextEval <= EVAL(currentNode)
−
|''Termination:''||'''return Best'''<math>(P)</math>
+
        //Return current node since no better neighbors exist
−
|}
+
        return currentNode;
 +
      currentNode = nextNode;
 +
</pre>
  
 
== Задачи ==
 
== Задачи ==

Версия 11:51, 20 июня 2012

Задача многокритериальной оптимизации

Постановка задачи

Определение:
Задача многокритериальной оптимизации:
[math]maximize \{f(x) = (f_1(x),\dots,f_K(x))\}[/math]
[math] x \in X[/math]
где [math] f(x) : X \rightarrow R^K[/math] - целевая вектор-функция, где [math]K \ge 2[/math]

Так как не существует единого решение, которое было бы максимальным для всех целевых функций, вместо него можно искать множество [math]X^* \subseteq X [/math] множество Парето оптимальных значений.

Множество Парето оптимальных значений

Определение:
Множество Парето оптимальных значений:
[math]\forall x^* \in X^* \not\exists x \in X [/math]:[math]x \succ x^*[/math], где [math]x \succ x^* \Leftrightarrow (\forall i \in 1..K, (f_i(x) \ge f_i(x^*))\land (\exists i \in 1..K, f_i(x) \gt f_i(x^*)))[/math]

Выражение [math]x \succ x^*[/math] означает, что [math]x[/math] доминирует над [math]x^*[/math].

Говорят, что [math]x[/math] доминирует над [math]x^*[/math]. по Парето, если [math]x[/math] не хуже [math]x^*[/math] по всем критериям и хотя бы по одному критерию превосходит [math]x^*[/math]. В таком случае в выборе [math]x^*[/math] нет смысла, т.к. [math]x[/math] по всем параметрам не уступает, а по каким-то и превосхожит [math]x^*[/math]. Если рассматривать всего два критерия то на рис. 1 показана область пространства, доминируемая данным решением А. Эта область «замкнута»: элементы на ее границе также доминируемы А

Рис.1 - Доминируемые решения


Определение:
Для двух решений [math]x[/math] и [math]x'[/math] говорят [math]x \sim x'[/math] тогда и только тогда, когда [math]\exists i \in 1..K \colon f_i(x) \gt f_i(x') \land \exists j \in 1..K, j \ne i \colon f_j(x') \gt f_j(x)[/math] - такую пару решений называют недоминируемой

На рис. 2 показана граница Парето для возможных решений в двухкритериальном пространстве

Рис.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)является наиболее известно из всего класса [math]NP[/math]-сложных задач. Формулируется задача следующим образом:

Задано [math]C=\{c_1,c_2,\dots,c_N\} [/math]- множество городов и для каждой пары [math]\{c_i,c_j\}[/math] задано расстояние. Наша цель - найти цепь из городов, минимизирующую величину:

[math]\sum^{N-1}_{i=1} d(C_{\pi(i)},C_{\pi(i+1)})+d(C_{\pi(N)},C_{\pi(1)})[/math]

Для того, чтобы объектизировать эту задачу, нам необходимо определить подзадачи. TSP - является [math]NP[/math]-сложной именно потому, что нет хорошего разложения этой задачи.

Разобьём задачу таким образом:

[math]minimize\{f(\pi,a,b) = (f_1(\pi,a,b),f_2(\pi,a,b))\}[/math]
where[math]f_1(\pi,a,b)=\sum^{\pi^{-1}(b)-1}_{i=\pi^{-1}(a)} d(C_{\pi(i)},C_{\pi(i+1)})[/math]
and [math]f_2(\pi,a,b)=\sum^{N-1}_{i=\pi^{-1}(b)} d(C_{\pi(i)},C_{\pi(i+1)}) + \sum^{\pi^{-1}(a)-1}_{i=1} d(C_{\pi(i)},C_{\pi(i+1)}) [/math] [math]+ d(C_{\pi(N)},C_{\pi(1)})[/math],

где [math]a[/math] и [math]b[/math] - два города, указанных априори.

Предполагается, что [math]a[/math] и [math]b[/math] выбраны произвольно.

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Задача_многокритериальной_оптимизации._Multiobjectivization&oldid=25970»