Temperatur awal dalam algoritma anil simulasi

14

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?

Tidak terdefinisi
sumber
2
Temperatur awal memiliki banyak kaitan dengan domain masalah dan parameter lain yang Anda gunakan untuk bagian penurunan gradien dari algoritma. Bisakah Anda memberi lebih banyak konteks?
dhj

Jawaban:

9

0.8tmin t δ t E maks t - E min t π min t 1makstmintδtEmakst-Eminttπmint1|N(mint)|t

πsaya=|N(saya)|exp(-Esaya/T)j|N(j)|exp(-Ej/T)
, di mana N(saya) menunjukkan himpunan tetangga saya .

Akhirnya, exp(-δt/T) adalah probabilitas untuk menerima transisi positif t . Sekarang, kita dapat memiliki estimasi χ^ dari probabilitas penerimaan χ(T) berdasarkan set S "acak" Sdari transisi positif:

χ^(T)=tSπmint1|N(mint)|exp(-δt/T)tSπmint1|N(mint)|=tSexp(-Emakst/T)tSexp(-Emint/T).

Kami ingin menemukan suhu sehingga , di mana adalah probabilitas penerimaan yang kita inginkan. χ ( T 0 ) = χ 0 χ 0] 0 , 1 [T0χ(T0)=χ0χ0]0,1[

S E maks t E min t S T 1 T 0T0 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 rekursifSEmakstEmintST1T0

Tn+1=Tndalam(χ^(Tn))dalam(χ0)1/hal
, dengan adalah bilangan real .hal1

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].χ^(Tn)χ0TnT0


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

Juho
sumber
3

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

vzn
sumber