Metode Simulated annealing

Pendahuluan
Simulated annealing (Kirkpatrick et al. 1983) merupakan prosedure optimisasi fungsi berdasarkan:

1. Perturbasi random dari kandidat solusi
2. Keputusan probabilistik untuk mempertahankan solusi yang telah di mutasi

Simulated annealing diinspirasikan dari proses metalurgi à shaping hot metals menuju ke titik stabil melalui proses pendinginan bertahap dari bentuk:
• disordered,
• unstable,
• high-energy state to an ordered
• stable, low-energy state

Penjelasan singkat Algoritma SA
Dalam simulated annealing à material merupakan kandidat solusi, di mana parameter kandidat solusi diinisialisasi secara random
– Jika energi (eqivalen dengan invers fitness function) lebih rendah: Solusi mengalami mutasi dari kondisi sebelumnya dan solusi yang telah dimutasi menggantikan solusi sebelumnya
– Jika energi lebih tinggi, solusi yang telah dimutasi menggantikan solusi sebelumnya dengan tingkat probabilitas yang proporsional terhadap perbedaan energi dan temperatur
Inisialisasi dengan temperatur sistem tinggi, kemudian solusi dimutasi dengan tingkat energi yang lebih tinggi (low fitness) à beberapa solusi dipertahankan berdasarkan tingkat probabilitas tertentu
Temperatur sistem diturunkan setelah n kali evaluasi dan secara efektif dengan menurunkan probabilitas solusi yang telah dimutasi sebelumnya (state energi yang lebih tinggi)
Prosedur berhenti ketika temperatur annealing bernilai nol.

What is simulated annealing and why do we use it?
• Ketika kita menyelesaikan problem optimisasi yang sulit dengan proses iterasi, solusi mungkin secara prematur terhenti pada suatu lokal minimum (Lihat Gbr)
• Simulated annealing merupakan salah satu teknik di mana kita bisa menghindari solusi pada lokal minima yang tak diinginkan
• Secara umum banyak teknik optimisasi yang iteratif dapat menentukan solusi minimalisasi atau maksimalisasi fungsi objektif sistem, seperti total error, energi, biaya, dst
• Minimalisasi dan maksimalisasi secara teknik identik (teknik yang sama digunakan sama) à untuk minimalisasi kita menuju ke bawah dan sebaliknya untuk maksimalisasi kita menuju ke atas dalam hal pengaturan energi dan temperatur

Ide dasar untuk teknik iteratif sebagai berikut:
• Jika kita dapat menemukan solusi tentang nilai minimum fungsi objective dalam satu kali langkah iterasi maka itulah cara yang terbaik
• Dalam kalkulus, untuk menentukan nilai x sehingga suatu fungsi minimum, maka kita perlu mencari turunan fungsi f'(x) = 0 à inilah yang disebut solusi dengan satu kali langkah
• Akan tetapi, banyak persoalan yang sulit di mana pendekatan solusi satu kali langkah ini tidak berhasil, sehingga kita perlu melakukan proses iterasi
• Proses iterasi à kita perlu memulai dengan pemilihan solusi awal sendiri (bisa diambil random), kemudian solusi ini perlahan-lahah diperbaiki melalui proses iterasi
• Dalam setiap iterasi ini, fungsi f(x) ini menurun secara perlahan dan diharapkan mencapai nilai yang paling bawah (absolute bottom).
• Persoalan umum yang bisa muncul yaitu secara prematur kita sampai pada suatu titik minimum dan secara langsung mengklaim bahwa inilah solusi yang terbaik

•Simulated annealing mencoba menyelesaikan persoalan solusi prematur pada lokal minima dengan mengambil pendekatan probabilistik dibanding sekedar deterministik dalam proses pencarian optimal solusi
•Istilah “probabilistic” = “statistical” or “stochastic”
•Originalitas "simulated annealing“: pendinginan bertahap (proses annealing) metal ke level energi paling rendah sehingga dihasilkan kristal
•Jika metal dipanaskan hingga temperatur tinggi, maka metal akan mencair.
•Jika metal ini didinginkan secara cepat (quenching), atom atau molekul mengikat bersama tanpa mencapai level energi ikat atorm yang terendah sehingga akan diperoleh bahan amorphous (defective state) è Inilah merupakan analogi ketika proses iterasi terhenti pada lokal minimum yang tak diharapkan
•Target kita dalam simulated annealing bahwa kita ingin menghasilkan crystal state, à a global minimum, dengan proses annealing.
•Oleh karena itu kita mula-mula mengeset temperatur tinggi kemudian perlahan-lahan menurunkan temperatur hingga dekat dengan temperartu thermal equilibrium material.

Analogi algoritma dengan konteks fisik dari sistem: • Algoritma yang dijelaskan di sini beranalogi dengan fenomena fisik à khususnya mekanika statistik (statistic mechanics)
• Istilah Energy E adalah ukuran yang digunakan untuk menentukan apakah solusi minimum atau maksimum telah dicapai
• E bisa menyatakan total error, cost, profit, etc., bergantung pada aplikasi
• E tidak menggambarkan energi secara fisik
• Sama halnya dengan temperature T merupakan ukuran lain yang sering disebut pseudo-temperature ;
• T beranalogi dengan temperature dalam thermodynamics, tetapi bukan secara fisik

Probabilities of states in terms of the energy and the temperature
(teori singkat tentang statistic mechanics berkaitan dengan simulated annealing)
Dalam thermodynamics, probabilitas sistem dalam state dengan energy E and temperature T secara proporsional dengan faktor probabilitas Boltzmann:

Selengkapnya silahkan download materinya disini