SIMULATED ANNEALING

Simulated Annealing  berjalan berdasarkan analogi dengan proses annealing. Pada awal proses Simulated Annealing dipilih suatu solusi awal yang merepresentasikan kondisi materi sebelum proses dimulai. Gerakan bebas dari atom-atom materi,direpresentasikan dalam bentuk modifkasi terhadap solusi awal atau solusi sementara. Pada awal proses  Simulated Annealing, saat parameter Temperature (T) diatur tinggi,solusi sementara yang sudah ada diperbolehkan untuk mengalami modifikasi secara bebas. 

            Kebebasan ini secara relatif diukur berdasarkan nilai fungsi tertentu yang mengevaluasi seberapa optimal solusi sementara yang telah diperoleh. Bila nilai fungsi evaluasi hasil modfikasi 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 temperature annealing masih tinggi, solusi yang lebih buruk (uphill) ini masih mungkin diterima. Dalam tahapan selanjutnya saat temperature 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.

                        Simulated Annealing memanfaatkan analogi antara cara pendinginan dan pembekuan metal menjadi sebuah struktur crystal dengan energi yang minimal (proses penguatan) dan proses pencarian untuk state tujuan minimal dalam proses pencarian. Simulated Annealing lebih banyak menjadi jebakan pada local minimal. Biasanya digunakan untuk penyelesaian masalah yang mana perubahan keadaan suatu kondisi ke kondisi yang lainnya membutuhkan ruang yang sangat luas.

Algoritma: Simulated Annealing

1.        Evaluasi keadaan awal. Jika start adalah tujuan maka pencarian solusi selesai.

       Jika tidak lanjutkan dengan keadaan awal sebagai keadaan sekarang

2.        Inisialisasi BEST_SO_FAR untuk keadaan sekarang

3.        Inisialisasi T (Temperature) sesuai dengan annealing schedule

4.        Kerjakan hingga solusi ditemukan atau sudah tidak ada operator baru lagi akan diaplikasikan kekondisi sekarang

a.         Gunakan operator yang belum pernah digunakan untuk menghasilkan keadaan baru

b.         Evaluasi kondisi baru dengan menghitung:

 ∆E = nilai sekarang – nilai keadaan baru..............................................(2.1)

i.          Jika keadaan baru adalah tujuan maka keadaan baru tersebut menjadi solusi akhir

ii.        Jika keadaan baru bukan tujuan, namun nilainya lebih baik dari sekarang, maka  jadikan   keadaan tersebut sebagai keadaan sekarang

iii.       Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka tetapkan keadaan baru sebagai keadaan sekarang dengan probabilitas         .......................................................................(2.2)

dalam kondisi ini juga buat angka random dengan range yang sama dengan range P. Jika angka random lebih kecil dari P maka solusi diterima. Jika angka random lebih besar dari P maka solusi tidak diterima

c.         Perbaiki T (Temperature) sesuai dengan annealing scheduling

5.       BEST_SO_FAR adalah jawaban yang dimaksud

            Simulated Annealing mempunyai tiga komponen untuk melakukan Annealing schedule. Pertama adalah temperature, kedua adalah kapan temperature itu akan berkurang, ketiga adalah berapa besar temperature tersebut berkurang setiap terjadi perubahan. Juga yang tidak boleh dilupakan kapan temperature tersebut berhenti berkurang.

            Percobaan yang telah menggunakan Simulated Annealing pada berbagai permasalahan menyatakan bahwa cara yang terbaik untuk memilih suatu Annealing Schedule adalah dengan mencoba dan mengamati efeknya pada solusi yang ditemukan dan proses yang terjadi. Untuk mulai menentukan Annealing Schedule, pertama-tama yang perlu diperhatikan adalah ketika T mendekati nol, P menerima solusi yang lebih buruk mendekati kosong. Kedua yang perlu diperhatikan adalah dalam menghitung penerimaan P tergantung dari besarnya nilai ΔE/T. Dengan pentingnya nilai T sehingga perbandingan antara T dengan ΔE dapat dijadikan acuan untuk mencari nilai T yang baik. Nilai T yang baik apabila nilai rata-rata ΔE menghasilkan P = 0,5.  

            Dalam penyelesaian masalah Traveling Salesman Problem menggunakan algoritma simulated Annealing, setelah mengevaluasi keadaan awal atau pembangkitan solusi awal urutan kota yang dikunjungi sebagai solusi sementara, Bangkitkan solusi baru dengan cara membangkitkan dua bilangan random (r1 dan r2) dengan r1 < r2, sehingga urutan kota akan dibagi menjadi tiga bagian yaitu depan, tengah dan belakang. Seterusnya bangkitkan bilangan random R3 dengan syarat jika r3 < 0,5 maka bagian tengah dari kota akan dibalik urutannya sehingga solusi baru menjadi depan, tengah dengan urutan terbalik dan belakang.  Namun ketika r3 ≥ 0,5 maka bagian urutan depan dan belakang digandeng dilanjutkan dengan membangkitkan lagi satu bilangan random r4, kemudian pisahkan menjadi depan baru dan belakang baru sehingga solusi baru menjadi depan baru, tengah, belakang baru.

            Tahapan proses penyelesaian Travelling Salesman Problem dengan Algoritma Simulated Annealing :

1.        Tentukan nilai awal parameter temperature (T) dan temperature akhir

       (T1):0<T1<T

2.        Fungsi atau faktor penurun nilai temperature (F) : 0<F<1

