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

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

Метод перехресної ентропії складається з двох етапів:

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

Оцінка за допомогою вибірки по значущості

Розглянемо загальну задачу оцінки кількості $\ell =\mathbb {E} _{\mathbf {u} }[H(\mathbf {X} )]=\int H(\mathbf {x} )\,f(\mathbf {x} ;\mathbf {u} )\,{\textrm {d}}\mathbf {x}$, де $H$ деяка функція продуктивності та $f(\mathbf {x} ;\mathbf {u} )$ член деякого параметричного сімейства розподілів. Використовуючи вибірку за значенням ця кількість може бути оцінена як ${\hat {\ell }}={\frac {1}{N}}\sum _{i=1}^{N}H(\mathbf {X} _{i}){\frac {f(\mathbf {X} _{i};\mathbf {u} )}{g(\mathbf {X} _{i})}}$, де $\mathbf {X} _{1},\dots ,\mathbf {X} _{N}$ — випадкова вибірка з $g\,$. Для додатних $H$ теоретично оптимальну вибірку за значущістю функції щільності ймовірностей задається $g^{*}(\mathbf {x} )=H(\mathbf {x} )f(\mathbf {x} ;\mathbf {u} )/\ell$. Це, однак, залежить від невідомого $\ell$. Метод перехресної ентропії націлений на наближення до оптимальної функції щільності адаптивно обираючи членів параметричного сімейства які є найближчими (з точки зору дивергенції Кульбака-Лейбера) до оптимальної функції щільності.

Загальний алгоритм методу перехресної-ентропії

1. Обрати початковий вектор параметрів $\mathbf {v} ^{(0)}$; взяти t = 1.
2. Згенерувати випадкову вибірку $\mathbf {X} _{1},\dots ,\mathbf {X} _{N}$ з $f(\cdot ;\mathbf {v} ^{(t-1)})$

3. Розв'язати для $\mathbf {v} ^{(t)}$, де
   $\mathbf {v} ^{(t)}=\mathop {\textrm {argmax}} _{\mathbf {v} }{\frac {1}{N}}\sum _{i=1}^{N}H(\mathbf {X} _{i}){\frac {f(\mathbf {X} _{i};\mathbf {u} )}{f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})}}\log f(\mathbf {X} _{i};\mathbf {v} )$
4. Якщо збіжності досягнуто, то stop; інакше, збільшити t на 1 та перейти на крок 2.

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

• Коли $f\,$ належить до класу експоненційного розподілу
• Коли $f\,$ дискретна зі скінченним носієм функції
• Коли $H(\mathbf {X} )=\mathrm {I} _{\{\mathbf {x} \in A\}}$ та $f(\mathbf {X} _{i};\mathbf {u} )=f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})$, то $\mathbf {v} ^{(t)}$ відповідає оцінці максимальної правдоподібності основаній на $\mathbf {X} _{k}\in A$.

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

Такий самий алгоритм перехресної ентропії може бути застосований для оптимізації. Нехай маємо задачу: максимізувати деяку функцію $S(x)$, наприклад, $S(x)={\textrm {e}}^{-(x-2)^{2}}+0.8\,{\textrm {e}}^{-(x+2)^{2}}$. Для того щоб застосувати метод перехресної ентропії, спочатку розглядається асоційована стохастична задача оцінки $\mathbb {P} _{\boldsymbol {\theta }}(S(X)\geq \gamma )$ для заданого рівня $\gamma \,$ та параметричного сімейства $\left\{f(\cdot ;{\boldsymbol {\theta }})\right\}$, наприклад одновимірний нормальний розподіл, параметризований своїм математичним сподіванням $\mu _{t}\,$ та дисперсією $\sigma _{t}^{2}$ (таким чином ${\boldsymbol {\theta }}=(\mu ,\sigma ^{2})$). Отже, для заданого$\gamma \,$ задачею є знайдення такого ${\boldsymbol {\theta }}$ що $D_{\mathrm {KL} }({\textrm {I}}_{\{S(x)\geq \gamma \}}\|f_{\boldsymbol {\theta }})$ що є мінімальним. Це робиться шляхом вирішення версії вибірки (стохастичний аналог) задачі мінімізації дивергенції Кульбака-Лейблера, як на кроці 3 раніше. Виявляється що параметрами, що мінімізують стохастичний аналог для цього вибору цільового розподілу та параметричного сімейства, є математичним сподівання та дисперсія вибірки що відносяться до елітних вибірок, тобто вибірок, що мають значення цільової функції $\geq \gamma$. Найгірший з елітних вибірок використовується як рівень для наступної ітерації. Це дає наступний рандомізований алгоритм, що збігається з так-званим Алгоритмом Оцінки Багатовимірної Нормалі, алгоритмом оцінки розподілу.

