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

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

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

Існують наступні способи нормалізації критеріїв:

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

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

Безліч альтернатив, які між собою незрівняні або еквівалентні по багатьом критеріям, називається безліччю Парето.

1) Ei домінує альтернативу Ek (Ei> Ek), якщо

fj(Ei) >= fj(Ek), j=1,2.,N,прічем хоч би одна нерівність строга.

2) Ei еквівалентна Ek (Ei~ek), якщо

fj(Ei)= fj(Ek), j=1,2.,N.

Якщо немає домінування або еквівалентності, то вони незрівняні.

Для вирішення завдання векторної оптимізації існує декілька підходів:

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

Вводиться деяка скалярна функція:

f₀(E)= f₀(f₁(E), f₂(E),…, f_N(E))

Суперкритерій дозволяє упорядкувати альтернативи за значенням f0.

При цьому підході, як правило, приватні критерії нормалізують по одному з правил, приводячи їх до безрозмірного вигляду або до однієї розмірності. Найчастіше застосовують 2^а суперкритерія:

	Аддитивний суперкритерій(лінійна згортка);
	Мультиплікативний суперкритерій.

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

Метод головного часного критерію

Часні критерії, як правило, нерівнозначні по важливості.

Основна ідея полягає в тому, що один з критеріїв вважається головним, а останні - додатковими.

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

Часто обмеження на додаткові критерії задаються у вигляді нерівностей: f2 >= с.

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

Пошук альтернатив із заданими властивостями

Метод застосовується у тому випадку, коли задані значення часних критеріїв.

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

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

Ранжирування по Парето

Не ставиться мета визначення однієї кращої альтернативи.

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

	відбираються альтернативи, для яких немає альтернатив, строго їх домінуючих (недомінуючі альтернативи). Ця група складає еліту 1-го рангу
	потім для альтернатив, що залишилися, знову виділяють групу недомініючих (еліта 2-го рангу).

Процес триває до вичерпання всіх альтернатив. Для реалізації цього підходу зазвичай застосовується матриця переваги:

b_ij=1, E_i> E_j

b_ij=0, E_i<= E_j.

Приклад:

Ранжирування по Парето виконується таким чином:

	A1	A2
E1	2	4
E2	3	5
E3	1	3
E4	3	4
E5	3	3

	E1	E2	E3	E4	E5
E1	0	0	1	0	0
E2	1	0	1	1	1
E3	0	0	0	0	0
E4	1	0	1	0	1
E5	0	0	0	0	0

У групу з рангом 1 відносимо всі альтернативи, для яких стовпчики нульові: E2.

З рангом 2: E4.

З рангом 3: E1, E5.

З рангом 4: E3.

Використання функції корисності для оцінки альтернатив

Теорема Фішберна: якщо безліч альтернатив Ei скінчена і між ними існує відношення строгої переваги, то можна побудувати таку функцію U(E): U(Ei) >U(Ej), Ei>ej (переважно).

Функція U(E) - функція корисності.

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

Оцифрування порядкової шкали ще не є числовою шкалою.

Приклади:

	шкала твердості по Моосу: 1. тальк 2. гіпс 3. ... 10. алмаз
	шкала сили вітру: 0 - штиль ... 6 - сильний вітер ... 10 - шторм ... 12 - ураган

шкала землетрясений по Рихтеру:

.
10 - руйнування кам'яних будівель
.
12 - руйнування всіх будівель.

Порядкова шкала - не цифрова шкала.