Метод перехресної ентропії

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

Задачу максимального перерізу графу може бути сформульовано наступним чином. Дано зважений граф ${\displaystyle G(V,E)}$ з набором вершин ${\displaystyle V=}${${\displaystyle 1,\dots ,n}$} та набором ребер ${\displaystyle E}$.

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

${\displaystyle {\begin{pmatrix}0&c_{12}&c_{13}&0&0&0\\c_{21}&0&c_{23}&c_{24}&0&0\\c_{31}&c_{32}&0&c_{34}&c_{35}&0\\0&c_{42}&c_{43}&0&c_{45}&c_{46}\\0&0&c_{53}&c_{54}&0&c_{56}\\0&0&0&c_{64}&c_{65}&0\end{pmatrix}}}$ що відповідає графу на рис. 1

Зручно представляти переріз як вектор ${\displaystyle {\vec {x}}=(x_{1},\dots ,x_{n})}$ де ${\displaystyle x_{i}=1}$ якщо i-та вершина належить тій самій підмножині вершин графу що і перша вершина, та 0 в протилежному випадку. За визначенням ${\displaystyle x_{1}=1}$. Наприклад, переріз на рис.1 може бути заданий як вектор (1, 0, 1, 1, 0, 0). Нехай ${\displaystyle X}$ — множина усіх векторів перерізу ${\displaystyle {\vec {x}}=(x_{1},\dots ,x_{n})}$ і нехай ${\displaystyle S(x)}$ — відповідна вартість перерізу. Наша мета — максимізувати ${\displaystyle S(x)}$ методом перехресної ентропії. Таким чином, нам потрібно визначити як генерувати випадковий вектор та обчислити відповідні формули оновлення. Найпростіший спосіб генерації вектори перерізу — взяти ${\displaystyle (X_{2},\dots ,X_{n})}$ як незалежні випадкові змінні Бернуллі з ймовірностями успіху ${\displaystyle (p_{2},\dots ,p_{n})}$ з цього випливає: ${\displaystyle {\hat {p_{i,j}}}={\frac {\sum _{i=1}^{N}I_{S(x)\geq {\hat {\gamma }}}I_{X_{ij}=1}}{\sum _{i=1}^{N}I_{S(x)\geq {\hat {\gamma }}}}}}$ Примітка Ми можемо легко розширити метод на випадок, в якому набір вузлів ${\displaystyle V}$ розбивається на ${\displaystyle r>2}$ підмножин { ${\displaystyle V_{1},\dots ,V_{n}}$ }Таких, що загальна сума ваг всіх ребер, що виходять з підмножини ${\displaystyle V_{i}}$ в підмножину ${\displaystyle V_{j}}$, ${\displaystyle i,j=1\dots ri\neq j}$ максимальна. В цьому випадку можна взяти незалежний точковий розподіл r, а не незалежні розподіли Бернуллі.

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

${\displaystyle {\begin{pmatrix}0&1&3&5&6\\1&0&3&6&5\\3&3&0&2&2\\5&6&2&0&2\\6&5&2&2&0\end{pmatrix}}}$

Ясно бачно що в даному випадку оптимальним є переріз ${\displaystyle {x}^{*}=(1,1,0,0,0)}$ з ${\displaystyle S({x}^{*})={\gamma }^{*}=28}$ Далі ми покажімо що в «детермінованій» версії алгоритму перехресної ентропії параметричні вектори ${\displaystyle {\vec {p_{0}}},{\vec {p_{1}}},\dots }$ збігається до оптимального ${\displaystyle {\vec {{p}^{*}}}=(1,1,0,0,0)}$ після двох ітерації, за умови ${\displaystyle \rho ={10}^{-1}}$ та ${\displaystyle p_{0}=(1,1/2,1/2,1/2,1/2)}$ .