Псевдо-код

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 є безліч двійкових векторів довжини $n$, легкий механізм генерації полягає в залученні кожного компонента незалежно від розподілу Бернуллі, тобто$X=\mathbf {X} _{1},\dots ,\mathbf {X} _{N}$ ~ Бер(р), де р — $\mathbf {p} _{1},\dots ,\mathbf {p} _{N}$. З урахуванням елітного зразку $\varepsilon$ маємо: ${\hat {{p}_{i}}}={\frac {\sum _{x\in \varepsilon }^{}{X_{i}}}{N^{E}}}$, $i=$ $1,\dots ,n$ Тобто, оновлена ймовірність успіху для і-го компонента середнього і-й компоненти векторів в елітний набір. Можливе правило зупинки для задач комбінаторної оптимізації, зупинитися, коли загальне краще цільове значення не змінюється протягом кількох ітерацій. Крім того, можна зупинитися, коли вибірковий розподіл «вироджується». Зокрема, в разі Бернуллі можна зупинити коли все {${p}_{i}$} менше, ніж на деякій відстані ε від 0 або 1.

Умовна оптимізація (оптимізація з обмеженнями)

Задача оптимізації з обмеженнями може бути поставлена в рамках методу перехресної ентропії для оптимізації $S({x}^{*})={\gamma }^{*}$ $=$ $max_{{\vec {x}}\in \mathbb {X} }f({\vec {x}})$ приймаючи X (нелінійний) з області, яка визначається деякою системою нерівностей: $\mathbf {G} _{i},\leq {0}$ ${i}={1}\dots {n}$

Для вирішення можуть бути прийняті два підходи. Перший підхід використовується прийняття-відмову: генерації випадкового вектора $\mathbb {X}$ з, наприклад, багатовимірним нормальним розподілом з незалежними компонентами, і прийняти або відхилити його в залежності від того чи потрапляє зразок в Х чи ні. Крім того, можна спробувати прямо з усіченим розподілом (наприклад, усіченого нормального розподілу) або поєднувати такий метод з прийняттям-відмовою. Після того, як фіксоване число таких векторів було прийнято, параметри нормального розподілу можуть бути оновлені в точності так само, як і в безумовному випадку — просто за допомогою вибіркового середнього та стандартного відхилення елітних зразків. Недоліком цього методу є те, що велика кількість зразків може бути відхилена перед тим як можливий зразок знайдений. Другий підхід — штрафний. Тут ідея полягає в зміні цільової функції так: ${\tilde {S}}(x)=S(x)+\sum _{i=1}^{L}{P_{i}(x)}$ де {$P_{i}$} — штрафні функції. А саме і-та функція {$P_{i}$ відповідає і-му обмеженню, визначається як: $P_{i}=H_{i}\max _{}({G_{i}},0)$, де $H_{i}$ визначає вагу і-го штрафу. Таким чином зводячи задачу з обмеженнями до звичайної (з ${\tilde {S}}(x)$ замість $S(x)$ у $S({x}^{*})={\gamma }^{*}$ $=$ $max_{{\vec {x}}\in \mathbb {X} }f({\vec {x}})$) можна застосувати алгоритм перехресної ентропії.

Стохастична оптимізація

Стохастична задача оптимізації — задача в якій цільова функція спотворена шумами, з'являється у різних контекстах, наприклад у стохастичному плануванні розкладів, стохастичними задачами пошуку найкоротших/найдовших шляхів а оптимізації на основі моделювання. Метод перехресної ентропії може бути легко модифікований для цього класу задач. Розглянемо задачу максимізації $S({x}^{*})={\gamma }^{*}$ $=$ $max_{{\vec {x}}\in \mathbb {X} }f({\vec {x}})$ нехай цільова функція спотворена шумами. Зокрема, приймемо що $S(x)=\mathbb {E} *{\hat {S}}(x)$ не доступна, але значення вибірки ${\hat {S}}(x)$, наприклад, за допомогою симуляцій. Принципова модифікація звичайного алгоритму методу перехресної ентропії полягає в заміні ${S}(x)$ на ${\hat {S}}(x)$. Також, може знадобитися збільшення розміру вибірки щоб зменшити вплив шуму. Незважаючи на те що різні застосування стохастичного підходу до методу перехресної ентропії засвідчують його корисність, ще мало відомо відносно теоретичної збіжності.

Приклади застосування

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

Задача максимального перерізу

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

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

Файл:Grapppff.jpg

Рис.1 Сіть з 6 вузлів, з перерізом{{1, 3, 4}},{{2, 5, 6}}.

${\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

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

Приклад 1

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

${\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}}$

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

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

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

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

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

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

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

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

Приклад 2

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

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

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

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

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

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

де

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

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

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

Задача комівояжера

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

Файл:Tsp.jpg

Графічне задання задачі комівояжера

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

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

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

Простий метод генерації випадкового шляху $X=(X_{1},\dots ,X_{n}\in {\tilde {X}}$ — застосувати ланцюг Маркова графу G починаючи з вершини 1 та закінчуючи після n кроків. Нехай $P=(p_{ij})$ позначає матрицю однокрокових переходів ланцюга Маркова. Візьмемо діагональні елементи P рівними 0, а інші строго додатніми. Функція щільності $f(-;P)$ таким чином параметризована матрицею P і її логарифм: $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, ми отримуємо задачу максимізації:

$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)]$, продиференціювавши та підсумувавши, маємо:

