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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Перехресна ентропія[ред.ред. код]

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

Перехресна ентропія двох розподілів p і q на тому самому ймовірностному просторі визначається наступним чином:

\mathrm{H}(p, q) = \mathrm{E}_p[-\log q] = \mathrm{H}(p) + D_{\mathrm{KL}}(p \| q)\!,

де H(p) — енропія p, і D_{\mathrm{KL}}(p || q) — дивергенція Кульбака-Лейбера від q до p (також відома як відносна ентропія).

Для дискретного випадку p і q це значить

\mathrm{H}(p, q) = -\sum_x p(x)\, \log q(x). \!

Для неперервного розподілу аналогічно:

-\int\limits_X p(x)\, \log q(x)\, dx. \!

NB: Запис \mathrm{H}(p,q) іноді використовується як для перехресної ентропії, так і для приєднанної ентропії p і q.

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

Розглянемо загальну задачу оцінки кількості \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^{L}_{i=1} {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^{N}_{i=1} I_{S(x) \geq \hat{\gamma} } I_{X_{ij}=1} } {\sum^{N}_{i=1} I_{S(x) \geq \hat{\gamma} }} Примітка Ми можемо легко розширити метод на випадок, в якому набір вузлів V розбивається на  r > 2 підмножин {  V_{1}, \dots , V_{n} }Таких, що загальна сума ваг всіх ребер, що виходять з підмножини V_{i} в підмножину V_{j},  i,j = 1 \dots r i \ne 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} ln f(\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) over x \in   \tilde{X} .

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