Simulated Annealing

Ide dasar simulated annealing terbentuk dari pemrosesan logam. Annealing (memanaskan kemudian mendinginkan) dalam pemrosesan logam ini adalah suatu proses bagaimana membuat bentuk cair berangsur-angsur menjadi bentuk yang lebih padat seiring dengan penurunan temperatur. Simulated annealing biasanya digunakan untuk penyelesaian masalah yang mana perubahan keadaan dari suatu kondisi ke kondisi yang lainnya  membutuhkan ruang yang sangat luas, misalkan perubahan gerakan dengan menggunakan permutasi pada masalah Travelling Salesman Problem. Pada simulated annealing, ada 3 parameter yang sangat menentukan, yaitu: tetangga, gain, temperatur, pembangkitan bilangan random. Tetangga akan sangat berperan dalam membentuk perubahan pada solusi sekarang. Pembangkitan bilangan random akan berimplikasi adanya probabilitas.

Algoritma Simulated Annealing
Algoritma Simulated Annealing adalah sebagai berikut :
a. Evaluasi keadaan awal. Jika keadaan awal merupakan tujuan, maka  pencarian berhasil dan KELUAR. Jika tidak demikian, lanjutkan dengan menetapkan keadaan awal sebagai kondisi sekarang.
b. Inisialisasi BEST_SO_FAR untuk keadaan sekarang.
c. Inisialisasi T sesuai dengan annealing schedule.
d. Kerjakan hingga solusi ditemukan atau sudah tidak ada operator baru lagi akan diaplikasikan ke kondisi sekarang.
1. Gunakan operator yang belum pernah digunakan tersebut untuk menghasilkan kondisi baru.
2. Evaluasi kondisi yang baru dengan menghitung:
E = nilai sekarang – nilai keadaan baru.

  • Jika kondisi baru merupakan tujuan, maka pencarian berhasil dan KELUAR.
  • Jika bukan tujuan, namun memiliki nilai yang lebih baik daripada kondisi sekarang, maka tetapkan kondisi baru sebagai kondisi sekarang. Demikian pula tetapkan BEST_SO_FAR untuk kondisi yang baru tadi.
  • Jika nilai kondisi baru tidak lebih baik dari kondisi sekarang, maka tetapkan
  • kondisi baru sebagai kondisi sekarang dengan probabilitas:

p’ eE / T
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.
3. Perbaiki T sesuai dengan annealing scheduling.
e. BEST_SO_FAR adalah jawaban yang dimaksudkan.

Operator untuk Penyelesaian TSP dengan Simulated Annealing
Ada beberapa operator yang bisa digunakan untuk penyelesaian TSP dengan
Simulated Annealing. Berikut adalah salah satu contoh operator untuk menentukan jalur. Misalkan jumlah kota yang akan dikunjungi adalah NC.
a. Kota-kota disimpan pada larik L.
b. Kita bangkitkan 2 bilangan random antara 1 sampai NC, misalkan kedua bilangan itu adalah N1 dan N2 dengan N1 < N2.
c. Depan = L(1) sampai L(N1-1).
d. Tengah = L(N1) sampai L(N2).
e. Belakang = L(N2+1) sampai L(NC).
f. Bangkitkan bilangan random r, apabila r < 0,5; maka:
o DepanBaru = Depan.
o TengahBaru = Tengah dengan urutan dibalik.
o BelakangBaru = Belakang.
o Lbaru = [DepanBaru TengahBaru BelakangBaru]
g. Jika r = 0,5; maka kerjakan:
o Sementara = [Depan Belakang], misalkan memiliki M elemen.
o Bangkitkan bilangan random r dengan nilai antara 1 sampai M.
o DepanBaru = Sementara(1:r).
o TengahBaru = Tengah.
o BelakangBaru = Sementara(r+1:M).
o Lbaru = [DepanBaru TengahBaru BelakangBaru]

Metodologi Penelitian
Penelitian dilakukan melalui langkah-langkah sebagai berikut:
a. Menentukan variabel-variabel input properti sistem, yang meliputi: jumlah mesin, dimensi setiap mesin (panjang dan lebar), mesin-mesin yang digunakan pada setiap part, volume produksi, dan ukuran batch;
b. Merepresentasikan solusi dengan analogi TSP.
c. Menentukan parameter-parameter Simulated Annealing, yang meliputi: maksimum perulangan, maksimum sukses, dan penurunan temperatur.
d. Mengaplikasikan simulated annealing untuk mencari tata letak mesin dengan biaya minimum.

Sri kusuma dewi , Hari purnomo, UII

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s