KECERDASAN BUATAN : SEARCH 2

Assalamu’alaikum, selamat pagi. Masih bersama saya Teguh Ramdhani-17190987, kelas 17.4C.25. pada kesempatan kali ini saya akan membahas materi dari mata kuliah kecerdasan buatan pada pertemuan 5.  Materi pada pertemuan 5 kali ini kita akan melanjutkan pembahasan mengenai “Search”. Materi Search kali ini, kita akan membahas tentang :

1.    Masalah dan ruang masalah.

2.    Cara merepresentasikan masalah.

3.    Konsep Pencarian.

4.    Metode pencarian Heuristik.

a.     Generate and Test (Pembangkit dan Pengujian).

b.    Hill Climbing(Pendakian Bukit).

c.     Best-First-Search.

 

1.     Masalah dan Ruang Masalah.

·        Membangun sistem dengan menyelesaikan masalah menggunakan kecerdasan buatan :

1)    Mendefinisikan masalah dengan tepat.

2)    Menganalisis masalah dan mencari teknik penyelesaiannya.

3)    Merepresentasikan pengetahuan untuk menyelesaikan masalah.

4)    Memilih teknik penyelesaian masalah yang terbaik.

 

·        Cara mendefinisikan suatu masalah :

1)    Mendefinisikan/membuat state space atau ruang masalah.

2)    Menentukan keadaan awal (initial state).

3)    Menentukan keadaan akhir (goal state).

4)    Menentukan operator/aturan.

 

·        Contoh : “Permainan Catur”.

Yang harus ditentukan adalah :

1)    Posisi awal pada papan catur, posisi awal setiap permainan catur selalu sama, yaitu semua bidak diletakkan di ataspapan catur dalam posisi, yaitu kubu putih dan kubu hitam.

2)    Aturan-aturan untuk menentukan gerakan secara legal, aturan sangat berguna untuk menentukan suatu bidak bergerak dari suatu keadaan lain sesuai dengan aturan yang ada.

3)    Tujuan (Goal), tujuan yang diingin dicapai adalah kemenangan terhadap lawan yang ditunjukan dengan posisi Raja yang tidak bisa bergerak lagi.

 

2.    Cara Mempresentasikan Masalah

1)    Graph Keadaan

2)    Pohon Pelacakan

3)    Pohon And/Or

 

3.    Konsep Pencarian.

·       Hal penting dalam menentukan keberhasilan system cerdas adalah kesuksesan dalam pencarian.

·       Pencarian = suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space).

·       Ruang keadaan = merupakan suatu ruang yang berisi semua keadaan yang mungkin.

·       Krtiteria yang digunakan ntuk mengukur perfomansi metode pencarian adalah :

1)   Completeness : Apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?

2)   Time complexity : Berapa lama waktu yang diperlukan? Space complexity : Berapa banyak memori yang diperlukan?

3)   Optimality : Apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda?

 

4.    Metode Pencarian Heuristik

Heuristik adalah teknik yang digunakan untuk melakukan suatu pencarian dengan mengorbankan kelengkapan (completeness). Heuristik digunakan untuk mencari masalah/problem dan menentukan untuk mendapatkan solusi yang diinginkan.

a.     Generate And Test (Pembangkit dan Pengujian)

·        Teknik Generate-and-Test adalah teknik yang paling mudah dibandingkan teknik search yang lain, namun relatif lebih lama dalam mendapatkan solusi.

 

·        Metode pencarian yang merupakan penggabungan antara Depth First Search dengan Pelacakan Backtracking (Bergerak ke belakang menuju ke keadaan awal).

 

·        Algoritma Generate and Test:

1)    Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal).

2)    Uji untuk melihat apakah node tersebut benar-benarmerupakan solusinya dengan cara membandingkan nodetersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.

3)    Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.

 

·        Kebaikan dan Keburukan Generate-and-Test

Jika penurunan solusi yang mungkin dilakukan secara sistematis, maka procedure diatas akan dapat menemukan solusi suatu saat, jika memang ada. Tapi sayangnya jika ruang permasalahan sangat luas maka saat ditemukannya solusi akan menjadi sangat lama. Cara terbaik menerapkan generate-and-test yang sistematis adalah pada tree dari depth-first search denganbacktracking, yaitu kembali ke stata sebelumnya bila ditemui stata yg sudah pernah di test atau memodifikasi prosedurnya untuk menelusuri stata pada bentuk graph.

 

b.    Hill Climbing (Pendaki Bukit)

·        Metode pencarian yang mirip dengan metode Generate and Test tetapi menggunakan fungsi heurustic.

·        Generate pada keadaan berikutnya tergantung pada feedback dari test yang dilakukan.

·        Fungsi heuristic yang dilakukan menunjukkan seberapa baik nilai yang akan diambil terhadap keadaan yang mungkin.

·        Tiga masalah dalam Simple Hill Climbing :

1)    Algoritma akan berhenti jika mencapai nilai optimum local

2)    Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi.

3)    Tidak diijinkan untuk melihat satupun langkah sebelumnya.

 

·        Algoritma Simple Hill Climbing :

1)    Evaluasi initial state. Jika ini goal state maka return dan keluar.

2)    Jika bukan maka lanjutkan dengan initial state sebagai current state.

3)    Ulangi langkah berikut sampai menemukan solusi atau sampai tidak ada lagi operator yang dapat digunakan pada current state

a.     Pilih operator yang belum digunakan pada current state dan gunakan untuk menghasilkan/menuju stata baru

b.     Evaluasi stata baru.

Ø Jika ini goal state maka return dan keluar

Ø Jika bukan goal state tetapi lebih baik dari current state maka jadikan stata baru sebagai current state

Ø Jika tidak lebih baik dari current state lanjutkan perulangan.

 

c.      Best-First-Search

·        Teknik Best-First-Search adalah teknik search yang menggabungkankebaikan yang ada dari teknikDepth-First-Search dan Breadth-First Search.

·        Tujuan menggabungkan dua teknik search ini adalah untuk menelusuri satu jalur saja pada satu saat, tapi dapat berpindah ketika jalur lain terlihat lebih menjanjikan dari jalur yang sedang ditelusuri.

·        Untuk mendapatkan jalur yang menjanjikan adalah dengan memberikan skala prioritas pada setiap statasaat dihasilkan dengan fungsi heuristic.

·        Untuk menggunakan Best-First-Search, kita memerlukan dua daftar simpul, yaitu :

1)    OPEN.

Berisi simpul yang dihasilkan dari fungsi heuristic tapi belum dievaluasi, memilki antrian prioritas dimana elemen dengan prioritas tertinggi adalah yang memiliki nilai paling baik yang dihasilkan fungsi heuristic.

2)    CLOSED.

Berisi simpul yang sudah dievaluasi. Kita perlu tetap menyimpan simpul-simpul ini dalam memori jika kita ingin melakukan search pada Graph, sehingga jika kita menemui suatu simpul kita bisa memeriksa apakah simpul ini sudah pernah dieavaluasi atau belum.

 

·        Algoritma Best-First-Search :

1)    Mulai dengan OPEN hanya berisi initial state.

2)    Sampai goal ditemukan atau tidak ada lagi simpul yang tersisa dalam OPEN, lakukan :

a.     Pilih simpul terbaik dalam OPEN

b.     Telusuri successor-nya

c.      Untuk tiap successor, lakukan :

·        Jika belum pernah ditelusuri sebelumnya, evaluasi simpul ini, tambahkan kedalam OPEN dan catat parentnya.

·        Jika sudah pernah ditelusuri, ganti parent nya jika jalur baru lebih baik dari sebelumnya.