Simulated
Annealing adalah suatu algoritma optimasi yang
mensimulasikan proses annealing pada pembuatan materi yang terdiri dari butir
kristal atau logam. 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
Berikut ini
adalah pemetaan dari Physical
Annealing ke Simulated
Annealing :
Fisika (termodinamika)
|
Simulated Annealing
|
Keadaan
sistem
|
Solusi
yang mungkin
|
Energi
|
Biaya
|
Perubahan
keadaan
|
Solusi
tetangga
|
Temperatur
|
Parameter
kontrol
|
Keadaan
beku
|
Solusi
heuristik
|
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.
Secara umum ada
3 hal pokok pada simulated annealing, yaitu:
a.
Nilai awal untuk temperatur (T0).
Nilai T0 biasanya
ditetapkan cukup besar (tidak mendekati nol), karena jika T mendekati 0 maka
gerakan simulated annealing akan sama dengan hill climbing. Biasanya temperatur
awal ini ditetapkan sebesar 2 kali panjang suatu jalur yang dipilih secara
acak.
b.
Kriteria yang digunakan untuk
memutuskan apakah temperatur sistem seharusnya dikurangi.
c.
Berapa besarnya pengurangan
temperatur dalam setiap waktu.
Contoh Simulated Annealing
Source : http://tomatcoklat.wordpress.com/2012/07/10/simulated-annealing/
2. TABU SEARCH (Pencarian Tabu)
Tabu Search merupakan suatu metode optimasi yang menggunakan short-term memory untuk menjaga agar proses pencarian tidak terjebak pada nilai optimum lokal. Metode ini menggunakan Tabu List untuk menyimpan sekumpulan solusi yang baru saja dievaluasi.3
Selama proses optimasi, pada setia piterasi, solusi
yang akan dievaluasi akan dicocokkan terlebih dahulu dengan isi Tabu List untuk
melihat apakah solusi tersebut sudah ada pada Tabu List.
Apabila solusi tersebut sudah ada pada Tabu List, maka
solusi tersebut tidak akan dievaluasi lagi pada iterasi berikutnya.Apabila sudah
tidak ada lagi solusi yang tidak menjadi anggota Tabu List, maka nilai terbaik
yang baru saja diperoleh merupakan solusi yang sebenarnya.
Algoritma:
1. Tetapkan:
X = Matriks input berukuran nxm & MaxItr = maksimum iterasi.
2. S = bangkitkan solusi secara random.
3. GlobalMin = FCost(S).
4. Best = S.
5. TabuList = [].
6. Kerjakan dari k =1 sampai MaxItr:
–BestSoFar = FCost(S).
–BestMove = S.
–Kerjakan dari i=1 sampai (n-1)
Contoh Pencarian Tabu
0 komentar:
Post a Comment