modul bahan-ajar-kecerdasan-buatan-ptiik-final

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

Modul Bahan Ajar

KECERDASAN BUATAN

of 98

Kecerdasan buatan / MateriKuliah 2012 Brawijaya University

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

of 98


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

of 98


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

of 98


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

PEN

GA

NT

AR

KE

CER

DA

SA

N B

UA

TA

N

MODUL

1

of 98


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

Sistem yang berpikirseperti manusia

Thinking humanly

Sistem yang berpikir secara rasional

Thinking rationally

Sistem yang bertindak seperti manusia

Acting humanly

Sistem yang bertindaksecara rasional

Acting rationally

of 98


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

of 98


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 yang bertindak optimal berdasarkan umpan balik dari lingkungan.

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)

of 98


- 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 masing-

masing sub bidang tersebut! 1. Pengolahan Bahasa Alami

2.Knowledge representation 3.Automated Reasoning 4. Machine Learning

5. Computer Vision 6. Robotika

of 98


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]


2. Konsep Agen Cerdas dan Lingkungan

3. Konsep Perancangan Agen Cerdas

4. Jenis Lingkungan 5. Jenis Agen


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.

1.2 Tujuan


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.

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

AG

EN

CER

DA

S

MODUL

2

of 98


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 kotoran dibersihkan, Jumlah waktu yang dibutuhkan, Jumlah listrik yang dikonsumsi,

Jumlah 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,

of 98


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. Aspek-aspek 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

of 98


• 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

of 98


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

of 98


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)

of 98


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.


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 aspek-aspeknya: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!

of 98


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


2. Jenis Problem 3. Formulasi Problem

4. Algoritma Pencarian Dasar 5. Strategi Pencarian Uninformad


Pada bagian ini dibahas agen cerdas penyelesaian problem, serta strategi uninformed untuk memecahkan masalah. Terdapat

beberapa teknik yang termasuk dalam strategi pencarian uninformed.

1.2 Tujuan


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.

Pen

yele

saia

n P

ro

ble

m d

en

gan

Pen

caria

n (

search

ing

)

MODUL

3

of 98


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

<action,successor(state)>

misalnya, S (Arad) = {<Arad à Zerind, Zerind>, ...} 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

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

of 98


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.

of 98


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)

of 98


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

of 98


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:

of 98


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

of 98


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!

of 98


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


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

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

4 PE

NC

AR

IA

N H

EU

RIS

TIK

/ I

NFO

RM

ED

SEA

RC

H

(SPEED

)

MODUL

of 98


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:

Gambar 4.1

Penyelesaian : Membangkitkan solusi - solusi yang mungkin dengan menyusun kota – kota dalam urutan

abjad, yaitu:

A B

D C

8

6

7 5 3 4

of 98


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

Panjang

Lintasan

terpilih

1. ABCD 19 ABCD 19

2. ABDC 18 ABDC 18

3. ACBD 12 ACBD 12

4. ACDB 13 ACBD 12

5. ADBC 16 ACBD 12

6. ADCB 18 ACBD 12

7. BACD 17 ACBD 12

8. BADC 21 ACBD 12

9. BCAD 15 ACBD 12

10. BCDA 18 ACBD 12

11. BDAC 14 ACBD 12

12. BDCA 13 ACBD 12

13. CABD 15 ACBD 12

14. CADB 14 ACBD 12

15. CBAD 20 ACBD 12

16. CBDA 16 ACBD 12

17. CDAB 21 ACBD 12

18. CDBA 18 ACBD 12

19. DABC 20 ACBD 12

20. DACB 15 ACBD 12

21. DBAC 15 ACBD 12

22. DBCA 12 ACBD atau

DBCA

12

23. DCAB 17 ACBD atau

DBCA

12

24. DCBA 19 ACBD atau

DBCA 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:

of 98


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.

Bila ada n kota maka kombinasi lintasan :

