Kombinatorická minimalizace

Cílem je nalézt globální minimum ve velké diskrétní množině, kde může být mnoho lokálních minim.

Příkladem uvedeného typu úlohy je úloha obchodního cestujícího.
Cílem je najít nejkratší cestu, kterou cestující projede všechny uzly a vrátí se zpět do výchozího bodu. Možností je sice konečný počet, ale příliš mnoho na to, abychom je všechny vyzkoušeli. Např. pro 20 mezilehlých uzlů máme $\frac{N!}{2} = \frac{20!}{2} \approx 10^{18}$ možností.

Používá se Metropolisův algoritmus (simulované žíhání). Postup má následující kroky:

1. Popis možných konfigurací.
2. Generátor náhodných změn konfigurace.
3. Hledáme minimum funkce $E \equiv L = \sum \limits_{i=0}^{N+1} \sqrt{(x_i - x_{i+1})^2 + (y_i - y_{i+1})^2} + \lambda (\mu_i - \mu_{i+1})^2$ (poslední člen je například pokuta za překročení hranice - pokud $\lambda > 0$ chceme omezit překračování hranice, $\lambda < 0$ výhodné pro pašeráka).
4. Rychlost ochlazování. Na počátku provádíme i změny konfigurací, při nichž $E$ poněkud vzroste, abychom se dostali z okolí lokálních minim. Změnu konfigurace provedeme, pokud $\Delta E < T_n > 0$ a pro $n \to \infty$ snižujeme $T_n \to 0$.

Elementární změny konfigurací pro úlohu obchodního cestujícího:

1. Při reversi původní pořadí $i-1, i, i+1, \dots, j-1, j, j+1$ transformací změníme na $i-1, j, j-1, \dots, i+1, i, j+1$.
2. Při transportu původní posloupnost $i-1, i, i+1, \dots, j-1, j, j+1, \dots, k-1, k, k+1, \dots$ transformujeme na $i-1, j+1, \dots, k-1, k, i, i+1, \dots, j-1, j, k+1$