Modul Bahan Ajar KECERDASAN BUATAN

Modul Bahan Ajar KECERDASAN BUATAN DIAN EKA RATNAWATI, S.Si.M.Kom DEWI YANTI LILIANA,S.Kom,M.Kom REKYAN REGASARI MP, ST.MT LAILIL MUFLIKHAH, S.Kom.M.Sc

PROGRAM TEKNOLOGI INFORMASI DAN ILMU KOMPUTER UNIVERSITAS BRAWIJAYA

Kecerdasan buatan / MateriKuliah

Brawijaya University

2012

KATA PENGANTAR

Alhamdulillah, puji Syukur penulis panjatkan kehadirat Allah SWT karena atas bimbingan dan petunjuk-Nya lah akhirnya penulis (tim teaching Kecerdasan Buatan PTIIK ) bisa menyelesaiakan Modul Ajar Kecerdasan Buatan ini dengan baik. Tak lupa sholawat dan salam semoga tetap tercurah kepada junjungan kita Nabi Muhammad saw. Modul ajar ini merupakan materi yang diberikan tim teaching khususnya untuk mahasiswa PTIIK yang mengambil mata kuliah Kecerdasan Buatan. Tetapi tidak ada salahnya kalau dipergunakan oleh mahasiswa lain yang sedang menempuh mata kuliah tersebut. Dengan modul ajar ini diharapkan bisa membantu meningkatkan kompetensi siswa dalam penguasaan materikecerdasan Buatan yang saat ini dianggap masih relative sulit oleh mahasiswa. Penguasaan materi ini sangat penting, karena kecerdasan buatan sebagai materi dasar untuk penguasaaan mata kuliah lain. Penulis menyadari sepenuhnya, bahwa modul ini masih jauh dari kesempurnaan. Untuk itu, kritik konstruktif dan saran dalam rangka meningkatkan modul pengajaran ini kami tunggu. Selain itu, penulis berharap bahwa modul pengajaran dapat memberikan manfaat bagi ilmu pengetahuan dan bagi kita semua. Akhirnya, terima kasih untuk semuanya. Malang, Desember 2012

Penulis Tim teaching Kecerdasan Buatan

Page 1 of 98



2012

DAFTAR ISI KATA PENGANTAR ....................................................................................... 0 DAFTAR ISI ..................................................................................................... 2 PENGANTAR KECERDASAN BUATAN ......................................................... 4 1. PENDAHULUAN ................................................................................................................................................................ 4 2. DEFINISI KECERDASAN BUATAN........................................................................................................................... 4 3. FONDASI ILMU KECERDASAN BUATAN .............................................................................................................. 6 4. SEJARAH KECERDASAN BUATAN ........................................................................................................................... 7 5. CONTOH APLIKASI KECERDASAN BUATAN ...................................................................................................... 8

AGEN CERDAS .............................................................................................. 9 1. PENDAHULUAN ................................................................................................................................................................ 9 2. KONSEP AGEN CERDAS DAN LINGKUNGAN ..................................................................................................... 9 3. KONSEP PERANCANGAN AGEN CERDAS ......................................................................................................................... 10 4. JENIS LINGKUNGAN ........................................................................................................................................................... 11 5. JENIS AGEN .......................................................................................................................................................................... 12

PENYELESAIAN PROBLEM DENGAN PENCARIAN (SEARCHING) ........... 16 1. PENDAHULUAN .............................................................................................................................................................. 16 2. JENIS PROBLEM ............................................................................................................................................................. 16 3. FORMULASI PROBLEM ............................................................................................................................................... 17 4. ALGORITMA PENCARIAN DASAR ......................................................................................................................... 19 5. STRATEGI PENCARIAN UNINFORMED .............................................................................................................. 20

PENCARIAN HEURISTIK / INFORMED SEARCH ....................................... 25 1. PENDAHULUAN .............................................................................................................................................................. 25 2.GENERATE AND TEST ................................................................................................................................................... 26 3.HILL CLIMBING ............................................................................................................................................................... 27 4.BEST FIRST SEARCH ..................................................................................................................................................... 32

CONSTRAINT SATISFACTION PROBLEM .................................................. 40 1. PENDAHULUAN .............................................................................................................................................................. 40 2. KOMPONEN CSP ............................................................................................................................................................. 41 3. BACKTRACKING ............................................................................................................................................................. 42 4. FORWARD CHECKING ................................................................................................................................................. 45 5.CONSTRAINT PROPAGATION .................................................................................................................................. 46 6.ARC CONSISTENCY ....................................................................................................................................................... 46

Page 2 of 98



2012

LOGICAL AGENTS ....................................................................................... 51 1. PENDAHULUAN .............................................................................................................................................................. 51 2. AGEN BERBASIS PENGETAHUAN (KNOWLEDGE-BASED AGENT) ............................................................................. 52 3. AGEN BERBASIS LOGIKA................................................................................................................................................... 54

FIRST ORDER LOGIC ................................................................................... 60 1.PENDAHULUAN................................................................................................................................................................ 60 2. FIRST ORDER LOGIC ................................................................................................................................................... 61 3. CONTOH.............................................................................................................................................................................. 66 4. PROPAGASI ...................................................................................................................................................................... 68

LOGIC PROGRAMMING .............................................................................. 69 1. PENDAHULUAN .............................................................................................................................................................. 69 2. PARADIGMA PEMROGRAMAN ............................................................................................................................................ 69 3. LOGIC PROGRAMMING IN PROLOG ................................................................................................................................. 70 4. APLIKASI PEMROGRAMAN LOGIKA ................................................................................................................................. 73

UNCERTAINTY (KETIDAKPASTIAN) ........................................................ 74 1. PENDAHULUAN .............................................................................................................................................................. 74 2.UNCERTAINTY ................................................................................................................................................................. 75 3. CONTOH.............................................................................................................................................................................. 79

BAYESIAN NETWORK ................................................................................ 82 1. PENDAHULUAN .............................................................................................................................................................. 82 2. SINTAK BAYESIAN NETWORK ............................................................................................................................... 82

KECERDASAN BUATAN:LEARNING ........................................................... 87 1.PENDAHULUAN................................................................................................................................................................ 87 2. LEARNING (PEMBELAJARAN) ................................................................................................................................ 88 3.PROPAGASI ....................................................................................................................................................................... 90

LAMPIRAN .............................................................................................. 91

Page 3 of 98



2012

Kecerdasan Buatan: PENGANTAR KECERDASAN BUATAN

Dian Eka Ratnawati, S.Si, M.Kom,Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc,Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya, Email : [email protected]

1. Pendahuluan 1.1. Pengantar 1.2. Tujuan 2. Definisi Kecerdasan Buatan 3. Fondasi Ilmu Kecerdasan Buatan 4. Sejarah Kecerdasan Buatan

5. Contoh Aplikasi Kecerdasan Buatan 6. Rangkuman 7. Latihan

1.1 Pengantar Kecerdasan Buatan adalah salah satu disiplin ilmu dalam bidang komputer yang terus berkembang. Bidang Kecerdasan Buatan atau bahasa aslinya Artificial Intelligence (disingkat AI) berusaha tidak hanya untuk memahami tetapi juga untuk membangun entitas cerdas. AI meliputi banyak sub-bidang, mulai dari bidang umum sampai untuk tugas-tugas spesifik. 1.2 Tujuan Penguasaan materi dalam modul ini dirancang agar mahasiswa mampu untuk :  Mengetahui apa itu kecerdasan buatan.  Mengetahui fondasi dan sejarah kecerdasan buatan.  Mengetahui contoh aplikasi kecerdasan buatan.

2. DEFINISI KECERDASAN BUATAN Definisi AI menurut Russel dan Norvig (Russel, Norvig, 2003) dapat dikategorikan menjadi dua dimensi utama yang membahas proses/penalaran berpikir (reasoning) dan perilaku/tindakan (behavior). Selanjutnya definisi AI dapat dijabarkan lagi berdasarkankinerja (performance) dan rasionalitasnya. Keempat sudut pandang tersebut membentuk matriks definisi AI, seperti yang terdapat pada gambar 1.1.

Page 4 of 98

1 PENGANTAR KECERDASAN BUATAN

1. PENDAHULUAN

MODUL



Sistem yang berpikir seperti manusia Thinking humanly

Sistem yang berpikir secara rasional Thinking rationally

Sistem yang bertindak seperti manusia Acting humanly

Sistem yang bertindak secara rasional Acting rationally

2012

Gambar 1.1. Matriks definisi kecerdasan buatan Penjelasan dari matriks pada gambar 1.1. adalah sebagai berikut: 1. Sistem yang bertindak seperti manusia (act humanly) “Ilmu tentang bidang mental melalui penggunaan model komputasional.” (Charniak & McDermott, 1985) Tes Turing: Pada tahun 1950 Turing mengusulkan ide untuk mendefinisikan kecerdasandalam makalahnya yang berjudul “Computing machinery and intelligence". Pertanyaan utamanya adalah untuk mengetahui apakah mesin dapat berpikir atau tidak yang masih tidak jelas. Untuk mengetahui jawaban atas masalah tersebut, ia merancang sebuah skenario pengujian antara komputer dan manusia, serta seorang interrogator yaitu manusia. Fokusnya bukan untuk menjawab pertanyaan tentang kemampuan mesin untuk berpikir, tetapi untuk mengamati kemampuan mesin untuk berperilaku cerdas. komputer berhasil melewati tes jika interogator manusia, setelah mengajukan beberapa pertanyaan tertulis , tidak bisa menentukan apakah jawaban tertulis itu berasal dari komputer atau manusia. Turing memprediksi bahwa pada tahun 2000, komputer mungkin memiliki kesempatan 30% untuk membodohi orang awam selama 5 menit. Prediksi Turing tersebut terbukti. Saat ini komputer sudah dapat melakukan serangkaian tes Turing yang dikenal sebagai imitation game. Untuk dapat melakukan hal tersebut komputer perlu memiliki beberapa kemampuan yaitu:      

Pemrosesan bahasa alami (natural language processing) agar komputer dapat berkomunikasi dengan bahasa alami manusia. Representasi pengetahuan (knowledge representation) untuk menyimpan apa yang diketahuinya. Penalaran otomatis (Automated reasoning) yang menggunakan informasi yang tersimpan untuk menjawab pertanyaan maupun menarik kesimpulan baru. Pembelajaran mesin (Machine learning) untuk beradaptasi pada lingkungan baru dan mendeteksi serta mengenali pola Computer vision untuk menangkap dan mempersepsikan obyek. Robotika untuk memanipulasi obyek dan bergerak

Keenam disiplin ini membentuk ilmu AI, dan Allan Turing adalah orang yang berjasa mendesain serangkaian tes yang tetap relevan 50 tahun kedepan. 2. Sistem yang berpikir seperti manusia (think humanly) “Upaya untuk membuat komputer dapat berpikir. Mesin dengan pikiran dalam makna sebenarnya.” (Haugeland, 1985) Pendekatan pemodelan kognitif: Untuk menyatakan apakah suatu program komputer dapat berpikir seperti manusia, haruslah dapat ditentukan bagaimanakah proses manusia berpikir. Untuk menjawabnya perlu Page 5 of 98



2012

eksperimen psikologi. Jika kita punya cukup pengetahuan tentang teori pikiran, maka sangat memungkinkan mengekspresikan teori tersebut dalam program komputer. Pada era 1960an muncul ilmu kognitif sebagai suatu bidang interdisipliner yang menggabungkan model komputer pada AI dengan teknik eksperimen pada psikologi untuk membangun teori tentang cara kerja otak manusia. Ahli komputer menyatakan bahwa algoritma komputer yang berjalan baik dalam menyelesaikan suatu masalah merupakan model proses berpikir manusia. Pada akhirnya bidang AI terpisah dari psikologi kognitif. Kedua bidang tersebut saling mendukung khususnya pada ranah computer vision dan pemrosesan bahasa alami. 3. Sistem yang berpikir rasional (think rationally) “Seni menciptakan mesin yang dapat mengerjakan fungsi yang membutuhkan kecerdasan jika dikerjakan oleh manusia.” (Kurzweil, 1990) “Laws of thought” = pendekatan penalaran Filosofis Yunani, Aristotles adalah orang pertama yang berupaya mengkodekan “berpikir dengan benar” atau melalui proses penalaran (reasoning). Proses ini dikenal dengan silogisme, yaitu suatu struktur/pola memberikan argument melalui sekumpulan premis yang akan selalu memberikan konklusi yang benar. Contoh silogisme: Premis 1: Socrates adalah manusia Premis 2: Semua manusia bisa mati Konklusi: Socrates bisa mati Ilmu yang mempelajari pendekatan penalaran ini disebut Logika. Para ahli logika di abad ke-19 membangun notasi standar logika untuk menyatakn seluruh kejadian di dunia beserta relasinya. Ada beberapa hambatan pada pendekatan logika yaitu: 1. Tidak mudah untuk memperoleh pengetahuan informal dan menyatakannya dalam istilah formal (notasi logika). 2. Mekanisme logika membutuhkan biaya komputasi yang tinggi. 3. Pemecahan masalah "pada prinsipnya" ≠ pemecahan masalah dalam praktek. 4. Sistem yang bertindak rasional (act rationally) “AI berfokus pada perilaku cerdas pada suatu alat.” (Nilsson, 1998) Pendekatan agen rasional. Agen adalah sesuatu yang dapat melakukan tindakan. Agen kecerdasan buatan diharapkan dapat melakukan tindakan yang membedakannya dari program komputer biasa. Tindakan tersebut seperti operasi otonom, mempersepsikan (merasa) lingkungannya, adaptif terhadap perubahan, dan bisa mencapai suatu tujuan. Agen rasional adalah agen yang dapat bertindak untuk mencapai hasil yang terbaik (memaksimalkan tercapainya goal/tujuan).

3. FONDASI ILMU KECERDASAN BUATAN Ilmu kecerdasan buatan merupakan kontribusi dari berbagai disiplin ilmu, tidak eksklusif dari bidang komputer saja. Fondasi ilmu yang membentuk kecerdasan buatan yaitu: 1. Filsafat:  Pikiran adalah seperti mesin  Menggunakan pengetahuan untuk mengoperasikan sesuatu  Pemikiran digunakan untuk mengambil tindakan 2. Matematika  Alat untuk memanipulasi pernyataan logis  Memahami perhitungan Page 6 of 98

Kecerdasan buatan / MateriKuliah 


2012

Penalaran algoritma

3. Ekonomi Pengambilan keputusan untuk memaksimalkan hasil yang diharapkan 4. Neuroscience (Ilmu syaraf)  Studi tentang sistem syaraf  Bagaimana otak memproses informasi 5. Psikologi  Ilmu kognitif  Manusia dan hewan adalah mesin pengolah informasi 6. Teknik komputer Menyediakan alat/artefak untuk aplikasi AI 7. Teori kontrol Merancang perangkat lingkungan.

yang

bertindak

optimal

berdasarkan

umpan

balik

dari

8. Bahasa Bagaimana bahasa berhubungan dengan pikiran. Knowledge representation language dan natural language processing.

4. SEJARAH KECERDASAN BUATAN Sejarah perkembangan kecerdasan buatan dibagi menjadi beberapa periode yang dapat dijabarkan sebagai berikut: 1. Cikal bakal Kecerdasan Buatan (1943 – 1955) - Cikal bakal AI dikerjakan oleh McCulloh & Pitts dengan Neuron buatan yang menirukan cara kerja neuron manusia dengan logika proposisional. Bisa menyelesaikan fungsi komputasi dengan struktur neuron network. - Hebbian learning, memperkenalkan aturan sederhana untuk meng-update kekuatan antar neuron. - Minsky & Edmonds membangun komputer neural network pertama pada 1950. - Allan Turing dianggap sebagai orang pertama yang mengeluarkan pikiran tentang AI secara lengkap pada artikelnya yang berjudul “Computing machinery and Intelligent” pada tahun 1950. 2. Kelahiran Kecerdasan Buatan (1956) - McCarthy menginisiasi Dartmouth Workshop pada tahun 1956 yang melahirkan suatu nama bidang baru “Artificial Intelligence”. - Mengapa AI berbeda dengan disiplin ilmu lain yang serupa? Karena AI berfokus menirukan kemampuan manusia seperti kreatifitas, pengembangan diri, dan penggunaan bahasa. Selain itu juga karena metodologi AI merupakan cabang dari ilmu komputer yang berupaya membangun mesin yang berfungsi otonom pada lingkungan yang kompleks dan berubah-ubah. 3. Awal mula AI yang penuh antusias dan harapan besar (1952 – 1969) Merupakan tahap pengembangan aplikasi AI yang sukses jika dibandingan dengan program komputer primitif. Banyak aplikasi AI yang berhasil sehingga memunculkan istilah “evolusi mesin” 4. AI menjadi industry (1980 – sekarang) Page 7 of 98



2012

-

Aplikasi komersial pertama menggunakan sistem pakar bernama R1 yang digunakan oleh perusahaan Ameriak (1982). - Jepang juga membentuk proyek jangka panjang menggunakan komputer cerdas berbasis Prolog. 5. Kecerdasan Buatan menjadi disiplin ilmu (1987 – sekarang) 6. AI menampakkan diri di semua bidang (1995 – sekarang)

5. CONTOH APLIKASI KECERDASAN BUATAN Beberapa contoh aplikasi kecerdasan buatan yang telah diterapkan:     

DEEP BLUE mengalahkan dunia catur Garry Kasparov juara pada tahun 1997. ALVINN mengemudi melintasibenua Amerika (mengemudi otonom 98% dari total jarak, dari Pittsburgh ke San Diego). Selama Perang Teluk 1991, penggunaan aplikasi AI untuk perencanaan logistik dan program penjadwalan yang melibatkan hingga 50.000 kendaraan, kargo, dan pasukan AS. Program perencanaan otonom milik NASA yang mengontrol penjadwalan operasi untuk pesawat ruang angkasa. Proverb, aplikasi AI untuk memecahkan teka-teki silang yang lebih baik daripada kebanyakan manusia.

REFERENSI Russell, Stuart; dan Norvig, Peter. 2003. Artificial Intelligence A Modern Approach. International Edition, Edisi 2. Pearson Prentice-Hall Education International. New Jersey

RANGKUMAN   

Kecerdasan Buatan (AI) berkaitan dengan pemikiran (thinking) dan perilaku (behavior). Fondasi ilmu yang mendasari terbentuknya AI adalah: Filsafat, Matematika, Ekonomi, Neuroscience, Teknik Komputer, Teori Kontrol, dan Bahasa (linguistik). AI telah maju lebih pesat saat ini karena peningkatan penggunaan metode ilmiah dalam bidang AI.

PROPAGASI A. Latihan (evaluasi mandiri) Jelaskan istilah pada bidang AI serta berikan beberapa contoh implementasi untuk masingmasing sub bidang tersebut! 1. Pengolahan Bahasa Alami 2.Knowledge representation 3.Automated Reasoning 4. Machine Learning 5. Computer Vision 6. Robotika Page 8 of 98



2012

Kecerdasan Buatan: AGEN CERDAS Dian Eka Ratnawati, S.Si, M.Kom,Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc,Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya, Email : [email protected]

1. Pendahuluan 1.1. Pengantar 1.2. Tujuan 2. Konsep Agen Cerdas dan Lingkungan 3. Konsep Perancangan Agen Cerdas

4. Jenis Lingkungan 5. Jenis Agen

2

1. PENDAHULUAN

1.2 Tujuan Penguasaan materi dalam modul ini dirancang agar mahasiswa mampu untuk :  Mengetahui konsep agen cerdas dan lingkungan agen cerdas.  Mengetahui konsep PEAS (Performance measure, Environment, Actuators, Sensors) untuk merancang agen cerdas.  Mengetahui jenis lingkungan dan jenis agen cerdas.

2. KONSEP AGEN CERDAS DAN LINGKUNGAN

  

Agen adalah segala sesuatu yang dapat dipandang sebagai entitas pada suatu lingkungan yang mengamati melalui alat sensor dan bertindak melalui alat aktuator. Sebagai perbandingan, agen manusia memiliki alat sensor: mata, telinga, dan organ sensor lainnya; alat actuator: tangan, kaki, mulut, dan bagian tubuh lain sebagai alat gerak. Sedangkan pada agen robot: kamera dan inframerahi untuk sensor, danlengan, serta berbagai motor sebagaiaktuator. Agen menerima (percept) sensor dari lingkungan. Keseluruhan percept yang diterima agen pada suatu selang waktu disebut percept sequence.

AGEN CERDAS

1.1 Pengantar Pada bagian ini dapat kita lihat bahwa konsep rasionalitas dapat diterapkan pada lingkungan yang luas. Pembahasan pada bagian ini meliputi konsep agen dan lingkungannya. Selain itu juga akan dipelajari prinsip mendesain agen cerdas yang benar, berdasarkan jenis lingkungan serta jenis agen.



MODUL

Hubungan antara agen dan lingkungan dan digambarkan seperti pada gambar 2.1.

Page 9 of 98



2012

Gambar 2.1. Ilustrasi hubungan agen dan lingkungan   

