Temperatura początkowa w symulowanym algorytmie wyżarzania

Przeprowadziłem pewne testy różnych temperatur początkowych w moim algorytmie symulującym wyżarzanie i zauważyłem, że temperatura początkowa ma wpływ na wydajność algorytmu.

Czy jest jakiś sposób obliczenia dobrej temperatury początkowej?

$0.8$$t$min t δ t E max t - E min t π min t $\max_t$$\min_t$$\delta_t$$E_{\max_t} - E_{\min_t}$$\pi_{\min_t} \dfrac{1}{|N(\min_t)|}$$t$

N(i)

$$\pi_i = \dfrac{|N(i)|\text{exp}(-E_i/T)}{\sum_j |N(j)| \exp(-E_j/T)}$$ , gdzie oznacza zbiór sąsiadów .$N(i)$$i$

Wreszcie, to prawdopodobieństwo zaakceptowania przejścia dodatniego . Teraz możemy uzyskać oszacowanie prawdopodobieństwa akceptacji na podstawie „losowego” zestawu pozytywnych przejść:T Ď Ď ( T ) $\text{exp}(-\delta_t/T)$$t$$\hat{\chi}$$\chi(T)$$S$

$$\begin{eqnarray} \hat{\chi}(T) &=& \dfrac{\sum_{t \in S} \pi_{\min_t} \dfrac{1}{|N(\min_t)|} \text{exp}(- \delta_t / T)}{\sum_{t \in S} \pi_{\min_t} \dfrac{1}{|N(\min_t)|}} \\ &=& \dfrac{ \sum_{t \in S} \text{exp}(- E_{\max_t} / T) }{ \sum_{t \in S} \text{exp}(- E_{\min_t} / T) }. \end{eqnarray}$$

Chcemy znaleźć temperaturę taką, że , gdzie to oczekiwane prawdopodobieństwo akceptacji. χ ( T 0 ) = χ 0 χ 0 ∈ ] 0 , 1 $T_0$$\chi(T_0) = \chi_0$$\chi_0 \in ] 0,1 [$

S E max t E min t S T 1 T $T_0$ oblicza się metodą iteracyjną. Generowane są niektóre stany i sąsiad dla każdego stanu. To daje nam zestaw przejścia . Energie i odpowiadające stanom podzbioru są przechowywane. Następnie wybierana jest wartość dla , która może być dowolną wartością dodatnią. Następnie znajduje się w formule rekurencyjnej$S$$E_{\max_t}$$E_{\min_t}$$S$$T_1$$T_0$

$$T_{n+1} = T_n \dfrac{\ln(\hat{\chi}(T_n))}{\ln(\chi_0)}^{1/p}$$ , gdzie jest liczbą rzeczywistą .$p$$\geq 1$

Kiedy zbliży się do , możemy przestać. jest teraz dobrym przybliżeniem pożądanej temperatury początkowej . Więcej wyjaśnień, dowodów i dyskusji znajduje się w pierwszej części oryginalnego artykułu [1].$\hat{\chi}(T_n)$$\chi_0$$T_n$$T_0$

---

[1] Ben-Ameur, Walid. „Obliczanie początkowej temperatury symulowanego wyżarzania”. Optymalizacja obliczeniowa i aplikacje 29, no. 3 (2004): 369–385.

jest to bardzo zaawansowany temat związany z uzyskiwaniem bardzo ciasnych optymów. rozumiem, początkowa temperatura jest ogólnie uważana za część strategii „harmonogramu temperatur”, dla której istnieją pewne głębokie badania. innymi słowy zarówno początkowy warunek temperatury, jak i algorytm zaniku temperatury (o których nie wspominasz) wpływają na ogólne wyniki optymalizacji. proste strategie lub heurystyka dla obu często dają dobre lub „wystarczająco dobre” wyniki.

istnieje jednak co najmniej jeden artykuł, który bada samą początkową temperaturę. [1] Najważniejsze jest to, że jeśli nie wykonujesz bardzo zaawansowanej pracy, traktowanie temperatury początkowej jako parametru problemu i iteracja różnych temperatur początkowych jako część ogólnej optymalizacji [po stwierdzeniu, że rzeczywiście wpływa na wyniki] jest bardzo rozsądne i prawdopodobnie powszechna praktyka.

lub nawet samo wybranie temperatury początkowej, która daje dobre wyniki, jest również powszechne (wydaje się to nieco zaskakujące i nie często wyniki optymalizacji wystąpienia problemu różnią się znacznie od „lepszego” parametru temperatury początkowej stwierdzonego metodą prób i błędów) . jak wskazał dhj, niektóre problemy będą bardziej wrażliwe niż inne na temperaturę początkową.

[1] Obliczanie początkowej temperatury symulowanego wyżarzania Ben-Ameur 2004

[2] Wydajny harmonogram symulowanego wyżarzania: pochodzenie Lam i Delosme

[3] Kontrola temperatury dla symulowanego wyżarzania Munakata i Nakamura