$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)}}}$ Щоб обновити $p_{ij}$ просто беремо частину разів, які з'являється перехід із і в j, розглядаючи тільки ті шляхи, що мають довжину меншу або рівну $\gamma$.

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

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

Обговорення та майбутні напрямки

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

По-друге, збіжність даного методу заслуговує подальшого вивчення. Результати збіжності, що стосуються методу перехресної ентропії можна знайти в декількох джерелах. Як правило, ці є асимптотичними за своєю природою, як і існуючі результати збіжності генетичного алгоритму, імітації відпалу і алгоритмів мурашиної колонії. В результаті вони не завжди проливають багато світла на дійсну (не асимптотичну) поведінку алгоритму. В контексті моделювання рідкісної подій, яке може бути легко пристосована до комбінаторної оптимізації, збіжність методу перехресної ентропії наведена в Homem-de-Mello and Rubinstein(2002). Основне припущення — що в ймовірність рідкісних випадках не звертається в нуль в околиці оптимального рішення. Алгоритм, запропонований в Homem-de-Mello and Rubinstein (2002) такий самий як звичайний алгоритм, окрім того, що ρ і N визначаються адаптивно. Інша теорема про збіжність в заданні рідкісних подій наведено в Lieber (1998). Margolin (2005) надає асимптотичний результат збіжності двох модифікацій основного алгоритму перехресної ентропії. Доказ аналогічно Gutjahr (2000) для оптимізації алгоритму мурашиної колонії. Цей асимптотичний результат результат не дає вказівки по швидкості збіжності. У дослідженні збіжності методу перехресної ентропії належить зробити ще набагато більше, зокрема, встановити межі та швидкість збіжностей, принаймні для деяких особливо складних задач оптимізації.

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

Посилання

• Сторінка присвячена методу перехресної ентропії

Джерела