Fungsi Agen (pada gambar 2.2. berupa kotak dengan tanda tanya) memetakanpercept sequence/percept history ke tindakan (action): [f: P * A à] Program agen berjalan pada arsitektur fisik untuk menghasilkan nilai fungsi f. agen = arsitektur + program

3. Konsep Perancangan Agen Cerdas

Rasional dapat didefinisikan sebagai: melakukan hal yang benar. Agen rasional melakukan hal yang benar berdasarkan percept apa yang ditangkap dan tindakan (action) apa yang diambil. Tindakan yang tepat adalah tindakan yang akan menyebabkan agen menjadi yang paling sukses. Beberapa hal yang perlu ditekankan:   

Rasionalitas berbeda dari omniscience (serba tahu/mengetahui semua dengan pengetahuan tak terbatas). Agen dapat melakukan tindakan dalam rangka untuk mengubah persepsi masa depan untuk memperoleh informasi yang berguna (pengumpulan informasi, eksplorasi). Sebuah agen dikatakan otonom jika perilaku agen ditentukan oleh pengalaman sendiri (dengan kemampuan untuk belajar dan beradaptasi).

Pengukuran kinerja: Sebuah kriteria obyektif untuk mengukur keberhasilan suatu perilaku agen Misalnya, mengukur kinerja dari agen vacuum-cleaner:    

Jumlah Jumlah Jumlah Jumlah

kotoran dibersihkan, waktu yang dibutuhkan, listrik yang dikonsumsi, kebisingan yang dihasilkan, dll

Pengukuran kinerja haruslah dapat dinyatakan dalam ukuran kuantitatif. Kata “jumlah” mengindikasikan suatu ukuran kuantitatif/terukur. Untuk setiap urutan persepsi (percept sequence) yang ada, agen rasional harus memilih tindakan yang diharapkan untuk memaksimalkan ukuran kinerjanya. Tujuan (Goal): Setelah menentukan criteria obyektif (seperti diatas), pilih salah satu tujuan untuk menjadi fokus utama dari agen. Goal adalah tujuan utama yangberusaha dicapai oleh agen (prioritas utama) Konsep utama perancangan agen cerdas/rasional dapat dilakukan dengan bantuan PEAS yang merupakan singkatan dari:Performance measurement, Environment, Actuators, Page 10 of 98



2012

Sensors. PEAS harus ditentukan sebelum desain agen cerdas. Berdasarkan informasi PEAS, kita benar dapat merancang agen untuk memenuhi tujuan yang ingin dicapai.Sebagai contoh, misalnya tugas merancang sebuah sopir taksi otomatis. Definisikan PEAS agen cerdas tersebut seperti berikut:  Performance Measure: Aman, cepat, legal, perjalanan nyaman, memaksimalkan keuntungan  Environment: Jalan, lalu lintas lainnya, pejalan kaki, pelanggan  Aktuator: Setir, pedal gas, rem, sinyal, klakson  Sensor: Kamera, sonar, speedometer, GPS, odometer, sensor mesin, keyboard Contoh lain dari mendefinisikan PEAS: Agen: sistem diagnosis Medis    

Performance Measure: Pasien Sehat, meminimalkan biaya, tuntutan hukum Environment: Pasien, rumah sakit, staf Aktuator: Layar display (pertanyaan, tes, diagnosis, pengobatan, rujukan) Sensor: Keyboard (masuknya gejala, temuan, jawaban pasien)

Agen: Part-picking robot (robot pengambil komponen)    

Performance Measure: Persentase berapa bagian masuk ke kotak yang benar Environment: Conveyor, komponen-komponen, kotak komponen Aktuator: lengan dan tangan robot Sensor: Kamera, sensor sudut persendian

4. Jenis Lingkungan

Jenis lingkungan tempat agen cerdas bekerja dapat ditinjau dari beberapa aspek (berikut aspek yang menjadi lawannya,) bergantung lingkungan dimana agen tersebut berada. Aspekaspek lingkungan adalah: 

 



 

Sepenuhnya teramati vs Sebagian teramati: Lingkungan sepenuhknya teramati jika sensor mendeteksi semua aspek yang relevan dengan pilihan action. Sebuah sensor agen memberikan akses ke keadaan lengkap lingkungan pada setiap titik waktu. Lingkungan sebagian teramati karena sensor berisik dan tidak akurat. Deterministik vs Stokastic: Keadaan berikutnya lingkungan sepenuhnya ditentukan oleh keadaan saat ini dan tindakan yang dilakukan oleh agen. (Jika lingkungan deterministik kecuali untuk tindakan agen lain, maka disebut lingkungan strategis). Episodik vs Sekuensial: Pengalaman agen dibagi menjadi "episode" atom (setiap episode terdiri dari: agen mengamati (percept) dan kemudian melakukan tindakan tunggal), dan pilihan tindakan di setiap episode hanya bergantung pada episode itu sendiri. - Contoh: Klasifikasi (episodik), catur danpengemudi taksi otonom (sekuensial). Statis vs Dinamis: Lingkungan berubah, agen tidak perlu terus mencari pada lingkungan untuk memutuskan sesuatu. Pada lingkungan dinamis terus meminta agen apa yang ia ingin lakukan. (Lingkungan semidinamis jika lingkungan itu sendiri tidak berubah dengan berlalunya waktu namun skor kinerja agen berubah) Diskrit vs Kontinu: Jumlah state/tindakan untuk mencapai goal terbatas (diskrit), persepsi yang jelas dan tindakan yang terhingga. (misalnya, catur - diskrit, mengemudi taksi - kontinyu). Agen tunggal vs agen multi: Seorang agen yang beroperasi dengan sendirinya dalam suatu lingkungan.

• Jenis Lingkungan sangat menentukan desain agen Page 11 of 98



2012

• Dunia nyata (tentu saja) secara parsial diamati, stokastik, sekuensial, dinamis, terus menerus, multi-agen.

5. Jenis Agen

Empat jenis dasar agen terurut dari yang paling umum ke khusus:     

Agen refleks sederhana: Agen memilih tindakan berdasarkan persepsi saat ini, mengabaikan sisa sejarah persepsi. Agen reflex berbasis model: Agen mempertahankan state internal yang bergantung pada sejarah persepsi, mencerminkan beberapa aspek teramati dari kondisi saat ini. Agen berbasis tujuan: Agen memiliki informasi tentang tujuan dan memilih tindakan untuk mencapai tujuan Agen berbasis utilitas: Agen menyatakan/menetapkan pengukuran kuantitatif terhadap lingkungan (ranking). Pemilihan tindakan yang rankingnya paling tinggi (paling dekat mencapai tujuan). Agen berbasis pembelajaran: Agen belajar dari pengalaman, dapat beradaptasi untuk meningkatkan kinerja.

Penjelasan: 1. Agen refleks sederhana (Simple Reflex Agent)

Gambar 2.2. Simple Reflex Agent Agen Refleks Sederhana:     

Aturan kondisi-tindakan: Kondisi yang memicu beberapa tindakan ex. Jika mobil di depan mengerem (kondisi) kemudian memulai pengereman (tindakan) Agen refleks Sederhana sederhana namun sangat terbatas kecerdasannya. Menghubungkan percept ke tindakan. keputusan yang benar dapat dibuat hanya dalam lingkungan yang penuh teramati.

Simple Reflex Agent function SIMPLE-REFLEX-AGENT (percept) return an action static: rules, a set of condition-action rules state INTERPRET-INPUT (percept) rule RULE-MATCH(state,rules) action RULE-ACTION[rule] return action Page 12 of 98



2012

o INTERPRET-INPUT merupakan fungsi yang menghasilkan deskripsi dari kondisi saat ini dari percept. o RULE-MATCH merupakan fungsi yang mengembalikan aturan pertama dalam seperangkat aturan yang cocok dengan deskripsi yang diberikan oleh suatu state. 2. Agen Berbasis Model

Gambar 2.3. Model berbasis Agen    

Cara yang paling efektif untuk menangani pengamatan parsial adalah melacak bagian dari dunia yang bisa teramati saat ini (current state). Agen mempertahankan keadaan internal yang bergantung pada sejarah persepsi dan dengan demikian mencerminkan beberapa aspek teramati dari kondisi saat ini. Untuk memperbarui informasi keadaan internal memerlukan dua pengetahuan: o Bagaimana dunia berkembang secara independen dari agen o Bagaimana tindakan agen memengaruhi dunia Pengetahuan tentang "bagaimana dunia bekerja" disebut model

Agen berbasis Model: function REFLEX-AGENT-WITH-STATE (percept) return an action static:

state, a description of the current world state rules, a set of condition-action rules action, the most recent action, initially none state UPDATE-STATE (state,action,percept) rule RULE-MATCH(state,rules) action RULE-ACTION[rule]

return action o UPDATE-STATE menciptakan keadaan internal baru

Page 13 of 98



2012

3. Agen Berbasis Goal

Gambar 2.4. Goal based agent  

Mengetahui tentang keadaan saat ini saja tidak selalu cukup untuk memutuskan apa yang harus dilakukan. Agen membutuhkan informasi tujuan (goal) yang menggambarkan situasi yang diinginkan

4. Agen berbasis Utilitas

Gambar 2.5. AgenberbasisUtilitas   

Mencapai tujuan saja tidak cukup untuk menghasilkan perilaku berkualitas tinggi perilaku dalam lingkungan. Seberapa cepat? Seberapa aman? Bagaimana murah? Dapat diukur Fungsi Utilitas memetakan state ke bilangan real (ukuran kinerja)

Page 14 of 98



2012

5. Agen berbasis Pembelajaran

Gambar 2.6. AgenberbasisPembelajaran   

Elemen learning bertanggung jawab untuk membuat perbaikan Elemen Kinerja bertanggung jawab untuk memilih tindakan eksternal Kritik memberikan umpan balik tentang bagaimana tindakan yang dilakukan agen

REFERENSI Russell, Stuart; dan Norvig, Peter. 2003. Artificial Intelligence A Modern Approach. International Edition, Edisi 2. Pearson Prentice-Hall Education International. New Jersey

Rangkuman        

Agen berinteraksi dengan lingkungan melalui sensor dan aktuator Fungsi agen menjelaskan apa yang dilakukan agen dalam segala situasi Ukuran kinerja mengevaluasi lingkungan agen Sebuah agen rasional memaksimalkan kinerja yang diharapkan Agen program mengimplementasikan (beberapa) agen fungsi Deskripsi PEAS membantu mendefinisikan agen cerdas dan lingkungannya Lingkungan dikategorikan menjadi beberapa dimensi bergantung pada aspekaspeknya:diamati, deterministik, episodik, statis, diskrit, single-agent? Beberapa arsitektur agen dasar: refleks, berbasis model, berbasis goal, berbasis utilitas, pembelajaran.

PROPAGASI A. Latihan (evaluasi mandiri) 1. Buatlah sebuah makalah yang menjelaskan tentang agen rasional yang anda pilih sebagai agen cerdas dalam menyelesaikan suatu masalah! (Anda dapat membuat agen sendiri yang tidak pernah ada sebelumnya atau sesuatu dalam imajinasi Anda, misal agen pembantu rumah tangga.) 2. Tentukan lingkungan agen dan jenis agen, dan penjelasannya!

Page 15 of 98



2012

Kecerdasan Buatan:

Penyelesaian Problem dengan Pencarian (searching)

Dian Eka Ratnawati, S.Si, M.Kom, Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc, Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya

1.

Pendahuluan 1.1. Pengantar 1.2. Tujuan 2. Jenis Problem 3. Formulasi Problem

4. Algoritma Pencarian Dasar 5. Strategi Pencarian Uninformad

1. PENDAHULUAN

1.2 Tujuan Penguasaan materi dalam modul ini dirancang agar mahasiswa mampu untuk :  Mengetahui jenis problem/masalah  Dapat memformulasi problem  Mengetahui contoh penyelesaian problem  Mengetahui strategi pencarian tanpa informasi (uninformed)

2. JENIS PROBLEM     

Agen penyelesaian problem adalah jenis agen berbasis tujuan/goal. Agen berbasis tujuan memutuskan apa yang harus dilakukan dengan menemukan urutan tindakan yang mengarah ke state yang paling diinginkan. Tahapan penting/utama adalah perumusan tujuan dan perumusan masalah. Searching merupakan mekanisme yang menggunakan masalah sebagai masukan dan mengembalikan solusi dalam bentuk urutan tindakan. Eksekusi didasarkan pada algoritma pencarian yang digunakan.

Page 16 of 98

3 Penyelesaian Problem dengan Pencarian (searching)

1.1 Pengantar Pada bagian ini dibahas agen cerdas penyelesaian problem, serta strategi uninformed untuk memecahkan masalah. Terdapat beberapa teknik yang termasuk dalam strategi pencarian uninformed.

MODUL



2012

3. FORMULASI PROBLEM Deskripsi Masalah:  Pada suatu liburan di negara Rumania, saat ini (current state) berada di kota Arad.  Penerbangan meninggalkan Rumania besok dari kota Bucharest.  Merumuskan tujuan:berada di Bucharest  Merumuskan masalah: o states: berbagai kota o tindakan: menyetir melewati kota-kota di Rumania dari Arad ke Bucharest o Cari Solusi:urutan kota, misalnya, Arad, Sibiu, Fagaras, Bucharest

Gambar 3.1 Peta Rumania Sebuah masalah yang didefinisikan oleh: 1. state awal misalnya, "di Arad" 2. tindakan atau fungsi successor S (x) = set tindakan-state   misalnya, S (Arad) = {, ...}  tujuan, dapat berupa tujuan eksplisit, misalnya, x = "di Bucharest", implisit, misalnya, Checkmate (x) 3. jalur biaya (aditif)  Menetapkan biaya numerik untuk setiap jalur  Misalnya, jumlah jarak, jumlah tindakan yang dieksekusi, dll  c (x, a, y) adalah biaya per langkah, diasumsikan ≥ 0  Solusi adalah urutan tindakan dari state awal ke state tujuan  kualitas Solusi diukur oleh fungsi biaya Contoh State Space 1. Vacuum world state space

Gambar 3.2. Vacuum world Page 17 of 98



 states? Letak kotoran dan lokasi robot  actions?Left, Right, Suck  goal test?Tidak ada kotoran sama sekali di semua lokasi  path cost? 1 per action 2. The 8-puzzle Problem

Gambar 3.3. Problem 8-puzzle  states?Lokasi setiap kotak nomor  actions? move, blank, left, right, up, down  goal test? = goal state (terdapat pada gambar)  path cost? 1 per move 3. 8-Queens Problem

   

Gambar 3.4. 8-Queens Problem states?Papan catur dengan n queens (n= 1…8) actions? move, left, right, up, down goal test? = 8 queens pada posisi yang benar, tidak ada yang saling serang path cost? 1 per move

4. Robotic assembly

Gambar 3.5. Robotic assembly    

states?: Nilai riil koordinat robot joint angles actions?: gerakan kontinyu robot joints goal test?: complete assembly path cost?: waktu eksekusi

Page 18 of 98

2012



2012

4. ALGORITMA PENCARIAN DASAR Ide dasar: Eksplorasi secara offline , simulasi state space dengan menghasilkan turunan (successor) dari state yang sudah dieksplorasi (dikenal sebagai expanding state). Algoritma pencarian dasar:

General tree search

Contoh Tree untuk permasalahan Tur Rumania:

Gambar 3.6. Tree untuk tur Rumania Implementasi: state vs node  Sebuah state adalah (representasi) konfigurasi fisik  Sebuah node adalah sebuah struktur data yang merupakan bagian dari tree pencarian meliputi state, parent node, tindakan, jalur biaya g (x), dan kedalaman.  Fungsi Expand menciptakan node baru, mengisi berbagai bidang dan menggunakan SuccessorFn dari masalah untuk menciptakan state yang sesuai. Page 19 of 98



2012

Gambar 3.7. Implementasi state vs node

5. STRATEGI PENCARIAN UNINFORMED  

Sebuah strategi pencarian didefinisikan dengan memilih urutan ekspansi node. Strategi dievaluasi sepanjang dimensi berikut: o kelengkapan: apakah selalu mencari solusi jika ada? o kompleksitas waktu: jumlah node yang dihasilkan o kompleksitas ruang: jumlah maksimum node dalam memori o optimalitas: apa selalu menemukan solusi yang paling murah?  kompleksitas waktu dan ruang diukur dalam hal: b: faktor percabangan maksimum search tree d: kedalaman solusi yang paling murah m: panjang maksimum setiap path (mungkin ∞) Strategi pencarian uninformed hanya menggunakan informasi yang tersedia dalam definisi masalah. Terdapat 5 teknik yang termasukstrategi uninformed, yaitu: 1. Breadth-first search 2. Uniform-cost search 3. Depth-first search 4. Depth-limited search 5. Iterative Deepening search Penjelasan masing-masing adalah: 1. Breadth-first search (BFS)  Memperluas node terdangkal yang belum diekspansi  Implementasi:

Urutan ekspansi dari node A – D : A-B-C-D Properti BFS  Lengkap? Ya (jika b adalah terbatas) Page 20 of 98

Kecerdasan buatan / MateriKuliah    


2012

Waktu? 1 1+b+b2+b3+… +bd + b(bd-1) = O(bd+1) Ruang? O(bd+1) (setiap node terus disimpan dalam memori) Optimal? Ya (jika biaya = 1 per langkah) Ruang adalah masalah yang lebih besar (lebih dari waktu)

2. Uniform Cost Search (UCS)  Sama seperti BFS dengan tambahan pembentukan tree diurutkan berdasarkan cost yang paling murah/least-cost  Urutan ekspansi seperti BFS  Implementasi: tree/queue diurutkan berdasarkan least-cost  Lengkap? Ya, jika biaya langkah ≥ ε  Waktu? Jumlahnode dengan g ≤ biaya solusi optimal, O(bceiling(C*/ ε))di mana C* adalah biaya dari solusi optimal  Space? Jumlah node dengan g ≤ biaya solusi optimal, O(bceiling(C*/ ε))  Optimal? Ya - node diperluas dalam rangka peningkatan g (n) 3. Depth-first search (DFS) Pencarian unexpanded node terdalam

Page 21 of 98



2012

Urutan ekspansi dari A ke M: A-B-D-H-I-E-J-K-C-F-L-M Properti BFS:  Lengkap? Tidak: bisa gagal dalam ruang pencarian takterbatas, ruang pencarian dengan loop  Waktu? O(bm):mengerikan jika m jauh lebih besar daripada d tetapi jika solusi padat, mungkin jauh lebih cepat daripada BFS  Space? O (bm), yaitu, ruang linear!  Optimal? Tidak 4. Depth Limited Search (DLS) • Merupakan strategi DFS dengan batas kedalaman tree l yang didefinisikan sebelumnya. • Rekursif Pelaksanaan DLS:

5. Iterative Deepening Search (IDS) • Prinsip dari strategi ini adalah melakukan pencarian DLS secara bertahap dengan nilai l yang ditambahkan pada setiap iterasinya. • Strategi ini mengkombinasikan keuntungan BFS dan DFS (kelengkapan dan kompleksitas ruang linear dijamin). Lakukan pencarian DLS dengan l = 0,1,2, ... sampai tidak cutoff • Ilustrasi: 

Page 22 of 98



2012

