2015

10/7/2015

Sistem Kecerdasan Buatan Masalah, Ruang Masalah dan Pencarian Solusi

Bahan Bacaan : Sri Kusumadewi, Artificial Intelligence. Russel, Artificial Intelligence Modern Approach

Masalah • Untuk membangun sistem yang mampu menyelesaikan masalah, perlu dipertimbangkan 4 hal: • Mendefinisikan masalah dengan tepat • Spesifikasi yang tepat mengenai keadaan awal • Solusi yang diharapkan • Menganalisis masalah serta mencari beberapa teknik penyelesaian masalah yang sesuai • Merepresentasikan pengetahuan yang perlu untuk menyelesaikan masalah • Memilih teknik penyelesaian masalah yang terbaik

2 bagian utama kecerdasan buatan : a. basis pengetahuan (knowledge base): berisi fakta-fakta, teori, pemikiran & hubungan antara satu dengan lainnya. b. motor inferensi (inference engine) : kemampuan menarik kesimpulan berdasarkan basis pengetahuan

Masalah Sebagai Ruang Keadaan • Suatu ruang yang berisi semua keadaan yang mungkin • Misalkan permasalahan yang dihadapi adalah Permainan Catur. • Maka harus ditentukan • Posisi awal pada papan catur • Aturan-aturan untuk melakukan gerakan secara legal • Tujuan (goal)

1

10/7/2015

Posisi awal pada papan catur • Posisi awal selalu sama

Aturan-aturan untuk melakukan gerakan secara legal • Aturan-aturan sangat berguna untuk menentukan gerakan suatu bidak • Untuk mempermudah • huruf (a,b,c,d,e,f,g,h) horizontal • angka (1,2,3,4,5,6,7,8) vertikal • Contoh • bidak (e,2) ke (e,4) – IF Bidak putih pada Kotak(e,2), •AND Kotak(e,3) Kosong, •AND Kotak(e,4) Kosong – Then Gerakkan bidak dari (e,2) ke (e,4)

Aturan-aturan untuk melakukan gerakan secara legal

Tujuan (goal) • Tujuan yang ingin dicapai adalah posisi pada papan catur yang menunjukkan kemenangan seseorang terhadap lawannya • Ditandai dengan posisi Raja yang sudah tidak dapat bergerak lagi

2

10/7/2015

Ruang Keadaan (State Space) • Suatu ruang yang berisi semua keadaan yang mungkin • Sehingga secara umum, untuk mendeskripsikan masalah dengan baik, harus: • Mendefinisikan suatu ruang keadaan • Menetapkan satu atau lebih keadaan awal • Menetapkan satu atau lebih tujuan • Menetapkan kumpulan aturan • Ada beberapa cara untuk merepresentasikan Ruang Keadaan (Graph keadaan, Pohon pelacakan)

Contoh : Masalah PETANI • Identifikasi ruang keadaan

Contoh : Masalah PETANI • Seorang petani akan menyebrangkan seekor kambing, seekor serigala dan sayur mayur dengan sebuah perahu melalui sungai. • Perahu hanya bisa memuat petani dan satu penumpang lain. • Jika Petani menyebrangkan serigala, sayur akan dimakan kambing • Jika Petani menyebrangkan sayur maka kambing akan dimakan serigala

Contoh : Masalah PETANI • Aturan-aturan

– Permasalahan ini dapat dilambangkan dengan (kambing,serigala,sayuran,perahu). – Contoh : daerah asal (0,1,1,1) = daerah asal tidak ada kambing,ada serigala,ada sayuran,ada perahu

• Keadaan awal & tujuan – Keadaan awal, pada kedua daerah : • daerah asal = (1,1,1,1) • daerah seberang = (0,0,0,0)

– Keadaan tujuan, pada kedua daerah : • daerah asal = (0,0,0,0) • daerah seberang = (1,1,1,1)

3

10/7/2015

Contoh : Masalah PETANI • Solusi

Contoh : Masalah Ember • Ada 2 ember masing-masing berkapasitas 4 galon (ember A) dan 3 galon (ember B). Ada pompa air yg akan digunakan untuk mengisi air pada ember tersebut. Bagaimana dapat mengisi tepat 2 galon air ke dalam ember berkapasitas 4 galon? Ember A Kapasitas : 4 galon

Ember B Kapasitas : 3 galon

Isi = 2 galon?

Contoh : Masalah Ember

Contoh : Masalah Ember

• Penyelesaian : • Identifikasi ruang keadaan (state space) – Permasalahan ini dapat digambarkan sebagai himpunan pasangan bilangan bulat : • x = jumlah air yg diisikan ke ember 4 galon (ember A) • y = jumlah air yg diisikan ke ember 3 galon (ember B)

– Ruang keadaan = (x,y) sedemikian hingga x є {0,1,2,3,4} dan y є {0,1,2,3}

