metode pencarian dan pelacakan (prolog)
TRANSCRIPT
Metode Pencarian Dan Pelacakan
Hal penting dalam menentukan keberhasilan sistem berdasarkan kecerdasan
adalah dalam pencarian dan pencocokan. Pada dasarnya ada 2 teknik pencarian dan
pelacakan yang digunakan, yaitu pencarian buta (blind search) dan pencarian
terbimbing (heuristic search).
1. Pencarian Buta (Blind Search)
A. Pencarian Melebar Pertama (Breadth-First Search)
Pada metode Breadth-First Search, Semua node pada level n akan dikunjungi
terlebih dahulu sebelum level n+1. Pencarian dimulai dari akar terus ke level 1 dari
kiri ke kanan, kemudian ke level selanjutnya hingga solusi ditemukan (Gambar 1.0)
Gambar 1.0 Metode Breadth-First Search
1
Algoritma
1. Buat suatu variabel Node_List dan tetapkan sebagai keadaan awal.
2. Kerjakan langkah-langkah berikut ini sampai tujuan tercapai atau Node_List
dalam keadaan kosong :
Hapus elemen pertama dari Node_List, sebut dengan nama C. Jika Node_List
kosong, keluar.
Pada setiap langkah yang aturannya cocok dengan C, kerjakan :
(i) Aplikasi aturan tersebut untuk membentuk suatu keadaan baru.
(ii) Jika keadaan awal adalah tujuan yang diharapkan,
sukses dan keluar.
(iii) Jika tidak demikian, tambahkan keadaan awal yang
baru tersebut pada akhir Node_List.
Keuntungan
1. Tidak akan menemui jalan buntu.
2. Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang
ditemukan pasti yang paling baik.
3. Jika ada satu solusi maka bread-first search akan menemukannya.
Kelemahannya
1. Membutuhkan memori yang cukup banyak.
2. Membutuhkan waktu yang cukup lama karena akan menguji n level untuk
mendapatkan solusi pada level yang ke-(n+1).
B. Pencarian mendalam pertama (Depth-First Search)
2
Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian
ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih
tinggi. Proses ini diulangi terus hingga ditemukannya solusi (Gambar 1.1).
Gambar 1.1 Metode Depth-First search
Algoritma
1. Jika keadaan awal merupakan tujuan, keluar (sukses).
2. Jika tidak demikian, kerjakan langkah-langkah berikut ini sampai tercapai
keadaan sukses atau gagal.
Bangkitkan successor C dari keadaan awal. Jika tidak ada successor,
maka akan terjadi kegagalan.
Panggil depth-first search dengan C sebagai keadaan awal.
Jika sukses berikan tanda sukses. Namun jika tidak, ulangi langkah-2
Keuntungan
1. Memori yang relatif kecil
3
C
A
B
2. Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak
lagi.
Kelemahan
1. Memungkinkan tidak ditemukannya tujuan yang diharapkan.
2. Hanya akan mendapatkan 1 solusi pada setiap pencarian.
2. Pencarian Heuristik (Heuristic Search)
Pencarian buta tidak selalu dapat diterapkan dengan baik, hal ini disebabkan
waktu aksesnya yang cukup lama serta besarnya memori yang diperlukan. Metode
heuristic search diharapkan bisa menyelesaikan permasalahan yang lebih besar.
Metode heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan
(estimasi) dari suatu simpul tertentu menuju ke simpul tujuan disebut fungsi heuristic.
Sebagai contoh aplikasi yang menggunakan fungsi heuristic : Google, Deep Blue
Chess Machine.
Misalkan pada kasus 8 puzzle (Gambar 2.0)
Ada 4 operator yang dapat kita gunakan untuk menggerakkan dari satu keadaan ke
keadaan yang baru.
1). Ubin kosong digeser ke kiri
2). Ubin kosong digeser ke kanan
3). Ubin kosong digeser ke bawah
4). Ubin kosong digeser ke atas
4
Keadaan awal Tujuan
Gambar 2.0 Kasus 8 puzzle
Tujuan
Gambar 2.1 Langkah awal kasus 8-puzzle
1 2 3
7 8 4
6 5
1 2 3
8 4
7 6 5
1 2 3
8 4
7 6 5
1 2 3
8 4
7 6 5
1 2 3
7 8 4
6 5
1 2 3
7 4
6 8 5
1 2 3
7 8 4
6 5
5
Langkah Awal hanya 3 operator yang bisa digunakan ubin kosong digeser ke
kiri, ke kanan dan ke atas. Jika menggunakan pencarian buta, tidak perlu mengetahui
operasi apa yang akan dikerjakan (sembarang). Pada pencarian heuristik perlu
diberikan informasi khusus dalam domain tersebut.
Informasi yang bisa diberikan, antara lain:
Untuk jumlah ubin yang menempati posisi yang benar jumlah yang lebih
tinggi adalah yang lebih diharapkan (lebih baik), Gambar 2.2.
Tujuan
h=6 h=4 h=5
Gambar 2.2 Fungsi heuristic pertama kasus 8-puzzle
Dari 3 operator yang digunakan, diperoleh hasil: pergeseran ubin kosong ke
kiri bernilai 6 (h=6), pergeseran kosong ke kanan bernilai 4 (h=4), dan pergeseran
ubin kosong ke atas bernilai 5 (h=5). Sehingga nilai bilangannya adalah 6 (terbesar).
1 2 3
8 4
7 6 5
1 2 3
8 4
7 6 5
1 2 3
7 8 4
6 5
1 2 3
7 8 4
6 5
1 2 3
7 4
6 8 5
6
Sehingga langkah selanjutnya yang harus dilakukan adalah menggeser ubin kosong
ke kiri.
Untuk jumlah ubin yang menempati posisi yang salah jumlah yang lebih kecil
adalah yang diharapkan (lebih baik), Gambar 2.3.
Tujuan
h=2 h=4 h=3
Gambar 2.3 Fungsi heuristic kedua kasus 8-puzzle
1 2 3
8 4
7 6 5
1 2 3
8 4
7 6 5
1 2 3
7 4
6 8 5
1 2 3
7 8 4
6 51 2 3
7 8 4
6 5
7
Nilai terbaik diperoleh dengan menggeser ubin kosong ke kiri (h=2). Karena nilai ini
paling kecil diantara nilai lainnya (4 & 3). Sehingga langkah selanjutnya adalah
menggeser ubin kosong ke kiri.
Menghitung total gerakan yang diperlukan untuk mencapai tujuan jumlah
yang lebih kecil adalah yang diharapkan (lebih baik), Gambar 2.4.
Tujuan
h=2
h=4 h=4
1 2 3
8 4
7 6 5
1 2 3
8 4
7 6 5
1 2 3
8 4
7 6 5
1 2 3
8 4
7 6 5
1 2 3
8 4
7 6 5
8
Gambar 2.4 Fungsi heuristic ketiga kasus 8-puzzle
Nilai terbaik adalah 2 (h=2) yang diperoleh dengan menggeser ubin kosong ke kiri.
Nilai ini paling kecil dibandingkan dengan nilai lainnya (4). Sehingga menggeser
ubin ke kiri adalah yang harus dilakukan selanjutnya.
Ada 4 metode pencarian heuristic:
A. Pembangkit & Pengujian (Generate and Test)
B. Pendakian Bukit (Hill Climbing)
C. Pencarian Terbaik Pertama (Best First Search)
D. Simulated Annealing
A. Pembangkit & Pengujian (Generate and Test)
Pada prinsipnya metode ini merupakan penggabungan antara depth-first
search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju
pada suatu keadaan awal. Nilai pengujian berupa ‘ya’ atau ‘tidak’.
Algoritma
1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu
atau lintasan tertentu dari keadaan awal).
2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya
dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan
yang dipilih dengan kumpulan tujuan yang diharapkan.
3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang
pertama.
9
Contoh : Traveling Salesman Problem (TSP)
Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah
diketahui. Ingin diketahui rute terpendek dimana setiap kota hanya boleh dikunjungi
tepat 1 kali. Disini, penyelesaian dengan menggunakan generate & test akan
membangkitkan semua solusi yang mungkin denagn menyusun kota-kota dalam
urutan abjad, yaitu:
– A – B – C – D
– A – B – D – C
– A – C – B – D
– A – C – D – B, dll
Kelemahan dari Pembangkit & Pengujian (Generate and Test) yaitu ;
– Perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian
– Membutuhkan waktu yang cukup lama dalam pencariannya.
B. Pendakian Bukit (Hill Climbing)
Metode ini hampir sama dengan metode pembangkitan & pengujian, hanya saja
proses pengujian dilakukan dengan menggunakan fungsi heuristik. Pembangkitan
keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes
yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan
yang diambil terhadap keadaan-keadaan lainnya yang mungkin.
B.1. Simple Hill Climbing
Algoritma
10
1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka
berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan
awal.
2. Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai
tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:
(a) Cari operator yang belum pernah digunakan; gunakan operator ini untuk
mendapatkan keadaan yang baru.
(b) Evaluasi keadaan baru tersebut.
(i) Jika keadaan baru merupakan tujuan, keluar.
(ii) Jika bukan tujuan, namun nilainya lebih baik daripada keadaan
sekarang, maka jadikan keadaan baru tersebut menjadi keadaan
sekarang.
(iii) Jika keadaan baru tidak lebih baik daripada keadaan sekarang,
maka lanjutkan itera
Pada simple hill climbing ini, ada 3 masalah yang mungkin, yaitu:
Algoritma akan berhenti kalau mencapai nilai optimum local.
Urutan penggunaan operator akan sangat berpengaruh pada pemuan
solusi.
Tidak diijinkan untuk melihat satupun langkah sebelumnya.
Contoh : Traveling Salesman Problem dengan simple hill climbing
Disini ruang keadaan berisi semua kemungkinan lintasan yang mungkin. Operator
digunakan untuk menukar posisi kota-kota yang bersebelahan. Fungsi heuristic yang
digunakan adalah panjang lintasan yang terjadi.
11
Operator : Tukar kota ke-i dengan kota ke-j (Tk i,j)
• Untuk 4 kota:
– Tk 1,2 : tukar kota ke-1 dengan kota ke-2.
– Tk 1,3 : tukar kota ke-1 dengan kota ke-3.
– Tk 1,4 : tukar kota ke-1 dengan kota ke-4.
– Tk 2,3 : tukar kota ke-2 dengan kota ke-3.
– Tk 2,4 : tukar kota ke-2 dengan kota ke-4.
– Tk 3,4 : tukar kota ke-3 dengan kota ke-4.
B.2 Steepest Ascent Hill Climbing
Steepest-ascent hill climbing sebenarnya hampir sama dengan simple hill
climbing, hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri. Gerakan
selanjutnya dicari berdasarkan nilai heuristik terbaik. Dalam hal ini urutan
penggunaan operator tidak menentukan penemuan solusi.
Algoritma
1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka
berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan
awal.
2. Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan
pada keadaan sekarang.
a. Tentukan SUCC sebagai nilai heuristic terbaik dari successor-successor.
b. Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang:
12
Gunakan operator tersebut dan bentuk keadaan baru..
Evaluasi keadaan baru tersebut. Jika merupakan tujuan, keluar. Jika bukan,
bandingkan nilai heuristiknya dengan SUCC. Jika lebih baik, jadikan nilai
heuristic keadaan baru tersebut sebagai SUCC. Namun jika tidak lebih baik,
nilai SUCC tidak berubah..
c. Jika SUCC lebih baik daripada nilai heuristic keadaan sekarang, ubah node
SUCC menjadi keadaan sekarang.
Pada steepest-ascent hill climbing ini, ada 3 masalah yang mungkin, yaitu:
Local optimium: keadaan semua tetangga lebih buruk atau sama dengan
keadaan dirinya.
Plateau: keadaan semua tetangga sama dengan keadaan dirinya.
Ridge: local optimum yang lebih disebabkan karena ketidak mampuan untuk
menggunakan 2 operator sekaligus.
C. Pencarian Terbaik Pertama (Best First Search)
Metode best-first search ini merupakan kombinasi dari metode depth-first
search dan metode breadth-first search dengan mengambil kelebihan dari kedua
metode tersebut. Apabila pada pencarian dengan metode hill climbing tidak
diperbolehkan untuk kembali ke node pada level yang lebih rendah meskipun node
pada level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik, lain
halnya dengan metode best-first search ini. Pada metode best-first search, pencarian
diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata
node pada lebih yang lebih tinggi ternyata memiliki nilai heuristik yang lebih buruk.
C.1. OR Graph
13
Pada metode depth-first search mampu menemukan solusi tanpa harus
mengeksplorasi semua cabang dalam level yang sama. Pada metode breadth-first
search juga cukup bagus, karena mampu mengantisipasi adanya lintasan yang
mengalami jalan buntu. Kombinasi medua metode ini sangat dimungkinkan, dimana
pencarian dilakukan dengan hanya melihat satu lintasan, namun demikian masih
memungkinkan untuk berpindah ke lintasan lain apabila lintasan lain tersebut lebih
menjanjikan untuk mendapatkan solusi.
Untuk mengimplementasikan metode ini dengan menggunakan graph keadaan,
dibutuhkan 2 antrian yang berisi node-node solusi.
OPEN, berisi node,node yang sudah dibangkitkan, namun belum diuji.
Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan
nilai heuristik tertinggi.
CLOSED berisi node-node yang sudah diuji .
Algoritma
1. Tempatkan node awal A pada antrian OPEN.
2. Kerjakan langkah-langkah berikut hingga tujuan ditemukan atau antrian OPEN
sudah kosong:
a. Ambil node terbaik dari OPEN;
b. Bangkitkan semua successornya;
c. Untuk tiap-tiap successor kerjakan:
14
A
D
A
CB
E
DCB
A
G
DCB
A
H E F
F
(i) Jika node tersebut belum pernah dibangkitkan sebelumnya,
evaluasi node tersebut dan masukkan ke OPEN;
(ii) Jika node tersebut sudah pernah dibangkitkan sebelumnya, ubah
parent jika lintasan baru lebih menjanjikan. Hapus node tersebut
dari antrian OPEN.
Gambar 2.27 menunjukkan metode pencarian terbaik pertama. Diasumsikan bahwa
node dengan nilai yang lebih besar, memiliki nilai evaluasi yang lebih baik. Pada saat
keadaan awal, antrian berisi A. Pengujian dilakukan pada level pertama, node D
memiliki nilai terbaik, sehingga menempati antrian pertama, disusul dengan C dan B.
Node D memiliki cabang E dan F yang masing-masing bernilai 2 dan 4. Dengan
demikian C merupakan pilihan terbaik dengan menempati antrian pertama. Demikian
seterusnya.
15
Gambar 2.27 Metode Best-First Search
C.2. Algoritma A*
Algoritma A* merupakan perbaikan dari metode best-first search dengan
memodifikasi fungsi heuristiknya. A* akan meminimumkan total biaya lintasan. Pada
kondisi yang tepat, A* akan memberikan solusi yang terbaik dalam waktu yang
optimal.
Funsi f sebagai estimasi evaluasi terhadap node n, dapat dituliskan:
f(n) = g(n) + h’(n)
denagan :
f(n) = fungsi evaluasi
g(n) = biaya yang sudah dikeluarkan dari keadaan awal sampai keadaan n.
h’(n) = estimasi biaya untuk sampai pada suatu tujuan mulai dari n.
Dengan demikian dapat dikatakan bahwa:
Apabila h’ = h berarti proses pelacakan sudah sampai pada suatu tujuan.
16
Apabila g = h’ = 0, maka f random, artinya system tidak dapat dikendalikan
oleh apapun.
Apabila g = k (konstanta biasanya 1) dan h’ = 0 berarti system menggunakan
breadth-first search.
Pada Algoritma A*, juga dibutuhkan 2 antrian, yaitu:
OPEN, yang berisi node-node yang sudah dibangkitkan, sudah memiliki
fungsi heuristic namun belum diuji.
CLOSED berisi node-node yang sudah diuji.
D. 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
Algoritma Simulated Annealing adalah sebagai berikut:
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.
17
3. Inisialisasi T sesuai dengan annealing schedule.
4. Kerjakan hingga solusi ditemukan atau sudah tidak ada operator baru lagi akan
diaplikasikan ke kondisi sekarang.
a. Gunakan operator yang belum pernah digunakan tersebut untuk menghasilkan
kondisi baru.
b. 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.
c. Perbaiki T sesuai dengan annealing scheduling.
5. 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.
18
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]
19