Properti IDS  Lengkap? Ya  Waktu? ((d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd)  Space? O (bd)  Optimal? Ya, jika step cost= 1 Ringkasan Strategi Uninformed Search

Gambar 3.8. Ringkasan strategi uninformed search

REFERENSI Russell, Stuart; dan Norvig, Peter. 2003. Artificial Intelligence A Modern Approach. International Edition, Edisi 2. Pearson Prentice-Hall Education International. New Je rsey Page 23 of 98



2012

Rangkuman    

Perumusan masalah biasanya membutuhkan abstrak pergi rincian dunia nyata untuk menentukan ruang state yang bisa dieksplorasi. Agen penyelesaian problem dapat memecahkan masalah dan mencapai tujuan melalui strategi pohon pencarian (searching tree). Berbagai strategi pencarian uninformed: BFS, UCS, DFS, DLS, IDS IDS hanya menggunakan ruang linear dan tidak banyak waktu lebih dari algoritma uninformed lainnya.

PROPAGASI A. Latihan (evaluasi mandiri) Formulasikan masalah perjalanan dari Arad ke Bucharest (Lihat Peta Rumania)! desainlah search treemasalah ini menggunakan kelima strategi uninformed search, kemudian bandingkan total step costnya!

Page 24 of 98



2012

Kecerdasan Buatan: PENCARIAN HEURISTIK / INFORMED SEARCH Dian Eka Ratnawati, S.Si, M.Kom, Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc, Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya

Program Teknologi Informasi dan Ilmu Komputer, 1. PENDAHULUAN 1.1 Pengantar 1.2 Tujuan 1.3 Definisi 2. Generate and Test

3. Hill Climbing 4. Best First Search 5. Latihan

MODUL

1. PENDAHULUAN 1.1

1.2 Tujuan Penguasaan materi dalam modul ini dirancang agar mahasiswa mampu untuk : 1. Memahami dan mengerti Metode Pencarian heuristikyaitu Bangkitkan - dan - Uji (Generate and Test), Pendakian Bukit (Hill Climbing) yang meliputiSimple Hill Climbing dan SteepestAscent Hill Climbing, Best First Search yang meliputi Greedy Best First Search dan Algoritma A*. 2. Menerapkan metode inform search tersebut untuk menyelesaikan berbagai permasalahan

Page 25 of 98

(SPEED)

Pengantar Pada modul 4 ini akan dibahas mengenai pencarian heuristik. Pencarian heuristik (informed search) lebih cepat dan bagus daripada pencarian buta (uninformed search) yang sudah dibahas pada modul 3. Hal ini karena pada pencarian heuristik ditambahkan informasi tambahan yang bisa berupa bobot, jarak atau yang lain. Informasi tambahan tersebut yang akan mempercepat dan membantu proses pencarian. Tetapi ada kelemahan dari metode ini yaitu solusi yang dihasilkan bisa jadi bukan yang terbaik. Ada beberapa pencarian heuristik yang akan dibahas pada modul 4 ini , diantaranya adalah pertama : Bangkitkan - dan Uji (Generate and Test), kedua :Pendakian Bukit (Hill Climbing)yang meliputiSimple Hill Climbing dan SteepestAscent Hill Climbing, kemudian yang terakhir Pencarian Terbaik Pertama (Best First Search) yang meliputi Greedy Best First Search dan Algoritma A*.

PENCARIAN HEURISTIK/ INFORMED SEARCH

4



2012

1.3 Definisi Heuristik - Kata Heuristic berasal dari sebuah kata kerja bahasa Yunani, heuriskein, yang berarti ‘mencari’ atau menemukan. - Dalam dunia pemrograman, sebagian orang menggunakan kata heuristik sebagai lawan kata algoritmik, dimana kata heuristik ini diartikan sebagai suatu proses yang dapat menyelesaikan suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari selalu dapat ditemukan. - Pencarian heuristik merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (statespace) suatu problem secara selektif, yang memandu proses pencarian yang dilakukan di sepanjangjalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang sia-sia dan memboroskan waktu - Untuk dapat menerapkan heuristik tersebut dengan baik dalam suatu domain tertentu, diperlukan suatu Fungsi Heuristik. - Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

2.GENERATE AND TEST Algoritma : 1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu ataulintasan tertentu dari keadaan awal) 2. Uji apakah node tersebut adalah solusi dengan membandingkan node tersebut atau node akhir dari lintasan yang dipilih dengan kumpulan tujuan yang diharapkan 3. Jika solusi ditemukan,langkah–langkah tersebut dihentikan, jika tidak, kembali ke langkah pertama 4. Jika pembangkitan atau pembuatan solusi–solusi yang dimungkinkan dapat dilakukan secara sistematis, maka prosedur ini akan dapat segera menemukan solusinya, (bila ada). 5. Namun, jika ruang problem sangat besar, maka proses ini akan membutuhkan waktu yang lama, sehingga metode generate and test ini kurang efisien untuk masalah yang besar atau kompleks. Kelemahan metode Generate and Test: - Membangkitkan semua kemungkinan sebelum dilakukan pengujian - Membutuhkan waktu yang cukup besar dalam pencariannya Contoh Soal : Seorang salesman ingin mengunjungi n kota. Jarak tiap kota sudah diketahui seperti terlihat pada gambar 4.1.Bantu salesman untuk menentukan rute terpendek, dimana setiap kota hanya boleh dikunjungi 1 kali. Misal ada 4 kota dengan jarak sebagai berikut: A 7 D

B

8 3

4

6

5 C

Gambar 4.1 Penyelesaian : Membangkitkan solusi - solusi yang mungkin dengan menyusun kota – kota dalam urutan abjad, yaitu: Page 26 of 98



2012

A–B–C–D  A – D – B – C dan seterusnya Jumlah seluruh kombinasi abjad yangmenjadi sulusi adalah n!. Pilih keadaan awal, mis ABCD dengan panjang lintasan 19.Lakukan backtracking untuk mendapatkan lintasan ABDC 18.Bandingkan lintasan ABDC dengan sebelumnya, lintasan terpendek akan dipilih untuk dilakukan backtracking lagi.

Tabel 4.1 Alur pencarian dengan generate & test pada TSP. Pencarian ke-

Lintasan

Panjang Lintasan

Lintasan terpilih

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21.

ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC

19 18 12 13 16 18 17 21 15 18 14 13 15 14 20 16 21 18 20 15 15

22.

DBCA

12

23.

DCAB

17

24.

DCBA

19

ABCD ABDC ACBD ACBD ACBD ACBD ACBD ACBD ACBD ACBD ACBD ACBD ACBD ACBD ACBD ACBD ACBD ACBD ACBD ACBD ACBD ACBD atau DBCA ACBD atau DBCA ACBD atau DBCA

Panjang Lintasan terpilih 19 18 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12

3. HILL CLIMBING Hill climbing merupakan salah satu variasi metode Bangkitkan - dan - Uji (generate and test) dimana umpan balik yang berasal dari prosedur uji digunakan untuk memutuskan arah gerak dalam ruang pencarian. Dalam prosedur Hill Climbing, fungsi ujidikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan (goal). 3.1.

Simple Hill Climbing

Algoritma : 1. Mulai keadaan awal, lakukan pengujian: jika tujuan maka stop,jika tidak maka lanjuntukan dengan keadaan sekarang sebagai keadaan awal. 2. Ulangi langkah berikutnya hingga solusi ditemukan atau sampai tidak ada operator baru yang diaplikasikan pada keadaan sekarang: Page 27 of 98



2012

a. Pilih operator yang belum pernah digunakan, gunakan operator untukmendapatkan keadaan yang baru b.Evaluasi keadaan baru tersebut : (i) Jika keadaan baru adalah tujuan, keluar (ii) Jika tidak, namun nilainya lebih baik dari keadaan sekarang, maka jadikan keadaan baru tersebutmenjadi keadaan sekarang (iii) Jika keadaan baru tidaklebih baik daripada keadaan sekarang, makalanjuntukan iterasi Masalah yangakan timbulpadaprosedur Hill Climbing :  Local optimum : adalah suatu keadaan yang lebih baik daripada semua tetangganya namun masih belum lebih baik dari suatu keadaan lain yang jauh letaknya darinya  Sering muncul ketika sdh mendekati solusi.

Gambar 4.5. Hill Climbing  Plateau(Daratan):adalah suatu daerah datar dari ruang pencarian (search) dimana keadaan semua tetangga sama dengann keadaan dirinya  Ridengane (Punggung) : local optimum yang lbh disebabkan karena ketidak mampuan untuk menggunakan 2 operator sekaligus. Solusinya: 1. Melakukan langkah balik (backtracking) ke simpul yang lebih awal dan mencoba bergerak ke arah yang lain. 2. Melakukan lompatan besar ke suatu arah untuk mencoba bagian ruang pencarian yang baru. 3. Menerapkan dua atau lebih aturan sebelum melakukan uji coba. Ini bersesuaian dengan bergerak ke beberapa arah sekaligus. Contoh Soal : Selesaikan permasalahan TSP pada Gambar 4.1 dengan menggunakan metode Simple Hill Climbing Jawab :  Operator yang digunakan adalah operator yang bisa menghasilkan kombinasi lintasan kota yang berbeda, yaitu dengan menukar urutan posisi 2 kota dalam suatu lintasan. n!  Bila ada n kota maka kombinasi lintasan :

2!n  2!

Sehingga kalau ada 4 kota, menjadi:

4! 6 2! (4  2)!

dipakai semuanya sebagai operator, yaitu Page 28 of 98

kombinasi. Keenam kombinasi ini akan

Kecerdasan buatan / MateriKuliah 1. 2. 3. 4. 5. 6.

(1,2) (2,3) (3,4) (4,1) (2,4) (1,3)

tukar tukar tukar tukar tukar tukar

urutan urutan urutan urutan urutan urutan

posisi posisi posisi posisi posisi posisi


kota kota kota kota kota kota

ke-1 ke-2 ke-3 ke-4 ke-2 ke-1

dengan dengan dengan dengan dengan dengan

kota kota kota kota kota kota

2012

ke-2 ke-3 ke-4 ke-1 ke-4 ke-3

Pencarian dilihat dari anak kiri, bila nilai heuristik anak kiri lebih baik maka dibuka untuk pencarian selanjutnya, bilatidak baru melihat tetangga dari anak kiri tersebut. Pada pencarian ini, penggunaan urutan dari kombinasi harus konsisten, misalnya pada penyelesaian ini urutan sesuai no 1 sampai dengan 6 seperti yang ada di atas. Urutan kombinasi yang lain juga diperkenankan, yang penting konsisten untuk semua level. Untuk lebih jelasnya bisa dilihat seperti pada Gambar 4.2. ABCD D

(19) Tk 1,2 Tk 2,3

BACD

(17)

Tk 3,4

ACBD

Tk 1,3

Tk 4,1

ABDC

Tk 2,4

DBCA

ADCB

CBAD

Tk 1,2 (15) Tk 2,3

ABCD

Tk 3,4

BCAD Tk 1,2

Tk 4,1

BADC

Tk 2,3

DACB

Tk 3,4

Tk 4,1

(20)

CBAD

Tk 2,4

BACD

(17)

(14)

BCDA

DCAB

BDAC

Tk 1,2 (21)

Tk 1,2

BDCA

BCDA Tk 3,4 (19)

DCBA

Tk 2,3 Tk 3,4 (13)

BADC

(12)

Tk 2,3

CABD

Tk 1,3

Tk 2,4

DBAC

Tk 1,2

BDCA

(18)

(15)

DBCA

Tk 1,3

BDCA

Tk 2,3

Tk 3,4

Tk 4,1

Tk 2,4

ADCB

Tk 2,4 (15)

DBAC

Tk 4,1

Tk 2,4

CDAB

Tk 4,1

BDAC

ACBD Tk 1,3

BCAD

ADBC

Tk 1,3

BACD

CDBA

Tk 1,3 (16)

(19)

ABCD

DACB

CBDA

(15)

Gambar 4.2 Metode Simple Hill Climbing dengan 6 operator. Keterangan Gambar 4.2: o Pada Gambar 4.2 terlihat bahwa, pada keadaan awal, lintasan terpilih adalah ABCD (=19). o Pada level pertama, hill climbing akan mengunjungi BACD (=17), BACD memiliki nilai heuristik lebih kecil dibandingkan dengan ABCD (17<19), sehingga BACD menjadi pilihan selanjutnya dengan operator Tukar1,2. o Pada level kedua, hill climbing akan mengunjungi ABCD. Karena operator Tukar1,2 sudah digunakan oleh BACD, maka dipilih node yang lain yaitu BCAD (=15). Karena Page 29 of 98


o o o o

o

o o






2012

nilai heuristik BCAD lebih kecil dibanding dengan BACD (15<17), maka node BCAD akan menjadi pilihan selanjutnya dengan operator Tukar2,3. Kemudian hill climbing akan mengunjungi CBAD (=20). Karena nilai heuristik CBAD lebih besar jika dibanding dengan BCAD (20>17), maka dipilih node lain. Pencarian menuju ke node BACD, karena operator Tukar2,3 sudah pernah digunakan oleh BCAD, maka dipilih node lain. Kunjungan berikutnya ke node BCDA (=18). Nilai inipun masih lebih besar dari nilai heuristic BCAD, sehingga dipilih node lain. Node yang dikunjungi berikutnya adalah DCAB (=19). Nilai heuristik DCAB ternyata juga lebih besar dibanding dengan BCAD, sehingga pencarian dilanjuntukan di node lainnya lagi, yaitu BDAC (=14). Nilai heuristik ini sudah lebih kecil daripada nilai heuristik node BCAD (14<15), maka sekarang node ini yang akan diekplorasi. Pencarian pertama ditemukan node DBAC (=21), yang lebih besar daripada nilai BDAC. Nilai heuristik yang lebih kecil diperoleh pada node BDCA (=13). Sehingga node BDCA ini akan diekplorasi. Pencarian pertama sudah mendapatkan node dengan nilai heuristik yang kebih kecil, yaitu DBCA (=12). Sehingga node ini diekplorasi juga. Dari hasil ekplorasi dengan pemakaian semua operator, ternyata sudah tidak ada node yang memiliki nilai heuristik yang lebih kecil dibanding dengan nilai heuristik DBCA, sehingga sebenarnya node DBCA (=12) inilah lintasan terpendek yang kita cari (SOLUSI). Misalkan tidak dipergunakan semua operator, melainkan hanya dipergunakan 4 operator pertama saja, yaitu: (a) Tukar 1,2 (menukar urutan posisi kota ke-1 dengan kota ke-2). (b) Tukar 2,3 (menukar urutan posisi kota ke-2 dengan kota ke-3). (c) Tukar 3,4 (menukar urutan posisi kota ke-3 dengan kota ke-4). (d) Tukar 4,1 (menukar urutan posisi kota ke-4 dengan kota ke-1). Maka pencarian dengan simple hill climbing ini dapat dilihat pada Gambar 4.3. Lintasan terpendek yang diperoleh adalah B-C-A-D yaitu sepanjang 15. Disini kita akan terjebak pada nilai minimum lokal yang disebabkan oleh kurangnya operator yang kita gunakan. Kita tidak dapat memperoleh nilai minimum globalnya yaitu sebesar 12. (19)

ABCD

Tukar 1,2 Tukar 2,3 (17)

(20)

Tukar 1,2

CBAD

ACBD

Tukar 3,4 Tukar 2,3 (15)

Tukar 1,2

ABCD

BACD

BCAD

BACD

BCDA

ABDC

Tukar 4,1

DBCA

Tukar 4,1

BADC

Tukar 3,4 Tukar 2,3 (17) (18)

Tukar 3,4

Tukar 4,1

DACB (17)

DCAB

Gambar 4.3. Metode Simple Hill Climbing dengan 4 operator.

Page 30 of 98



2012

KelemahanSimple Hill Climbing : 1. tidak semua solusi dapat ditemukan seperti pada metode generate and test 2. pembatasan kombinasi operator  penemuan solusi yang tidak maksimal 3.2. Steepest-Ascent Hill Climbing  Algoritma : (1) Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjuntukan dengan keadaan sekarang sebagai keadaan awal. (2) Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang. (a) Tentukan SUCC sebagai nilai heuristik terbaik dari successor-successor. (b) Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang: i.Gunakan operator tersebut dan bentuk keadaan baru. ii. 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. Pada steepest-ascent hill climbing ini, ada 3 masalah 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) Ridengane: local optimum yang lebih disebabkan karena ketidakmampuan untuk menggunakan 2 operator sekaligus. Contoh Soal : Selesaikan permasalahan TSP pada Gambar 4.1 dengan menggunakan metode steepest ascent hill climbing Jawab : Pada metode ini, juga dipergunakan 6 operator seperti operator yang dipergunakan unttuk menyelesaikan TSP pada Simple Hill Climbing. Fungsi heuristik yang digunakan adalah panjang lintasan yang terjadi. (19)

ABCD

Tk 1,2

(15)

CABD

Tk 2,3

(17)

(12)

BACD

ACBD

Tk 1,2 Tk 3,4 Tk 2,3 (13)

(19)

ABCD

ACDB

(18)

Tk 3,4

ABDC

Tk 4,1 Tk 2,4 (19)

DCBA

Tk 4,1

Tk 1,3 Tk 2,4 (12) (18)

DBCA Tk 1,3 (16)

ADBC

ADCB

(20)

CBAD

(15)

BCAD

Gambar 4.4 Metode Steepest Ascent Hill Climbing  o o

Keterangan gambar 4.4.: Pada Gambar 4.4, terlihat bahwa, keadaan awal, lintasan terpilih adalah ABCD (19). Pada level pertama, hill climbing akan memilih nilai heuristik terbaik dari keenam succesor yang ada, yaitu: BACD(17), ACBD(12), ABDC(18), DBCA(12), ADCB (18) atau CBAD(20). Tentu saja yang terpilih adalah ACBD, karena memiliki nilai heuristik paling kecil (=12). Page 31 of 98

Kecerdasan buatan / MateriKuliah o

o


2012

Dari ACBD ini akan dipilih nilai heuristik terbaik dari succesornya yaitu: CABD(15), ABCD(19), ACDB(13), DCBA(19), ADBC(16) atau BCAD(15). Ternyata dari keenam successor tersebut memiliki nilai heuristik yang lebih besar disbanding dengan ACBD. Sehingga tidak akan ada perubahan nilai keadaan (tetap ACDB). Hasil yang diperoleh, lintasannya adalah ACBD (12).

4. BEST FIRST SEARCH  Merupakan kombinasi kelebihan teknik depth first search dan breadth first search  Pencarian diperkenankan mengunjungi node yang ada di level yang lebih rendah jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristik yang buruk  Best First Search akan membangkitkan node berikutnya dari semua node yang pernah dibangkitkan  Hill climbing tidak diperbolehkan untuk kembali ke node pada lebih rendah meskipun node tersebut memiliki nilai heuristik lebih baik.  Pada best first search, pencarian diperbolehkan mengunjungi node di lebih rendah, jika ternyata node di level lebih tinggi memiliki nilai heuristik lebih buruk. Pada metode Best First Search cara untuk menentukan sebuah node terbaik saat inidengan menggunakan biaya perkiraan. Biaya perkiraan dapat ditentukan dengan fungsi heuristic. Suatu fungsi heuristic dikatakan baik jika bisa memberikan biaya perkiraan yang mendekati biaya sebenarnya.Semakin mendekati biaya sebenarnya, fungsi heuristic tersebut semakin baik. Dalam kasus pencarian rute terpendek, biaya sebenarnya adalah panjang jalanRaya yang sebenarnya. Sedangkan fungsi heuristiknya adalah garis lurus dari1 kota ke kota lainnya.

Gambar 4.6. Hill Climbing Untuk menghitung jarak antar kota bisa dipergunakan rumus euclidian: dab = ( yb – ya )2 + ( xb – xa )2

Untuk mengimplementasikan metodeBest First Search ini, dibutuhkan 2 antrian yang berisi node-node, yaitu :  OPEN : berisi node-node yang sudah dibangkitkan, sudah memiliki fungsi heuristik namun belum diuji. Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan nilai heuristik tertinggi.  CLOSED : berisi node-node yang sudah diuji Pada modul ini diperkenalkan 2 algoritma yang tergolong Best First Search yaitu : 1. Greedy Best First Search 2. Algoritma A* Page 32 of 98

Kecerdasan buatan / MateriKuliah 4.1.


2012

Greedy Best First Search  Algoritma ini merupakan jenis algoritma Best First Search yang paling sederhana  Algoritma ini hanya memperhitungkan biaya perkiraan saja f(n) = h’(n)  Karena hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya, maka algoritma ini menjadi tidak optimal Contoh soal: Dari gambar 4.7, lalukan penemuan jalur terpendek dari Arad menuju ke Bucharet dengan menggunakan menggunakan algoritma Greedy,

Gambar 4.7Kota Romania Penyelesaian :

Page 33 of 98



2012

Gambar 4.8Penyelesaian TSP Romania dengan algoritma Greedy

Properti dari greedy best-first search  Complete?Tidak, dapat terjebak dalam looping,contoh: Iasi  Neamt  Iasi  Neamt   Time?O(bm), tetapiheuristikyang baikdapat memberikanperbaikan secara dramatis  Space?O(bm) -- menyimpansemua nodedalam memori  Optimal?Tidak (memperluas jalurbiayaminimal tapitidak bisamenjadi optimal) 4.2.

Algoritma A*(Admissible Heuristic )

 Berbeda dengan Greedy, algoritma ini akan menghitung fungsi heuristic dengan cara menambahkan biaya sebenarnya dengan biaya perkiraan.  Heuristik adalah kriteria, metoda, atau prinsip-prinsip untuk menentukan pilihansejumlah alternatif untuk mencapai sasaran dengan efektif.  Nilai heuristik dipergunakan untukmempersempit ruang pencarian  Dengan heuristik yang benar, maka A* pasti akan mendapatkan solusi (jika memang ada solusinya) yang dicari.  Dengan kata lain, heuristik adalah fungsi optimasi yang menjadikan algoritma A* lebih baik dari pada algoritma lainnya.  Namun heuristik masih merupakan estimasi / perkiraan biasa saja,sama sekali tidak ada rumus khususnya. Artinya, setiap kasus memiliki fungsi heuristik yang berbedabeda.  Algoritma A* ini bisa dikatakan mirip dengan algoritma Dijkstra, namun pada algoritma Dijkstra, nilai fungsi heuristiknya selalu 0 (nol) sehingga tidak ada fungsi yang mempermudah pencarian solusinya.  Metode ini berdasarkan formula fungsi evaluasi: f(n) = g(n) + h(n) Keterangan : h(n) = biaya estimasi dari node n ke tujuan. g(n) = biaya path / perjalananuntuk menuju n f(n) = solusi biaya estimasi termurah node n untuk mencapai tujuan. (Russell, Stuart J and Norvig, Peter, 2003). Langkah Algoritma A* 1. Masukan node awal ke openlist Loop Langkah – langkah di bawah ini : a. Cari node (n) dengan nilai f(n) yang paling rendah dalamopen list. Node ini sekarang menjadi current node. b. Keluarkan current node dari openlist dan masukan ke close list Page 34 of 98



2012

