Simulated annealing: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k r2.6.1) (bot Menambah: uk:Алгоритм імітації відпалу |
Tidak ada ringkasan suntingan Tag: Suntingan perangkat seluler Suntingan peramban seluler |
||
(18 revisi perantara oleh 13 pengguna tidak ditampilkan) | |||
Baris 1:
{{
'''Simulated annealing''' (SA) adalah salah satu [[algoritma]] untuk untuk optimisasi yang bersifat generik. Berbasiskan [[probabilitas]] dan [[mekanika statistik]], algoritma ini dapat digunakan untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahan. Masalah yang membutuhkan pendekatan SA adalah masalah-masalah optimisasi kombinatorial, di mana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan itu. Publikasi tentang pendekatan ini pertama kali dilakukan oleh S. Kirkpatrick, C. D. Gelatt dan M. P. Vecchi, diaplikasikan pada desain optimal hardware komputer, dan juga pada salah satu masalah klasik [[ilmu komputer]] yaitu ''Traveling Salesman Problem''. ▼
[[Berkas:Travelling salesman problem solved with simulated annealing.gif|jmpl|Salah satu contoh penerapan ''simulated annealing'']]
Annealing adalah satu teknik yang dikenal dalam bidang metalurgi, digunakan dalam mempelajari proses pembentukan kristal dalam suatu materi. Agar dapat terbentuk susunan kristal yang sempurna, diperlukan pemanasan sampai suatu tingkat tertentu, kemudian dilanjutkan dengan pendinginan yang perlahan-lahan dan terkendali dari materi tersebut. Pemanasan materi di awal proses annealing, memberikan kesempatan pada atom-atom dalam materi itu untuk bergerak secara bebas, mengingat tingkat energi dalam kondisi panas ini cukup tinggi. Proses pendinginan yang perlahan-lahan memungkinkan atom-atom yang tadinya bergerak bebas itu, pada akhirnya menemukan tempat yang optimum, di mana energi internal yang dibutuhkan atom itu untuk mempertahankan posisinya adalah minimum.▼
▲'''
▲[[Annealing (metalurgi)|Sepuh lindap]] adalah satu teknik yang dikenal dalam bidang [[metalurgi]], digunakan dalam mempelajari proses pembentukan [[kristal]] dalam suatu [[materi|bahan]]. Agar dapat terbentuk susunan kristal yang sempurna, diperlukan pemanasan sampai suatu tingkat tertentu, kemudian dilanjutkan dengan pendinginan yang perlahan-lahan dan terkendali dari materi tersebut. Pemanasan materi di awal proses
Simulated Annealing berjalan berdasarkan analogi dengan proses annealing yang telah dijelaskan diatas. Pada awal proses SA, dipilih suatu solusi awal, yang merepresentasikan kondisi materi sebelum proses dimulai. Gerakan bebas dari atom-atom pada materi, direpresentasikan dalam bentuk modifikasi terhadap solusi awal/solusi sementara. Pada awal proses SA, saat parameter suhu (T) diatur tinggi, solusi sementara yang sudah ada diperbolehkan untuk mengalami modifikasi secara bebas. ▼
▲''Simulated Annealing'' berjalan berdasarkan analogi dengan proses ''annealing'' (sepuh lindap) yang telah dijelaskan
Kebebasan ini secara relatif diukur berdasarkan nilai fungsi tertentu yang mengevaluasi seberapa optimal solusi sementara yang telah diperoleh. Bila nilai fungsi evaluasi hasil modifikasi ini membaik (dalam masalah optimisasi yang berusaha mencari minimum berarti nilainya lebih kecil/downhill) solusi hasil modifikasi ini akan digunakan sebagai solusi selanjutnya. ▼
Bila nilai fungsi evaluasi hasil modifikasi ini memburuk, pada saat temperatur annealing masih tinggi, solusi yang lebih buruk (uphill) ini masih mungkin diterima. Dalam tahapan selanjutnya saat temperatur sedikit demi sedikit dikurangi, maka kemungkinan untuk menerima langkah modifikasi yang tidak memperbaiki nilai fungsi evaluasi semakin berkurang. Sehingga kebebasan untuk memodifikasi solusi semakin menyempit, sampai akhirnya diharapkan diperoleh solusi yang mendekati solusi optimal.▼
▲Kebebasan ini secara relatif diukur berdasarkan nilai fungsi tertentu yang mengevaluasi seberapa optimal solusi sementara yang telah diperoleh. Bila nilai fungsi evaluasi hasil
== ''Pemodelan dengan SA'' ==▼
Menurut Kirkpatrick ada empat hal utama yang perlu diperhatikan dalam penggunaan SA untuk memodelkan suatu permasalahan :▼
▲Bila nilai fungsi evaluasi hasil
* Representasi yang akurat dari konfigurasi dalam suatu permasalahan. ▼
* Proses modifikasi, langkah acak atau perubahan apa yang harus dilakukan terhadap elemen-elemen konfigurasi untuk menghasilkan konfigurasi berikutnya.▼
▲Menurut Kirkpatrick ada empat hal utama yang perlu diperhatikan dalam penggunaan SA untuk memodelkan suatu permasalahan
▲* Proses
* Fungsi evaluasi atau fungsi objektif yang dapat menyatakan baik-buruknya suatu solusi terhadap permasalahan
* Jadwal penurunan suhu dalam proses
== ''Pseudo Code'' ==
Baris 22 ⟶ 25:
SolusiSementara = Pilih Suatu Solusi Awal (Random Initialization)
NilaiEvaluasiSementara = Evaluasi(SolusiSementara)
T = Suhu awal
WHILE (belum tercapai konvergensi yang diinginkan)
'''
SolusiBaru = Modifikasi(SolusiSementara)
NilaiEvaluasiBaru = Evaluasi(SolusiBaru)
IF ( SolusiBaru lebih baik )
SolusiSementara = SolusiBaru
NilaiEvaluasiSementara = NilaiEvaluasiBaru
ELSE
Delta = SolusiBaru - SolusiSementara
IF exp(-Delta/T) > Random(0 ..1)
SolusiSementara = SolusiBaru
NilaiEvaluasiSementara = NilaiEvaluasiBaru
'''
T = 0.9*T // Turunkan
</code>
=== Keterangan Pseudo Code ===
'''Evaluasi'''
'''Modifikasi''' atau '''oprek''': Mekanisme sederhana untuk mengubah solusi yang sudah ada, untuk menghasilkan solusi baru yang berbeda tidak terlalu jauh dengan solusi yg sudah ada. Biasanya disebut neighbour solution. Contoh dalam TSP bila solusi sementara dari TSP dengan 3 kota adalah
'''exp(-Delta/T)'''
'''T = 0.9*T'''
== Referensi ==
* S. Kirkpatrick and C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, Science, Vol 220, Number 4598, pages 671-680, 1983. http://citeseer.ist.psu.edu/kirkpatrick83optimization.html.
[[Kategori:
|