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

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

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

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

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

${\displaystyle y_{k}^{I}=\min _{x\in X}f_{k}(x)=\min _{y\in Y}y_{k}.}$

Точка надіру ${\displaystyle y^{N}=(y_{1}^{N},\dots ,y_{p}^{N})}$ визначається як вектор:

${\displaystyle y_{k}^{N}=\max _{x\in X_{E}}y_{k}(x)=\max _{y\in Y_{N}}y_{k},\qquad k=1,\dots ,p.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle F_{1}({\vec {f}}({\vec {x}}))=w_{1}f_{1}({\vec {x}})+\dots +w_{r}f_{r}({\vec {x}}).}$

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

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

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

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

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

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

${\displaystyle \min _{x}f_{r}({\vec {x}}),}$

за умов ${\displaystyle f_{i}({\vec {x}})\leq \varepsilon _{i},i=1,\dots ,r-1,}$

${\displaystyle {\vec {x}}\in X.}$

Значення ${\displaystyle \varepsilon _{1},\dots ,\varepsilon _{r-1}}$ можуть розглядатись як припустимі рівні для ${\displaystyle 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), після чого задача прийняття рішень зводиться до скалярної оптимізації.

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

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

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

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

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

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