c. Untuk setiap tetangga dari current node lakukan berikut : • Jika tidak dapat dilalui atau sudah ada dalam close list, abaikan. • Jika belum ada di open list . Buat current node parent dari node tetangga ini. Simpan nilai f,g dan h dari node ini. • Jika sudah ada di open list, cek bila node tetangga ini lebih baik, menggunakan nilai g sebagai ukuran. Jika lebih baik ganti parent dari node ini di openlist menjadi current node, lalu kalkulasi ulang nilai g dan f dari node ini. Contoh 1: Dari gambar 4.7, lalukan penemuan jalur terpendek dari Arad menuju ke Bucharet dengan menggunakan menggunakan algoritma A* Penyelesaian TSP dengan A*

Page 35 of 98



2012

Gambar 4.9Penyelesaian TSP Romania dengan algoritma A* Contoh 2 Temukan jalur terpendek dari S menuju ke G dengan menggunakan lgoritma A*, pada Gambar 4.10

Gambar 4.10. Graph dengan informasi biaya dan jarak antar kota Penyelesaian

Gambar 4.11. langkah 1 dan 2 penyelesaian dengan algoritma A*

Page 36 of 98



Gambar 4.12. langkah 3 penyelesaian dengan algoritma A*

Gambar 4.13. langkah 4 dan 5 penyelesaian dengan algoritma A*


Page 37 of 98

2012



2012



Gambar 4.17. langkah 9(sudah ditemukan jarak terpendek menuju kota G) Jadi jalur terpendek untuk menuju kota G dari S adalah : S- A-B-F-K-G dengan total jarak 95

Page 38 of 98



2012

Properties A*  Complete? Ya (kecuali adanodetak terhinggadengan f ≤ f(G) )  Time? Exponential  Space?Menyimpan semua node dalam memori  Optimal? Ya 

REFERENSI       

Anonim, TEKNIK PENCARIAN HEURISTIK(HEURISTIC SEARCHING), http://journal.mercubuana.ac.id/data/Heuristic-search.pdf, tanggal akses 15 Agustus 2012 Anonim, HEURISTIC SEARCH Presentation Part IV, ,http://hxpinter.files.wordpress.com/2012/11/ai_04.ppt,tanggal akses 15 Agustus 2012 Anonim, TeknikPencarianHeuristik, http:// hendrik.staff.gunadarma.ac.id/.../files/.../teknik-pencarian-heuristik.p...,, tanggal akses 20 Agustus 2012 Azhar,Yulis,heuristic Search Best First Search , Teknik Informatika -UMM, www.mdp.ac.id/materi/2011-2012-1/.../TI322-041035-666-9.ppt, tanggal akses 20 Agustus 2012 Russel, S., Norvig 1997, Artificial Intelligence: A Modern Approach , Prentice Hall. 2. Suyanto, ST.MSc ,2007,”Artificial Intelligence : Searching, Reasoning, Planning dan Learning” , Informatika Bandung Sri Kusumadewi, 2003, Artificial Intelligence : Teknik dan Aplikasinya, Graha Ilmu, Yogyakarta

PROPAGASI A. Latihan dan Diskusi 1. Coba simpulkan apa yang anda ketahui tentangGenerate and Test, Hill Climbing, Best First Search? 2. Dari Gambar 4.18 lakukan pencarian rute terpendek dengan menggunakan a. Generate and Test b. Hill Climbing c. Best First Search Estimasi waktu (dalam 50 F menit) untuk menuju 10 goal (H) B 20

C

10

50

10

20

40

A

80

H

20

90

D

20

E

A: 60 B: 80 C: 20 D: 25 E: 70 F: 25 G: 35

30

G

Gambar 4.18.

Page 39 of 98



2012

Kecerdasan Buatan CONSTRAINT SATISFACTION PROBLEM

Dian Eka Ratnawati, S.Si, M.Kom,Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc,Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya

1. PENDAHULUAN 1.1.Pengantar 1.2.Tujuan 1.3.Definisi 2.Komponen CSP

3. 4. 5. 6. 7.

Backtracking Forward Checking Constrain Propagation Arc consistency Latihan

1. PENDAHULUAN

1.2 Tujuan Penguasaan materi dalam modul ini dirancang agar mahasiswa mampu untuk : 1. Mahasiswa mengerti dan bisa menyelesaikan kasus-kasus Constraint Satisfaction Problems (CSP) 2. Mahasiswa mengerti DAN BIBacktracking 3. Mahasiswa mengerti Local search CSP

1.3. Definisi Constraint satisfaction problems (CSP) :  Constraint satisfaction problem (CSP) didefinisikan sebagai serangkain variabel {X1, X2, …, Xn}, dan serangkaian constraints {C1, C2, …, Cm}.  Setiap variabel Xi mempunyai domain Di. Setiap constraint Ci meliputi beberapa subset variabel dan menentukan nilai yang diijinkan untuk subset ini.  State problem kemudiandidefinisikan sebagai tugas untukbeberapa atau semuavariabel, {Xi =vi, Xj=vj, ...}. Solusi untukCSPadalahtugaslengkapyang tidak melanggar semuakendala Page 40 of 98

5

CONSTRAINT SATISFACTION PROBLEM

1.1.Pengantar Constraint satisfaction problem (CSP) merupakan sebuah pendekatan dari problem yang bersifat matematis dengan tujuan menemukan keadaan atau obyek yang memenuhi sejumlah persyaratan (constrain) yang sudah ditetapkan. Banyak problem dapat dikategorikan CSP diantaranya n-queen problem, crossword(teka-teki silang), penjadwalan ,boolean satisfiability problem (SAT), ataupun pewarnaan peta(map coloring). Pada modul ini akan diperkenalkan beberapa metode untuk menyelesaiakan CSP diantaranya adalah backtracking, forward checking,constraint propagation, dan arc and path consistency. Untuk lebih memahami algoritma tersebut akan diberikan beberapa contoh.

MODUL



2. KOMPONEN CSP CSP terdiri dari komponen komponen berikut:  Variabel, yang merupakan penampung dapat diisi berbagai nilai.  Constraintyang merupakan suatu aturan yang ditentukan untuk mengatur nilai boleh diisikan ke variabel, atau kombinasi variabel.  Domain yang merupakan kumpulan nilai legal dapat diisi ke variabel.  Solusi/Goal test yang merupakan assignment nilai-nilai dari domain ke setiap variabel tidak ada constraint yang dilanggar.  Solusi adalah penetapan nilai (assignment) terhadap semua variabel sehingga semua syarat dipenuhi  CSP dimulai dari solusi kosong dan diakhiri dengan sebuah solusi yang memenuhi semua constraint (consistent).Pencarian solusi dilakukan dengan mencoba mengisi nilai domain pada setiap variabel satu demi satu tanpa melanggar constraint, sampai solusi ditemukan. Contoh CSP: Mewarnai Peta Lakukan pewarnaan pada Peta Gambar 5.1 sehingga pada kota yang saling berbatasan tidak diperbolehkan mempunyai warna yang sama, dimana hanya disaediakan 3 waarna yang berbeda

Gambar 5.1 PETA Ketentuan yang harus dipenuhi untuk melakukan pewarnaan PETA pada gambar 5.1 adalah : Variabel: WA, NT, Q, NSW, V, SA, T Ranah: Di = {red, green, blue} Syarat: 2 wilayah yang berbatasan harus berbeda warna: WA ≠ NT, NT ≠ SA, . . . (WA, NT) Є{(red, green), (red, blue), (green, red), (green, blue), . . .}, . . . Dari Gambar 5.1 tersebut bisa dimungkinkan ada banyak solusi , yang salah satu contoh solusinya seperti pada Gambar 5.2.

Gambar 5.2 Contoh solusi pada perawrnaan PETA Solusi adalah pemberian nilai setiap variabel yang memenuhi syarat, mis:{WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, Page 41 of 98

2012



T=green}

Constraint graph •

merupakan representasi di mana node adalah variabel, edge adalah constraint, misal peta pada gambar 5.2 bisa dibuat seperti gambar 5.3

Gambar 5.3 Contoh Constraint graph

Jenis constraint

Unaryconstraint::menyatakan persyaratan sebuahvariabel, mis: SA ≠ green Binary constraint::menyatakan persyaratan sepasangvariabel, mis: SA ≠ WA n-ary constraint(Higher-Order) :menyatakan persyaratan tiga atau lebih variabel, mis: Cryptarithmetic Preferences (soft constraints) :syarat yang sebaiknyadipenuhi, tetapi tidak harus. Mis: r lebih baik dari g. Biasanya dinyatakan sebagai cost sebuah nilaivariabel. ! constrained optimization problem.

Menyelesaikan CSP dengan search biasa

State ditentukan dengan nilai yang sudah dialokasikan sekarang Initial state: assignment kosong: {} Successor function: pilih nilai untuk sebuah variabelyang belum diassign yang sah: tidak konflik denganassignment. Jika tidak ada: gagal! Goal test: apakah assignment sudah lengkap Catatan: 1. Hal ini berlaku untuk setiap masalah CSP 2. Karena variabel terbatas maka setiap solusi akan muncul pada kedalaman n dengan n variabel gunakan depth-first Search 3. Karena path irrelevan kita dapat gunakan algoritma local search

3. BACKTRACKING    

Algoritma backtracking search (penelusuran kembali) adalah suatu bentuk algoritma depth-first-search. Backtracking dapat dilihat sebagaimana searching dalam tree, karena setiap node mewakili state dan turunan dari setiap node mewakili ekstensi dari state tersebut. Pada metode backtracking, variabel diisi secara sequential selagi semua variabel relevan dengan constraint yang sudah diinisialisasi. Jika solusi partial melanggar constraint, backtracking melakukan langkah kembali ke solusi partial sebelumnya dan memilih nilai lain yang belum dicoba untuk variabel yang ingin diisikan. Page 42 of 98

2012

Kecerdasan buatan / MateriKuliah  

 




Langkah tersebut berguna untuk menghindari eksplorasi lebih lanjut dari solusi partial yang salah. Keuntungan backtracking : pemeriksaan consistency hanya perlu dilakukan terhadap assignment yang terakhir dilakukan karena pemeriksaan terhadap assignment yang sebelumnya sudah dilakukan sebelumnya. Pada algoritma backtracking, teknik look ahead digunakan untuk meramalkan efek pemilihan variabel branching untuk mengevaluasi nilai-nilai variabel tersebut. Forward checking adalah salah satu cara untuk melakukan look ahead. Forward checking mencegah terjadinya konflik dengan melarang nilai-nilai yang belum diisikan ke variabel untuk dipakai. Ketika suatu nilai diisikan ke suatu variabel, nilai yang berada di domain dari variabel yang konflik dengan assignment tersebut akan dihilangkan dari domain.

Backtracking search  Variabel assignment berlaku komutatif, dalam arti:[WA=red lalu NT=green] sama saja [NT=green lalu WA=red]  Pada tiap level, hanya perlu meng-assign satu variabel b = d, ada dn leaf  Depth first search pada CSP dengan assignment satuvariabel tiap level disebut backtracking search.  Algoritma uninformed standar untuk masalah CSP Algoritma Bactracking

Contoh Lakukan pewarnaan peta pada Gambar 5.1 dengan menggunakan Bactracking

Page 43 of 98

2012



Gambar 5.4 Contoh backtraking Memperbaiki kinerja backtracking  Urutan pemilihan variabel dan nilai mempengaruhi kinerja backtracking  Terdapat beberapa strategi yang berlaku secara umum (generalpurpose): 1. Variabel mana yang perlu di-assign terlebih dulu? 2. Nilai apakah yang perlu dicoba terlebih dulu? 3. Apakah kita bisa mendeteksi kepastian failure lebih awal? 4. Apakah kita bisa memanfaatkan struktur masalahCSP? (Representasinya jelas!)

PRINSIP PEWARNAAN

Ada beberapa prinsip dalam melakukan pewarnaan antara lain : Prinsip 1: Most Constrained Variabel  Adalah :Variabel paling dibatasi  Pilih variabel yang memiliki kemungkinan nilai sah paling sedikit

Gambar 5.5 Contoh prinsip 1 Prinsip 2: Most Constraining Variabel  Adalah variabel paling membatasi  Pilih variabel yang terlibat constraint dengan variabel lain (yang belum di-assign) yang paling banyak.  Tie − breaker : gunakan kalau ada 2 atau lebih variabel yang sama bagusnya berdasarkan prinsip 1.

Gambar 5.6 Contoh prinsip 2 Prinsip 3: Least Constraining Value  Adalah variabel paling membebasi  Pilih nilai yang menimbulkan batasan kemungkinan nilai variabel lain (yang belum di-assign) yang paling sedikit.  Jika ketiga prinsip ini digunakan, masalah n-queens Page 44 of 98

2012



dengan n=1000 bisa diselesaikan!

Gambar 5.7 Contoh prinsip 3

4. FORWARD CHECKING  

 

Cara termudah untuk menghindari konflik isi variabel Melalui forward checking hanya akan dievaluasi constraint antara variabel saat ini dan variabel berikutnya. Jika suatu nilai dialokasikan untuk variabel saat ini, maka nilai apapun dari variabel berikutnya yang dapat membawa konflik dari variabel saat ini akan disingkirkan dari domain. Keuntungannya adalah jika domain dari variabel berikutnya adalah kosong, maka segera dikeahui bahwa solusi yang terbentuk ternyata salah. Dengan forward checking, maka pencabangan dari pohon pencarian akan dipangkas lebih awal, dibanding dengan backtracking. Catat kemungkinan nilai sah untuk semua variabel yang belum diassign. Jika ada sebuah variabel yang tidak ada kemungkinan nilai sah, langsung failure (backtrack).

Gambar 5.8 Inisialisasi nilai untuk forward checking Ideforward checking:  Simpan nilai valid untuk variabel yang belum di-assign  Bila salah satu variabel tidak mempunyai kemungkinan nilai yang valid maka search dihentikan  Untuk lebih jelasnya langkah forward checkingdapat dillihat pada gambar 5.9

Page 45 of 98

2012



Gambar 5.9 Langkah penyelesaian untuk forward checking

5.CONSTRAINT PROPAGATION Constraint propagation  Forward checking memberikan informasi dari variabel yang dialokasi, namun tidak dapat mendeteksi kegagalan sebelumnya

Gambar 5.10 Pengecekan untuk Constraint propagation Pada Gambar 5.10 , diketahui NT dan SA berwarna sama yakni biru, padahal NT dan SA tetanggaan, sehingga hal ini tidak diperbolehkan.   

Forward checking hanya mempertimbangkan setiap constraint secara terpisah. Forward checking mem-propagasi (meneruskan) informasi dari variabel yang sudah di-assign ke yang belum. Secara umum, ini disebut constraint propagation. Namun, tidak semua failure bisa di-deteksi secara dini

6.ARC CONSISTENCY 

Arc consistency adalah metode constraint propagation yang lebih canggih. Konsistensi antar constraint dipertahankan.  Arc X Yadalah edge satu arah dari variable X ke Y dalam constraint graph. Prinsip Con Prinsip Arc Consistency X Ydikatakan konsisten jika dan hanya jika untuk setiap nilai sah x dari X ada nilai sah y dari Y.

Page 46 of 98

2012



sistency

Gambar 5.11Langkah penyelesaian untuk Arc Consistency Algoritma AC3 Algoritma AC3 melakukan constraint propagation sbb:  Periksa semua arc dalam constraint graph  Jika untuk X Yada nilai sah x dari X sehingga tidak ada nilai sah y dari Y, buang x.  Jika ada nilai x yang dibuang, periksa ulang semua“tetangga” Xdi dalam constraint graph.  Algoritma AC3 ini bisa mendeteksi failurelebih cepat daripada forward checking.  AC3 dapat dijalankan sebagai pra-proses sebelum melakukan backtracking, atau bisa dijalankan setelah setiap assignment.

Page 47 of 98

2012



Local search untuk CSP          

Dalam praktek, local search cocok untuk CSP. State harus lengkap/complete (semua variable harus ter-assign) tapi boleh melanggar constraint. Operator/action-nya: menukar nilai variabel (reassign). Pemilihan variable: pilih secara acak variable yang melanggar sebuah constraint. Pemilihan nilai: gunakan heuristic minimum conflict: pilih nilai yang melanggar constraint paling sedikit. Lakukan local search (hillclimb, simulated annealing, genetic algorithm, dll.) meminimalkan h(n) = jumlah pelanggaran constraint Perhatian: secara teoritis pendekatan ini tidak dijamin complete.

Contoh : Local search untuk 4 –queen State: 4 queen dalam 4 kolom (44= 256 state) Operator/action: pindahkan menteri dalam kolom Goal test: tidak ada menteri saling makan Evaluation/fitness function: h(n) = jumlah pasangan queen saling makan Bisa menyelesaikan 1000000-queens problem!

Gambar 5.12. Langkah penyelesaian untuk Arc Consistency

Page 48 of 98

2012



2012

Rangkuman  CSP adalah masalah yang bentuknya spesifik:  State berupa assignment nilai terhadap himpunan variabel  Goal test berupa constraint terhadap nilai variabel.  Backtracking: depth-first search mempertimbangkan satu variable di setiap node  Heuristic urutan pemilihan variable dan nilai sangat mempengaruhi kinerja  Forward checking dan arc consistency adalah bentuk constraint propagation yang mendeteksi kegagalan (failure) lebih dini.  Representasi CSP yang spesifik memungkinkan analisis masalah ! penyederhanaan: CSP berbentuk tree bisa diselesaikan dalam waktu linier.  Metode local search untuk CSP (dengan heuristic min-conflicts) dalam praktek cukup efektif.

REFERENSI     



Anonim, Teknik Pencarian Heuristik, http://journal.mercubuana.ac.id/data/Heuristicsearch.pdf, tanggal akses 24 November 2011 Anonim, Costraint Satisfaction Problem, PIB lesson9 CSP, http://sitoba.itmaranatha.org/PIB%200809/eBooks/PIB%20lesson9.pdf, ,tanggal akses 30 Agustus 2012 Anonim, Constraints And Adversarial Search, http://sitoba.itmaranatha.org/PIB%200809/.../PIB0809-07%2009%2010.pp..., tanggal akses 27 Agustus 2012 Lianto, Joko dkk, Penjadwalan matakuliah dengan menggunakan algoritma genetik dan metode constrain satisfaction, teknik informatika, FTI, ITS, openpaper.its.ac.id/download.php/?idf=41, tanggal akses 25 Agustus 2012 Manurung, Ruli , 2007 IKI 30320: Sistem CerdasKuliah 7: Constraint Satisfaction Problems,Fakultas Ilmu Komputer,Universitas Indonesia, www.cs.ui.ac.id/WebKuliah/IKI30320/.../iki30320_20070924_hand..., tanggal akses 15 Maretr 2012 Russel, S., Norvig 1997, Artificial Intelligence: A Modern Approach , Prentice Hall. 2. Firebaugh, M.W.,1998, Artificial Intelligence: A Knowledge-Base Approach, Boyd and Page 49 of 98

Kecerdasan buatan / MateriKuliah    


2012

Frasser Sri Kusumadewi, Artificial Intelligence : Teknik dan Aplikasinya, Graha Ilmu, Yogyakarta, 2003 Suyanto, ST.MSc Artificial Intelligence Searching, Reasoning, Planning dan Learning , informatika Bandung tahun 2007 Yunarsono Muhyi , Penjadwalan kuliah otomatis dengan Constraint Programming, http://muhyi.hostei.com/media/blogs/paper/ARTIKEL_SNASTI_MUHYI_Revisi.pdf, tanggal akses 23 Agustus 2012 Wijaya, Teddy dan Ruli Manurung, Solving University Timetabling As a Constraint Satisfaction Problem with Genetic Algorithm ,http://ejournal.narotama.ac.id/files/Solving%20University%20Timetabling%20As%2 0a%20Constraint%20Satisfaction%20Problem%20with%20Genetic%20Algorithm.pdf, tanggal akses 17 September 2012

PROPAGASI B. Latihan dan Diskusi 1. Gunakan Algoritma Backtracking untuk menyelesaikan kasus 8-puzzle 2.

Gambar 5.13. Isikan bidang pada Gambar 5.13 di atas dengan warna: merah, kuning, hijau, biru. Bidang bertetangga tidak boleh memiliki warna yang sama. 1. Sebutkan variabel yang Anda ! 2. Sebutkandomain yang tersedia! 3. Bagaimana Anda mengevaluasi constraints-nya? Selamat mengerjakan

Page 50 of 98



2012

Kecerdasan Buatan: Logical Agents

Dian Eka Ratnawati, S.Si, M.Kom,Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc,Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya Email : [email protected]

1. PENDAHULUAN 1.1 Pengantar 1.2 Tujuan 2. Agen Berbasis Pengetahuan

3. 4. 5. 6.

Agen Berbasis Logika Logika Proposisi Metode Pembuktian Latihan

1. PENDAHULUAN

Inference engine Knowledge engine

Domain-independent algorithms Domain-specifics content

Page 51 of 98

6 LOGICAL AGENTS

