Simulated Annealing
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
b. Pseudocode
Apabila data diberikan dalam bentuk koordinat kota ke-I (Xi,Yi ), dengan jumlah kota NC, maka pseudocode-nya sebagai berikut :
Function PjgJalur(L,X,Y):real;
1. Panjang = 0
2. For i = 1 to (NC-1) do
3. Panjang = Panjang + Σ((XL(i+1) - XL(i))2 + (YL(i+1)-YL(i))2)
4. PjgJalur = Panjang
Function T0(MTemp:integer):real;
1. LMax = 0
2. For i = 1 to MTemp do
3. LA = ambil jalur sembarang
4. Len = PjgJalur(LA)
5. IF Len > LMax then LMax=Len
6. T0 = 2*LMax
Function JalurBaru(L):arrayNC;
1. Bangkitkan 2 bilangan random N1 dan N2 antara 1 sampai NC (N1>N2)
2. Depan = L(1) sampai L(N1-1);
3. Tengah = L(N1) sampai L(N2);
4. Belakang = L(N2+1) sampai L(NC);
5. Bangkitkan bilangan random r
6. If r < 0,5 then
7. DepanBaru = Depan
8. TengahBaru(1..NT) = Tengah(NT..1); dengan NT=N2-N1+1
9. BelakangBaru = Belakang
10. Lbaru = [DepanBaru TengahBaru BelakangBaru]
11. else
12. Sementara = [Depan Belakang]; dengan M elemen
13. Bangkitkan bilangan random r dengan nilai antara 1 sampai M
14. DepanBaru = Sementara(1..r)
15. TengahBaru = Tengah
16. BelakangBaru = Sementara(r+1..M)
17. Lbaru = [DepanBaru TengahBaru BelakangBaru]
18. JalurBaru = LBaru
Procedure SimulatedAnneal (MTemp:integer; NC:integer;X,Y:real; MItr:integer;MSukses:integer;decT:real);
1. T = T0(MTemp);
2. L = [1 2 3 . . . NC];
3. MaxIterasi = MItr*NC;
4. MaxSukses = MSukses*NC;
5. JalurTerpendek = L;
6. PjgJalurTerpendek = PjgJalur(L);
7. Sukses = 1;
8. While Sukses > 0
9. Sukses = 0;
10. MinPjgJalur = PjgJalur(L);
11. For i = 1 to MaxIterasi do
12. Jalur = JalurBaru(L);
13. Pjg = PjgJalur(Jalur);
14. If pjg < MinPjgJalur then
15. MinPjgJalur = Pjg;
16. Lbaru = Jalur;
17. Sukses = Sukses + 1;
18. If MinPjgJalur < PjgJalurTerpendek then
19. PjgJalurTerpendek = MinPjgJalur;
20. JalurTerpendek = Lbaru;
21. If Sukses = MaxSukses then BREAK;
22. else
23. Bangkitkan bilangan random r;
24. If r < e-(Pjg-MinPjgJalur)/T then Lbaru = Jalur;
25. L = Lbaru;
26. T = decT * T;
Simulasi Operator
Ada beberapa operator yang bisa digunakan untuk menentukan jalur. Misalkan jumlah kota yang akan dikunjungi adalah NC.
• Kota-kota disimpan pada larik L.
• Bangkitkan 2 bilangan random antara 1 sampai NC. Misalkan kedua bilangan itu adalah N1 dan N2 dengan N1 < N2.
• Depan = L(1) sampai L(N1-1)
• Tengah = L(N1) sampai L(N2)
• Belakang = L(N2+1) sampai L(NC)
• 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]
•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]
Output SimulatedAnneal
• Jalur terpendek yang terletak pada variable jalur terpendek
• Panjang jalur terpendk yang terletak pada variabel PanjangJalurTerpendek
Contoh TSP Dengan Simulated Annealing :
• Misalkan jalur yang ada adalah :
L = [4 3 6 9 11 2 5 1 7 8 12 10] Æ NC = 12
• Bangkitkan bilangan random,
misal: N1 = 4 dan N2 = 10; maka:
o Depan = [4 3 6]
o Tengah = [9 11 2 5 1 7 8]
o Belakang = [12 10]
• Bangkitkan bilangan random r, apabila r < 0,5; maka:
o DepanBaru = [4 3 6]
o TengahBaru = [8 7 1 5 2 11 9]
o BelakangBaru = [12 10]
o Lbaru = [4 3 6 8 7 1 5 2 11 9 12 10]
•Jika r ≥ 0,5; maka diperoleh :
o Sementara = [4 3 6 12 10], M = 5
o Bangkitkan bilangan random r, misal : r = 2
o DepanBaru = [4 3]
o TengahBaru = [9 11 2 5 1 7 8]
o BelakangBaru = [6 12 10]
o Lbaru = [4 3 9 11 2 5 1 7 8 6 12 10]
Ukuran Performasi
- Completeness
Algoritma Simulated Annealing menggunakan pencarian acak untuk mencari solusi optimum, Jadi pasti akan di temukan solusi.
- . Optimality
Karena bergantung pada suatu nilai probabilitas, maka SA tidak selalu menemukan solusi terbaik. Dengan kata lain, SA tidak optimal.
- Time complexity
Pencarian dalam algoritma SA menggunakan pencarian acak, jadi akan memakan waktu yang cukup lama
- Space complexity
Algoritma Simulated Annealing akan menggunakan kapasitas memori yang cukup banyak karena pencarian solusi dengan cara acak.
alhamdulillah, thanks mas.....
catatan mas sngat mmbantu sy dalm mnyelesaikan tugas kuliah sy...
oy, bisa minta gambar program simulasi annealingnya ga?? biar da gmbaran pembuatan programnya. pake java kan ya?????