Ide dasar simulated annealing terbentuk dari pemrosesan logam. Annealing -> memanaskan kemudian mendinginkan. SA memanfaatkan analogi antara cara pendinginan dan pembekuan metal menjadi sebuah struktur crystal dengan energi yang minimal (proses penguatan) dan pencarian untuk state tujuan minimal dalam proses pencarian. SA biasanya digunakan untuk penyelesaian masalah yang mana perubahan keadaan dari suatu kondisi ke kondisi yang lainnya membutuhkan ruang yang sangat luas
Tidak seperti pendekatan HC (dengan jalan mengikuti sebuah turunan yang tetap dalam meminimisasi masalah), SA lebih banyak menjadi jebakan pada local minima. Pada Seperti diilustrasikan oleh gambar di bawah, simulated annealing berusaha keluar dari jebakan minimum local.
Random Search pada SA:
• Algoritma SA menggunakan pencarian acak yang tidak hanya menerima perubahan yang mengurangi fungsi energi (sebagai harapan : fungsi ini mungkin memberikan resiko perjalanan antara dua kota), tapi juga beberapa perubahan yang menambah fungsi nilai, kemudian SA ijin untuk melompat keluar dari local minima.
• Probabilitas dengan SA yang akan menerima sebuah penambahan dalam energi system DE adalah dinyatakan sebagai berikut:
• Kenapa fungsi ini? Mengadopsi dari fisika, dimana fungsi ini merepresentasikan distribusi Boltzman dari energi dalam system termodinamik. Sehingga didapat persamaan probabilitas dari level energi yang diberikan dalam system pada temperatur T.
• Dugaan dari temperatur sistem adalah intrinsic pada proses SA. Dengan penurunan temperatur yang lambat dari awal system acak, kita mendorong elemen-elemen dari system disimpulkan dengan sebuah pesan, paling sedikit susunan energi. Dalam mencari proses terminal, sebuah pendinginan yang lambat dapat kemudian menuju sebuah state opsional.
Algoritma untuk mensimulasikan penguatan sedikit berbeda dengan prosedur simple HC, yaitu:
• Jadwal penguatan harus di-maintain.
• Pindah ke state yang lebih jelek mungkin diterima.
• Ini adalah ide yang baik untuk maintain, untuk menambahkan current state, state terbaik ditemukan terlalu jauh. Maka, jika state tujuan lebik jelek daripada state sebelumnya (karena kegagalan dalam penerimaan pemindahan worse state), state sebelumnya masih tersedia.
Ada 3 hal yang perlu diperhatikan dari algoritma simulated annealing :
1. Nilai awal untuk Temperatur (T0). Nilai T0 biasanya ditetapkan cukup besar (tidak mendekati nol). Biasanya T0 ditetapkan 2 kali panjang suatu jalur yang dipilih secara acak.
2. Kriteria yang digunakan untuk memutuskan apakah temperatur sistem seharusnya dikurangi atau tidak.
3. Berapa besarnya pengurangan temperatur dalam setiap waktu.
Simulated Annealing pada TSP :
1. Simulated Annealing padaTSP digunakan untuk menelusuri dan mencari setiap rute yang mungkin, kemudian mendapatkan rute yang jaraknya paling pendek.
2. Model Simulated Annealing untuk menyelesaikan TSP adalah model state yang dibangun untuk menyatakan rute yang mungkin dan definisi energi yang dinyatakan dengan total jarak yang ditempuh.
Prosedur Pencarian ( Algoritma dan pseudocode ) :
1. Evaluasi Keadaan awal. Jika keadaan awal merupakan tujuan, maka pencarian berhasil dan KELUAR. Jika tidak demikian, lanjutkan dengan menetapkan keadaan awal sebagai kondisi sekarang.
2. Inisialisasi BEST_SO_FAR untuk keadaan sekarang.
3. Inisialisasi T sesuai dengan annealing schedule
4. Kerjakan hingga solusi ditemukan atau sudah tidak ada operator baru lagi yang akan diaplikasikan ke kondisi sekarang.
a. Gunakan operator yang belum pernah digunakan tersebut untuk menghasilkan kondisi baru
b. Evaluasi kondisi yang baru dengan menghitung :
∆Ε = nilai sekarang – nilai keadaan baru
i. Jika kondisi baru = tujuan, maka pencarian berhasil dan KELUAR.
ii. Jika bukan tujuan, namun memiliki nilai yang lebih baik dari pada kondisi sekarang, maka kondisi baru = kondisi sekarang. Demikian pula tetapkan BEST_SO_FAR untuk kondisi yang baru tadi.
iii. Jika nilai kondisi baru tidak lebih baik dari kondisi sekarang, maka tetapkan kondisi baru = kondisi sekarang, dengan probabilitas :
p´ = e-∆Ε/Τ
Langkah ini biasanya dikerjakan dengan membangkitkan suatu bilangan random r pada range [0 1]. Jika r < p’, maka perubahan kondisi baru menjadi kondisi sekarang diperbolehkan. Namun jika tidak demikian, maka tidak akan dikerjakan apapun.
c. Perbaiki T sesuai dengan annealing scheduling
5. BEST_SO_FAR adalah jawaban yang dimaksudkan
Read More >>