1.1 Pengantar Agen logika merupakan agen yang memiliki kemampuan bernalar secara logika. Ketika beberapa solusi tidak secara eksplisit diketahui, maka diperlukan suatu agen berbasis logika. Logika sebagai Bahasa Representasi Pengetahuan memiliki kemampuan untuk merepresenasikan fakta sedemikian sehingga kesimpulan (fakta baru, jawaban) dapat ditarik, sedangkan pengetahuan merupakan komponen yang penting, sehingga terdapat perbedaan jika diterapkan pada dua agent, yakni problem solving agent dan knowledge-based agent. - Problem solving agent: memilih solusi di antara kemungkinan yang. Apa yang ia “ketahui” tentang dunia tidak berkembang untuk mencapai problem solution (initial state, successor function, goal test) - Knowledge-based agent: lebih “pintar”. Ia “mengetahui” hal-hal tentang dunia dan dapat melakukan reasoning (berpikit, bernalar) mengenai: o Hal-hal yang tidak diketahui sebelumnya (imprefect/ partial information) o Tindakan yang paling baik untuk diambil

MODUL



2012

1.2 Tujuan Penguasaan materi dalam modul ini dirancang agar mahasiswa mampu untuk :  Menjelaskan dan memahami tentang definisi dan konsep dasar agen berbasis pengetahuan  Menjelaskan dan memahami tentang definisi dan konsep dasar agen berbasis logika.  Menjelaskan dan memahami tentang konsep dasar logika proporsisi baik secara sintaks maupun semantik  Menjelaskan dan memahami tentang metode pembuktian dari logika proporsisi

2. Agen Berbasis Pengetahuan (Knowledge-based Agent)    

-

-

-

-

Knowledge Base menyatakan apa yang “diketahui” oleh si agent Pendekatan deklaratif membangun agent: “beritahu” informasi yang relevan, simpan dalam KB  (TELL). Agen dapat ditanya (atau bertanya diri sendiri) apa yang sebaiknya dilakukan berdasarkan KB  (ASK). Maka sebuah agen berbasis pengetahuan harus bisa: o Mereprentasikan world, state, action, dst. o Menerima informasi baru (dan meng-update representasinya) o Menyimpulkan pengetahuan lain yang tidak eksplisit (hidden property) o Menyimpulkan action apa yang perlu diambil Knowledge Base merupakan o Himpunan representasi fakta yang diketahui tentang lingkungannya o Tiap fakta disebut sentence o Dinyatakan dalam bahasa formal sehingga bisa diolah o TELL: menambahkan sentence baru ke KB Inference Engine merupakan: o Menentukan fakta baru yang dapat diturunkan dari pengetahun yang sudah ada dalam KB o Menjawab pertanyaan (ASK) berdasarkan KB yang sudah ada. Dalam representasi, agent dapat dipandang dari knowledge level: informasi apa yang diketahui? Misal: sebuah robot “mengetahui” bahwa gedung B di antara gedung A dan gedung C Agent dapat dipandang dari implementation level: bagaimana representasi informas yang diketahuinya? o Logical sentence: di_antara(gdB, gdA, gdC) o Natural language: “Gedung B ada di antara gedung A dan gedung C” o Tabel posisi koordinat gedung-gedung o Gambar diagram peta (dalam bitmap atau vektor?) Pilihan representasi berpengaruh terhadap apa yang bisa dilakukan inference engine Pada pendekatan deklaratif programmer memberitahu (TELL) agent informasi tentang environment. Kalau informasi kurang, agen bisa melengkapinya sendiri. Jika dibandingkan dengan pendekatan prosedural: programmer secara eksplisit memrogram agen untuk bertindak. Sehingga bagaimana jika program tidak benar, maka akan besar kemungkinan menyebabkan kesalahan Page 52 of 98

Kecerdasan buatan / MateriKuliah -

-


2012

Permasalahannya adalah bagaimana representasi yang tepat, sehingga ada dua hal yang harus memperhatikan dua hal: o Expressive: bisa menyatakan fakta tentang environment o Tractable: bisa diolah/ diproses inference engine (dengan cepat?) Knowledge merupakan kekuatan dari pemrograman secara deklaratif. Representasi dan penalaran membentuk suatu Intelligence.

Contoh Aturan Permainan dalam Wumpus World -

-

Performance measure: emas +1000, mati -1000, gerak -1, panah -10 Environment: Matriks 4x4 ruang dengan initial state [1,1]. Ada gold, wumpus, dan pit yang lokasinya dipilih secara acak. Percept terdiri dari: o Breeze: kamar di samping lubang jebakan ada hembusan angin o Glitter: kamar di mana ada emas ada kilauan/ sinar. o Smell: kamar di samping Wumpus berbau busuk Action: maju, belok kiri 900,belok kanan 900, tembak panah (hanya 1!), ambil benda

Sifat dari Wumpus World: -

Fully observable? Tidak, hanya bisa berpresepsi lokal Deterministic? Ya, hasil tindakan jelas dan pasti Episodic? Tidak, tergantung action sequence Static? Ya, gold, wumpus, pit tidak bergerak Discrete? Ya Single agent? Ya

Bahasa Representasi Pengetahuan (Knowledge Representation Language) Menyatakan suatu bahasa yang digunakan untuk menyatakan fakta tentang “dunia”. Suatu bahasa representasi pengetahuan didefinisikan dalam dua aspek, yakni: 1. Sintaks dari bahasa merupakan aturan yang mendefinisikan sentence yang sah dalam bahasa 2. Semantik menyatakan aturan yang mendefinisikan “arti” sebuah sentence, misalkan: kebenaran sentence dalam dunia ContohKRL dalam bahasa aritmetika Page 53 of 98



2012

Secara Sintaks dituliskan: x + 2 ≥ y adalah kalimat sah. x2 + y ≥ bukan kalimat sah. Secara semantik: x + 2 ≥ y benar jika dan hanya jika bilangan x + 2 tidak lebih kecil dari bilangan y: - x + 2 ≥ y benar dalam “dunia” di mana x=7, y=1 - x + 2 ≥ y benar dalam “dunia” di mana x=0, y=6 Contoh KRL dalam bahasa Indonesia Secara sintaks dituliskan: -

“Jakarta adalah ibukota Indonesia” adalah kalimat sah. “Ibu Indonesia kota Jakarta adalah” bukan kalimat sah.

Maka secara Semantik: “X adalah ibukota Y” benar jika dan hanya jika adalah pusat pemerintahan negara Y. - “Jakarta adalah ibukota Indonesia” benar dalam “dunia” kita sekarang. - “Jakarta adalah ibukota Indonesia” salah dalam “dunia” tahun 1948 (Yogya? Bukitinggi?)

3. Agen Berbasis Logika Logika sebagai Bahasa Representasi Pengetahuan memiliki pengertian: - Logika sebagai bahasa formal untuk merepresenasikan fakta sedemikian sehingga kesimpulan (fakta baru, jawaban) dapat ditarik. - Ada banyak metode inference yang diketahui. - Sehingga kita bisa membangun agent Wumpus World dengan logika: memanfaatkan perkembangan logika oleh ahli matematika, filsafat selama ratusan tahun! Entailmentdapat diartikan sebagai suatu fakta bisa disimpulkan dari (kumpulan) fakta lain. - KB |= α berarti KB melakukan entailment sentence α jika dan hanya jikaa α true dalam “dunia” di mana KB true. Contoh: - KB mengandung dua sentence, yakni “ Anto ganteng” dan “Ani cantik”. - KB |= α1: “Anto ganteng dan Ani cantik” (artinya: hasil entailment bisa berupa kalimat gabungan dari dua kalimat) - KB |≠ α2 : “Anto pintar” - x + y = 4 =| 4= x+y Inferensiatau reasoning merupakan pembentukan fakta (sentence) baru yang meng-entail fakta-fakta lama. Reasoning bukan dilakukan pada fakta di dunia (berdasarkan semantik), melainkan representasi fakta dalam bahasa representasi pengetahuan si agent (secara sintaks) Otak manusia melakukan proses reasoning dalam suatu bentuk sintak dapat diilustrasikan sebagaimana gambar berikut:

Page 54 of 98


-


2012

Model merupakan suatu “dunia” di mana kebenaran suatu sentence bisa diuji. m adalah model α jika dan hanya jika true di “dalam” m. M(α) adalah himpunan semua model dari α. KB |= α jika dan hanya jika M(KB) subset dari M(α), sehingga bisa dilihat pada ilustrasi gambar berikut:

Misalkan: -

KB= Anto ganteng dan Ani cantik α = Anto ganteng Hal ini bisa diartikan bahwasanya sentence Anto ganteng lebih luas konotasinya dibandingkan dengan sentence Anto ganteng dan Ani cantik

Entailment dalam Wumpus World bisa diilustrasikan sebagaimana berikut, dengan melihan [1,1] OK, [2,1] Breeze:

Maka model jebakan ada 3 pilihan boolean di [2,1],[2,2],[3,1], dengan 8 kemungkinan model

Page 55 of 98



2012

KB = pengamatan (percept) + aturan main Wumpus World, maka kita menyatakan apakah kamar [1,2] aman dengan cara melakukan entailment yang mana dibuktikan dengan menggunakan model checking, yakni memeriksa semua kemungkinan M(KB), M(α1).

Sehingga dari ilustrasi tersebut diatas menunjukkan bahwasannya: M(KB) subset dari M(α1), sehingga bisa disimpulkan bahwa kamar [1,2] aman. Lain halnya ketika melakukan pengamatan apakah kamar [2,2] aman, dengan ditunjukkan oleh α2., sehingga terlihat sebagaimana ilustrasi berikut:

Dari gambar tersebut menunjukkan bahwasannya M(KB) bukan subset dari M(α2), sehingga bisa disimpulkan bahwa KB |≠ α2, dengan kata lain kamar [2,2] tidak aman. Inferensi merupakan proses atau algoritma yang “menurunkan” fakta baru dari fakta-fakta lama. -

KB|- iα: sentence α bisa diturunkan dari KB oleh prosedur i Soundness: idikatakan sound jika untuk semua KB |- i α, KB |= α benar Completeness: i dikatakan complete jika untuk semua KB |= α, KB |- i α benar

Logika Proposisi Merupakan logika yang paling sederhana. Sebuah sentence dinyatakan sebagai simbol proposional P1, P2, dst. Sintaks dari logika proposisi - Jika S adalah kalimat, ⌐S adalah kalimat (negasi) - Jika S1 dan S2 adalah kalimat S1Ʌ S2 adalah kalimat (conjunction) - Jika S1 dan S2 adalah kalimat S1 V S2 adalah kalimat (disjunction) - Jika Jika S1 dan S2 adalah kalimat S1→ S2 adalah kalimat (implication) Page 56 of 98



2012

- Jika S1 dan S2 adalah kalimat S1↔ S2 adalah kalimat (biconditional) Semantik dari logika proposisi - Sebuah model memberi nilai true/ false terhadap setiap proposisi, misal P1,2 = true, P2,2=true, P3.1=false - Sebuah proses rekursif bisa mengevaluasi kalimat sembarang: ⌐P1,2 Ʌ (P2,2 V P3,1) = true Ʌ (false V true) = true Ʌ true = true - Maka kalimat yang digunakan untuk merepresentasikan Wumpus World o Secara semantik:  Pi,j = true menyatakan kalau ada lubang jebakan (pit) di [i, j].  Bi,j = true menyatakan kalau ada hembusan angin (breeze) o Aturan main dalam Wumpus World: kamar di samping lubang jebakan ada hembusan angin:  B1,1↔ (P1,2 V P2,1)  B2,1↔ (P1,2 V P2,2 V P3,1) o Hasil pengamatan (percept):  ⌐P1,1  ⌐ B1,1  B2,1 - Inferensi bisa juga dilakukan dengan menggunakan tabel kebenaran dalam rangka untuk membuktikan terhadap entailment dari suatu knowledge. Sehingga kita dapat membuktikan apakah KB |= α1 menggunakan tabel kebenaran (sejenis model checking), di mana α1menyatakan kamar di [1, 2] aman sebagaimana tabel di bawah ini.

Metode Pembuktian Secara umum, ada dua jenis metode pembuktian: - Pengaplikasian inference rule o Dihasilkan kalimat baru yang sah (sound) dari yang lama o Bukti(proof) merupakan serangkaian pengaaplikasian inference rule (operator ) dari algoritma search o Biasanya, kalimat harus diterjemahkan ke dalam sebuah normal form -

-

-

Model o o o

checking Penjabaran truth table (sehingga dihasilkan nilai eksponensial dalam n) Backtracking lebih efisien, misalkan: algoritma DPLL Heuristic search dalam model space (sound tetapi incomplete), misalkan : minconflicts hill –climbing Horn Form o Dalam Horn form, KB merupakan conjuction dari Horn Clauses o Horn Clause terdiri:  Proposition symbol  (Conjuction of symbol)  symbol Misalkan: Page 57 of 98



2012

-

Modus ponen pada Horn form (yang mana lengkap pada Horn KB):

-

Horn form bisa digunakan dengan algoritma forward chaining atau backward chaining Konsep dasar dari algoritma forward chaining adalah aplikasikan rule yang premise-nya diketahui benar dalam KB, kemudian tambahkan conclusionnya ke dalam KB, ulangi sampai query (Q) terbukti. Sehingga bisa dikatakan kinerja dari forward chaining merupakan metoda bottom up dari fakta menuju konklusi Misal:

Sedangkan konsep dasar dari algoritma backward chaining digunakan untuk membuktikan query q, dengan cara memeriksa q jika sudah diketahui, atau secara rekursif, dengan membuktikan semua premise rule yang conclusion-nya q (dikenal sebagai metode top down) Dalam backward chaining ada beberapa hal yang perlu diketahui: o Menghindari loop: dengan cara memeriksa apakah subgoal yang baru sudah ada di goal stack o Menghindariperulangan pekerjaan: periksa apakah subgoal yang baru sudah dibuktikan benar atau sudah dibuktikan salah. Perbandingan antara Forward dan backward chaining o Forward chaining adalah pendekatan data-driven, bottom up sehingga pemrosesan informasi secara tak sadar o Melakukan banyak usaha yang tidak relevan terhadap goal o Backward chainingadalah pendekatan goal-driven, top-down sehingga pemrosesan inforasi secara sadar o Kompleksitas BC bisa jauh lebih kecil dari dalam linear ukuran KB

-

-

-

Kesimpulan - Agen berbasis pengetahuan menggunakan inferensi dan knowledge base untuk menghasilkan informasi baru atau untuk mengambil keputusan - Konsep-konsep dasar logika sebagai knowledge representation language meliputi: o Sintak: struktur kalimat bahasa formal o Semantik: arti kalimat sebagai kebenaran terhadao model o Entailment: menyimpulkan kalimat baru yang benar o Inferensi: proses menurunkan kalimat baru dari kalimat-kalimat lama o Soundness: proses menurunkan hanya kalimat yang di-entail o Completeness: pross menurunkan SEMUA kalimat yang di-entail - Forward, backward chaining merupakan proses inferensi complete dan linear untuk Horn form

REFERENSI o

Russell, Stuart; dan Norvig, Peter. 2003. Artificial Intelligence A Modern Approach. International Edition, Edisi 2. Pearson Prentice-Hall Education International. New Jersey Page 58 of 98



2012

Kumpulan Slide Kuliah Kecerdasan Buatan disusun oleh dosen Fakultas Ilmu Komputer, Universitas Indonesia

PROPAGASI C. Latihan dan Diskusi 1. Jelaskan konsep dasar dari agen berbasis pengetahuan dan hal-hal apa saja yang harus dipenuhi ketika membuat agen tersebut 2. Berilah contoh kasus entailment dari permainan Wumpus World berdasarkan aturan yang diberikan 3. Dari soal nomor 2, tunjukkan dengan metoda pembuktian baik model checking ataupun menggunakan tabel kebenaran

D. Pertanyaan (Evaluasi mandiri) Buatlah sebuah agen berbasis logika dengan menerapkan pula proses inferensi dengan cara entailment yang kemudian dibuktikan dengan model checking dan tabel kebenaran.

Page 59 of 98



2012

First Order Logic Dian E.R, M.Kom; Dewiyanti L, M.Kom; Laili M, M.Sc; Rekyan RMP, MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya Email : [email protected]

1.PENDAHULUAN 1.1.Pengantar 1.2.Tujuan 1.3.Definisi

2.3 Semantik 2.4 Quantifier 2.5 Equality 2.6 Inferensi pada First Order Logic

1. FIRST ORDER LOGIC 2.1 Definisi First Order Logic 2.2 Sintaks First Order Logic

2. CONTOH 3. PROPAGASI 4.1 Pertanyaan/Latihan Soal 4.2 Diskusi 4.3 Project

1. P E N D A

HULUAN 1.1 Pengantar Dalam sistem kecerdasan buatan untuk menyelesaikan permasalahan ada beberapa metode yang dapat digunakan. Dalam menggunakan metode tersebut harus disesuaikan karena masing-masing metode memiliki spesifikasi tersendiri. Salah satu metode adalah Reasoning (penalaran). Reasoning adalah teknik penyelesaian masalah dengan cara merepresentasikan masalah ke dalam basis pengetahuan (knowledge base) menggunakan logic yang dapat dipahami oleh komputer. FOL (First Order Logic) merupakan penyempurnaan dari Propositional Logic yang ada pada bab sebelumnya yang merupakan jenis reasoning untuk permasalahan sederhana, sedangkan first order logic digunakan untuk permasalahan yang lebih kompleks. Pada bab ini akan dijelaskan bagaimana first order logic dapat merepresentasikan pengetahuan lebih efisien pada permasalahan kompleks beserta contoh permasalahan. 1.2 Tujuan Setelah mempelajari Pokok Bahasan ini, diharapkan mahasiswa akan : 1. Memahami konsep first order logic 2. Bisa memahami komponen-komponen yang ada pada first order logic 3. Menerapkan first order logic pada pemecahan masalah 4. Memiliki sikap disiplin dalam mengumpulkan tugas

1.3 Definisi Page 60 of 98

MODUL

7

Kecerdasan buatan / MateriKuliah 


2012

Objects : merupakan sesuatu yang dikenai logika-logika yang memiliki identitas untuk masing-masing individual (komputer, rumah, mobil, ...). Properties : sifat yang dimiliki oleh objek dan merupakan pembeda dengan objek lainnya (merah, besar, lingkaran, ...). Relations : aksi atau aktifitas yang menjadi penghubung antar objek dalam berelasi (saudara dari, lebih tinggi dari, bagian dari). Functions : merupakan relation yang memiliki satu nilai (ayah dari, teman baik,...).

  

2. FIRST ORDER LOGIC 2.1 Definisi First Order Logic Proses reasoning untuk menyelesaikan masalah dengan merepresentasikan masalah kedalam logic sudah dilakukan oleh propositional logic. Propositional logic dalam menyelesaikan permasalahan dengan menggunakan fakta-fakta yang diproses menggunakan logika-logika sederhana saja. Sedangkan pada first order logic permasalahan diselesaikan dengan sentence yang merepresentasikan fakta dan term yang merepresentasikan objek. Komponen-komponen penting yang ada pada first order logic yaitu : Objects : merupakan sesuatu yang dikenai logika-logika yang memiliki identitas untuk masing-masing individual (komputer, rumah, mobil, ...). 

Properties : sifat yang dimiliki oleh objek dan merupakan pembeda dengan objek lainnya (merah, besar, lingkaran, ...).  Relations : aksi atau aktifitas yang menjadi penghubung antar objek dalam berelasi (saudara dari, lebih tinggi dari, bagian dari).  Functions : merupakan relation yang memiliki satu nilai (ayah dari, teman baik,...). Komponen-komponen yang sudah dijelaskan diatas disebut sebagai ontological commitment atau hal-hal apa saja yang diketahui dan dijelaskan di dalam logic yang digunakan dalam menyelesaikan permasalahan. Selanjutnya akan ditunjukkan beberapa jenis logic lain yang memiliki ontological commitment dan epistemological commitment (kebenaran apa yang dapat dinyatakan tentang sebuah sentence). Contoh beberapa logic lain adalah sebagai berikut :

Logic Propositiona l logic First-order logic Temporal logic Probability theory Fuzzy logic

Ontological Facts Facts, objects, relations Facts, objects, relations, times Facts Degree of truth

Page 61 of 98

Epistemolog ical True/false/unk nown True/false/unk nown True/false/unk nown Degree of believe 0…1 Degree of believe 0…1



2012

Elemen-elemen dasar terkecil yang dimiliki oleh first order logic adalah sebagai berikut : 

Constants Dituliskan dalam huruf besar seperti A, X, NAMA. Pada simbol konstanta ini, setiap simbol harus menyatakan secara spesifik objek yang dimaksud. Tetapi, mungkin saja satu simbol mengacu pada beberapa nama berbeda. Misalnya, MOBIL bisa mengacu pada MOBIL SEDAN, MOBIL JEEP, dan sebagainya. Oleh karena itu penulisan simbol konstanta harus dilakukan secara hati-hati agar tidak terjadi kerancuan atau ambiguitas.



Predicates Menyatakan relasi khusus dalam suatu model yang menghubungkan antar objek yang memiliki hubungan. Misalkan Berwarna adalah suatu predicate yang memiliki beberapa nilai. Contoh : Berwarna(Mobil, Biru), Berwarna(Mobil, Merah), dan sebagainya.