3.        Solusi awal (urutan kota yang dikunjungi)

4.        Jarak total perjalanan (E)

5.        Jika r < 0.5 tengah di balik urutannya, jika r ≥ 0.5 Gandeng muka belakang

6.        Evaluasi solusi baru dengan rumus  ∆E = Eskrg-Ebaru

7.        Proses akan berhenti apabila nilai T ≤ T1

Penyelesaian Travelling Salesman Problem dengan metode Simulated

Annealing menggunakan graph dengan 5 kota :

Gambar 1.1 Graph dengan lima kota

Maka inisialisasikan :

T          = 1000

T1        = 500

F          = 0.8

Solusi awal      (x)        = A – B – C – D – E – A 

E          = 22

Proses 1.

Bangkitkan bilangan Random            : 0,2936 dan 0,5746.

                                   r1                  r2

Maka dapat ditentukan :

Depan              = A     

Tengah                        = B – C – D

Belakang         = E – A 

Selanjutnya masukkan bilangan random 0.1858 untuk menentukan iterasi baru. Karena bilangan random (0.1858) ≤ 0.5, maka syaratnya bagian tengah dibalik urutannya, sehingga iterasinya menjadi X baru = A – D – C – B – E – A , maka  Ebaru = 31. Sehingga ∆E = Elama-Ebaru = E – Ebaru = 22 – 31 = - 7 .

Karena Ebaru ≥ Elama maka hitung probabilitasnya sbb:

P

 

 

Masukkan bilangan random ke 4 : 0.8084, Karena Bilangan random (0.8084) < dari nilai probabilitas, maka jalur yang digunakan sebagai solusi selanjutnya adalah jalur baru = A – D – C – B – E – A, dengan E1 = 31.

Maka hitung faktor penurun temperatur sbb:

T          = T . F

            = 1000 . 0.8

            = 800

Proses 2

X         = A – D – C – B – E – A

E          = 31

Bangkitkan bilangan random 0.7038 dan 0.4367

 

Maka dapat ditentukan

Depan                          = A ─ D

Tengah                        = C ─ B ─ E

Belakang         = A 

Selanjutnya masukkan bilangan random 0.6422 untuk menentukan iterasi baru. Karena bilangan random (0.6422) ≥ 0.5, maka syaratnya depan belakang digabung atau digandeng, menjadi : A – D – A (solusi sementara) jadi untuk menentukan penempatan posisi bagian tengah akan masuk kemana maka masukkan bilangan random : 0.5166

 

sehingga iterasinya menjadi  X baru = A – C – B – E – D  – A = 26, maka Ebaru = 26. Sehingga ∆E = Elama-Ebaru = E – Ebaru = 31 – 26 = 5

Maka hitung faktor penurun temperatur sbb:

T          = T . F

= 800 . 0.8

= 640

Proses 3

X         = A – C – B – E – D  – A

E          = 26

Bangkitkan bilangan random 0.6104 dan 0.6494

 

                                        

Maka dapat ditentukan :

Depan              = A – C – B

Tengah                        = E

Belakang         = D – A

Selanjutnya masukkan bilangan random 0.0280 untuk menentukan iterasi baru Karena bilangan random (0.0280) ≤ 0.5, maka syaratnya bagian tengah dibalik urutannya, sehingga iterasinya menjadi Xbaru = A – C – B – E – D – A , maka Ebaru = 26. Sehingga ∆E = Elama-Ebaru = E – Ebaru = 26 – 26 = 0

Maka hitung faktor penurun temperatur sbb:

T          = T . F

            = 640 . 0.8

            = 512

Proses 4

X         = A – C – B – E – D  – A

E          = 26

Bangkitkan bilangan random  0.5358 dan 0.4246

                                 

Maka dapat ditentukan :

Depan              = A – C

Tengah                        = B – E

Belakang         = D – A 

Selanjutnya masukkan bilangan random 0.8930 untuk menentukan iterasi baru. Karena bilangan random (0.8930) ≥ 0.5, maka syaratnya depan-belakang digandeng, menjadi :  A – C – D – A  (solusi sementara) jadi untuk menentukan penempatan posisi bagian tengah akan masuk kemana maka masukkan bilangan random : 0.4845

             

sehingga iterasinya menjadi Xbaru = A – C – B – E – D – A , maka Ebaru = 26. Sehingga ∆E = Elama-Ebaru = E – E1 = 26 – 26=  0 .

Maka hitung faktor penurun temperatur sbb:

T          = T . F

            = 512 . 0.8

            = 409,6

Karena T ≤ T1 maka proses diberhentikan.

Dari keempat proses tersebut maka didapatkan jalur terpendek untuk kasus TSP dengan jarak total perjalanan 22 satuan.

2.2       Distribusi Uniform

Bila variabel random X berharga  , …, dengan peluang yang sama (equal likely), maka kita dapat gambarkan variabel random ini dengan distribusi uniform :

F(x;k) = ,untuk x =  …, ……................………………….…....(2.3)

2.3`      Mean dan Variansi

Mean: E(X)  = ………….………....................………………...…......(2.4)  

Var   :  (X)   =              ………..……...........…….……..…......…......…..(2.5)

Misalkan sebuah dadu seimbang dilemparkan satu kali,maka                           S ={1,2,3,4,5,6}. X menyatakan mata dadu yang muncul, maka X brdistribusi peluang uniform, yakni  f (x,6) = 1/6.

E(X) =  =   =  =  = 3,5

Var(X) = =  =  =