• G. Alon, D. P. Kroese, T. Raviv, and R. Y. Rubinstein. Application of the cross-entropy method to the buffer allocation problem in a simulationbased environment. Annals of Operations Research, 134:137–151, 2005.
• S. Asmussen, D. P. Kroese, and R. Y. Rubinstein. Heavy tails, importance sampling and cross-entropy. Stochastic Models, 21(1):57–76, 2005.
• I. Bendavid and B. Golany. Setting gates for activities in the stochastic project scheduling problem through the cross entropy methodology. Annals of Operations Research, 2009. To appear.
• Z. I. Botev and D. P. Kroese. Global likelihood optimization via the crossentropy method, with an application to mixture models. In R. G. Ingalls, M. D. Rossetti, J. S. Smith, and B. A. Peters, editors, Proceedings of the 2004 Winter Simulation Conference, pages 529—535, Washington, DC, December 2004.
• A. Boubezoula, S. Paris, and M. Ouladsinea. Application of the cross entropy method to the GLVQ algorithm. Pattern Recognition, 41(10): 3173–3178, 2008.
• M. Caserta and M. Cabo-Nodar. A cross entropy based algorithm for reliability problems. Journal of Heuristics, pages 1381—1231, 2007.
• M. Caserta and M. Cabo-Nodar. A cross-entropy based algorithm for combinatorial optimization problems. European Journal of Operations Research, 2008.
• M. Caserta and E. Qui˜nonez-Ricob. A cross entropy-Lagrangean hybrid algorithm for the multi-item capacitated lot-sizing problem with setup times. Computers & Operations Research, 36(2):530–548, 2009.
• J. C. C. Chan and D. P. Kroese. Randomized methods for solving the winner determination problem in combinatorial auctions. In Proceedings of the 2008 Winter Simulation Conference, 2008.
• J. C. C. Chan and D. P. Kroese. Rare-event probability estimation with conditional Monte Carlo. Annals of Operations Research, 2009. To appear.
• K. Chepuri and T. Homem-de-Mello. Solving the vehicle routing problem with stochastic demands using the cross entropy method. Annals of Operations Research, 134(1):153–181, 2005.
• I. Cohen, B. Golany, and A. Shtub. Managing stochastic finite capacity multi-project systems through the cross-entropy method. Annals of Operations Research, 134(1):183–199, 2005.
• A. Costa, J. Owen, and D. P. Kroese. Convergence properties of the crossentropy method for discrete optimization. Operations Research Letters, 35(5):573–580, 2007.
• P. T. de Boer. Analysis and Efficient Simulation of Queueing Models of Telecommunication Systems. PhD thesis, University of Twente, 2000.
• P. T. de Boer, D. P. Kroese, S. Mannor, and R. Y. Rubinstein. A tutorial on the cross-entropy method. Annals of Operations Research, 134(1):19–67, 2005.
• P. T. de Boer, D. P. Kroese, and R. Y. Rubinstein. A fast cross-entropy method for estimating buffer overflows in queueing networks. Management Science, 50(7):883–895, 2004.
• A. Eshragh, J. A. Filar, and M. Haythorpe. A hybrid simulationoptimization algorithm for the Hamiltonian cycle problem. Annals of Operations Research, 2009. To appear.
• G. E. Evans. Parallel and Sequential Monte Carlo Methods with Applications. PhD thesis, The University of Queensland, Brisbane, 2009.
• J. M. Keith G. E. Evans and D. P. Kroese. Parallel cross-entropy optimization. In Proceedings of the 2007 Winter Simulation Conference, pages 2196—2202, Washington, 2007.
• B. E. Helvik and O. Wittner. Using the cross-entropy method to guide/govern mobile agent's path finding in networks. In S. Pierre and R. Glitho, editors, Mobile Agents for Telecommunication Applications: Third International Workshop, MATA 2001, Montreal, pages 255—268, New York, 2001. Springer-Verlag.
• T. Homem-de-Mello. A study on the cross-entropy method for rare event probability estimation. INFORMS Journal on Computing, 19(3):381–394, 2007.
• K-P. Hui, N. Bean, M. Kraetzl, and D.P. Kroese. The cross-entropy method for network reliability estimation. Annals of Operations Research, 134:101–118, 2005.
• E. Ianovsky and J. Kreimer. An optimal routing policy for unmanned aerial vehicles (analytical and cross-entropy simulation approach). Annals of Operations Research, 2009. To appear.
• J. Keith and D. P. Kroese. Sequence alignment by rare event simulation. In Proceedings of the 2002 Winter Simulation Conference, pages 320—327, San Diego, 2002.