Functions Menyatakan relasi yang hanya membutuhkan satu nilai. Karena setiap orang hanya memiliki satu ayah, maka Ayah merupakan suatu function. Misalkan Ayah(Boediono, Zaki).



Variables Dituliskan dalam huruf kecil seperti a, x, s dan sebagainya. Variable ini menyatakan simbol yang dapat digantikan oleh konstanta apapun dan bersifat dinamis.



Connectives Merupakan logika yang menghubungkan di dalam suatu kalimat kompleks seperti : ∧∨ ¬ ⇒⇔ 

Equality Merupakan logika yang membandingkan kesamaan antara dua atau lebih kalimat yang memiliki kesamaan nilai logika. Equality disimbolkan dengan tanda = 

Quantifiers Terdapat dua quantifier secara umum yaitu Universal quantifier (∀) yang menyatakan sesuatu yang bersifat umumdan Existential quantifier (∃) yang menyatakan sesuatu yang berlaku sebagian saja.

2.2 Sintaks First Order Logic Tata bahasa pada first order logic meliputi : 

Terms Merupakan ekspresi logika yang mengacu pada sebuah objek. Terms bisa berupa constant, variable, atau function. Penulisan term dapat dilihat pada contoh di bawah ini :

Page 62 of 98



2012

Terms function(term1,....,termn) atau constant atau variable 

Atomic sentences Merupakan komponen yang dapat terbentuk dari Predicate(Term, ...) atau Term=Term. Atomic sentence merupakan kalimat paling sederhana dan belum memiliki komponen logika lainnya. Bentuk penulisan atomic sentences adalah sebagai berikut : Atomic sentences predicate(term1,....,termn) atau term1 = term2

Contoh penggunaan adalah sebagai berikut : Sepatu(Budi), Saudara(Ahmad, Anton), Saudara(Andi)=Budi, dan sebagainya. 

Memberi(Andi,Budi,KueCoklat),

Complex sentences Merupakan kalimat kompleks yang tersusun dari beberapa atomic sentence yang saling terhubung berdasarkan logika dengan menggunakan connective. Bentuk penulisan dari complex sentences adalah sebagai berikut : Complex sentences predicate1(term1,term2) ⇒ perdicate2(term3)

Contoh penggunaan dari complex sentence adalah sebagai berikut:      

Belajar(Andi)⇒ Pintar(Andi) ¬S, S1 ∧ S2, S1 ∨ S2, S1 ⇒ S2, S1 ⇔ S2 Saudara(Ahmad,Andi)⇒Saudara(Andi,Ahmad) >(1, 2) ∨ ≤(1, 2) >(1, 2) ∧ ¬>(1, 2) Belajar(x, SC) ⇒ Mengerti(x, AI)

2.3 Semantik First Order Logic Pada first order logic sama halnya dengan propositional logic sebuah kalimat first order logic dikatakan true terhadap sebuah model, artinya kalimat first order logic memiliki nilai kebenaran tertentu sehingga dianggap true atau false. Satu kalimat dalam first order logic dapat diinterpretasikan banyak cara dalam sebuah model. Model dalam first Page 63 of 98



2012

order logic terdiri dari :  

Objects : elemen-elemen yang nyata ada pada permasalahan (domain elements) Relations : hubungan antara elemen-elemen / objek-objek tertentu

Sebuah interpretasi mendefinisikan referent (yang dipetakan) sebagai berikut :  Constant symbols : objects  Predicate symbols : relations  Functions symbols : functional relations Kalimat first order logic memiliki maksud kalimat atomik predicate(term1,...,term2) dikatakan bernilai true dalam model m di bawah unterpretasi i jika dan hanya jika object yang di-refer (term1, ... , term2) di bawah i terhubung oleh relation yang di refer oleh predicate dalam m. Ilustrasi pada gambar disamping menggambarkan komponen-komponen yang ada pada first order logic. Pada ilustrasi digambarkan bahwa terdapat orang dan raja. Hubungan keduanya adalah sebagai saudara satu dengan lainnya. Dari gambar tersebut dapat dilihat masing-masing komponen adalah sebagai berikut :



object Ilustrasi menggambarkan ada seorang raja dan orang biasa, dapat kita ambil contoh objek yang ada adalah orang, raja, kaki raja dan kaki orang. Objek memiliki identitas tertentu yang nantinya akan melalui proses logika.



function function merupakan hubungan yang hanya membutuhkan satu nilai untuk satu objek, contoh pada ilustrasi adalah kaki digunakan oleh orang untuk berjalan.



relation menyatakan hubungan antar objek yang memiliki relasi tertentu, pada gambar ilustrasi terdapat relasi saudara antara orang dan raja.

2.4 Quantifiers 

Universal quantifiers Page 64 of 98



2012

Universal menyatakan logika yang digunakan untuk menunjuk sesuatu yang bersifat umum. Simbol ∀ yang memiliki makna "untuk semua atau setiap" atau "for all" terhadap sebuah variabel x yang disimbolkan dengan ∀x berarti bahwa kalimat tersebut berlaku untuk setiap objek x. Contoh permasalahan pada first order logic yang menggunakan Universal Quantifiers adalah sebagai berikut : Misalkan ada kalimat "Ikhsan adalah anak kecil", kalimat ini akan dinyatakan sebagai AnakKecil(Ikhsan), dan ada kalimat "Andi suka permen" dinyatakan sebagai Suka(Andi,Permen). Jika kita ingin membuat kalimat "Untuk setiap objek x, jika x adalah anak kecil maka x suka permen". Maka kalimat dapat kita tuliskan pada bentuk first order logic sebagai: ∀x AnakKecil(x)⇒Suka(x,Permen) kalimat tersebut akan bernilai benar jika dan hanya jika semua kalimat di bawah ini benar. AnakKecil(Budi) ⇒Suka(Budi,Permen)∧ AnakKecil(Rahmad)⇒Suka(Rahmad,Permen)∧ AnakKecil(Anton) ⇒Suka(Anton,Permen)∧ Hal-hal yang harus dihindari pada penggunaan Quantifier Universal adalah penggunaan logika ∧ pada kalimat utama karena akan menimbulkan pengertian yang ambigu.  Existential quantifiers Existential menyatakan logika yang digunakan untuk menunjuk sesuatu yang bersifat khusus. Artinya hanya beberapa bagian atau sebagian saja dari keseluruhan himpunan. Logika ini merupakan kebalikan dari logika Universal. Logika ini disimbolkan dengan ∃ yang memiliki makna "There Exist" atau (ada satu atau beberapa). Kita dapat menyatakan kalimat "Ada objek x, jika x adalah anak kecil maka x suka permen" menjadi first order logic sebagai berikut: ∃x AnakKecil(x) ∧ SukaPermen(x). Hal-hal yang harus dihindari pada penggunaan Quantifier Universal adalah penggunaan logika⇒pada kalimat utama karena akan menimbulkan pengertian yang ambigu. 2.5Equality Equality merupakan pembandingan terhadap dua kalimat atau term yang memiliki nilai logika true atau false. Kedua kalimat dianggap sama jika memiliki nilai logika yang sama. Term1 =Term2 akan diinterpretasikan benar jika dan hanya jika memiliki nilai yang sama. Contoh bentuk dari equality adalah sebagai berikut :

Equality x,ySaudara(x,y)  [(x = y) m,f  (m = f)OrangTua(m,x)OrangTua(f,x)OrangTua (m,y) OrangTua (f,y)]

Page 65 of 98



2012

2.6 Inferensi pada First Order Logic Proses Inferensi pada First Order Logic menggunakan 7 aturan inferensi yang digunakan pada Propositional Logic, dengan ditambah aturan yang lebih kompleks sehubungan dengan quantifiers, sebagai berikut : 1. Inference Rules Involving Quantifiers SUBST(,): untuk menotasikan hasil dari pengaplikasian operasi subsitusi  terhadap sentence . SUBST({x/Andi, y/Budi}, Saudara(x,y)) = Saudara(Andi, Budi). 2. Universal Elimination: untuk setiap sentence , variabel v, dan ground term (term yang tidak berisi variabel) g :

v  SUBST ({v / g}, ) Dari x Suka(x, Membaca), dapat digunakan substitusi {x/Andi} dan melakukan inferensi bahwa Suka(Andi, Membaca) 3. Existential Elimination: untuk setiap sentence , variabel v, dan simbol konstanta k yang tidak tampak dimanapun di dalam basis pengetahuan:

v  SUBST ({v / k}, ) Dari x Membunuh(x, Korban), kita dapat menyimpulkan Membunuh{Penjahat, Korban}, selama Penjahat tidak tidak tampak dimanapun di dalam basis pengetahuan. 4. Existential Introduction: untuk setiap sentence , variabel v yang tidak terjadi pada , dan ground term g yang terjadi pada :

 v SUBST ({g / v}, ) Dari Suka(Budi, Membaca) kita dapat menyimpulkan xSuka(x, Membaca).

3. CONTOH terdapat pernyataan-pernyataan sebagai berikut : – Andi adalah seorang mahasiswa – Andi masuk Jurusan elektro – Setiap mahasiswa elektro pasti mahasiswa Teknik – Kalkulus adalah matakuliah yang sulit – Setiap mahasiswa Teknik pasti akan suka kalkulus atau akan membencinya – Setiap mahasiswa pasti akan suka terhadap suatu matakuliah – Mahasiswa yang tidak pernah hadir pada kuliah matakuliah sulit, maka mereka pasti tidak suka terhadap matakuliah tersebut. Page 66 of 98



– Andi tidak pernah hadir kuliah matakuliah kalkulus. • Kedelapan pernyataan di atas dapat dibawa ke bentuk logika predikat : 1. 2. 3. 4. 5. 6. 7. 8.

mahasiswa(Andi) Elektro(Andi) ∀x: Elektro(x) ->Teknik(x) sulit(Kalkulus) ∀x: Teknik(x) ->suka(x, Kalkulus) ∨benci(x, Kalkulus) ∀x:∃y : suka(x,y) ∀x: ∀y: mahasiswa(x) ∧sulit(y) ∧~hadir(x,y) ->~suka(x,y) ~hadir(Andi, Kalkulus)

• Kemudian dibuat dalam bentuk klausa : 1. mahasiswa(Andi) 2. Elektro(Andi) 3. ~Elektro(x1) ∨Teknik(x1) 4. sulit(Kalkulus) 5. ~Teknik(x2) ∨suka(x2, Kalkulus) ∨benci(x2, Kalkulus) 6. suka(x3,f1(x3)) 7. ~mahasiswa(x4) ∨~sulit(y1) ∨hadir(x4,y1) ∨~suka(x4,y1) 8. ~hadir(Andi,Kalkulus) • Akan dibuktikan apakah “Andi benci kalkulus” atau dapat ditulis : benci(Andi,Kalkulus) Pohon resolusi pada first order logic (logika predikat 1) untuk contohdi atas adalah :

Page 67 of 98

2012



2012

4. PROPAGASI a.

Pertanyaan / Latihan Soal (Evaluasi Mandiri) 1. Bagaimana semantik pada first order logic ? 2. Apa perbedaan inferensi (resolusi) pada logika proposisi dan logika predikat (first order logic) ? Jelaskan !

b.

Latihan Soal Pengembangan dan Diskusi 1. Representasikan permainan “Dunia Wumpus” dengan menggunakan first order logic ! 2. Dika adalah adik bungsu dari Dede. Dede menikah dengan astuti, dan dari pernikahan mereka lahir anak perempuan bernama Anin. Anin hendak menikah dengan Dika. Buktikan bahwa pernikahan Anin dan Dika tidak sah, dengan representasi first order logic!

c.

PROYEK (Eksplorasi entrepreneurship, penerapan topic bahasan pada dunia nyata) Kembangkan sebuah game dengan representasi first order logic, berkelompok @ 3 orang

REFERENSI    

Russel &Artificial Intelligence : A Modern Approach (2nd ed.) by Russel & Norvig Suyanto, ST., MT., Artificial Intelligent : searching, reasoning, planning and learning Sri Kusumadewi, Artificial Intelligence : Teknik dan Aplikasinya, Graha Ilmu, Yogyakarta, 2003 Giarrantano, J and G.Riley, Expert System : Principle and Programming,4thed, PWS Kent, 2004

Page 68 of 98



2012

Kecerdasan Buatan: LOGIC PROGRAMMING Dian Eka Ratnawati, S.Si, M.Kom,Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc,Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya Email:[email protected]

1. PENDAHULUAN 1.1 Pengantar 1.2 Tujuan 2. Paradigma Pemrograman

3. Logic Programming pada Prolog 4. Aplikasi Logic Programming 5. Latihan

1. PENDAHULUAN

1.2 Tujuan Penguasaan materi dalam modul ini dirancang agar mahasiswa mampu untuk :  Menjelaskan dan memahami tentang konsep dari berbagai paradigma pemrograman  Menjelaskan dan memahami tentang konsep dari pemrograman berbasis logika  Mampu merancang dan mengaplikasikan program berbasis logika dari kasus sederhana.  Menjelaskan dan memahami beberapa aplikasi dari pemrograman logika

2. Paradigma Pemrograman Paradigma pemrograman merupakan suatu pola yang menyajikan suatuacuan berpikirterhadap pemrograman komputer. Terdapat empat paradigma pemrograman utama: o Paradigma imperative o Obyek oriented paradigma o Paradigma fungsional o Paradigma logika

Page 69 of 98

8 LOGIC PROGRAMMING

1.1 Pengantar Logic Programming merupakan paradigma pemrograman deklaratif yang menekankan atas apa yang program lakukan daripada bagaimana dia akan melakukan. Ketika diterapkan logic programming digunakan suatu bahasa logika untuk menspesifikasi permasalahan dan kemudian menggunakan suatu prosedur pembuktian untuk melakukan komputasi.

MODUL



2012

Paradigma Imperatif - Komputasi sebagai suatu urutan aksi “ pertama melakukan ini dan berikutya melakukan itu” - Penekanan pada bagaimana daripada apa yang dikomputasi o Ketika memecahkan suatu permasalahan, menempatkan pada metoda daripada arti dari permasalahan - Contoh: bahasa pemrograman Pascal, C, … Paradigma Object Oriented - Data beserta operasi-operasinya dibungkus dalam obyek - Objek terhubung dengan cara melewatkan pesan - Objek-objek dikelompokkan dalam kelas-kelas o Mengijinkan pemrograman atas kelas-kelas (berkebalikan atas pemrograman objek secara individu) - Contoh: bahasa pemrograman C++, Java,… Paradigma Fungsional - Berasal dari matematika murni, dengan disiplin ilmu: teori fungsi o Komputasi didasarkan atas fungsi o Fungsi memiliki status yang sama dengan yang lainnya (angka-angka, list)  Fungsi merupakan nilai kelas utama  Misalkan: Haskell, LISP,... Paradigma Logika - Mendasarkan pada matematika logika - Secara khusus keterkaitan diantara nilai-nilai data - Menggunakan fakta dan aturan-aturan untuk mendefinisikan dasar pengetahuan - Mengajukan pertanyaan terhadap lingkungannya.

3. Logic Programming in Prolog Sejarah singkat - Pemrograman Logika diperkenakan oleh Robert Kowalski pada tahun 1974 - Algoritma tersusun atas Logika dan kontrol Prolog - Merupakan pemrograman dalam logika - Bahasa pemrograman yang menggunakan pemrograman logika untk komputasi - Diperkenalkan oleh Alain Colmerauer pada tahun 1970 an - Imprementasi Prolog yang digunakan SWI Prolog versi 5.6.32 - Bebas melakukan download di URL: http://www.swi-prolog.org/ - Dikembangkan oleh Jan Wielenmaker, Universitas Amsterdam - Ada berbagai implementasi lain seperti: SICStus Prolog, XSB, dsb.) - Contoh 1 dari Paradigma Pemrograman Logika o Menyiapkan database untuk koneksi penerbangan  Adakah suatu penerbangan langsung dari A ke B?  Dapatkah saya terbang dari C ke D?  Tujuan apa saja yang mungkin dapat saya capai dari E?  dst. o Daftar penerbangan langsung direct(jakarta,denpasar). direct(jakarta,surabaya). direct(denpasar,mataram). direct(mataram,kupang).

Page 70 of 98



2012

Untuk menemukan koneksi diantara dua kota:  Ada suatu koneksi dari X ke Y, jika ada suatu penerbangan langsung dari X ke Y, sehingga diberikan aturan sebagai berikut: direct(X, Y)  connecton(X, Y). Dalam bahasa prolog: connection(X,Y):- direct( X,Y) 

Ada suatu koneksi dari X ke Y, jika ada suatu penerbangan langsung dari X ke Z dan suatu koneksi dari Z ke Y. direct(X,Z),connection(Z,Y)connection(X,Y). Dalam bahasa prolog: connection(X,Y):-direct(X,Z),connection(Z,Y)



Untuk menjawab pertanyaan-pertanyaan sebelumnya: o Tuliskan program yang berisikan database sebagai knowledge based-nya. o Jalankan program dengan query yang berhubungan dengan pertanyaan



Q1: apakah ada suatu penerbangan dari Jakarta ke Kupang? ?- connection(jakarta,kupang). Q2: Ke manakah seseorang dapat terbang dari Denpasar? ?- connection(denpasar,X). Q3: Dapatkah seseorang terbang dari Kupang? ?- connection(kupang,X). Q4: Dari manakah seseorang dapat terbang ke Kupang? ?- connection(X,kupang).

  

o

Dua aspek dari Prolog  Dengan program yang sama dapat digunakan untuk menjawab permasalahan (query) yang berbeda  Program dapat digunakan seperti kebanyakan suatu database  Pengetahuan disimpan dalam bentuk fakta dan aturan  Prolog memodelkan pemrosesan query dalam database deduktif

o

Paradigma Pemrograman Logika – Contoh 2  Temukan seluruh elemen yang beranggotakan dua list yang diberikan  List: [a1, a2, ..., an] atau [a1 | [a2..., an]]  a1 disebut dengan head dari [a1, a2, ..., an]  [a2, ..., an] disebut tail dari [a1, a2, ..., an]  Contoh: [1,2,3,4,5=[1|[2,3,4,5]]  X merupakan suatu member dari keduanya L1 dan L2 jika X adalah member dari L1 dan X adalah member dari L2. member_both (X,L1,L2)  member(X,L1), member(X,L2). 

Kita memerlukan mendefinisikan pada saat X merupakan member dari suatu list.  Jika X adalah sebagai head-nya, maka jawabannya positif (benar) member(X,[X|List]).  Sebaliknya, lakukan pengecekan apakah X adalah member dari tail. member(X,[Y|List])  member(X,List). Page 71 of 98





Maka dalam bahasa Prolog bisa dituliskan terurut sebagaimana berikut: member(X|[X|List]). member(X,[Y|List]):-member(X,List). member_both(X,L1,L2):-member(X,L1),member(X,L2).



Kemudian jalankan program untuk memecahkan permasalahan ?-member_both(X,[1,2,3],[2,3,4,5]).



Bagaimana kita memecahkan permasalahan ini dengan tipe pemrograman imperative ? (misalkan bahasa C)

2012

#define SIZE1 3 #define SIZE2 4 void memberBoth(int a[],int b[],int c[]) { int i, j; int k=0; for (i=0;i<SIZE1;i++) { for (j=0;j<SIZE2;j++) { if (a[i] == b[j]) { c[k] = a[i]; k = k+1; } } } } int main() { int list1[SIZE1] = {1,2,3}; int list2[SIZE2] = {2,3,4,5}; int result[SIZE2]; memberBoth(list1,list2,result); … }



Aspek-aspek lain dari Prolog:  Mekanisme pencarian tidak memerlukan secara eksplisit untuk dispesifikasikan, namun diberikan secara implisit  Cara pemecahan dari Prolog dapat digunakan dalam berbagai cara jika dibandingkan dengan cara pemecahan menggunaan bahasa C, misal: o Pengecekan keanggotaan ?-member_both(2,[1,2,3],[2,3,4,5]). o Perumpamaan suatu elemen dari suatu list ?-member_both(2,[1,2,3],[X,3,4,5]).  Prolog menyusun suatu list secara dinamis o Tidak ada ukuran dari list yang harus didefinisikan, jika dibandingkan dengan arrayyang digunakan untuk merepresentasikan list dalam bahasa pemrograman C



Paradigma Pemrograman Logika – Contoh 3  Menyatakan ontology Contoh database animal animal(mammal,tiger,carnivore,stripes). animal(mammal,hyena,carnivore,ugly). animal(mammal,lion,carnivore,mane). animal(mammal,zebra,herbivore,stripes). animal(bird,eagle,carnivore,large). Page 72 of 98



2012

animal(bird,sparrow,scavenger,small). animal(reptile,snake,carnivore,long). animal(reptile,lizard,scavenger,small). 



Kemudian jika diberikan beberapa pertanyaan berikut: a) Temukan semua binatang yang termasuk mamalia (mammal)? b) Temukan semua binatang karnivora yang mamalia? c) Temukan semua binatang mamalia yang berstrip? d) Apakah ada binatang reptil yang memiliki bulu di tengkuknya (mane)? Maka bisa diberikan bentuk perintah query dalam prolog sebagai berikut: a) animal(mammal,X,Y,Z). b) animal(mammal,X,carnivore,Z). c) animal(mammal,X,Y,stripes). d) animal(reptile,X,Y,mane).

