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

Метод перехресної ентропії складається з двох етапів: Генерація випадкової вибірки даних (траєкторії, вектора тощо) відповідно до визначеного механізму. Оновлення параметрів випадкового механізму базуючись на даних щоб отримати «кращу» вибірку на наступній ітерації. Цей крок включає мінімізацію перехресної ентропії або дивергенції Кульбака — Лейблера.

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

Загальний алгоритм методу перехресної-ентропії Обрати початковий вектор параметрів ; взяти t = 1. Згенерувати випадкову вибірку з </p> Розв'язати для , де Якщо збіжності досягнуто, то stop; інакше, збільшити t на 1 та перейти на крок 2.

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

Неперервна оптимізація

Такий самий алгоритм перехресної ентропії можна застосувати для оптимізації. Нехай маємо задачу: максимізувати деяку функцію , наприклад, . Для того щоб застосувати метод перехресної ентропії, спочатку розглядається асоційована стохастична задача оцінки для заданого рівня та параметричного сімейства , наприклад одновимірний нормальний розподіл, параметризований своїм математичним сподіванням та дисперсією (таким чином ). Отже, для заданого задачею є знайдення такого що що є мінімальним. Це робиться шляхом вирішення версії вибірки (стохастичний аналог) задачі мінімізації дивергенції Кульбака-Лейблера, як на кроці 3 раніше. Виявляється що параметрами, що мінімізують стохастичний аналог для цього вибору цільового розподілу та параметричного сімейства, є математичним сподівання та дисперсія вибірки що відносяться до елітних вибірок, тобто вибірок, що мають значення цільової функції . Найгірший з елітних вибірок використовується як рівень для наступної ітерації. Це дає наступний рандомізований алгоритм, що збігається з так-званим Алгоритмом Оцінки Багатовимірної Нормалі, алгоритмом оцінки розподілу.

Псевдо-код 1. mu:=-6; sigma2:=100; t:=0; maxits=100; // Ініціалізація параметрів 2. N:=100; Ne:=10; // 3. while t < maxits and sigma2 > epsilon // Виконується доки не знаходиться та не перевищу maxits 4. X = SampleGaussian(mu,sigma2,N); // Отримати N зразків з поточного вибірки 5. S = exp(-(X-2)^2) + 0.8 exp(-(X+2)^2); // Обчислити цільову функцію у обраних токах 6. X = sort(X,S); // Сортувати X по значенням цільової функції ( в спадному порядку 7. mu = mean(X(1:Ne)); sigma2=var(X(1:Ne)); // Оновити параметри 8. t = t+1; // Збільшити лічильник ітерацій на 1 9. return mu

Комбінаторна оптимізація Коли простір станів Х скінченний, завдання оптимізації часто називають дискретною або комбінаторною задачею оптимізації. Наприклад, X може бути простір комбінаторних об'єктів, таких як двійкові вектори, дерева, шляхи у вигляді графів тощо. Для застосування методу перехресної ентропії, необхідно спочатку вказати параметризований випадковий механізм для створення об'єктів в X. Наприклад, коли в X є безліч двійкових векторів довжини , легкий механізм генерації полягає в залученні кожного компонента незалежно від розподілу Бернуллі, тобто ~ Бер(р), де р — . З урахуванням елітного зразку маємо: , Тобто, оновлена ймовірність успіху для і-го компонента середнього і-й компоненти векторів в елітний набір. Можливе правило зупинки для задач комбінаторної оптимізації, зупинитися, коли загальне краще цільове значення не змінюється протягом кількох ітерацій. Крім того, можна зупинитися, коли вибірковий розподіл «вироджується». Зокрема, в разі Бернуллі можна зупинити коли все {} менше, ніж на деякій відстані ε від 0 або 1.

Умовна оптимізація (оптимізація з обмеженнями) Задача оптимізації з обмеженнями може бути поставлена в рамках методу перехресної ентропії для оптимізації приймаючи X (нелінійний) з області, яка визначається деякою системою нерівностей:

