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

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

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

Визначення

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

$\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\geq 2$) цільових функцій. Вектори розв'язків ${\vec {x}}=(x_{1},x_{2},\dots ,x_{n})^{T}$ належать до не порожньої області визначення $S$.

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

Еталонні точки

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

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

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

Ідеальна точка визначається як вектор $y^{I}=(y_{1}^{I},\dots ,y_{p}^{I})$, кожна з координат якого має оптимальне значення відповідної складової цільової функції:

$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_{k}^{N}=\max _{x\in X_{E}}y_{k}(x)=\max _{y\in Y_{N}}y_{k},\qquad k=1,\dots ,p.$

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

$y^{U}=y^{I}-\epsilon U,$

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

Критерії оптимальності

Критерій Парето

Вектор розв'язку ${\vec {x}}\in S$ називається оптимальним за Парето якщо не існує ${\vec {x}}'\in S$ такого, що $f_{i}({\vec {x}})\leq 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}\leq {\vec {y}}^{2}\implies F({\vec {y}}^{1})<F({\vec {y}}^{2}),$

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

Якщо $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$ є слабкими за Парето.

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

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

Функція скаляризації Чебишева

$F_{\infty }({\vec {f}}({\vec {x}}))=\max _{1\leq i\leq r}w_{i}f_{i}({\vec {x}}).$

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

Метод зміни обмежень (ε-обмеження)

За методом зміни обмежень одну з цільових функцій залишають як цільову, а решту перетворюють на обмеження. Тобто, нехай $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}.$

Методи розв'язання

Інтерактивність

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

Еволюційні методи

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

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

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

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

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

В процедурах апріорного типу робиться явне та неявне припущення, що вся інформація, що дозволяє визначити найкраще рішення, прихована у формальній моделі задач та, відповідно, за допомогою деяких перетворень може бути з цієї формальної моделі витягнена та використана. Прийнято, що множина альтернатив 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), після чого задача прийняття рішень зводиться до скалярної оптимізації.

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

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

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

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

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

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

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

Див. також

• Оптимум Парето
• Задача оптимізації
• Задача прийняття рішень
• Тестові функції для оптимізації
• Злісна проблема

Посилання

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

Література

• Matthias Ehrgott (2005). Multicriteria Optimization. Springer. ISBN 3-540-21398-8.
• M. Ehrgott and X. Gandibleux. Approximative Solution Methods for Multiobjective Combinatorial Optimization // TOP. — Sociedad de Estadística e Investigación Operativa, 2004. — Т. 12, вип. 1. Архівовано з джерела 23 липня 2007. Процитовано 28 грудня 2009.
• ОСНОВИ БАГАТОКРИТЕРІАЛЬНОЇ ОПТИМІЗАЦІЇ