4. Aplikasi Pemrograman Logika Beberapa aplikasi dalam pemrograman logika bisa diterapkan sebagaimana berikut: - Reasoning Agents - Semantic Web - Natural Language Processing - Security Protocol Analysis - Molecular Biology REFERENSI Russell, Stuart; dan Norvig, Peter. 2003. Artificial Intelligence A Modern Approach. International Edition, Edisi 2. Pearson Prentice-Hall Education International. New Jersey

PROPAGASI Latihan dan Diskusi 1. Jelaskan konsep dasar dari paradigma pemrograman, jelaskan perbedaan dari keempat paradigma tersebut! 2. Tuliskan struktur dasar dari pemrograman berbasis logika menggunakan prolog! 3. Sebutkan dan jelaskan beberapa aplikasi dari pemrograman logika!

Pertanyaan (Evaluasi mandiri) Buatlah sebuah perancangan aplikasi yang menyatakan silsilah keluarga. Tunjukkan rule dan faktanya. Dari aplikasi terebut, gunakan pemrograman imperatif untuk menyelesaikannya, serta tunjukkan apakah perbedaan di antara keduanya.

Page 73 of 98



2012

Kecerdasan Buatan: UNCERTAINTY (KETIDAKPASTIAN)

Dian Eka Ratnawati, S.Si, M.Kom,Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc,Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya Email : [email protected] 1. PENDAHULUAN 1.1. Pengantar 1.2.Tujuan 1.3.Definisi 2. UNCERTAINTY 2.1 Definisi Ketidakpastian 2.2 Probabilitas

2.3 Teorema Bayes 2.4 Faktor Kepastian 3. CONTOH 4. PROPAGASI 4.1 Pertanyaan/Latihan Soal 4.2 Diskusi 4.3 Project

1.1 Pengantar Sistem kecerdasan buatan dikembangkan dengan memiliki pengetahuan yang terbatas tentang permasalahan yang ditanganinya, maka sistem tersebut dapat memiliki kesalahan dalam memberikan solusi dengan menggunakan pendekatan logika. Sistem tidak akan pernah mempunyai pengetahuan atau fakta secara lengkap untuk permasalahan yang ditanganinya, sehingga sistem harus bekerja dalam ketidakpastian dan kesamaran. Oleh karena itu, sistem harus menggunakan teknik-teknik khusus yang dapat menangani ketidakpastian dan kesamaran dalam menyelesaikan permasalahan-permasalahan yang ditanganinya. 1.2 Tujuan Setelah mempelajari Pokok Bahasan ini, diharapkan mahasiswa akan : 1. Memahami konsep ketidakpastian dalam sistem kecerdasan buatan 2. Bisa memahami sifat-sifat ketidakpastian dalam sistem kecerdasan buatan dan teknik penyelesaiannya 3. Menerapkan Probabilitas Bayes dalam melakukan penyelesaian masalah ketidakpastian 4. Memiliki kreatifitas dalam penyelesaian masalah

Page 74 of 98

9 UNCERTAINTY (KETIDAKPASTIAN)

1. PENDAHULUAN

MODUL



1.3 Definisi 

     

Uncertainty : teori ketidakpastian pada kecerdasan buatan untuk menyelesaikan permasalahan yang ada dengan pendekatan logika (mengadopsi logika manusia) dimana sistem tidak dapat mengakses seluruh fakta yang ada. Contoh (sample point) : hasil dari percobaan Ruang Contoh (sample space): kumpulan dari semua kemungkinan titik contoh. Kejadian (event) : subset dari ruang contoh. Kejadian sederhana (simple event): hanya ada satu elemen kejadian. Kejadian gabungan (compound event): terdapat lebih dari dari satu kejadian Penalaran Deduktif dan Induktif dilihat dari populasi dan contoh (sample)

2.UNCERTAINTY 2.1 DefinisiKetidakpastian Pada sistem yang menggunakan kecerdasan buatan yang mengandalkan fakta-fakta dalam melakukan pengambilan kesimpulan logika tidak akan menggunakan keseluruhan fakta yang ada, sehingga akan muncul kesalahan-kesalahan dari proses pengambilan kesimpulan. Ketidakpastian dapat dianggap sebagai suatu kekurangan informasi yang memadai untuk membuat suatu keputusan. Ketidakpastian merupakan suatu permasalahan karena mungkin menghalangi kita membuat suatu keputusan yang terbaik. Beberapa teori yang berhubungan dengan ketidakpastian adalah sebagai berikut :  Probabilitas Klasik  Probabilitas Bayes  Teori Hartley yang berdasarkan pada himpunan klasik  Teori Shanon yang didasarkan pada peluang  Teori Dempster-Shafer  Teori Fuzzy Zadeh Contoh aplikasi yang menggunakan ketidakpastian dalam pengambilan kesimpulan logika yang sukses adalah sistem pakar MYCIN untuk diagnosa medis dan PROPECTOR untuk ekplorasi mineral. Salah satu contoh permasalahan yang memiliki ketidakpastian adalah permasalahan diagnosa pasien terhadap suatu penyakit. Misalkan terdapat aturan dalam mendiagosa gejala-gejala dari suatu penyakit sebagai berikut : IF badan_demam(pasien) AND IF badan_ruam(pasien) AND IF badan_pegal(pasien) THEN mengalami_tifus(pasien) Berdasarkan aturan diatas, terlihat bahwa jika ada pasien yang mengalami ketiga jenis gejala tersebut maka akan dideteksi bahwa pasien menderita penyakit tifus. Akan tetapi pada dunia nyata ketika terdapat gejala-gejala tersebut memenuhi belum tentu penyakit yang diderita adalah tifus. Bisa jadi penyakit lain memiliki gejala yang sama sehingga bisa terjadi kesalahan diagnosa. Bagaimana jika derajat gejala yang dialami seorang pasien dengan Page 75 of 98

2012



pasien lainnya bisa jadi berbeda. Kemungkinan-kemungkinan kesalahan yang ada tersebut bisa jadi terjadi dan merupakan hal ketidakpastian dan kesamaran pengetahuan dalam permasalahan ini. 2.2 Probabilitas Klasik Probabilitas merupakan cara yang digunakan dalam menghitung ketidakpastian dengan jalan kuantitas. Dalam probabilitas klasik disebut juga dengan a priori probability karena berhubungan dengan game atau sistem. Secara fundamental formula probabilitas klasik seperti pada persamaan 9.1 : P=W/N dimana :

(9.1)

W adalah jumlah kemenangan dalam permainan N adalah jumlah kemungkinan kejadian yang dilakukan dalam

percobaan Contoh permasalahan adalah pelemparan dadu yang memiliki 6 sisi dan memiliki 6 kemungkinan. Maka peluang-peluang yang mungkin adalah P(1) P(2) P(3) P(4) P(5) P(6)

= = = = = =

1/6 1/6 1/6 1/6 1/6 1/6

Teori formal probabilitas dibuat dengan menggunakan beberapa aturan, aturan-aturan tersebut antara lain adalah :  0 ≤ P(E) ≤ 1 Aturan ini menyebutkan bahwa jangkauan dari probabilitas berada antara 0 dan 1. Jika suatu kejadian itu pasti terjadi maka nilai probabilitasnya adalah 1, dan jika kejadiannya tidak mungkin terjadi maka nilai probabilitasnya adalah 0. 



Aturan ini menyatakan jumlah semua kejadian tidak memberikan pengaruh pada kejadian lainnya maka disebut mutually exclusive events yaitu 1. Pembuktian matematis dari aturan tersebut adalah : P(E) + P(E') =1 Kejadian E1 dan E2 adalah kejadian mutually exclusive. Kejadian mempunyai makna bahwa jika E1 dan E2 keduanya tidak dapat terjadi secara simultan, maka probabilitas dari satu atau kejadian lainnya dalah jumlah dari masing-masing probabilitasnya.

Probabilitas Bersyarat Probabilitas kondisional merupakan probabilitas yang menghitung pengaruh suatu kejadian terhadap kejadian lainnya. Hal ini mengindikasikan bahwa kejadian terjadinya sesuatu bergantung dari kejadian yang lain. Rumusan dari probabilitas kondisional adalah sebagai berikut : (9.2) Pada contoh diatas tersebut dapat dibaca sebagai peluang A dengan syarat B. Page 76 of 98

2012



2.3 Teorema Bayes Teorema peluang Bayes merupakan teori probabilitas dan statistika yang melakukan penafsiran terhadap seberapa jauh derajat kepercayaab subjektif harus berubah secara rasional ketika ada petunjuk baru. Dalam melakukan penafsiran teorema ini melakukan perhitungan terhadap keseluruhan kemungkinan. Teorema bayes banyak digunakan pada banyak bidang ilmu untuk melakukan pengambilan keputusan pada permasalahan tertentu. Ilustrasi Teorema Bayes : A

A

Bn

Bn

B1 B2

B3

 

Gambar 9.1 Ilustrasi teorema Bayes Teorema probabilitas bersyarat yang hanya dibatasi oleh dua buah kejadian dapat diperluas untuk kejadian n buah. Digunakan bila ingin diketahui probabilitas P(B1|A),P(B2|A)….,P(Bk|A)

Secara matematis Teorema Bayes ditulis sebagai persamaan : (9.3) 2.4 Faktor Kepastian (Certainty Faktor) Dalam mengekspresikan derajat keyakinan digunakan suatu nilai yang disebut certain factor (CF)untuk engasumsikan derajat keyakianan seorang pakar terhadap suatu data. Formulasi certain factor : CF[H,E] = MB[H,E] –MD[H,E] Dimana : CF = Certain Factor(faktor kepastian) dalam hipotesis H yang dipengaruhi oleh fakta E MB = Measure of Belief(tingkat keyakinan), adalah ukuran kenaikan dari kepercayaan hipotesis H dipengaruhi oleh fakta E. MD = Measure of Disbelief(tingkat tidakyakinan), adalah kenaikan dari ketidakpercayaan hipotesis H dipengaruhi fakta E. E = Evidence(peristiwa ataua fakta). Penggabungan kepercayaan dan ketidakpercayaan dalam bilangan yang tunggal memiliki dua kegunaan, yaitu : •Faktor kepastian digunakan untuk tingkat hipotesis di dalam urutan kepentingan. Contoh : jika seorang pasien mempunyai gejala tertentu yang mengindikasikan beberapa kemungkinan penyakit, maka penyakit dengan CF tertinggi menjadi urutan pertama dalam urutan pengujian Page 77 of 98

2012

Kecerdasan buatan / MateriKuliah •Ukuran kepercayaan dan probabilitas sebagai berikut :

Brawijaya University ketidapercayaan

didefinisikan

dalam

Karakteristik dari MB, MD dan CF

Faktor kepastian (CF) menunjukkan jaringan kepercayaan dalam suatu hipotesis yang berdasarkan pada beberapa fakta. •CF Positif : mendukung hipotesis, karena MB > MD. •CF=1 : fakta secara definisi membuktikan suatu hipotesis •CF=0 : CF=MB-MD = 0 , berarti tidak ada fakta. MD=MB, berarti kepercayaan dihapus/ditiadakan oleh ketidakpercayaan •CF Negatif : fakta menandakan negasi dari hipotesis, karena MB <MD. Dengan kata lain menyatakan ketidakpercayaan terhadap hipotesis daripada mempercayainya. Faktor kepastian memberikan seorang pakar untuk menyatakan kepercayaan tanpa menyatakan nilai ketidakpercayaan. Formulanya : CF(H,E) + CF(H’,E) = 0 Berarti, fakta mendukung suatu hipotesis dan mengurangi dukungan terhadap negasi dari hipotesis dengan jumlah yang sama, sehingga jumlahnya selalu nol. Contoh : Seorang calon karyawan akan diterima jika mendapatkan nilai 80 untuk tes kemampuan CF(H,E) = 0,75CF(H’,E) = -0,75 Seberapa kepercayaan Anda bahwa mendapatkan nilai 80 pada tes kemampuan akan membantu Anda diterima bekerja ? Jawab : saya pastikan 75% bahwa saya akan diterima bekerja jika saya memperoleh nilai 80 untuk tes Page 78 of 98

2012



kemampuan. Seberapa ketidakpercayaan Anda bahwa mendapatkan nilai 80 pada tes kemampuan akan membantu Anda diterima bekerja ? Jawab : saya pastikan -75% bahwa saya tidak akan diterima bekerja jika saya memperoleh nilai 80 untuk tes kemampuan Definisi asli dari CF adalah : CF = MB – MD. Tahun 1977 definisi asli tersebut diubah dalam MYCIN menjadi :

Aturan MYCIN untuk mengkombinasikan antecedent evidence dari ekspresi dasar Evidence E1 AND E2 E1 AND E2 NOT E

Ketidakpastian anteseden Min[CF(H,E1), CF(H,E2)] Max[CF(H,E1), CF(H,E2)] -CF(H,E)

Contoh : Diketahui ekspresi logika untuk ANDE2 AND E3) OR (E4 AND NOT E5). Evidence E akan dihitung sebagai berikut (E4,-E5)] Jika diketahui : E1 = 0.9E2= 0.8E3 = 0.3E4 Maka hasilnya :E = max [min(0.9;0.8;0.3), 0.5]

