HEURISTIC SEARCH
UTHIE
Pendahuluan
Pencarian buta biasanya tidak efisien karena waktu akses memori yang dibutuhkan cukup besar.
Untuk mengatasi hal ini maka perlu ditambahkan suatu informasi pada domain yang bersangkutan sehingga proses pencarian yang baru akan dihasilkan.
Pencarian seperti ini disebut sebagai informed search atau pencarian heuristic atau pencarian terbimbing, yaitu pencarian berdasarkan panduan.
(Dalam sutojo dkk) teknik pencarian heuristic merupakan suatu strategi untuk melakukan proses pencarian secara selektif dan dapat memandu proses pencarian yang memiliki kemungkinan sukses paling besar, namun dengan kemungkinan mengorbankan kelengkapan (completeness) UTHIE
Pendakian Bukit (Hill Climbing)
Ada 2 macam yaitu : 1. Simple hill climbing 2. Stepest ascent hill climbing
UTHIE
Langkah pencarian (Rich, Elaine and knight, kevin, 1991, “Artificial Intelligent”, Mc Graw Hill, Inc, second edition) : Mulai dari keadaan awal, lakukan pengujian : jika merupakan 1. 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 3. Cari operator yang belum pernah digunakan ; gunakan operator ini untuk mendapatkan keadaan yang baru 4. Evaluasi keadaan baru tersebut a. Jika keadaan baru merupakan tujuan, keluar b. Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang c. Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi UTHIE
Kasus 1. Implementasikan algoritma Simple Hill Climbing pada puzzle berikut ini :
Keadaan awal
Goal
Ruang keadaan
UTHIE
Ruang keadaan : Misalkan : x = baris = [1,2,3] y = kolom = [1,2,3] Jadi dalam hal ini ruang keadaan = semua kemungkinan posisi kotak pada puzzle – 8 Contoh : posisi kotak 7 pada keadaan awal adalah (3,1)
UTHIE
Aturan/operator : Posisi kotak kosong (x,y) x = baris kotak kososng y = kolom kotak kosong Aturan : 1. Gerakkan kotak kosong ke atas : if x > 1 then (x-1,y) 2. Gerakkan kotak kosong ke bawah : if x < 3 then (x+1,y) Gerakkan kotak kosong ke kanan : if y < 3 then (x,y+1) 3. Gerakkan kotak kososng ke kiri : if y > 1 then (x, y-1) 4.
UTHIE
Fungsi heuristik Fungsi heuristik yang digunakan adalah jumlah kotak yang menempati posisi benar. Kriteria yang dipakai adalah jumlah benar yang paling besar yang dipilih
UTHIE
Iterasi ke-1 Cek keadaan awal ≠ goal maka keadaan sekarang = keadaan awal kena operator 1 menjadi
Karena posisi benar keadaan sekarang > posisi benar keadaan selanjutnya, maka : keadaan sekarang = tetap
UTHIE
Cek keadaan sekarang ≠ goal Lanjut ke operator berikutnya : kena operator ke-2 menjadi
karena posisi benar keadaan sekarang > posisi benar keadaan selanjutnya, maka : keadaan sekarang = tetap
cek keadaan sekarang ≠ goal UTHIE
Lanjut ke operator berikutnya : kena operator ke-3 menjadi
karena posisi benar keadaan sekarang < posisi benar keadaan selanjutnya, maka : keadaan sekarang = keadaan selanjutnya.
cek keadaan sekarang ≠ goal UTHIE
Lanjut ke operator selanjutnya. kena operator ke-4 menjadi
karena posisi benar keadaan sekarang > posisi benar keadaan selanjutnya, maka keadaan sekarang = tetap
UTHIE
Iterasi ke-2 cek keadaan awal ≠ goal dimana keadaan sekarang = keadaan awal kena operator ke-1 menjadi
karena posisi benar keadaan sekarang > posisi benar keadaan selanjutnya, maka : keadaan sekarang = tetap
UTHIE
Cek keadaan sekarang ≠ goal lanjutkan ke operator berikutnya kena operator ke – 2 menjadi
karena posisi benar keadaan sekarang > posisi benar keadaan selanjutnya, maka keadaan sekarang = tetap
UTHIE
Cek keadaan sekarang ≠ goal lanjutkan ke operator selanjutnya kena operator ke-3 menjadi
karena posisi benar keadaan sekarang < posisi benar keadaan selanjutnya maka : keadaan sekarang = keadaan selanjutnya
UTHIE
Cek keadaan sekarang ≠ goal lanjutkan ke operator berikutnya
kena operator ke – 4
karena posisi benar keadaan sekarang > posisi benar keadaan selanjutnya, maka : keadaan sekarang = tetap
UTHIE
Iterasi ke-3 Cek keadaan awal ≠ goal keadaan sekarang = keadaan awal kena operator ke-1 menjadi
karena posisi benar keadaan sekarang > posisi benar keadaan selanjutnya, maka : keadaan sekarang = tetap
UTHIE
Cek keadaan sekarang ≠ goal lanjutkan ke operator berikutnya kena operator ke -2 menjadi
karena posisi benar keadaan sekarang < posisi benar keadaan selanjutnya, maka : keadaan sekarang = keadaan selanjutnya
UTHIE
Cek keadaan sekarang = goal, hentikan pencarian solusi
UTHIE
Kasus 2. Implementasikan algoritma Stepest ascent hill climbing pada puzzle berikut ini : Algoritmanya : Mulai dari keadaan awal, lakukan pengujian : jika merupakan tujuan, maka 1. berhenti; dan jika tidak, lanjutkan keadaan sekarang sebagai keadaan awal. Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan 2. perubahan pada keadaan sekarang. a. Tentukan SUCC sebagai nilai heuristik terbaik dari successorsuccessor b. Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang: 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 heuristik keadaan sekarang, ubah node SUCC menjadi keadaan sekarang UTHIE
Pada stepest Hill Climbing, ada 3 maslaah yang mungkin yaitu : 1. Local optimum : keadaan semua tetangga lebih buruk atau sama dengan keadaan dirinya. 2. Plateau : keadaan semua tetangga sama dengan keadaan dirinya 3. Ridge : local optimum yang lebih disebabkan karena ketidakmampuan untuk menggunakan 2 operator sekaligus.
UTHIE
Implementasikan puzzle di bawah ini menggunakan algoritma stepest ascent hill climbing
Keadaan awal
Goal
UTHIE
Ruang keadaan : y = kolom = [1,2,3] Misalkan : x = baris = [1,2,3] Jadi dalam hal ini ruang keadaan = semua kemungkinan posisi kotak pada puzzle – 8 Contoh : posisi kotak 7 pada keadaan awal adalah (3,1)
UTHIE
Aturan/operator : Posisi kotak kosong (x,y) x = baris kotak kososng y = kolom kotak kosong Aturan : 1. Gerakkan kotak kosong ke atas : if x > 1 then (x-1,y) 2. Gerakkan kotak kosong ke bawah : if x < 3 then (x+1,y) 3. Gerakkan kotak kosong ke kanan : if y < 3 then (x,y+1) 4. Gerakkan kotak kososng ke kiri : if y > 1 then (x, y-1) UTHIE
Fungsi heuristik Fungsi heuristik yang digunakan adalah jumlah kotak yang menempati posisi benar. Kriteria yang dipakai adalah jumlah benar yang paling besar yang dipilih
UTHIE
Iterasi ke 1 Cek keadaan awal , ternyata keadaan awal ≠ goal Keadaan sekarang = keadaan awal Keadaan sekarang dikenakan 4 operator sekaligus menjadi :
UTHIE
Pilih posisi yang terbesar yaitu : 6, sehingga keadaan sekarang menjadi :
UTHIE
Iterasi ke-2 Cek keadaan awal ≠ goal Keadaan sekarang = keadaan awal Keadaan sekarang dikenakan 4 operator sekaligus, menjadi :
UTHIE
Pilih posisi yang terbesar, yaitu 8, sehingga keadaan sekarang menjadi :
UTHIE
Iterasi ke-3 Cek keadaan awal, ternyata keadaan awal ≠ goal. Keadaan sekarang = keadaan awal Keadaan sekarang dikenakan 4 operator sekaligus menjadi:
UTHIE
Pilih posisi yang terbesar yaitu 8, sehingga keadaan sekarang menjadi :
UTHIE
Iterasi ke-4 Cek apakah keadaan awal = goal, ternyata iya, maka hentikan proses pencarian. Solusi :
UTHIE
Kasus ke. 3 Menggunakan Metode Best first search
Metode best first search merupakan kombinasi dari metode depth first search dan metode breadth first search yang mana pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah asalkan node ini memiliki nilai heuristik yang lebih baik.
UTHIE
Algoritma dari best first search : 1. Buat sebush stack, inisialisasi node akar sebagai node pertama. 2. Bila node pertama ≠ goal, node dihapus dan diganti dengan anak-anaknya. 3. Selanjutnya, keseluruhan node yang ada di stack di sort ascending berdasarkan fungsi heuristik yang digunakan 4. Bila node pertama ≠ goal, ualangi poin (2) 5. Bila node pertama = goal, cari solusi dengan cara menelusuri jalur dari goal ke node akar. 6. selesai UTHIE
Contoh gambar di bawah ini, menjelaskan tentang pencarian rute terpendek menggunakan algoritma best first search. A adalah keadaan awalnya dan Z adalah tujuannya. Fungsi heuristik yang digunakan adalah nodenode yang mempunyai jarak terpendek.
UTHIE
Iterasi ke - 1 Masukkan node A ke dalam stack
Keluarkan A dari stack dan lakukan pengecekan
Ternyata A ≠ goal A punya anak C(5) dan B(4), masukkan ke stack dan stack di – SORT ASCENDING
UTHIE
Stack setelah dilakukan sort ascending
Representasi keadaan
UTHIE
Iterasi ke-2 Keluarkan B dari stack dan cek
Ternyata B ≠ goal B punya anak D(3), masukkan ke stack dan stack di sort ascending.
UTHIE
Representasi keadaan :
UTHIE
Iterasi ke-3 Keluarkan D dari stack dan cek
Ternyata D ≠ goal D punya anak E(4), lalu masukkan ke stack dan lakukan sort ascending
UTHIE
Representasi keadaan :
UTHIE
Iterasi ke-4 Keluarkan E dari stack dan cek
Ternyata E ≠ Goal E punya anak G(6), masukkan ke stack dan laukan sort ascending
UTHIE
Representasi keadaan :
UTHIE
Iterasi ke-5 Keluarkan C dari stack dan cek
Ternyata C ≠ Goal C punya anak E(3) dan F(2), masukkan F(2) ke stack dan lakukan sort ascending
UTHIE
Representasi keadaan
UTHIE
Iterasi ke-6 Keluarkan F dari stack dan cek
Ternyata F ≠ Goal F punya anak I(4), lalu masukkan ke stack dan lakukan sort ascending
UTHIE
Representasi keadaan
UTHIE
Iterasi ke-7 Keluarkan E dari stack dan cek, apakah E goal atau bukan
Ternyata E ≠ Goal E punya anak G(6), dan sudah ada di stack, jadi tidak dimasukkan ke dalam stack
UTHIE
Representasi ruang keadaan
UTHIE
Iterasi ke-8 Keluarkan I dari stack dan lakukan pengecekan
Ternyata I ≠ Goal Karena I tidak punya anak, maka gunakan node I untuk menghapus orang tuanya direpresentasi keadaan.
UTHIE
Representasi keadaan
UTHIE
Iterasi ke-9 Keluarkan G dari stack dan lakukan pengecekan
Ternyata G ≠ Goal G punya anak H(2), J(4), Z(7), F(8). Masukkan semua anak ke dalam stack dan lakukan sort ascending.
UTHIE
Representasi keadaan
UTHIE
Iterasi ke 10 Keluarkan H dari stack dan lakukan pengecekan
Ternyata H ≠ Goal H punya anak Z(6), masukkan ke dalam stack dan lakukan sort ascending
UTHIE
Representasi keadaan
UTHIE
Iterasi ke 11 Keluarkan J dari stack dan lakukan pengecekan
Ternyata J ≠ Goal J punya anak K(1), masukkan ke stack dan lakukan sort ascending
UTHIE
Representasi ruang keadaan
UTHIE
Iterasi ke 12 Keluarkan K dari stack dan lakukan pengecekan
Ternyata K ≠ Goal Karena K tidak punya anak, gunakan untuk menghapus orang tuanya di representasi keadaan
UTHIE
Representasi keadaan
UTHIE
Iterasi ke 13 Keluarkan Z dari stack dan lakukan pengecekan
Ternyata Z = Goal, maka hentikan pencarian
UTHIE
