Kecerdasan Buatan : SEARCH LANJUTAN - Pertemuan 5

 

SEARCH LANJUTAN

 

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 : “Masalah Petani, Kambing, Serigala dan Sayuran”

v Seorang petani akan menyeberangkan seekor kambing, seekor serigala dan sayuran dengan sebuah boat yang melalui sungai. Boat hanya bisa memuat petani dan satu penumpang lain (kambing, serigala atau sayuran). Jika ditinggalkan oleh petani tersebut, maka sayuran akan dimakan oleh kambing dan kambing akan dimakan oleh serigala.

v  Bagaimana caranya agar petani, kambing, serigala dan sayuran dapat selamat sampai di seberang sungai ?

§ Contoh : “Permainan Catur”.

v Yang harus ditentukan adalah :

1.     Posisi awal pada papan catur, posisi awal setiap permainan catur selalu sama, yaitu semua bidak diletakkan di atas papan 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.

CARA MEREPRESENTASIKAN RUANG MASALAH

1.Graph Keadaan

2. Pohon Pelacakan

3. Pohon AND/OR

KARAKTERISTIK MASALAH

§ Memilih motode pemecahan masalah yang tepat perlu dilakukan analisa masalah.

§ Karakteristik yang digunakan untuk menganalisa suatu masalah adalah :

1. Apakah masalah dapat dipilah dan dibagi menjadi submasalah yang independent ?

2. Apakah ruang lingkup pembicaraan masalah dapat diperkirakan ?

3. Apakah solusi masalah yang baik telah dibandingkan dengan semua solusi yang mungkin ?

4. Apakah basis pengetahuan yang digunakan untuk memecahkan maslaah bersifat konsisten?

5. Apakah dibutuhkan informasi untuk memecahkan masalah yang dihadapi untuk membatasi proses pencarian ?

PENCARIAN DAN PELACAKAN

§ Hal penting dalam menentukan keberhasilan sistem 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.

§ Kriteria yang digunakan untuk mengukur performansi metode pencarian adalah :

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/SEARCH

§ Metode Pencarian Buta (Blind Search)

1. Breadth First Search (Pencarian Melebar Pertama)

2. Depth First Search (Pencarian Mendalam Pertama)

§ Metode Pencarian Heuristik

1. Generate And Test (Pembangkit dan Pengujian)

2. Hill Climbing (Pendakian Bukit)

3. Best-First-Search

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.

METODE GENERATE-AND-TEST

§ 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-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 pertama.

CONTOH GENERATE-AND-TEST

§ Kasus Travelling Salesman Problem (TSP)

§ Seorang salesman ingin mengunjungi n kota.

§ Jarak antara tiap-tiap kota sudah diketahui.

§ Kita ingin mengetahui ruter terpendek dimana setiap kota hanya boleh dikunjungi tepat 1 kali.

§ Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar berikut ini :

GENERATE-AND-TEST

§ Penyelesaian metode Generate and Test

§ Alur Pencarian metode Generate and Test

§ Hasil metode Generate and Test ü Total Pencarian = 24 lintasan ü Lintasan yang terpilih = ACBD ü Panjang lintasan yang terpilih = 12

§ Kelemahan Generate and Test :

1. Harus membangkitkan semua kemungkinan sebelum dilakukan pengujian.

2. Membutuhkan waktu yang cukup lama dalam pencarian.

CONTOH KASUS TSP Lain

§ Sebuah rute yang harus dilewati seorang sales dimana sales tersebut harus melewati setiap kota tepat sekali.

§ Terdapat 4 kota, dengan jarak masing-masing kota AB=2, AC=4, AD=1, BC=5, BD=3, CD=3.

§ Tujuannya adalah mencari jarak terpendek bagi sales untuk mengunjungi semua kota sekali.

CONTOH KASUS TSP

§ Penyelesaian menggunakan generate-test adalah dengan membangkitkan solusi- solusi yang mungkin ada sesuai permasalahan yang dihadapi oleh sales tersebut.

§ Kombinasi abjad sebagai solusi yang mungkin adalah n! = 4! = 24.

§ Tujuannya adalah mencari solusi dengan panjang terpendek

METODE HILL CLIMBING

§ 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.

SIMPLE HILL CLIMBING

§ Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang :

1. Cari operator yang belum digunakan, gunakan operator ini untuk mendapatkan keadaan yang baru.

2. Evaluasi keadaan baru tersebut :

ü Jika keadaan baru merupakan tujuan, keluar

ü Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.

ü Jika keadaan baru tidak lebih baik dari pada keadaan sekarang, maka lanjutkan iterasi.  

§ Kasus TSP (Traveling Salesmen Problem)

§ Ruang keadaan berisi semua kemungkinan lintasan yang mungkin.

§ Operator digunakan untuk menukar posisi kota yang bersebelahan.

§ Apabila ada n kota dan ingin mencari kombinasi lintasan maka dengan cara menukar posisi urutan 2 kota, n kombinasi 2.

§ Kombinasi yang didapat sebanyak 6 kombinasi atau dengan menggunakan rumus :

§ Kombinasi Simple Hill Climbing

ü Tukar 1,2 : Tukar kota ke-1 dengan kota ke-2

ü Tukar 2,3 : Tukar kota ke-2 dengan kota ke-3

ü Tukar 3,4 : Tukar kota ke-3 dengan kota ke-4

ü Tukar 4,1 : Tukar kota ke-4 dengan kota ke-1

ü Tukar 2,4 : Tukar kota ke-2 dengan kota ke-4

ü Tukar 1,3 : Tukar kota ke-1 dengan kota ke-3

§ Penyelesaian Metode Simple Hill Climbing

§ Hasil Metode Simple Hill Climbing

ü Panjang lintasan yang dihasilkan dari fungsi heuristic = 12

ü Tahapan heuristic 6 kombinasi = level 5

ü Jalur lintasan yang dipilih dengan fungsi heuristik = DBCA

§ Kasus game Number Puzzle Slider

§ Penyelesaian Kasus game Number Puzzle Slider

ALGORITMA HILL CLIMBING

§ Pencarian simple hill climbing dimulai dari anak kiri.

§ Apabila nilai heuristik anak kiri lebih baik maka dibuka untuk pencarian selanjutnya.

§ Jika tidak maka akan dilihat tetangga dari anak kiri tersebut, dan seterusnya.

§ Level 1 :

ü (ABCD=10 > BACD =9) buka node BACD tanpa harus mencek node yang selevel dengan BACD.

§ Level 2 : node ABCD dilewati.

ü (BACD=9 = CABD=9) periksa node tetangga CABD

ü (BACD=9 < DABC=10) periksa node tetangga DABC

ü (BACD=9 < BCAD=10) periksa node tetangga BCAD

ü (BACD=9 < BDAC=10) periksa node tetangga BDAC

ü (BACD=9 > BADC=6 ) buka node BADC

§ Level 3 :

ü (BADC=6 < ABDC=8) periksa tetangga ABDC

ü (BADC=6 < DABC=8) periksa tetangga DABC

ü (BADC=6 < CADB=8) periksa tetangga CADB

ü (BADC=6 < BDAC=8) periksa tetangga BDAC

ü (BADC=6 < BADC=9) selesai.

 

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. Contoh Best-First-Search

§ 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.

Contoh Best-First-Search

§ Pertama kali, dibangkitkan node A.

§ Kemudian semua suksesor A dibangkitan, dan dicari harga paling minimal.

§ Pada langkah 2, node D terpilih karena harganya paling rendah, yakni 1.

§ Langkah 3, semua suksesor D dibangkitkan, kemudian harganya akan dibandingkan dengan harga node B dan C.

§ Ternyata harga node B paling kecil dibandingkan harga node C, E, dan F.

§ Sehingga B terpilih dan selanjutnya akan dibangkitkan semua suksesor B.

§ Demikian seterusnya sampai ditemukan node tujuan.

§ Diketahui sebuah puzzle berukuran 3X3 yang berisi angka.

§ Permasalahan adalah angka-angka dalam puzzle tersebut belum teratur.

§ Nilai awal puzzle :

§ Nilai awal = {1,2,blank,4,5,3,7,8,6}

§ Goal = {1,2,3,4,5,6,7,8,blank}

§ Nilai heuristic = f(n) = g(n) + h(n)

§ g(n) = kedalaman dari pohon

§ h(n) = jumlah angka yang masih salah posisi

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 :

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

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