Sehingga kalau ada 4 kota, menjadi: 6)!24! (2

!4

kombinasi. Keenam kombinasi ini akan

dipakai semuanya sebagai operator, yaitu

!2!2

!

n

n

of 98


1. (1,2) tukar urutan posisi kota ke-1 dengan kota ke-2 2. (2,3) tukar urutan posisi kota ke-2 dengan kota 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.

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

ABCD

D

BACD ACBD ABDC DBCA

Tk 1,2

Tk 2,3 Tk 3,4 Tk 4,1

ADCB CBAD

Tk 2,4

Tk 1,3

(19)

(17)

ABCD BCAD BADC DACB

Tk 1,2

Tk 2,3 Tk 3,4 Tk 4,1

BDCA CABD

Tk 2,4 Tk 1,3 (15)

CBAD BACD BCDA DCAB BDAC ACBD

Tk 1,2 Tk 2,3 Tk 4,1 Tk 2,4 Tk 1,3 Tk 3,4

(20) (18) (17) (14)

DBAC BADC BDCA CDAB

Tk 1,2 Tk 3,4 Tk 4,1

BCAD ADBC

Tk 2,4 Tk 1,3

(15) Tk 2,3

(21) (13)

DBCA BCDA BDAC ADCB

Tk 1,2 Tk 3,4 Tk 4,1

BACD CDBA

Tk 2,4 (12)

Tk 2,3 Tk 1,3

BDCA DCBA DBAC ABCD DACB CBDA

Tk 1,2 Tk 2,3 Tk 4,1 Tk 2,4 Tk 1,3 Tk 3,4

(19) (15) (19) (16)

(15)

of 98


nilai heuristik BCAD lebih kecil dibanding dengan BACD (15<17), maka node BCAD akan menjadi pilihan selanjutnya dengan operator Tukar2,3.

o Kemudian hill climbing akan mengunjungi CBAD (=20). Karena nilai heuristik CBAD lebih besar jika dibanding dengan BCAD (20>17), maka dipilih node lain.

o Pencarian menuju ke node BACD, karena operator Tukar2,3 sudah pernah digunakan oleh BCAD, maka dipilih node lain.

o Kunjungan berikutnya ke node BCDA (=18). Nilai inipun masih lebih besar dari nilai

heuristic BCAD, sehingga dipilih node lain. o 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.

o 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. o Pencarian pertama sudah mendapatkan node dengan nilai heuristik yang kebih kecil,

yaitu DBCA (=12). Sehingga node ini diekplorasi juga.

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

Gambar 4.3. Metode Simple Hill Climbing dengan 4 operator.

ABCD

BACD ACBD ABDC DBCA

ABCD BCAD BADC DACB

Tukar 1,2

Tukar 2,3 Tukar 3,4 Tukar 4,1

Tukar 1,2 Tukar 2,3

Tukar 3,4

Tukar 4,1

CBAD BACD BCDA DCAB

Tukar 1,2 Tukar 2,3

Tukar 3,4

Tukar 4,1

(19)

(17)

(15)

(20) (17) (18) (17)

of 98


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.

Gambar 4.4 Metode Steepest Ascent Hill Climbing

Keterangan gambar 4.4.:

o Pada Gambar 4.4, terlihat bahwa, keadaan awal, lintasan terpilih adalah ABCD (19). o 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).

ABCD

ACBD ABDC DBCA

Tk 1,2

Tk 3,4 Tk 4,1

ADCB CBAD

Tk 2,4

Tk 1,3

(19)

(17)

CABD ABCD ACDB DCBA

Tk 2,3 Tk 3,4 Tk 4,1

ADBC BCAD

Tk 2,4 Tk 1,3 (15)

Tk 2,3 (12) (18) (12) (18) (20)

BACD

(13)

Tk 1,2

(19) (16) (15) (19)

of 98


o 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. o 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*

of 98


4.1. 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 :

of 98


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

of 98


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*

of 98


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*

of 98


Gambar 4.12. langkah 3 penyelesaian dengan algoritma A*

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


of 98




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

of 98


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

B

E

A

G

F

C

H

D

10

50

10

20

80

40

2090

30

50

10

20

20

Estimasi waktu (dalam menit) untuk menuju

goal (H) A: 60

B: 80

C: 20

D: 25

E: 70

F: 25

G: 35

Gambar 4.18.

http://journal.mercubuana.ac.id/data/Heuristic-search.pdf

http://www.mdp.ac.id/materi/2011-2012-1/.../TI322-041035-666-9.ppt

of 98


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. Backtracking 4. Forward Checking 5. Constrain Propagation 6. Arc consistency 7. Latihan

1. PENDAHULUAN 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.

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

CO

NS

TR

AIN

T S

ATIS

FA

CTIO

N

PR

OB

LEM

MODUL

5

of 98


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,

of 98


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 di-assign 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.