penggabungan evicence E=(E1 :E = max [min(E1,E2,E3), min = -0.5 E5 = -0.4 min (-0.5;(-0.4))]E = max[0.3;-

Rumus dasar untuk CF dari kaidah IF E THEN H adalah : Dimana :

CF(H,e) = CF(E,e) CF(H,E) CF(E,e) : faktor kepastian dari fakta E membuat antecedent dari kaidah berdasarkan pada ketidakpastian fakta e CF(H,E) : faktor kepastian dalam hipotesa dengan asumsi bahwa fakta diketahui dengan pasti, bila CF(E,e)=1 CF(H,e) : faktor kepastian hipotesis yang didasarkanpada ketidakpastian fakta e. Jika semua fakta dalam antecedent diketahui dengan pasti rumus faktor kepastiannya menjadi : CF(H,e) = CF(E,e) , karena CF (E,e) = 1

3. CONTOH kaidah streptococcus (bakteri) IF 1. Zat warna dari organisme adalah gram positif AND 2. morfologi dari organisme adalah coccus AND 3. penyesuaian diri dari organisme adalah merantai THEN Ada bukti sugesstif (0.7) bahwa identifikasi dari organisme Page 79 of 98

2012



tersebut adalah streptococcus Dimana faktor kepastian dari hipotesis dengan kepastian fakta adalah CF(H,E) = CF(H, E1∩E2∩E3) = 0.7 Dan disebut Attenuation factor. Attenuation factordidasarkan pada asumsi bahwa semua fakta E1, E2 dan E3 diketahui dengan pasti, yaitu : CF(E1,e) = CF(E2,e) = CF(E3,e) = 1 Jika diasumsikan : CF(E1,e) = 0.5 CF(E2,e) = 0.6 CF(E3,e) = 0.3 Maka CF(E,e) = CF(E1∩E2∩E3,e) = 0.7 = min[CF(E1,e), CF(E2,e), CF(E3,e)] = min[0.5;0.6;0.3] = 0.3 CF(H,e) = CF(E,e) CF(H,e) = (0.3) . (0.7) = 0.21 Karena CF dari antecedent CF(E,e) > 0.2; antecedent dinyatakan benar dan kaidah diaktifkan. 4. PROPAGASI a. 1. 2. 3. 4.

Pertanyaan / Latihan Soal (Evaluasi Mandiri) Apa yang dimaksud teorema ketidakpastian ? Apa peran teorema ketidakpastian dalam Kecerdasan Buatan ? Bagaimana cara menerapkan teorema ketidakpastian dalam aplikasi ? Apa perbedaan dari teori Probabilitas Klasik, Bayes dan Faktor Kepastian ?

b.

Latihan Soal Pengembangan dan Diskusi 1. Menurut anda, apa kelebihan maupun kekurangan dari teori-teori dalam teorema ketidakpastian ? 2. Apakah masing-masing teori tersebut bisa diaplikasikan untuk permasalahan yang sama atau masing-masing punya karakteristik sendiri ? 3. Jelaskan definisi teori demster-shafer dan Fuzzy Zadeh

c.

PROYEK (Eksplorasi entrepreneurship, penerapan topic bahasan pada dunia nyata) 1. Carilah sebuah jurnal / hasil penelitian yang menerapkan teori ketidakpastian dalam aplikasi kongrit dan berikan ulasan tentang implementasinya Page 80 of 98

2012



REFERENSI 1. Giarrantano, J and G.Riley, Expert System : Principle and Programming,4thed, PWS Kent, 2004 2. Sri Kusumadewi, Artificial Intelligence : Teknik dan Aplikasinya, Graha Ilmu, Yogyakarta, 2003

Page 81 of 98

2012



2012

Kecerdasan Buatan: Bayesian Network

Dian Eka Ratnawati, S.Si, M.Kom,Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc,Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya

1. PENDAHULUAN 1.3 Pengantar 1.4 Tujuan 1.5 Definisi

2. Sintak Bayesian Network 3. Semantik Bayesian Network

1. PENDAHULUAN

1.2 Tujuan Penguasaan materi dalam modul ini dirancang agar mahasiswa mampu untuk :  Menjelaskan dan memahami tentang definisi dan konsep dari sintaks bayesian network  Menjelaskan dan memahami tentang definisi dan konsep semantik dari bayesian network  Mampu merancang aplikasi sederhana dengan konsep bayesian network 1.3Definisi Bayesian Network merupakan suatu notasi grafis yang sederhana untuk pernyataan bebas bersyarat dan oleh karenanya untuk spesifikasi atas full joint distribution yang padat.

2. SINTAK BAYESIAN NETWORK Adapun sintak dari Bayesian Network terdiri atas: o Sekumpulan node, di mana satu node per variabel o Suatu graph tidak berputar dan berarah (link menyatakan“berpengaruh langsung”) o Suatu distribusi bersyarat untuk setiap node yang diberikan parent-nya: P(Xi|Parents(Xi)) - Suatu contoh sederhana, distribusi bersyarat direpresentasikan sebagaimana dalam suatu suatu tabel probabilitas bersyarat (CPT) memberikan distribusi atas Xiuntuk setiap kombinasi nilai parentnya - Contoh 1: o Topologi jaringan mengkodekan pernyataan-pernyataan bebas Page 82 of 98

10 Bayesian Network

1.1 Pengantar Ketika suatu permasalahan yang bisa dinyatakan dalam bentuk sebab akibat, dimana melibatkan adanya proporsisi/ ketidakpastian dari suatu kejadian, maka kita bisa menyelesaikannya dengan bayesian network.

MODUL



bersyarat, sebagai berikut:

Gambar 10.1 Hubungan antar variabel o o

-

Weather adalah bebas (independent) atas variabel-variabel lain. Toothache dan Catch adalah bebas bersyarat atas variabel Cavity yang diberikan.

Contoh 2: o Andi punya alarm baru. Alarm akan berbunyi jika ada pencuri (burglary) masuk rumah Andi. Tetapi alarm juga akan berbunyi jika ada gempa kecil, dimana gempa tersebut tidak terasa di tempat John dan Mary. Jika alarm berbunyi, John dan Mary berjanji untuk menelepon Andi saat Andi bekerja di kantor. Tetapi terkadang saat alarm berbunyi John ataupun Mary tidak tahu karena mereka sedang pergi, atau karena suara alarm yang kecil karena baterai habis, atau karena ada suara lain yang lebih keras dari alarm tersebut. Adakah seorang pencuri (burglar)? o Variabel-variabel yang terlibat: Burglar, Earthquake, Alarm, JohnCalls, MaryCalls o Topologi jaringan merefleksikan pengetahuan “sebab akibat”:  Seorang Burglary dapat menyebabkan alarm nyala  Earthquake dapat menyebabkan alarm nyala  Alarm dapat menyebabkan adanya panggilan dari Mary (MarryCall)  Alarm dapat menyebabkan adanya panggilan dari John (JohnCall) o Sehingga bisa diilustrasikan sebagaimana berikut:

Gambar 10.2 bayesian network dari kasus Andi -

Dari ilustrasi pada Gambar 10.2 dapat diartikan: Burglary dan Earthquake keduanya merupakan variabel independent dengan nilai probabilitas masing-masing: P(B)= 0.001 dan P(E)=0.002. Namun Alarm merupakan varibel bersyarat, yang Page 83 of 98

2012



dipengaruhi oleh Burglary dan Earthquake. -

Compactness - Suatu tabel probabilitas bersyarat (CPT) untuk nilai Boolean Xi dengan k Boolean parent mempunyai 2k baris untuk kombinasi dari nilai parent.

Gambar 10.3 Hubungan antar variabel Setiap baris meminta satu angka peluang p untuk Xi=true (angka untuk Xi=false sebesar1-p) - Jika setiap variabel tidak memiliki lebih banyak k parent, maka network yang lengkap memerlukan O(n.2k) angka. - Seperti, pertumbuhan secara linear dengan n terhadap O(2n) bagi distibrusi keterkaitan penuh (full joint distribution) - Dari nilai-nilai yang ada di dalam tabel CPT terlihat untuk jaringan burglary, terdapat 1+1+4+2+2 = 10 angka (vs. 251 = 31) Semantics - Full joint distribution didefinisikan sebagai perkalian atas distribusi bersyarat lokal: -

-

P (X1, … ,Xn) = πi = 1P (Xi | Parents(Xi)) Misal: P(j  m  a b e) = P (j | a) P (m | a) P (a | b, e) P (b) P (e)

Pengkonstruksian Bayesian network 1. Choose an ordering of variables X1, … ,Xn 2. For i = 1 to n add Xi to the network select parents from X1, … ,Xi-1 such that P (Xi | Parents(Xi)) = P (Xi | X1, ... Xi-1) This choice of parents guarantees: P (X1, … ,Xn) = πi =1P (Xi | X1, … , Xi-1) (chain rule) = πi =1P (Xi | Parents(Xi)) (by construction)

Contoh -

Andaikan kita pilih urutan M, J, A, B, E

Page 84 of 98

2012



-

P(J|M) = P(J) ? Apakah Peluang JohnCalls bersyarat terhadap MaryCalls sama dengan peluang terjadinya JohnCalls? Jawabannya: Tidak, karena dari graph di atas terlihat bahwa peluang terjadinya JohnCalls bergantung pada MaryCalls.

-

P(A| J,M) = P(A | J)?P(A | J, M) = P(A)?

Dari graph di atas terlihat bahwasannya peluang terjadinya Alarm dipengaruhi oleh adanya kejadian MaryCalls dan JohnCalls, sehingga: P(A| J,M) = P(A | J)?P(A | J, M) = P(A)? No Kemudian diberikan pertanyaan berikutnya: - P(B | A, J, M) = P(B | A)? - P(B | A, J, M) = P(B)?

-

Maka dari gambar di atas bisa menjawab pertanyaan sebelumnya bahwa Peluang terjadinya Burgary dipengarui oleh bunyi Alarm, sehingga: P(B | A, J, M) = P(B | A)? Yes P(B | A, J, M) = P(B)? No

-

Kemudian, jika diberikan P(E | B, A ,J, M)apakah sama denganP(E | A)? Juga apakahP(E | B, A, J, M) sama dengan P(E | A, B)?

-

Page 85 of 98

2012


-

-


2012

Dari graph di atas dapat digunakan untuk menjawab pertanyaan sebelumnya, bahwa: P(E | B, A ,J, M) = P(E | A)? No P(E | B, A, J, M) = P(E | A, B)? Yes Penentuan kebebasan bersyarat (conditional independence) adalah sulit pada arah sebab akibat secara langsung. Jaringan tersebut lebih sedikit padat: 1 + 2 + 4 + 2 + 4 = 13 angka yang diperlukan

Kesimpulan: - Bayesian network menyediakan suatu representasi alami untuk (induksi sebab akibat) kebebasan bersyarat - Topologi dan CPT membentuk representasi yang padat dari distribusi gabungan - Secara umum mudah bagi para pakar untuk mengkonstruksi

REFERENSI Russell, Stuart; dan Norvig, Peter. 2003. Artificial Intelligence A Modern Approach. International Edition, Edisi 2. Pearson PrenticeHall Education International. New Jersey

PROPAGASI Latihan dan Diskusi 1. Jelaskan konsep dasar dari Bayesian Network! 2. Jelaskan secara ringkas sintak dari Bayesian Network! Beserta komponenkomponen yang terdapat di dalamnya! 3. Jelaskan dengan memberikan contoh sederhana membuat konstruksi Bayesian Network secara semantik! 4. Jelaskan topologi jaringannya di tiap node atau variabel! 5. Jelaskan maksud dari compactness! Pertanyaan (Evaluasi mandiri) Buatlah sebuah perancangan aplikasi dalam bidang kedokteran untuk mendiagnosa suatu penyakit yang memiliki sebab akibat. Gambarkan dalam bentuk bayesian networknya. Jika diberikan nilai-nilai dalam CPT

Page 86 of 98



2012

Kecerdasan Buatan:Learning Dian Eka Ratnawati, S.Si, M.Kom,Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc,Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya Email : [email protected]

1. PENDAHULUAN 1.1 Pengantar 1.2 Tujuan 1.3 Definisi 2. Learning

3.

Latihan

MODUL

11

1.PENDAHULUAN 1.1 Pengantar

Page 87 of 98

LEARNING

Penyelesaian permasalahan dalam kasus kecerdasan buatan selanjutnya adalah teknik learning. Terdapat banyak sekali teknik learning dengan berbagai variasinya yang telah diteliti dan diimplementasikan. Namun pada modul ini hanya dibahas dua metode, yaitu Jaringan Syaraf Tiruan dan Decision Tree Learning (pembelajaran dengan pohon keputusan). Pada teknik-teknik sebelumnya : searching, reasoning dan planning kita harus tahu aturan lengkap yang berlaku untuk sistem yang akan kita bangun. Namun jika terdapat banyak atribut dengan masingmasing memiliki banyak variasi nilai yang berbeda, maka akan sangat banyak kombinasi data yang harus dibuat aturannya. Contoh ada 30 atribut, masing-masing atribut memiliki 3 nilai yang berbeda, maka terdapat 330 = 205.891.132.094.649 kombinasi data. Tentu sangat sulit atau bahkan tidak mungkin untuk menemukan aturan yang benar dan lengkap secara manual. Tetapi kita bisa membuat suatu program computer yang secara otomatis menemukan aturan-aturan yang kita harapkan. Hal itu kita lakukan dengan Teknik Learning. Meskipun untuk kombinasi data yang tidak lengkap kita tidak bisa berharap komputer akan menemukan aturan yang benar dan lengkap, tetapi komputer sanggup belajar. Pada teknik learning ini intinya kita membuat komputer bisa mempelajari data-data baru sehingga sehingga membuatnya semakin pintar.



2012

1.2 Tujuan Setelah mempelajari Pokok Bahasan ini, diharapkan mahasiswa akan : 1. Memahami konsep learning dalam sistem kecerdasan buatan 2. Bisa memahami sifat-sifat learning dalam sistem kecerdasan buatan dan teknik penyelesaiannya 3. Menerapkan teknik learning dalam melakukan penyelesaian kecerdasan buatan 4. Memiliki motivasi untuk mencari ilmu dan mengembangkan ilmu yang sudah dimiliki 1.3 Definisi     

Individu : menyatakan salah satu solusi yang mungkin = kromosom : kumpulan gen. Gen : sebuah nilai yang menyatakan satuan dasar yang membentuk arti tertentu dalam satu kesatuan (kromosom). bisa biner, float, integer maupun karakter, list of rule (R1, R2,…), elemen permutasi (E1, E2,…) atau kombinatorial, struktur data lainnya Allele : nilai dari gen populasi : sekumpulan individu (kromosom) yang akan diproses bersama dalam satu siklus proses evolusi Generasi : satu siklus proses evolusi atau satu iterasi dalam algoritma genetika

2. LEARNING (PEMBELAJARAN) 2.1 Jaringan Syarat Tiruan (Artificial Neural Network) 2.1.1 Sejarah Jaringan Syaraf Tiruan (JST) Perkembangan computer yang sangat pesat membuat para ahli tertantang untuk mengembangkan computer yang mampu yang mampu melakukan hal-hal seperti yang dilakukan manusia. Untuk perhitungan matematis, yang sulit sekalipun, computer mampu melakukan perhitungan dengan mudah, bahkan lebih cepat dari manusia. Akan tetapi, bagaimana dengan kemampuan manusia yang lain, terutama yang didapat dari pengalaman ? Misal dari seorang guru, siswa belajar mengenali huruf “A”, atau membedakan gambar penguin dengan gambar kucing, dan lain sebagainya. Berdasar keadaan tersebut, dikembangkan suatu jaringan yang memiliki konsep mirip dengan jaringan otak manusia. Jaringan tersebut dapat dilatih sehingga pada akhirnya dapat mengambil keputusan seperti yang dilakukan oleh otak manusia. Jaringan tersebutdisebut sebagai jaringan syaraf tiruan, dan computer dimanfaatkan sebagai sarana pelatihan jaringan (artificial neural network) 2.1.2 Konsep Jaringan Syaraf Tiruan. Seperti telah dijelaskan di atas, Jaringan syaraf tiruan merupakan sistem pemroses informasi yang memiliki karakteristik mirip dengan jaringan syaraf biologi. Jaringan syaraf tersebut adalah sebagaimana ditunjukkan pada gambar 1 berikut.

Gambar 1. Jaringan syaraf biologi Page 88 of 98



2012

Peniruan model otak manusia tersebut dilakukan dengan adaptasi seperti ditunjukkan tabel 1 berikut. Tabel 1. Model jaringan syaraf tiruan

Sehingga model neuron pada jaringan syaraf tiruan menjadi seperti pada gambar 2.

Gambar 11.1 Model neuron JST Karakteristik JST adalah :  Arsitektur Jaringan ◦ Single Layer, Multi Layer  Training/Learning ◦ Perceptron,, Backpropagation  Fungsi Aktivasi ◦ Fungsi treshold (ramp function) ◦ Fungsi sigmoid ◦ Fungsi identitas 2.1.3 Pelatihan Jaringan Syaraf Tiruan Pelatihan jaringan syaraf dimaksudkan untuk mencari bobot-bobot yang terdapat dalam tiap layer. Ada 2 jenis pelatihan dalam sistem jaringan syaraf tiruan, yaitu proses belajar terawasi (supervised learning) dan proses belajar tidak terawasi (unsupervised learning). a. Proses Belajar Terawasi Dalam proses belajar terawasi seolah-olah ada guru yang mengajari jaringan. Cara pelatihan jaringan tersebut adalah dengan memberikan data-data yang disebut data training. Data training terdiri atas pasangan input dan output yang diharapkan dan merupakan associative memory. Data-data tersebut biasanya didapat dari pengalaman atau pengetahuan seseorang dalam menyelesaikan persoalan. Setelah jaringan dilatih, associative memory akan mengingat suatu pola. Jika jaringan diberi input baru, jaringan dapat mengeluarkan output seperti yang diharapkan. Beberapa Page 89 of 98



2012

metode pembelajaran pada supervised learning adalah : delta rule, backpropagation, counterpropagation. b. Proses Belajar Tak Terawasi Dalam proses belajar tak terawasi tidak ada “guru” yang mengjari jaringan. Jaringan hanya diberi input tanpa vector target. Jaringan akan memodifikasi bobot, sehingga untuk input yang hamper sama output yang dihasilkan sama (cluster units). Metode yang dipakai antara lain Kohonen Self Organizing Map. Dalam pelatihan/pembelajaran jaringan, selain ada data untuk training set, juga ada data untuk tes. Data tes ini digunakan untuk mengetahui output yang dihasilkan jaringan, tidak mempengaruhi training.

3.PROPAGASI a.

Pertanyaan / Latihan Soal (Evaluasi Mandiri) 1. Apa yang anda ketahui mengenai JST? 2. Apa kelebihan teknik learning dibanding teknik yang lain?

b.

PROYEK (Eksplorasi entrepreneurship, penerapan topic bahasan pada dunia nyata) 1. Buat rancangan penjadwalan dengan algoritma genetika

REFERENSI     

Russel &Artificial Intelligence : A Modern Approach (2nd ed.) by Russel & Norvig Suyanto, ST., MT., Artificial Intelligent : searching, reasoning, planning and learning Sri Kusumadewi, Artificial Intelligence : Teknik dan Aplikasinya, Graha Ilmu, Yogyakarta, 2003 Giarrantano, J and G.Riley, Expert System : Principle and Programming,4thed, PWS Kent, 2004 Dr.Ir. Kuswara Setiawan, MT, “Paradigma Sistem Cerdas”, Bayumedia, 2003

Page 90 of 98

LAMPIRAN BIODATA KETUA Nama lengkap Fakultas Jurusan/Program Studi Alamat koresponden Telepon/Fax Nomor HP Email

: Dian Eka Ratnawati, S.Si, M.Kom : PTIIK :Informatika/Ilmu Komputer :Jl Akordion, Perum Bumi Tunggul Wulung Indah M3 Malang : 0341-9442404 : 082143517901 :[email protected]

Riwayat Pendidikan Perguruan No Tahun lulus Tinggi S1 1997 ITS S2 2002 ITS S3 -

Bidang Spesialisasi Matematika/bid studi Informatika Teknik Informatika

Nama Mata Kuliah yang diasuh No Nama Mata Kuliah 1 Kecerdasan Buatan 2 Basis data 3 Data Mining 4 Algoritma Genetik

Strata S1 S1 S1 S1

Jumlah Mahasiswa yang pernah diluluskan Strata Jumlah S1 87 S2 S3 Pengalaman penelitian No

Tahun

Topik/judul penelitian

1

2009

Kompresi File BerdasarkanPola Optimal secaraSekuensial

2

2010

Optimasikompresi file denganmenggunakangabunganmetode RunLength-Encoding (RLE), shannon-fannodan Lempel-Ziv-Welch (LZW) Teknikkompresicitramenggunakandekomposisi nilaisingulirberbasisblok Modifikasikodekarakteruntukkompresi Half-Byte berdasarkanfrekuensipasanganpolamaksimal

3

2010

4

2011

5

2012

Pengembanganmetodeklasifikasiuntukoptimalisasianggotakelasdengan menggunakan K-Means

6

2012

PengembanganMetodeKlasifikasiberdasarkan K-Means dan LVQ

Kecerdasan Buatan


Pengalaman publikasi di berkala ilmiah 5 tahun terakhir Nama Penulis

Tahun Judul Artikel Terbit

Nama Berkala

Volume dan halaman

Status akreditasi

Dian Eka Ratnawati, Marji -, Dewi Yanti Liliana

2011

Optimasi Kompresi File Dengan Menggunakan Gabungan Metode RunLength-Encoding (RLE), Shannon- Fano Dan Lempel-Ziv-Welch(LZW)

Jurnal Pointer – Ilmu Komputer

Vol 2, No 1 halaman 69

Belum terakreditasi

Dewi Yanti Liliana, Dian Eka Ratnawati, Marji

2011

Teknik Kompresi Citra Menggunakan Dekomposisi Nilai Singulir Berbasis Blok

Jurnal Vol 2, No Pointer – 2 Ilmu halaman Komputer

Belum terakreditasi

Page 92 of 98

2012

Kecerdasan Buatan

Brawijaya University BIODATA ANGGOTA

Nama lengkap Fakultas Jurusan/Program Studi Alamat koresponden Telepon/Fax Nomor HP Email

: : : : : : :

Dewi Yanti Liliana, S.Kom, M.Kom Program Teknologi Informasi dan Ilmu Komputer Informatika/Ilmu Komputer Jl. Yupiter No. 10 Malang 0341 554204 081218769796 [email protected]

Riwayat Pendidikan Perguruan No Tahun lulus Tinggi S1 ITS 2004 S2

2009

Universitas Indonesia

Bidang Spesialisasi Teknik Informatika Ilmu Komputer

S3 Nama Mata Kuliah yang diasuh No Nama Mata Kuliah 1 Kecerdasan Buatan 2 Pengenalan Pola 3 Analisis dan Desain Algoritma 4 Struktur Data dan Algoritma

Strata S1 S1 S1 S1


Tahun

1

2010

2

2012

Topik/judul penelitian Teknik Kompresi citra menggunakan dekomposisi nilai singulir berbasis blok. Deteksi Wajah menggunakan Fast Fourier Transformatioan

Page 93 of 98

2012

Kecerdasan Buatan



Tahun Terbit

Judul Artikel

Nama Berkala

Volume dan halaman

Status akreditasi

Dewi Yanti Liliana, T. Basaruddin

2009

Deteksi Pemalsuan Citra Berbasis Dekomposisi Nilai Singulir

Jurnal Makara seri sains UI

Volume 13, No. 2

Akreditasi B

Dewi Yanti Liliana, Rahmat Widyanto

2011

Particle Swarm Optimization with Fuzzy Adaptive Acceleration for Human Object Detection

IJViPNS

Volume 11 Issue 01

Dewi Yanti Liliana, Dwina Satrinia

2012

Adaptive IJCSIS Behaviometrics for Information Security and Authentication System using Dynamic Keystroke

Volume 10 No.1

Dewi Yanti Liliana, Eries Tri Utami

2012

The combination of palm print and hand geometry for biometrics palm recognition

Volume 12 No. 1

IJViPNS

Page 94 of 98

2012

Kecerdasan Buatan


Nama lengkap Fakultas Jurusan/ Program Studi Alamat koresponden Telepon/Fax Nomor HP Email

: Lailil Muflikhah, S.Kom., M.Sc. : Program Teknologi Informasi dan Ilmu Komputer : Informatika : Gedung A PTIIK, Jl. Veteran No.8 Malang : +62 341577911/ +62 341577911 : 08123220198 : [email protected]

Riwayat Pendidikan No

Tahun lulus

S1 S2 S3

1998 2010

Bidang Spesialisasi

Perguruan Tinggi ITS Surabaya UTP Malaysia

IT – Data Mining

Nama Mata Kuliah yang diasuh No Nama Mata Kuliah 1 Data Mining 2 Kecerdasan Buatan 3 Teknk Kompilasi 4 Sistem Pakar 5 Sistem Basis Data 6 Algoritma dan Struktur Data 1 7 Teori Bahasa & Automata

Strata S1 S1 S1 S1 S1 S1 S1

Jumlah Mahasiswa yang pernah diluluskan Strata Jumlah S1 50 S2 S3

Pengalaman penelitian No

Tahun

1 2

2007 2011

3

2012

4

2012

Topik/judul penelitian Pencarian dan Pengklasifikasian Susunan Kata pada Dokumen Teks Modifikasi Kode Karakter Untuk Kompresi Half-Byte Berdasarkan Frekuensi Pasangan Pola Maksimal Penggalian Data dalam Penentuan Keterkaitan Topik pada Terjemahan Ayat-Ayat Al-Qur’an Pengembangan Metode Klasifikasi berdasarkan K-Means dan LVQ

Page 95 of 98

2012

Kecerdasan Buatan



Tahun Judul Artikel Terbit

Nama Berkala

Volume dan halaman

Status akreditasi

Lailil Muflikhah, Muh. Arif Rachman

2007

Pencarian dan Pengklasifikasian Susunan Kata pada Dokumen Teks

Jurnal Natural, FMIPA UB

Vol 11, No 3, hal 212-219

Belum terakreditasi

Lailil Muflikhah, Baharum Baharudin

2008

Optimize Fuzzy Cluster of E-Documents using Validity Index”

Proceeding of International Graduate Conference on Engineering & Science, pp. 685-692 , UTM Skudai, Johor, Malaysia

pp.685692

Lailil Muflikhah, Baharum Baharudin

2011

Improving Performance of Document Clustering using Latent Semantic Index Approach

Jurnal Pointer, Ilmu Komputer UB

Vol.2 No.1

Belum terakreditasi

Lailil Muflikhah

2011

Penggunaan Indeks Validitas Pada Algoritman Fuzzy CMeans Clustering untuk Pengklasteran Dokumen

Jurnal SISTEM, Fakultas Teknik Universitas Wisnu Wardana

Vol. 7 No. 1, hal 2029

Belum terakreditasi

Lailil Muflikhah, Made Putra Adnyana

2011

Classifying Wine Quality Using K-Nearest Neighbor Based Associations

(IJCSIS) International Journalof Computer Science and Information Security

Vol.9, No. 12

Internasional

Page 96 of 98

2012

Kecerdasan Buatan


Nama lengkap Fakultas Jurusan/Program Studi Alamat koresponden Telepon/Fax Nomor HP Email

: Rekyan regasari MP : Program Teknologi Informasi dan Ilmu Komputer : Informatika/Ilmu Komputer : Mutiara Jingga 38 Malang : 0341-9503432 : 08123125356 : [email protected]

Riwayat Pendidikan No

Tahun lulus

S1 S2

2002

Perguruan Tinggi ITS-Surabaya Universitas Brawijaya

2010

Bidang Spesialisasi Elektronika Sistem Komunikasi dan Ilmu Komputer – Komputasi Cerdas

S3 Nama Mata Kuliah yang diasuh No Nama Mata Kuliah 1 Probabilitas Statistik 2 Matematika Komputasi 3 Kecerdasan Buatan

Strata S1 S1 S1


Tahun

1

2010

2

2011

Topik/judul penelitian Decision Support System Penentuan Penerima Bantuan Pemerintah dengan integrasi Metode Group Technology dan Decision Table Sistem Informasi Kelurahan

Pengalaman publikasi di berkala ilmiah 5 tahun terakhir Nama Penulis Rekyan Regasari MP

Tahun Terbit

Judul Artikel

2011

Metode Group technology pada Perancangan perangkat Lunak Portable Bio Electromyograph

Nama Berkala Jurnal Teknologi Informasi

Page 97 of 98

Volume dan halaman Vol 1, Hal 95 - 189

Status akreditasi ISSN:20862989

2012

Modul Bahan Ajar KECERDASAN BUATAN

Recommend Documents