Temperatur awal dalam algoritma anil simulasi

Saya telah melakukan beberapa pengujian suhu awal yang berbeda dalam simulasi algoritma anil saya dan memperhatikan suhu awal memiliki pengaruh pada kinerja algoritma.

Apakah ada cara untuk menghitung suhu awal yang baik?

$0.8$$t$min t δ t E maks 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$

$$\pi_i = \dfrac{|N(i)|\text{exp}(-E_i/T)}{\sum_j |N(j)| \exp(-E_j/T)}$$ , di mana $N(i)$ menunjukkan himpunan tetangga $i$ .

Akhirnya, $\text{exp}(-\delta_t/T)$ adalah probabilitas untuk menerima transisi positif $t$ . Sekarang, kita dapat memiliki estimasi $\hat{\chi}$ dari probabilitas penerimaan $\chi(T)$ berdasarkan set S "acak" $S$dari transisi positif:

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

Kami ingin menemukan suhu sehingga , di mana adalah probabilitas penerimaan yang kita inginkan. χ ( T 0 ) = χ 0 χ 0 ∈ ] 0 , 1 $T_0$$\chi(T_0) = \chi_0$$\chi_0 \in ] 0,1 [$

S E maks t E min t S T 1 T $T_0$ dihitung dengan metode berulang. Beberapa negara bagian dan tetangga untuk setiap negara bagian dihasilkan. Ini memberi kita seperangkat transisi . Energi dan sesuai dengan status subset disimpan. Kemudian nilai untuk dipilih, yang bisa berupa nilai positif apa pun. kemudian ditemukan dengan rumus rekursif$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}$$ , dengan adalah bilangan real .$p$$\geq 1$

Ketika mendekati kita bisa berhenti. sekarang merupakan perkiraan yang baik dari suhu awal yang diinginkan . Untuk penjelasan lebih lanjut, bukti dan diskusi, silakan lihat bagian pertama dari makalah asli [1].$\hat{\chi}(T_n)$$\chi_0$$T_n$$T_0$

---

[1] Ben-Ameur, Walid. "Menghitung suhu awal anil yang disimulasikan." Optimalisasi dan Aplikasi Komputasi 29, no. 3 (2004): 369-385.

ini adalah topik yang sangat canggih terkait dengan mendapatkan optimum yang sangat ketat. pemahaman saya, suhu awal umumnya dianggap bagian dari strategi "jadwal suhu" yang ada beberapa penelitian mendalam. dengan kata lain baik kondisi suhu awal dan algoritma peluruhan suhu (yang tidak Anda sebutkan) mempengaruhi hasil optimasi keseluruhan. strategi atau heuristik sederhana untuk keduanya sering kali menghasilkan hasil yang baik atau "cukup baik".

namun setidaknya ada satu makalah yang mempelajari suhu awal saja. [1] intinya adalah bahwa kecuali Anda melakukan pekerjaan yang sangat maju, memperlakukan suhu awal sebagai parameter masalah dan mengulangi lebih dari suhu awal yang berbeda sebagai bagian dari keseluruhan optimasi [setelah menemukan bahwa itu memang mempengaruhi hasil] adalah sangat wajar dan mungkin praktik yang tersebar luas.

atau, bahkan hanya memilih suhu awal yang memberikan hasil yang baik juga umum (akan terlihat agak mengejutkan & tidak sering bahwa hasil optimasi contoh masalah bervariasi secara substansial dari parameter suhu awal "lebih baik" yang ditemukan oleh coba-dan-kesalahan) . seperti dhj tunjukkan beberapa masalah akan lebih sensitif daripada yang lain untuk suhu awal.

[1] Menghitung Suhu Awal Simulasi Annealing Ben-Ameur 2004

[2] Jadwal Annealing Simulasi yang Efisien: Derivasi Lam & Delosme

[3] Kontrol suhu untuk anil simulasi Munakata & Nakamura