20
4.
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.
2.4
Reduksi Masalah
Pada algoritma-algoritma terdahulu, kita
mencari solusi
menggunakan pohon OR,
dimana
lintasan dari awal
sampai tujuan tidak terletak pada satu cabang. Apabila
lintasan
dari
keadaan
awal
sampai tujuan
dapat
terletak
pada
satu
cabang,
maka
kita
akan
dapat
menemukan tujuan
lebih cepat. Ada beberapa algoritma
untuk
mereduksi
masalah, antara
lain :
1.
Graph AND-OR
Algoritma Graph AND-OR ini pada dasarnya sama dengan Best-First Search,
dengan mempertimbangkan adanya arc AND.
2.
Algoritma AO*
Algoritma
AO*
menggunakan struktur
Graph.
Tiap-tiap
node
pada
graph
tersebut akan
memiliki
nilai
h’
yang
merupakan biaya estimasi
jalur dari
node
itu sendiri sampai suatu solusi.
 |