of 98


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

of 98


Gambar 5.4 Contoh backtraking

Memperbaiki kinerja backtracking Urutan pemilihan variabel dan nilai mempengaruhi kinerja

backtracking Terdapat beberapa strategi yang berlaku secara umum (general-

purpose):

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.


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

of 98


dengan n=1000 bisa diselesaikan!


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 di-

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

of 98


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.

of 98


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.

of 98


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

of 98


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

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



http://sitoba.itmaranatha.org/PIB%200809/eBooks/PIB%20lesson9.pdf

http://sitoba.itmaranatha.org/PIB%200809/.../PIB0809-07%2009%2010.pp

http://www.cs.ui.ac.id/WebKuliah/IKI30320/.../iki30320_20070924_hand

of 98


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%20a%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

http://muhyi.hostei.com/media/blogs/paper/ARTIKEL_SNASTI_MUHYI_Revisi.pdf

of 98


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. Agen Berbasis Logika 4. Logika Proposisi 5. Metode Pembuktian 6. Latihan

1. PENDAHULUAN 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

Inference engine Domain-independent algorithms

Knowledge engine Domain-specifics content

6

LO

GIC

AL A

GE

NTS

MODUL

of 98


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

of 98


- 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

of 98


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:

of 98


- 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

of 98


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)

of 98


- 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 checking

o Penjabaran truth table (sehingga dihasilkan nilai eksponensial dalam n) o Backtracking lebih efisien, misalkan: algoritma DPLL

o Heuristic search dalam model space (sound tetapi incomplete), misalkan : min-conflicts 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:

of 98


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


Jersey

of 98


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

of 98


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.

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.PENDAHULUAN 1.1.Pengantar 1.2.Tujuan 1.3.Definisi 1. FIRST ORDER LOGIC 2.1 Definisi First Order Logic 2.2 Sintaks First Order Logic

2.3 Semantik 2.4 Quantifier 2.5 Equality 2.6 Inferensi pada First Order Logic 2. CONTOH 3. PROPAGASI 4.1 Pertanyaan/Latihan Soal 4.2 Diskusi 4.3 Project

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

MODUL

7

First Ord

er Log

ic

of 98


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 Ontological Epistemolog

ical Propositiona

l logic

Facts True/false/unk

nown

First-order

logic

Facts, objects,

relations

True/false/unk

nown

Temporal

logic

Facts, objects,

relations, times

True/false/unk

nown

Probability

theory

Facts Degree of

believe 0…1

Fuzzy logic Degree of truth Degree of

believe 0…1

of 98


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 :

of 98


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), Memberi(Andi,Budi,KueCoklat),

Saudara(Andi)=Budi, dan sebagainya.

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

of 98


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

of 98


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)]

of 98


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 :

)},/({SUBST

gv

v

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:

)},/({SUBST

kv

v

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 :

)},/({SUBST

vgv

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.

of 98


– Andi tidak pernah hadir kuliah matakuliah kalkulus.

• Kedelapan pernyataan di atas dapat dibawa ke bentuk logika predikat :

1. mahasiswa(Andi) 2. Elektro(Andi)

3. ∀x: Elektro(x) ->Teknik(x)

4. sulit(Kalkulus)

5. ∀x: Teknik(x) ->suka(x, Kalkulus) ∨benci(x, Kalkulus)

6. ∀x:∃y : suka(x,y)

7. ∀x: ∀y: mahasiswa(x) ∧sulit(y) ∧~hadir(x,y) ->~suka(x,y)

8. ~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 :

of 98


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

of 98


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


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.

1.2 Tujuan


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

8

LO

GIC

PR

OG

RA

MM

IN

G

MODUL

of 98


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

http://www.swi-prolog.org/

of 98


o 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).

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)

#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).

of 98


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.

of 98


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


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

UN

CE

RT

AIN

TY

(KE

TID

AK

PA

ST

IAN

)

MODUL

9

of 98


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

of 98


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 (9.1)

dimana : 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) = 1/6 P(2) = 1/6 P(3) = 1/6

P(4) = 1/6 P(5) = 1/6

