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

Версия 12:01, 20 июня 2012

Содержание

1 Задача многокритериальной оптимизации
- 1.1 Постановка задачи
- 1.2 Множество Парето оптимальных значений
2 Multi-objectivization
3 Алгоритмы
- 3.1 Hill-Climbers
  - 3.1.1 Псевдокод
4 Задачи
5 Источники

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

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

Определение:

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

где – целевая вектор-функция, где

Так как не существует единого решение, которое было бы максимальным для всех целевых функций, вместо него можно искать множество [math]X^* \subseteq 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 – Доминируемые решения

Определение:

Для двух решений и говорят тогда и только тогда, когда – такую пару решений называют недоминируемой

На рис. 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] задано расстояние. Наша цель – найти цепь из городов, минимизирующую величину:

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

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

where

and ,

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

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

@@ Строка 72: / Строка 72: @@
 Формулируется задача следующим образом:
-Задано <math>C=\{c_1,c_2,\dots,c_N\} </math>- множество городов и для каждой пары <math>\{c_i,c_j\}</math> задано расстояние. Наша цель - найти цепь из городов, минимизирующую величину:
+Задано <math>C=\{c_1,c_2,\dots,c_N\} </math>- множество городов и для каждой пары <math>\{c_i,c_j\}</math> задано расстояние. Наша цель &ndash; найти цепь из городов, минимизирующую величину:
 :<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>-сложной именно потому, что нет хорошего разложения этой задачи.
+Для того, чтобы объектизировать эту задачу, нам необходимо определить подзадачи. TSP &ndash; является <math>NP</math>-сложной именно потому, что нет хорошего разложения этой задачи.
 Разобьём задачу таким образом:
@@ Строка 82: / Строка 82: @@
 ::'''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> &ndash; два города, указанных ''априори''.
 Предполагается, что <math>a</math> и <math>b</math> выбраны произвольно.

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

Версия 12:01, 20 июня 2012

Содержание