ARTIFICIAL INTELLIGENCE: PENCARIAN LANJUTAN

 SISTEM PADA AI

Input yg diberikan pada sistem adalah berupa masalah. Sistem harus dilengkapi dengan sekumpulan pengetahuan yang ada pada basis pengetahuan. Sistem harus memiliki motor inferensi agar mampu mengambil kesimpulan berdasarkan fakta atau pengetahuan. Output yang diberikan berupa solusi masalah sebagai hasil dari inferensi.

MASALAH DAN RUANG MASALAH

4 hal yang harus dilakukan agar sistem menyelesaikan masalah terpisah :

1.  Mendefinisikan masalah dengan tepat
• Spesifikasi yang tepat mengenai keadaan awal
• Solusi yang diharapkan
2. Menganalisa masalah serta mencari beberapa teknik penyelesaian masalah yang sesuai
3. Membatasi dan menghadirkan pengetahuan yang diperlukan untuk menyelesaikan masalah
4. Pilih teknik penyelesaian terbaik dan aplikasikan pada masalah

Untuk Mendefinisikan Suatu Masalah Sebagai Ruang Masalah

Beberapa hal yang harus dilakukan :

1. Definisikan ruang stata yang memuat semua konfigurasi yg mungkin dari objek yang terkait (dan mungkin beberapa yg tidak mungkin). Hal ini, tentu saja mungkin untuk mendefiniskan ruang stata dengan jumlah stata yang tidak terbatas.
2. Tentukan satu atau beberapa stata yang menyatakan keadaan awal dari masalah, disebut initial states.
3. Tentukan satu atau beberapa stata yang dapat diterima sebagai keadaan akhir (solusi), disebut goal states.
4. Tentukan sejumlah aturan yang menentukan aksi yang diperkenankan, hal ini mencakup beberapa hal sbb : 
• Apa asumsi non stata yang ditampilkan dalam deskripsi masalah non formal ? Akan menentukan yg termasuk dan tidak termasuk stata.
• Seberapa luas aturan harus dibuat ? Dapat menentukan aturan diberlakukan untuk stata mana saja.
• Berapa banyak pekerjaan yang diperlukan untuk menyelesaikan masalah harus disusun dan dimasukkan ke dalam aturan ? Akan menentukan jumlah baris aturan.

CARA MEMPRESENTASIKAN MASALAH

Beberapa Cara untuk Mempresentasikan ruang masalah yaitu :

• Graph Keadaan

• Pohon Pelacakan

• Pohon AND/OR

KONSEP PENCARIAN

Pencarian merupakan suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space). Ruang keadaan sendiri yaitu suatu ruang yang berisi semua keadaan yang mungkin.

Untuk mengukur perfomansi metode pencarian, terdapat empat kriteria yang dapat digunakan :

1. Completeness : Apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?
2. Time complexity : Berapa lama waktu yang diperlukan? 
3. Space complexity : Berapa banyak memori yang diperlukan?
4. Optimality : Apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda?

METODE PENCARIAN HEURISTIK

Pencarian terbimbing (heuristic search). Heuristic searching merupakan metode pencarian yang memperhatikan nilai heuristik (nilai perkiraan). Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness).

• Generate-and-Test

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

Algoritma Generate-and-Test :

1. Bentuk solusi yang mungkin.

Untuk beberapa masalah, ini berarti membentuk poin terpisah dari area permasalahan. Pada masalah lain, ini berarti membentuk jalur dari stata awal. 

2. Lakukan test untuk melihat apakah poin yang ditemui adalah solusi dengan membandingkan poin yang dipilih atau poin terakhir dari jalur yang dipilih dengan kumpulan stata tujuan 

3. Jika solusi sudah ditemukan, quit. Jika belum kembali ke langkah 1.

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 dengan backtracking, yaitu kembali ke stata sebelumnya bila ditemui stata yg sudah pernah di test atau memodifikasi prosedurnya untuk menelusuri stata pada bentuk graph.

• Hill Climbing

   Teknik Hill Climbing adalah pengembangan dari teknik Generate-and-Test, dengan penambahan adanya umpan balik dari prosedur test yang sudah digunakan untuk membantu memilih arah mana yang harus ditelusuri pada setiap area search.

   Pada prosedur Generate-and-Test yang murni, fungsi test hanya ditanggapi dengan Ya atau Tidak. Tetapi pada Hill Climbing fungsi test ditambahkan dengan fungsi heuristic atau fungsi objectif yang memungkinkan perkiraan seberapa dekat simpul yang ditelusuri terhadap goal state.

    Hill-climbing sering kali digunakan jika fungsi heuristic yang baik tersedia untuk mengevaluasi stata, tapi ketika tidak ada lagi pengetahuan yang dapat digunakan. Sebagai contoh, anda berada disuatu kota yang belum pernah anda kunjungi tanpa memiliki peta. Tujuannya menuju gedung tertinggi yang terlihat dari tempat anda berada. 

    Fungsi heuristic adalah hanya masalah jarak antara lokasi anda berada dengan letak gedung tertinggi dan bagaimana menemukan jarak yang terdekat atau cara tercepat menuju gedung tertinggi.

    Penyelesaian masalah diatas dimulai dengan meninjau karakteristik masalah, apakah solusi yang pertama ditemukan dapat diterima sebagai solusi yang baik ? (mutlak atau relatif ?) Karena tidak ada peta dan tidak ada pengalaman memilih jalan (tidak ada pengetahuan) maka dipilih saja jalan yang arahnya menuju solusi sampai kita tiba di tujuan tanpa mengulangi atau mencoba lagi jalur yang lain dan kita terima itu sebagai solusi terbaik (dgn mengabaikan kemungkinan lain). Jadi adalah masuk akal menerapkan hill-climbing ketika tidak ada alternatif yang dapat diterima untuk memilih atau menuju pada suatu stata.

Algoritma Simple Hill Climbing :

1. Evaluasi initial state. Jika ini goal state maka return dan keluar. Jika bukan maka lanjutkan dengan initial state sebagai current state.
2. Ulangi langkah berikut sampai menemukan solusi atau sampai tidak ada lagi operator yang dapat digunakan pada current state
• Pilih operator yang belum digunakan pada current state dan gunakan untuk menghasilkan/menuju stata baru
• 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

• Best-First-Search 

Teknik Best-First-Search adalah teknik search yang menggabungkan kebaikan yang ada dari teknik Depth-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 stata saat 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 :  
• Pilih simpul terbaik dalam OPEN
• Telusuri successor-nya
• 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.