P(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.

of 98


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 :

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

B1

B2

B3

A Bn

A Bn

of 98


•Ukuran kepercayaan dan ketidapercayaan didefinisikan dalam probabilitas sebagai berikut :

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

of 98


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

Contoh : Diketahui ekspresi logika untuk penggabungan evicence E=(E1

ANDE2 AND E3) OR (E4 AND NOT E5). Evidence E akan dihitung sebagai berikut :E = max [min(E1,E2,E3), min

(E4,-E5)] Jika diketahui : E1 = 0.9E2= 0.8E3 = 0.3E4 = -0.5 E5 = -0.4 Maka hasilnya :E = max [min(0.9;0.8;0.3), min (-0.5;(-0.4))]E = max[0.3;-

0.5]

Rumus dasar untuk CF dari kaidah

IF E THEN H

adalah : CF(H,e) = CF(E,e) CF(H,E)

Dimana : 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

Evidence Ketidakpastian anteseden

E1 AND E2

E1 AND E2

NOT E

Min[CF(H,E1), CF(H,E2)]

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

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

of 98


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. Pertanyaan / Latihan Soal (Evaluasi Mandiri)

1. Apa yang dimaksud teorema ketidakpastian ? 2. Apa peran teorema ketidakpastian dalam Kecerdasan Buatan ?

3. Bagaimana cara menerapkan teorema ketidakpastian dalam aplikasi ? 4. 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

of 98


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

of 98


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


2. Sintak Bayesian Network 3. Semantik Bayesian Network


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.

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

Ba

yesian

Netw

ork

MODUL

10

of 98


bersyarat, sebagai berikut:

Gambar 10.1 Hubungan antar variabel

o Weather adalah bebas (independent) atas variabel-variabel lain.

o 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

of 98


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. 25-1 = 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

of 98


- 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)?

of 98


- 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 Prentice-Hall Education International. New Jersey

PROPAGASI Latihan dan Diskusi

1. Jelaskan konsep dasar dari Bayesian Network! 2. Jelaskan secara ringkas sintak dari Bayesian Network! Beserta komponen-

komponen 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

of 98


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]


2. Learning

3. Latihan

1.PENDAHULUAN

1.1 Pengantar 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 masing-masing 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.

LE

AR

NIN

G

MODUL

11

mailto:[email protected]

of 98


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

of 98


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

of 98


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

LAMPIRAN

BIODATA KETUA

Nama lengkap : Dian Eka Ratnawati, S.Si, M.Kom

Fakultas : PTIIK Jurusan/Program Studi :Informatika/Ilmu Komputer

Alamat koresponden :Jl Akordion, Perum Bumi Tunggul Wulung Indah M3 Malang Telepon/Fax : 0341-9442404 Nomor HP : 082143517901

Email :[email protected]

Riwayat Pendidikan

No Tahun lulus Perguruan

Tinggi

Bidang Spesialisasi

S1 1997 ITS Matematika/bid studi Informatika

S2 2002 ITS Teknik Informatika

S3 -

Nama Mata Kuliah yang diasuh

No Nama Mata Kuliah Strata

1 Kecerdasan Buatan S1

2 Basis data S1

3 Data Mining S1

4 Algoritma Genetik 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 Run-Length-Encoding (RLE), shannon-fannodan Lempel-Ziv-Welch (LZW)

3 2010 Teknikkompresicitramenggunakandekomposisi nilaisingulirberbasisblok

4 2011 Modifikasikodekarakteruntukkompresi Half-Byte berdasarkanfrekuensipasanganpolamaksimal

5 2012 Pengembanganmetodeklasifikasiuntukoptimalisasianggotakelasdengan

menggunakan K-Means

6 2012 PengembanganMetodeKlasifikasiberdasarkan K-Means dan LVQ

of 98

Kecerdasan Buatan 2012 Brawijaya University

Pengalaman publikasi di berkala ilmiah 5 tahun terakhir

Nama

Penulis

Tahun

Terbit

Judul Artikel Nama

Berkala

Volume

dan

halaman

Status

akreditasi

Dian Eka

Ratnawati,

Marji -,

Dewi Yanti

Liliana

2011 Optimasi Kompresi File

Dengan Menggunakan

Gabungan Metode Run-

Length-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

Pointer –

Ilmu

Komputer

Vol 2, No

2

halaman

Belum

terakreditasi

of 98


BIODATA ANGGOTA

Nama lengkap : Dewi Yanti Liliana, S.Kom, M.Kom Fakultas : Program Teknologi Informasi dan Ilmu Komputer

Jurusan/Program Studi : Informatika/Ilmu Komputer Alamat koresponden : Jl. Yupiter No. 10 Malang Telepon/Fax : 0341 554204