Для вирішення можуть бути прийняті два підходи. Перший підхід використовується прийняття-відмову: генерації випадкового вектора з, наприклад, багатовимірним нормальним розподілом з незалежними компонентами, і прийняти або відхилити його в залежності від того чи потрапляє зразок в Х чи ні. Крім того, можна спробувати прямо з усіченим розподілом (наприклад, усіченого нормального розподілу) або поєднувати такий метод з прийняттям-відмовою. Після того, як фіксоване число таких векторів було прийнято, параметри нормального розподілу можуть бути оновлені в точності так само, як і в безумовному випадку — просто за допомогою вибіркового середнього та стандартного відхилення елітних зразків. Недоліком цього методу є те, що велика кількість зразків може бути відхилена перед тим як можливий зразок знайдений. Другий підхід — штрафний. Тут ідея полягає в зміні цільової функції так: де {} — штрафні функції. А саме і-та функція { відповідає і-му обмеженню, визначається як: , де визначає вагу і-го штрафу. Таким чином зводячи задачу з обмеженнями до звичайної (з замість у ) можна застосувати алгоритм перехресної ентропії.

Стохастична оптимізація Стохастична задача оптимізації — задача в якій цільова функція спотворена шумами, з'являється у різних контекстах, наприклад у стохастичному плануванні розкладів, стохастичними задачами пошуку найкоротших/найдовших шляхів а оптимізації на основі моделювання. Метод перехресної ентропії може бути легко модифікований для цього класу задач. Розглянемо задачу максимізації нехай цільова функція спотворена шумами. Зокрема, приймемо що не доступна, але значення вибірки , наприклад, за допомогою симуляцій. Принципова модифікація звичайного алгоритму методу перехресної ентропії полягає в заміні на . Також, може знадобитися збільшення розміру вибірки щоб зменшити вплив шуму. Незважаючи на те що різні застосування стохастичного підходу до методу перехресної ентропії засвідчують його корисність, ще мало відомо відносно теоретичної збіжності.

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

Задача максимального перерізу може бути сформульовано наступним чином. Дано зважений граф з набором вершин {} та набором ребер . Множина вершин графу розділена на 2 підмножини та таким чином, що сума ваг ребер з одної підмножини до іншої максимальна. Припустимо що ваги ребер невід'ємні та граф є повним. Не порушуючи загальності приймемо що граф є неорієнтованим. Таким чином граф можна задати невід'ємною, симетричною матрицею вартостей:

що відповідає графу на рис. 1

Зручно представляти переріз як вектор де якщо i-та вершина належить тій самій підмножині вершин графу що і перша вершина, та 0 в протилежному випадку. За визначенням . Наприклад, переріз на рис.1 може бути заданий як вектор (1, 0, 1, 1, 0, 0). Нехай  — множина усіх векторів перерізу і нехай  — відповідна вартість перерізу. Наша мета — максимізувати методом перехресної ентропії. Таким чином, нам потрібно визначити як генерувати випадковий вектор та обчислити відповідні формули оновлення. Найпростіший спосіб генерації вектори перерізу — взяти як незалежні випадкові змінні Бернуллі з ймовірностями успіху з цього випливає:

Примітка Ми можемо легко розширити метод на випадок, в якому набір вузлів розбивається на підмножин { }Таких, що загальна сума ваг всіх ребер, що виходять з підмножини в підмножину , максимальна. В цьому випадку можна взяти незалежний точковий розподіл r, а не незалежні розподіли Бернуллі.

Приклад 1 Розглянемо граф що складається з 5-ти вершин і задається наступною матрицею вартостей:

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

На першій ітерації ми маємо визначити з {} може приймати значення {0,10,15,18,19,20,21,26,28} з ймовірностями {1,1,4,2,2,2,2,1,1,}/16. Таким чином ми маємо . На другому кроці нам потрібно розв'язати {} що має розв'язок

Э всього 2 вектори для яких , а саме (1,1,1,0,0) та (1,1,0,0,0). Обидва мають ймовірність 1/16. Таким чином:

На другій ітерації = 26 або 28 з ймовірністю 1/2 таким чином отримуємо (оптимальне) і

Приклад 2 Синтетична задача максимального перерізу. Оскільки задача максимального перерізу є NP-складна (Гері і Джонсон, 1979; Пападімітріу і Yannakakis, 1991) відсутні ефективні методи її розв'язання. Простий загальний перебір допустимий лише для малих графів (наприклад з вузлів. Хоча евристика методу гілок та границь може справлятися з задачами середньої розмірності, для великих n вона все одно проблемна.

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

де  — симетрична матриця розмірності m × m, в якій всі елементи, що знаходяться над головною діагоналлю генеруються з розподілу U(a, b)

 — симетрична матриця розмірності (n-m) × (n-m), яка генерується аналогічно . Всі інші елементи — с, окрім, звичайно, головної діагоналі які дорівнюють 0.

Неважко помітити що для за побудовою оптимальний переріз задано

де

{} та {}

та оптимальний переріз: }

Звичайно такий самий оптимальний розв'язок можна знайти і в загальному випадку коли елементи в та генеруються шляхом довільно обмеженого розподілу з максимальним значенням носія меншим за b

Задача комівояжера Зада́ча комівояже́ра (комівояжер — бродячий торговець; , TSP; ) полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів.

Задача комівояжера може бути сформульована наступним чином. Розглядається зважений граф з вершинами пронумерованими . Вершини відповідають містам, а ребра — дороги між містами. Кожне ребро з в має вагу (вартість) . Таким задається довжина дороги. Мета — знайти найкращий (найкоротший) маршрут що відвідує всі міста виключно по одному разу (окрім стартового і фінального міста, див рис.2) Не порушуючи загальності, візьмемо повний граф, і такий що деякі ваги можуть бути Without loss of generality, let us assume that the graph is complete, and that some of +∞. Нехай  — множина усіх можливих маршрутів та  — загальна довжина маршруту .

Ми можемо представити кожний маршрут перестановкою Наприклад при n=4 перестановка визначає маршрут