• Keadaan awal & tujuan – Keadaan awal : kedua ember kosong = (0,0) – Tujuan : ember 4 galon berisi 2 galon air = (2,n) dengan sembarang n

• Keadaan ember • Keadaan ember bisa digambarkan sebagai berikut :

4

10/7/2015

Contoh : Masalah Ember

Contoh : Masalah Ember

• Aturan-aturan – Diasumsikan kita dapat mengisi ember air itu dari pompa air, membuang air dari ember ke luar, menuangkan air dari ember yang satu ke ember yang lain.

Contoh : Masalah Ember

TUGAS • 3 Kanibal & 3 Misionaris • Menyeberangkan semuanya ke seberang • Jika terdapat lebih banyak kanibal pada satu sisi, maka misionaris akan dimakan oleh kanibal • Notasi • M adalah Misionaris • K adalah Kanibal

• Harus dijaga agar M >= K pada satu sisi • Tentukan aturan-aturan yang digunakan dan penyelesaiannya!!

5

10/7/2015

Graph Keadaan

Representasi Ruang Keadaan Graph Keadaan • Terdiri dari node-node yang menunjukkan keadaan yaitu keadaan awal dan keadaan baru yang akan dicapai dengan menggunakan operator • Node-node saling dihubungkan dengan menggunakan arc (busur) yang diberi panah untuk menunjukkan arah

•

Node M : awal, node T : tujuan. Ada 4 lintasan dari M ke T : – – – –

•

Lintasan buntu atau lintasan yang tidak sampai ke tujuan : – – – – –

Pohon Pelacakan / Pencarian

M-A-B-C-E-T M-A-B-C-E-H-T M-D-C-E-T M-D-C-E-H-T M-A-B-C-E-F-G M-A-B-C-E-I-J M-D-C-E-F-G M-D-C-E-I-J M-D-I-J

Pohon Pelacakan / Pencarian

• menggambarkan keadaan secara hirarkis • Node pada level-0 disebut ’akar/root’ menunjukkan keadaan awal & memiliki beberapa percabangan yang terdiri atas beberapa node yg disebut ’anak/child’ • Node yg tidak memiliki anak disebut ’daun/leaf’ menunjukkan akhir dari suatu pencarian, dapat berupa tujuan yang diharapkan (goal) atau jalan buntu (dead end).

6

10/7/2015

Pohon AND / OR • Pohon OR

Pohon AND / OR • Masalah sebelumnya jika diselesaikan dengan pohon AND / OR :

– Solusi masalah M – 4 kemungkinan – A or B or C or D

• Pohon AND

– Solusi masalah M – A and B and C and D

Metode Pelacakan / Pencarian

Metode Pelacakan / Pencarian

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

• Dalam permainan catur misalnya, seorang pemain mempertimbangkan sejumlah kemungkinan tentang langkah langkah berikutnya, memilih yang terbaik menurut kriteria tertentu seperti kemungkinan respon lawannya. • Aspek tingkah laku cerdas yang mendasari teknik penyelesaian problema seperti dalam permainan catur tersebut dinamakan proses pencarian ruang keadaan (space state search).

7

10/7/2015

Kriteria • Completeness : apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada? • Time complexity : berapa lama waktu yang diperlukan? • Space complexity : berapa banyak memori yang diperlukan? • Optimality : apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda?

Breadth First Search

Teknik Pencarian • Pencarian buta (blind search) : tidak ada informasi awal yang digunakan dalam proses pencarian – Pencarian melebar pertama (Breadth – First Search) – Pencarian mendalam pertama (Depth – First Search)

• Pencarian terbimbing (heuristic search) : adanya informasi awal yang digunakan dalam proses pencarian – Pendakian Bukit (Hill Climbing) – Pencarian Terbaik Pertama (Best First Search)

Breadth First Search

• Semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. • Pencarian dimulai dari node akar terus ke level 1 dari kiri ke kanan, kemudian berpindah ke level berikutnya dari kiri ke kanan hingga solusi ditemukan.

8

10/7/2015

Breadth First Search • Keuntungan : – tidak akan menemui jalan buntu, menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik – jika ada 1 solusi, maka breadth – first search akan menemukannya,jika ada lebih dari 1 solusi, maka solusi minimum akan ditemukan. – Kesimpulan : complete dan optimal

• Kelemahan : – membutuhkan memori yang banyak, karena harus menyimpan semua simpul yang pernah dibangkitkan. Hal ini harus dilakukan agar BFS dapat melakukan penelusuran simpul-simpul sampai di level bawah – membutuhkan waktu yang cukup lama

Depth First Search

Depth First Search • Pencarian dilakukan pada suatu simpul dalam setiap level dari yang paling kiri. • Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yang kiri dapat dihapus dari memori. • Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi.

Depth First Search • Keuntungan : – membutuhkan memori relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan – Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan, jadi jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya dengan cepat (waktu cepat)