Nomor HP : 081218769796 Email : [email protected]

Riwayat Pendidikan

No Tahun lulus Perguruan

Tinggi Bidang

Spesialisasi

S1 2004

ITS Teknik Informatika

S2 2009

Universitas Indonesia

Ilmu Komputer

S3




2 Pengenalan Pola S1

3 Analisis dan Desain Algoritma S1

4 Struktur Data dan Algoritma S1


Strata Jumlah

S1 40

S2

S3


No Tahun Topik/judul

penelitian

1 2010 Teknik Kompresi citra menggunakan dekomposisi nilai

singulir berbasis blok.

2 2012 Deteksi Wajah

menggunakan Fast Fourier Transformatioan

of 98



Nama

Penulis

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

Behaviometrics

for Information

Security and

Authentication

System using

Dynamic

Keystroke

IJCSIS Volume 10

No.1

Dewi Yanti

Liliana,

Eries Tri

Utami

2012 The

combination of

palm print and

hand geometry

for biometrics

palm

recognition

IJViPNS Volume 12

No. 1

of 98


BIODATA ANGGOTA

Nama lengkap : Lailil Muflikhah, S.Kom., M.Sc.

Fakultas : Program Teknologi Informasi dan Ilmu Komputer

Jurusan/ Program Studi : Informatika

Alamat koresponden : Gedung A PTIIK, Jl. Veteran No.8 Malang

Telepon/Fax : +62 341577911/ +62 341577911

Nomor HP : 08123220198

Email : [email protected]

Riwayat Pendidikan

No Tahun lulus Perguruan Tinggi Bidang

Spesialisasi

S1 1998 ITS Surabaya

S2 2010 UTP Malaysia IT – Data Mining

S3



1 Data Mining S1


3 Teknk Kompilasi S1

4 Sistem Pakar S1

5 Sistem Basis Data S1

6 Algoritma dan Struktur Data 1 S1

7 Teori Bahasa & Automata S1


Strata Jumlah

S1 50

S2

S3



1 2007 Pencarian dan Pengklasifikasian Susunan Kata pada Dokumen Teks

2 2011 Modifikasi Kode Karakter Untuk Kompresi Half-Byte Berdasarkan

Frekuensi Pasangan Pola Maksimal

3 2012 Penggalian Data dalam Penentuan Keterkaitan Topik pada Terjemahan

Ayat-Ayat Al-Qur’an

4 2012 Pengembangan Metode Klasifikasi berdasarkan K-Means dan LVQ

of 98



Nama

Penulis

Tahun

Terbit

Judul Artikel 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.685-

692

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 C-

Means Clustering untuk

Pengklasteran Dokumen

Jurnal SISTEM,

Fakultas Teknik

Universitas

Wisnu Wardana

Vol. 7 No.

1, hal 20-

29

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

of 98


BIODATA ANGGOTA

Nama lengkap : Rekyan regasari MP

Fakultas : Program Teknologi Informasi dan Ilmu Komputer

Jurusan/Program Studi : Informatika/Ilmu Komputer

Alamat koresponden : Mutiara Jingga 38 Malang

Telepon/Fax : 0341-9503432

Nomor HP : 08123125356

Email : [email protected]

Riwayat Pendidikan

No Tahun lulus Perguruan Tinggi Bidang

Spesialisasi

S1 2002 ITS-Surabaya Elektronika

S2

2010

Universitas

Brawijaya

Sistem

Komunikasi dan

Ilmu Komputer –

Komputasi Cerdas

S3



1 Probabilitas Statistik S1

2 Matematika Komputasi S1



Strata Jumlah

S1 2

S2

S3



1 2010 Decision Support System Penentuan Penerima Bantuan

Pemerintah dengan integrasi Metode Group Technology dan

Decision Table

2 2011 Sistem Informasi Kelurahan


Nama

Penulis

Tahun Terbit Judul Artikel Nama

Berkala

Volume dan

halaman

Status

akreditasi

Rekyan

Regasari MP

2011 Metode Group

technology pada

Perancangan

perangkat Lunak

Portable Bio

Electromyograph

Jurnal

Teknologi

Informasi

Vol 1, Hal 95

- 189

ISSN:2086-

2989

modul bahan-ajar-kecerdasan-buatan-ptiik-final

Presentations & Public Speaking