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

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

Багатокритеріальна оптимізація або програмування (англ. 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]

Процедури вирішення задач багатокритеріальної оптимізації[ред.ред. код]

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

  • По методу використання інформації
  • Апріорні
  • Апостеріорні
  • Адаптивні
  • По методу прийняття рішення та ін.

Апріорні процедури багатокритеріальної оптимізації та відповідні їм методи прийняття рішень[ред.ред. код]

В процедурах апріорного типу робиться явне та неявне припущення, що вся інформація, що дозволяє визначити найкраще рішення, прихована у формальній моделі задач та, відповідно, за допомогою деяких перетворень може бути з цієї формальної моделі витягнена та використана. Прийнято, що множина альтернатив U та цільових функцій W1(u),W2(u),...достатньо для об'єктивного, не залежного від відсутніх в даній моделі факторів визначення оптмального рішення.

приклад 1. Вирішити задачу по двом критеріям, рахуючи найбільш бажаним. Його відхилення від максимального становить 10 %:

W1 = x1 + 2 x2 (r)max;

W1 = x1 + 2 x2 (r)min; 

x1 + 2 x2 >6; 

x1 < 4; 

x2 < 5; 

x1 > 0; x2 > 0.

Вирішуючи задачу лінійного програмування за першим показником ефективності W1, наприклад в середовищі

пакета EXCEL або графічно, отримуємо, що максимальне значення цільової функції W1*= 14 досягається 

при x1 = 4 і x2 = 5. Робимо поступку на 10%, тобто зменшуємо величину W1*= 14 до значення W1**= 14 × 0,9 = 12,6. 

Вносимо в завдання додаткове обмеження x1 + 2 x2 ³ 12,6. Далі, вирішуючи завдання лінійного програмування при мінімізації другого показника ефективності маємо 

W2*= 7,6 при x1 = 2,6 і x2 = 5. При цьому значення показника ефективності W1 не змінилося і дорівнює 12,6. 

Апостеріорні процедури багатоцільовий оптимізації і відповідні їм методи прийняття рішення[ред.ред. код]

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

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

Апостеріорні процедури прийняття рішень полягають у формулюванні додаткових вимог, накладених на переваги проектанта, виконання яких дозволяє однозначно відновити деяку скалярну функцію корисності P (u), після чого задача прийняття рішень зводиться до скалярної оптимізації. 

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

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

Адаптивні процедури багатоцільової оптимізації і відповідні їм методи прийняття рішення[ред.ред. код]

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

  • адаптація являє, як правило, безперервний динамічний керований випадковий процес;
  • в процесі адаптації управління процесом має бути оптимальним з якого - або одному або декільком критеріям (показниками).

У процесі адаптації (адаптивного управління) можуть змінюватися: параметри, структура системи, алгоритм функціонування, управляючі дії і т.д. як відомо, процес оптимального проектування може інтерпретуватися у вигляді задачі оптимального управління. Тому до нього можуть бути повністю застосовані як загальні принципи, так і методи адаптації. При цьому адаптація тут може розглядатися з двох точок зору:

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

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

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

  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, Academic Press С. 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 для розв'язування багатокритеріальних задач з гарантованою точністю за допомогою інтервального аналізу

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