• Kelemahan : – Memungkinkan tidak ditemukannya tujuan yang diharapkan, karena jika pohon yang dibangkitkan mempunyai level yang sangat dalam (tak terhingga) / tidak complete karena tidak ada jaminan menemukan solusi – Hanya mendapat 1 solusi pada setiap pencarian, karena jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka DFS tidak menjamin untuk menemukan solusi yang paling baik (tidak optimal).

9

10/7/2015

Heuristik Search • Pembangkit dan pengujian (generate and test) • hill climbing • Best first search • A*

Metode Heuristik • Pencarian buta tidak selalu dapat diterapkan dengan baik, karena waktu aksesnya yang cukup lama & besarnya memori yang diperlukan. Terutama untuk permasalah dengan ruang masalah yang besar. • Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness). • Metode heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan

Contoh : 8-puzzle

Langkah awal

• Ada 4 operator yang dapat digunakan 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

10

10/7/2015

Pada pencarian heuristik perlu diberikan informasi khusus, yaitu jumlah ubin yang menempati posisi yang benar. Jumlah yang lebih tinggi adalah yang lebih diharapkan (lebih baik).

Generate and Test • Gabungan dari Depth First Search dan backtracking, bergerak ke belakang menuju pada suatu keadaan awal. • Algoritma : 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 terebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan. 3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.

Untuk jumlah ubin yang menempati posisi yang salah Jumlah yang lebih kecil adalah yang diharapkan (lebih baik)

Contoh : “Travelling Salesman Problem (TSP)” • Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setaip kota hanya boleh dikkunjungi tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti berikut ini :

11

10/7/2015

Hill Climbing • Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya 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.

Algoritma Simple Hill Climbing • Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru. Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang : • Cari operator yang belum digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru. • 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 daripada keadaan sekarang, maka lanjutkan iterasi.

• Pada simple hill climbing, ada 3 masalah yang mungkin: – Algoritma akan berhenti kalau mencapai nilai optimum local – Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi – Tidak diijinkan untuk melihat satupun langkah sebelumnya.

12

10/7/2015

Contoh : TSP dengan Simple Hill Climbing • Operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Apabila ada 4 kota, dan kita ingin mencari kombinasi lintasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak 6 kombinasi. n! 4! 4! 4   2.3  6 2!(n  2)! 2!( 4  2)! 2!2! – – – – – –

(1,2) menukar posisi kota 1 dan 2 (1,3) menukar posisi kota 1 dan 3 (1,4) menukar posisi kota 1 dan 4 (2,3) menukar posisi kota 2 dan 3 (2,4) menukar posisi kota 2 dan 4 (3,4) menukar posisi kota 3 dan 4

Steepest Ascent Hill Climbing • Hampir sama dengan simple hill climbing, hanya gerakan pencarian tidak dimulai dari posisi paling kiri. Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik. Dalam hal ini urutan operator tidak menentukan penemuan solusi.

13

10/7/2015

A* • Perbaikan dari metode Best-First search dengan memodifikasi fungsi heuristiknya • A* meminimumkan total biaya lintasan. Pada kondisi yang tepat, A* akan memberikan solusi yang terbaik dalam waktu yang optimal.

• Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan : f’(n) = g(n) + h’(n) dimana : f’ = Fungsi evaluasi g = cost dari initial state ke current state h’ = perkiraan cost dari current state ke goal state

Contoh Misalkan kita memiliki ruang pencarian seperti pada gambar berikut. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengan node A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di node A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara node n dengan node tujuan (jalan buntu). Kita bisa merunut nilai untuk setiap node.

14

10/7/2015

Penelusuran dengan f’(n)=h’(n) Node diekspansi M C H T

Antrian OPEN [M(6)] [C(2), A(3), B(4)] [H(2), A(3), B(4), I(~)] [T(0), A(3), B(4), L(~), I(~)] [A(3), B(4), L(~) , I(~)]

Latihan – Blind Search 1. Diketahui gambar pohon berikut : S A

B

Penelusuran dengan f’(n)=g(n)+h’(n) Node diekspansi M C H T

C

Antrian OPEN [M(6)] [C(6), B(7), A(8)] [H(7), B(7), A(8), I(~)] [T(7), B(7), A(8), L(~), I(~)] [B(7), A(8), L(~), I(~)]

Latihan – Hill Climbing Carilah lintasan terpendek dari graph di bawah dengan metode simple hill climbing dan stepest hill climbing. Jika operator yang digunakan hanya 4, yaitu (1,2), (2,3), (3,4) dan (4,1)

H

D I

E

F

G

J*

Implementasikan algoritma BFS dan DFS untuk pohon diatas jila GOAL=J

Latihan – Best 1st Search & A* 3

A

S

4 5

B

4

C G

5 3

4

D

2

E

4

F

Jika h’(n) sbb : A-G=10,4; B-G=6,7; C-G=4; D-G=8,9; E-G=6,9; F-G=3, S-G=11. Carilah lintasan terpendek dimulai dari S ke G!

15