Багатокритеріальна оптимізація

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Багатокритеріальна оптимізація або програмування (англ. Multi-objective optimization),[1][2] — це процес одночасної оптимізації двох або більше конфліктуючих цільових функцій в заданій області визначення.

Задача багатокритеріальної оптимізації зустрічаються в багатьох галузях науки та техніки.

Визначення[ред.ред. код]

Задача багатокритеріальної оптимізації формулюється таким чином:[3]

\min_\vec{x} \{f_1(\vec{x}), f_2(\vec x), \dots, f_k(\vec x)\},
\vec x \in S

де f_i: R^n \to R це k (k\ge 2) цільових функцій. Вектори розв'язків \vec x = (x_1, x_2, \dots, x_n)^T належать до не порожньої області визначення S.

Задача багатокритеріальної оптимізації полягає у пошуку вектора цільових змінних, який задовільняє накладеним обмеженням та оптимізує векторну функцію, елементи якої відповідають цільовим функціям. Ці функції утворюють математичне описання критерію задовільності та, зазвичай, взаємно конфліктують. Звідси, «оптимізувати» означає знайти такий розв'язок, за якого значення цільових функцій були б прийнятними для постановника задачі.[4]

Еталонні точки[ред.ред. код]

Для можливості оцінки якості знайдених розв'язків, зазвичай розглядають такі точки в області значення цільової функції:

  • ідеальна точка, y^I,
  • утопічна точка, y^U,
  • надір (надир), y^N.

У деяких випадках ці точки можуть бути розв'язками.

Ідеальна точка визначається як вектор y^I = (y_1^I, \dots, y_p^I), кожна з координат якого має оптимальне значення відповідної складової цільової функції:[5]

y_k^I = \min_{x \in X} f_k(x) = \min_{y\in Y} y_k.

Точка надіру y^N = (y_1^N, \dots, y_p^N) визначається як вектор:

y^N_k = \max_{x\in X_E} y_k(x) = \max_{y\in Y_N} y_k, \qquad k = 1, \dots, p.

Утопічну точку y^U обчислюють на основі ідеальної:[6]

y^U = y^I - \epsilon U,

де \epsilon > 0, U — одиничний вектор.

Критерії оптимальності[ред.ред. код]

Критерій Парето[ред.ред. код]

Докладніше: Оптимум Парето

Вектор розв'язку \vec x\in S називається оптимальним за Парето якщо не існує \vec x'\in S такого, що f_i(\vec x) \le f_i(\vec x') для всіх i=1, \dots, k та f_i(\vec x) < f_i(\vec x') для бодай одного i. Множину оптимальних за Парето розв'язків можна позначити як P(S). Цільовий вектор є оптимальним за Парето, якщо відповідний йому вектор з області визначення також оптимальний за Парето. Множину оптимальних за Парето цільових векторів можна позначити як P(Z).

Множина оптимальних за Парето векторів є підмножиною оптимальних за Парето в слабкому сенсі векторів. Вектор \vec x'\in S є слабким оптимумом за Парето тоді, коли не існує вектора \vec x\in S такого, що f_i(\vec x) < f_i(\vec x') для всіх i=1, 2, \dots, k.

Діапазон значень оптимальних за Парето розв'язків в області допустимих значень дає корисну інформацію про досліджувану задачу якщо цільові функції обмежено областю визначення. Нижні границі оптимальної за Парето множини представлено в «ідеальному цільовому векторі» \vec z \in R^k. Його компоненти z_i отримані шляхом мінімазації кожної цільової функції у межах області визначення.

Множину оптимальних за Парето розв'язків також називають Парето-фронтом (англ. Pareto-frontier).

Лексикографічний порядок[ред.ред. код]

Якщо одні цільові функції важливіші за інші, критерій оптимальності можна визначити за лексикографічним порядком.

Відношення лексикографічного порядку <_{\mathrm{lex}} між векторами \vec a та \vec b виконується, якщо a_q < b_q, де q = min \left\{k : a_k \neq b_k\right\}. Тобто, перші q компонент вектора \vec a менші за компоненти вектора \vec b, а компоненти q+1 — рівні (якщо такі є). Лексикографічний порядок для випадку дійсних чисел є лінійним.

