Изменения

{{В разработке}}== Определение Введение ==В данной статье рассматривается многокритериальная оптимизация, её задача. Рассматривается понятие Парето-фронт - множество Парето оптимальных значений. Также рассматривается задача коммивояжера и предлагается алгоритм её мультиобъективизации

== Задача многокритериальной оптимизации ===== Постановка задачи ==={{Определение |definition='''Мультикритериальная оптимизацияЗадача многокритериальной оптимизации:''' :<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> &ndash; целевая вектор- это процесс одновременной оптимизации двух или более конфликтующих функция, где <math>K \ge 2</math>}}Так как не существует единого решение, которое было бы максимальным для всех целевых функций в заданной области определения, вместо него можно искать множество <math>X^* \subseteq X </math> множество Парето оптимальных значений.=== Множество Парето оптимальных значений ==={{Определение |definition=''' Множество Парето оптимальных значений: ''':<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) > f_i(x^*)))</math>}}Выражение <math>x \succ x^*</math> означает, что <math>x</math> ''доминирует над'' <math>x^*</math>.

== Задача многокритериальной оптимизации ={{Определение |definition=Задача многокритериальной оптимизации формулируется следующим образом:: Для двух решений <math>\min\limits_{\vec{x}}\{f_1(\vec{x}), f_2(\vec x), \dots, f_k(\vec x)\},</math>: и <math>\vec x \in S'</math>где говорят <math>f_i: R^n x \to Rsim x'</math> это тогда и только тогда, когда <math>k</math\exists i \in 1..K \colon f_i(x) > f_i(<mathx') \land \exists j \in 1..K, j \ne i \colon f_j(x') >k\ge 2f_j(x)</math>) &ndash; такую пару решений называют '''недоминируемой'целевых функций''}}На рис. Векторы 2 показана граница Парето длявозможных решений в двухкритериальном пространстве[[Файл:Pareto_front.jpg|мини|200px|Рис.2 &ndash; Парето фронт]]Множество Парето оптимальных недоминируемых решений <math>\vec x называется '''Парето фронтом.''' == Multi-objectivization == (x_1Суть метода мульти-объективизации заключается в разбитии сложной задачи с одной целевой функцией на несколько подзадач, x_2, \dots, x_n)^T</math> Относятся к области определения <math>S</math>найти для каждой подзадачи решение и выбрать оптимальное решение.

Задача Для выполнения оптимизации многокритериальной оптимизации состоит задачи мы должны добавить в поиске вектора целевых переменных, удовлетворяющего наложенным ограничениям и оптимизирующего векторную целевую функциюновые параметры, элементы которой соответствуют целевым функциямлибо должны добавить новые целевые функции.

== Критерий оптимальности ==Перечислим основные критерии оптимальности=== Критерий Парето ===Вектор решения <math>\vec x\in S</math> - оптимальный по Парето, если <math>\not\exists\vec x'\in S</math>:<math>f_i(\vec x) \le f_i(\vec x')</math> для всех <math>i=1, \dots, k</math> и <math>f_i(\vec x) < f_i(\vec x')</math> для хотя бы одного <math>i</math>Сложность этой процедуры заключается в разложении проблемы на ряд мелких независимых между собой подпроблем.

<math>P(Z)</math> === Hill- множество оптимальных по Парето целевых векторовClimbers ==={{Определение |definition='''Hill-Climbers''' &ndash; Итеративный алгоритм, который начинается с произвольного решения проблемы, а затем пытается найти лучшее решение, постепенно изменяя его.Если изменения позволяют найти лучшее решение, алгоритм сохраняет его и повторяет и повторяет своё выполнение до тех пор, пока лучшие решения не могут быть найдены}}

Множество оптимальных по Парето решений также называют Парето{||''Initialization:''||<math>P \leftarrow \emptyset </math><br/>'''Init_pop'''<math>(P)</math>|-фронтом.|''Main Loop:''||<math>x_1 \leftarrow </math>'''Rand_mem'''<math>(P)</math>,<math>x'_2 \leftarrow </math>'''Rand_mem'''<math>(P)</math><br/><math>x'_1 \leftarrow </math>'''Mutate'''<math>(P)</math>,<math>x_2 \leftarrow </math>'''Mutate'''<math>(P)</math><br/>'''if'''<math>(H(x_1,x'_1)+H(x_2,x'_2) > H(x_1,x'_2)+H(x_2,x'_1))</math><br/>:'''Swap'''<math>(x_1,x'_2)</math><br/>'''if''' <math>f(x'_1) > f(x_1)</math><br/>: <math>P \leftarrow P \cup x'_1 \setminus x_1</math><br/>'''if''' <math>f(x'_2) > f(x_2)</math><br/>: <math>P \leftarrow P \cup x'_2 \setminus x_2</math>|-|''Termination:''||'''return Best'''<math>(P)</math>|}

Парето== Задачи ======Hierarchical-фронт не может быть вычислен за полиномиальное времяif-and-only-if function===='''H-IIF''' &ndash; предназначена для моделирования проблемы с блочной структурой, каждый блок которой строго связан с остальными блоками.

Отношение лексикографического порядка :<math><_f(B)= \begin{cases}1,& \mathrmmbox{lexif }|B| = 1, \mbox{ else}</math> между векторами <math>\vec a</math> и <math>\vec b</math> выполняется|B|+f(B_L)+f(B_R), если <math>a_q < b_q</math>, где <math>q & \mbox{if }(\forall i \{b_i= min 0\left} \mbox{k : a_k or } \neq b_kforall i \right{b_i = 1 \}</math>. То есть) \\f(B_L) + f(B_R), первая <math>q</math> компонента вектора <math>& \vec a</math> меньше компоненты вектора <math>mbox{otherwise}\vec bend{cases}</math>, а компоненты <math>q+1</math> — уровни (если есть). Лексикографический порядок для случая действительных чисел является линейным.

Вектор где <math>\vec x \in XB</math> является лексикографическим решением, если не существует вектора &ndash; блок бит <math>\vec x' {b_1,b_2,\dots,b_n \in X}, |B|</math>&ndash; размер блока, такого, что а <math>f(\vec x') <_{\mathrm{lex}} f(\vec x)B_L, B_R</math>&ndash; левая и правая часть блока соответственно.

Поскольку отношение лексикографического порядка является линейнымПрименяя к этой задаче мультиобъективизацию, можно доказать, что вектор разобьём задачу <math>\vec xf</math> является лексикографическим решением, если для всех на <math>\vec x' \in Xk</math> выполняется:: <math>\vec f(\vec x) <_{\mathrm{lex}} \vec f(\vec x')-задач.</math>

Пусть где <math>F</math> - функция скаляризации. Если для <math> \forall \vec y^1, \vec y^2 \in \vec ff_0(Xx)</math> выполняется:: &ndash; первая цель; <math>\vec y^1 \le \vec y^2 \implies F (\vec y^1 ) < F f_0(\vec y^2x),</math>&ndash; вторая цель.

тогда решение <math>\vec x^0</math>, что минимизирует <math>F</math> до <math>X</math>, является решением по Парето.Если <math>F</math> сохраняет отношение порядка <math><</math> в <math>\vec y</math>, то есть, если для произвольных <math>\vec y^1, \vec y^2 \in \vec fДанный подход помогает избежать проблему локальных максимумов (Xминимумов)</math> выполняется:: <math>\vec y^1 < \vec y^2 \implies F (\vec y^1 ) < F (\vec y^2 ),</math>тогда решение <math>\vec x^0</math>, что минимизирует <math>F</math> до <math>X</math>, является ''слабым по Парето''. Если <math>F</math> непрерывна на <math>\vec y</math> и <math>\vec x^0</math> единственная точка минимума <math>F</math> на <math>X</math>, тогда <math>\vec x^0</math> является решением по Парето.

=== Метод взвешенных множителей = Задача коммивояжера ====: Задача коммивояжера (TSP)является наиболее известно из всего класса <math>F_1(\vec f(\vec x)) = w_1 f_1 (\vec x) + \dots + w_r f_r (\vec x).NP</math>-сложных задач.Формулируется задача следующим образом:

'''НедостаткиЗадано <math>C=\{c_1,c_2,\dots,c_N\} </math> &ndash; множество городов и для каждой пары <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 &ndash; является <math>F_\infty (\vec f(\vec x)) = \max_{1\leq i \leq r} w_i f_i(\vec x).NP</math>-сложной именно потому, что нет хорошего разложения этой задачи.Взвешенная функция скаляризации Чебышева сохраняет отношения <math><</math> и поэтому минимум <math>F_\infty</math> является слабым по ПаретоТем не менее задачу можно разбить на две или больше подтуров, каждый из которых мы можем минимизировать.

=== Метод ограничений ===В качестве решения задачи принимают компромиссное решениеПредставим подтуры в виде двух городов.Тогда наша задача примет вид:

:<math>minimize\{f(\pi,a,b) = (f_1(\pi,a,b),f_2(\pi,a,b))\}</math>::'''Компромиссное решениеwhere''' - эффективное решение, которое обеспечивает одинаковые минимальные взвешенные относительные потери по всем критериям одновременно. Если <math>p_if_1(\pi,a,b)=\sum^{\pi^{-1}(b)-1}_{i=\pi^{-1}(a)} d(C_{\pi(i)},C_{\pi(i+1)})</math> - вес нормализованного критерия ::'''and''' <math>w_i</math>f_2(\pi,a,b)=\sum^{N-1}_{i=\pi^{-1}(b)} d(C_{\pi(i)}, то величина <math>p_iw_iC_{\pi(i+1)}) + \sum^{\pi^{-1}(x_aa)-1}_{i=s1} d(C_{\pi(i)},C_{\pi(i+1)}) </math>, где <math>x_0+ d(C_{\pi(N)},C_{\pi(1)})</math> - компромиссное решение, будет постоянна для всех критериев.

====Описание алгоритма====# Задаем вектор предпочтений где <math>p=(p_1,p_2,\dots,p_k)a</math>;# Заменяем все критерии одним и <math>s \rightarrow minb</math>&ndash;# К системе ограничений добавляем неравенства два города, указанных ''априори''. Если <math>p_iw_i\pi (xa)< \leq spi (b)</math> для каждого из критериев, где <math>p_i</math> - вес нормализованного критерия <math>w_i</math>;# Решаем полученную однокритериальную задачу симплекс-методомменяем их местами.

=== Интерактивность =Источники ==Решение задачи происходит с участием эксперта (или группы экспертов) — человека* [http://ru.wikipedia.org/wiki/Многокритериальная_оптимизация Википедия: Многокритериальная оптимизация]* [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/3/multiobjectivization.pdf Knowles J., который выбирает и принимает решения на основе информацииWatson R., представленной системой поддержки принятия решенийCorne D.Reducing Local Optima in Single-Objective Problems by Multi-objectivization]=== Эволюционные методы ===* [http://en.wikipedia.org/wiki/Multiobjective_optimization Wikipedia: Multiobjective optimization]''предстоит написать''* [http://en.wikipedia.org/wiki/Hill_climbing Wikipedia: Hill climbing]