На першій ітерації ми маємо визначити ${\displaystyle {\gamma }_{1}}$ з ${\displaystyle \gamma _{t}=max}${${\displaystyle \gamma s.t.\mathbb {E} _{p_{t-1}}I_{S(x)\geq \gamma }\geq 0.1}$} ${\displaystyle S(x)}$ може приймати значення {0,10,15,18,19,20,21,26,28} з ймовірностями {1,1,4,2,2,2,2,1,1,}/16. Таким чином ми маємо ${\displaystyle \gamma =26}$. На другому кроці нам потрібно розв'язати ${\displaystyle p_{t}=argmax}${${\displaystyle \mathbb {E} _{p_{t-1}}I_{S(x)\geq \gamma }lnf({\vec {X}};{\vec {p}})}$} що має розв'язок ${\displaystyle p_{t,j}={\frac {\mathbb {E} _{p_{t-1}}I_{S(x)\geq \gamma }X_{j}}{\mathbb {E} _{p_{t-1}}I_{S(x)\geq \gamma }}}}$ Э всього 2 вектори ${\displaystyle {\vec {x}}}$ для яких ${\displaystyle S(x)\geq 26}$, а саме (1,1,1,0,0) та (1,1,0,0,0). Обидва мають ймовірність 1/16. Таким чином:

${\displaystyle p_{11}={\frac {2/16}{2/16}}=1}$

${\displaystyle p_{12}={\frac {2/16}{2/16}}=1}$

${\displaystyle p_{13}={\frac {1/16}{2/16}}=1/2}$

${\displaystyle p_{14}={\frac {0}{2/16}}=0}$

${\displaystyle p_{15}={\frac {0}{2/16}}=0}$

На другій ітерації ${\displaystyle S(x)}$ = 26 або 28 з ймовірністю 1/2 таким чином отримуємо (оптимальне) ${\displaystyle \gamma _{2}=28}$ і ${\displaystyle p_{2}=(1,1,0,0,0)}$

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

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

${\displaystyle {\begin{pmatrix}Z_{11}&B_{12}\\B_{21}&Z_{22}\end{pmatrix}}}$

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

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

Неважко помітити що для ${\displaystyle c>b(n-m)/m}$ за побудовою оптимальний переріз задано ${\displaystyle {\vec {V}}^{*}=({{\vec {V}}_{1}}^{*};{{\vec {V}}_{2}}^{*})}$

де

${\displaystyle {{\vec {V}}_{1}}^{*}=}${${\displaystyle 1,\dots ,m}$} та ${\displaystyle {{\vec {V}}_{2}}^{*}=}${${\displaystyle m+1,\dots ,n}$}

та оптимальний переріз: ${\displaystyle {\vec {\gamma }}^{*}=cm(n-m)}$}

Звичайно такий самий оптимальний розв'язок можна знайти і в загальному випадку коли елементи в ${\displaystyle Z_{11}}$ та ${\displaystyle Z_{22}}$ генеруються шляхом довільно обмеженого розподілу з максимальним значенням носія меншим за b

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

Задача комівояжера може бути сформульована наступним чином. Розглядається зважений граф ${\displaystyle G}$ з ${\displaystyle n}$ вершинами пронумерованими ${\displaystyle 1,\dots ,n}$. Вершини відповідають містам, а ребра — дороги між містами. Кожне ребро з ${\displaystyle i}$ в ${\displaystyle j}$ має вагу (вартість) ${\displaystyle c_{ij}}$. Таким задається довжина дороги. Мета — знайти найкращий (найкоротший) маршрут що відвідує всі міста виключно по одному разу (окрім стартового і фінального міста, див рис.2) Не порушуючи загальності, візьмемо повний граф, і такий що деякі ваги можуть бути Without loss of generality, let us assume that the graph is complete, and that some of +∞. Нехай ${\displaystyle X}$ — множина усіх можливих маршрутів та ${\displaystyle S(x)}$ — загальна довжина маршруту ${\displaystyle x\in X}$.

Ми можемо представити кожний маршрут перестановкою ${\displaystyle (1,\dots ,n)}$ Наприклад при n=4 перестановка ${\displaystyle (1,2,3,4)}$ визначає маршрут ${\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 1}$ Тепер може сформулювати задачу комівояжера так: ${\displaystyle min_{x\in X}S(x)=}$ ${\displaystyle min_{x\in X}\sum _{i=1}^{n-1}}$ Відмітимо що кількість елементів в ${\displaystyle X}$ звичайно дуже велика: ${\displaystyle |X|=(n-1)!}$