Вектор \vec x \in X є лексикографічним розв'язком, якщо не існує вектора \vec x' \in X такого, що f(\vec x') <_{\mathrm{lex}} f(\vec x).

Оскільки відношення лексикографічного порядку є лінійним, можна довести, що вектор \vec x є лексикографічним розв'язком, якщо для всіх \vec x' \in X виконується:

\vec f(\vec x) <_{\mathrm{lex}} \vec f(\vec x').

Основною особливістю розв'язків за лексикографічним порядком є існування вибору між критеріями. Лексикографічна впорядкованість вимагає ранжування критеріїв в тому сенсі, що оптимізація за критерієм f_k можлива лише тоді, коли було досягнено оптимуму для попередніх критеріїв. Це означає, що перший критерій має найбільший пріоритет, і лише у випадку існування декількох розв'язків за цим критерієм, буде пошук розв'язків за другим та рештою критеріїв.

Існування ієрархії серед критеріїв, дозволяє розв'язувати лексикографічні задачі послідовно, крок за кроком мінімізуючи за кожним наступним критерієм, та використовуючи оптимальні значення попередніх критеріїв як обмеження.

Скаляризація[ред.ред. код]

Для отримання оптимальних за Парето розв'язків часто використовують методи скаляризації. Оскільки цільова функція задачі багатокритеріальної оптимізації має векторні значення, її перетворюють на функцію зі скалярним значенням. Таким чином, задача багатокритеріальної оптимізації зводиться до задачі оптимізації з однією скалярною цільовою функцією. Функція скаляризації має задовільняти наступним умовам.

Нехай F — функція скаляризації, що перетворює векторну функцію \vec y = \vec f (\vec x) на скалярну. Якщо F зберігає впорядкованість за Парето \vec y, тобто, якщо для довільних \vec y^1, \vec y^2 \in \vec f(X) виконується:

\vec y^1 \le \vec y^2 \implies F (\vec y^1 ) < F (\vec y^2),

тоді розв'язок \vec x^0, що мінімізує F на X є розв'язком за Парето.[7]

Якщо F зберігає відношення порядку < в \vec y, тобто, якщо для довільних \vec y^1, \vec y^2 \in \vec f(X) виконується:

\vec y^1 < \vec y^2 \implies F (\vec y^1 ) < F (\vec y^2 ),

тоді розв'язок \vec x^0, що мінімізує F на X є слабким за Парето. Якщо F неперервна на \vec y, та \vec x^0 єдина точка мінімуму F на X, тоді \vec x^0 є розв'язком за Парето.

Зважена сума[ред.ред. код]

F_1(\vec f(\vec x)) = w_1 f_1 (\vec x) + \dots + w_r f_r (\vec x).

Наведена функція F_1 зберігає впорядкованість за Парето для w > 0. Тому розв'язки, що мінімізують F_1 на X для довільних w > 0 є оптимальними за Парето. Однак F_1 не зберігає впорядкованість за Парето для w \geq 0 а зберігає лише відношення < і тому розв'язки, що мінімізують F_1 на X для w \geq 0 є слабкими за Парето.[7]

Недоліком методу зважених сум у випадку не опуклої множини значень цільових функцій є неможливість охопити всі оптимальні за Парето точки з множини Парето-фронту.

В задачах комбінаторної багатокритеріальної оптимізації множина цільових значень не є опуклою, тому метод зважених сум не підходить для скаляризації цільових функцій для цих задач.

Функція скаляризації Чебишева[ред.ред. код]

F_\infty (\vec f(\vec x)) = \max_{1\leq i \leq r} w_i f_i(\vec x).

Зважена функція скаляризації Чебишева зберігає відношення < і тому мінімум F_\infty є слабким за Парето.[7]


Метод зміни обмежень (ε-обмеження)[ред.ред. код]

За методом зміни обмежень одну з цільових функцій залишають в якості цільової, а решту перетворюють на обмеження. Тобто, нехай f_r буде цільовою, а решта f_1, \dots, f_{r-1} як обмеження нерівності:

\min_x f_r(\vec x),
за умов  f_i(\vec x) \leq \varepsilon_i, i = 1, \dots, r - 1,
\vec x \in X.

Значення \varepsilon_1, \dots, \varepsilon_{r-1} можуть розглядатись як припустимі рівні для f_1, \dots, f_{r-1}.

Методи розв'язання[ред.ред. код]

Інтерактивність[ред.ред. код]

Часто, розв'язання задачі багатокритеріальної оптимізації відбувається за участю експерта — людини, яка обирає та ухвалює рішення на основі інформації, представленої системою підтримки прийняття рішень. Можлива участь групи з декількох експертів. У випадку участі людини у пошуку розв'язку алгоритми та методи називають інтерактивними.[3]

Еволюційні методи[ред.ред. код]

Згадки про застосування генетичних алгоритмів для розв'язання задачі багатокритеріальної оптимізації відносяться до кінця 1960-тих.[8]

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Steuer, R.E. (1986). Multiple Criteria Optimization: Theory, Computations, and Application. New York: John Wiley & Sons, Inc. ISBN 047188846X. 
  2. Sawaragi, Y.; Nakayama, H. and Tanino, T. (1985). Theory of Multiobjective Optimization (vol. 176 of Mathematics in Science and Engineering). Orlando, FL: Academic Press Inc. ISBN 0126203709. 
  3. а б Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen та Roman Slowinski (2008). Multiobjective Optimization: Interactive and Evolutionary Approaches (Lecture Notes in Computer Science). Springer. ISBN 3-540-88907-8.  Проігноровано невідомий параметр |місто= (довідка)
  4. A. Osyzka Multicriteria optimization for engineering design // Design Optimization. — С. 193-227.
  5. (Ehrgott, c. 34)
  6. (Jürgen et al, с. XI)
  7. а б в Nakayama, Hirotaka; Yun, Yeboon; Yoon, Min. Sequential Approximate Multiobjective Optimization Using Computational Intelligence (Vector Optimization). Springer. ISBN 978-3-540-88909-0. 
  8. R. S. Rosenberg (1967). Simulation of genetic populations with biochemical properties. Ann Harbor: University of Michigan.  Проігноровано невідомий параметр |note= (довідка)

Посилання[ред.ред. код]

  • А. Г. Трифонов. Многокритериальная оптимизация (рос.)
  • Вільний розв'язувач interalg з українського ПЗ OpenOpt для розв'язування багатокритеріальних задач з гарантованою точністю за допомогою інтервального аналізу

Література[ред.ред. код]