Тепер ми можемо застосувати метод перехресної ентропії. Проте зазначимо що нам потрібно модифікувати алгоритм перехресної ентропії, оскільки маємо задачу на мінімізацію. Нам потрібно визначити як генерувати випадкові маршрути та механізм оновлення параметрів на кожній ітерації. Найпростіше пояснити генерацію маршрутів та оновлення параметрів — зв'язати ${\displaystyle min_{x\in X}S(x)=}$ ${\displaystyle min_{x\in X}\sum _{i=1}^{n-1}}$ з еквівалентною задачею мінімізації. Нехай ${\displaystyle {\tilde {X}}=}$ {${\displaystyle ((x{1},\dots ,x_{n})}$: ${\displaystyle x_{i}\in }${ ${\displaystyle 1,\dots ,n}$ } ${\displaystyle i=2,\dots ,n}$} набір векторів що відповідає шляхам що починаються та закінчуються в 1 і можуть відвідувати одне місто більше одного разу. Зазначимо що ${\displaystyle {\tilde {|X|}}={n}^{n-1}}$ та ${\displaystyle X\in {\tilde {X}}}$. При n=4 маємо наприклад ${\displaystyle x=(1,3,1,3)\in {\tilde {X}}}$ відповідає шляху 1 → 3 → 1 → 3 → 1. Задамо функцію ${\displaystyle {\tilde {S(x)}}}$ на ${\displaystyle {\tilde {X}}}$ . Очевидно що ${\displaystyle {\tilde {X}}=}$ {${\displaystyle ((x{1},\dots ,x_{n})}$: ${\displaystyle x_{i}\in }${ ${\displaystyle 1,\dots ,n}$ } ${\displaystyle i=2,\dots ,n}$} — аналог задачі мінімізації: ${\displaystyle minimize{\tilde {S}}(x)overx\in {\tilde {X}}}$ .

Простий метод генерації випадкового шляху ${\displaystyle X=(X_{1},\dots ,X_{n}\in {\tilde {X}}}$ — застосувати ланцюг Маркова графу G починаючи з вершини 1 та закінчуючи після n кроків. Нехай ${\displaystyle P=(p_{ij})}$ позначає матрицю однокрокових переходів ланцюга Маркова. Візьмемо діагональні елементи P рівними 0, а інші строго додатніми. Функція щільності ${\displaystyle f(-;P)}$ таким чином параметризована матрицею P і її логарифм: ${\displaystyle lnf(x;P)=\sum _{r=1}^{n}\sum _{i,j}^{}I_{x\in {\tilde {X}}}lnp_{ij}.}$

де X ~ я J (Г) є безліч усіх шляхів у X ~ , для яких перехід від г-й вузол, щоб яу. Зміна оновлення правил для цього завдання оптимізації випливають з (W = 1), з {S (Xi) ≥ γ} замінити {S ~ (Xi) ≤ γ}, за умови, що сума рядків P дорівнює 1. Використання множників Лагранжа u1. . . un, ми отримуємо задачу максимізації:

${\displaystyle max_{p}min_{u}[\mathbb {E} _{p}I_{{\tilde {S}}(x)\leq \gamma }lnf(X;P)+\sum _{i=1}^{n}u_{i}(\sum _{j=1}^{n}p_{ij}-1)]}$, продиференціювавши та підсумувавши, маємо:

${\displaystyle p_{i,j}={\frac {\mathbb {E} _{p}I_{{\tilde {S}}(x)}\sum _{r=1}^{n}I_{X\in {\tilde {X}}(r)}}{\mathbb {E} _{p}I_{{\tilde {S}}(x)}\sum _{r=1}^{n}I_{X\in {\tilde {X}}(r)}}}}$ Щоб обновити ${\displaystyle p_{ij}}$ просто беремо частину разів, які з'являється перехід із і в j, розглядаючи тільки ті шляхи, що мають довжину меншу або рівну ${\displaystyle \gamma }$.

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

1. Визначаємо ${\displaystyle P^{(}1)=P}$ та ${\displaystyle X_{1}=1}$. Нехай ${\displaystyle k=1}$
2. Отримуємо ${\displaystyle P^{(}k+1)}$ з ${\displaystyle P^{(}k)}$ беручи Х_k-тий стовпець P^k як 0 та нормуючи суму рядків до 1. Генеруємо Х_k+1 з розподілу сформованого Х_k-тим рядком P^(k)
3. Якщо ${\displaystyle k=n-1}$ то стоп, інакше перейти на крок 2.