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
Page 1 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
Page 2 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
DAFTAR ISI
KATA PENGANTAR ....................................................................................... 0
DAFTAR ISI ..................................................................................................... 2
PENGANTAR KECERDASAN BUATAN ......................................................... 4
1. PENDAHULUAN ................................................................................................................................................................ 4
2. DEFINISI KECERDASAN BUATAN........................................................................................................................... 4
3. FONDASI ILMU KECERDASAN BUATAN .............................................................................................................. 6
4. SEJARAH KECERDASAN BUATAN ........................................................................................................................... 7
5. CONTOH APLIKASI KECERDASAN BUATAN ...................................................................................................... 8
AGEN CERDAS .............................................................................................. 9
1. PENDAHULUAN ................................................................................................................................................................ 9
2. KONSEP AGEN CERDAS DAN LINGKUNGAN ..................................................................................................... 9
3. KONSEP PERANCANGAN AGEN CERDAS ......................................................................................................................... 10
4. JENIS LINGKUNGAN ........................................................................................................................................................... 11
5. JENIS AGEN .......................................................................................................................................................................... 12
PENYELESAIAN PROBLEM DENGAN PENCARIAN (SEARCHING) ........... 16
1. PENDAHULUAN .............................................................................................................................................................. 16
2. JENIS PROBLEM ............................................................................................................................................................. 16
3. FORMULASI PROBLEM ............................................................................................................................................... 17
4. ALGORITMA PENCARIAN DASAR ......................................................................................................................... 19
5. STRATEGI PENCARIAN UNINFORMED .............................................................................................................. 20
PENCARIAN HEURISTIK / INFORMED SEARCH ....................................... 25
1. PENDAHULUAN .............................................................................................................................................................. 25
2.GENERATE AND TEST ................................................................................................................................................... 26
3.HILL CLIMBING ............................................................................................................................................................... 27
4.BEST FIRST SEARCH ..................................................................................................................................................... 32
CONSTRAINT SATISFACTION PROBLEM .................................................. 40
1. PENDAHULUAN .............................................................................................................................................................. 40
2. KOMPONEN CSP ............................................................................................................................................................. 41
3. BACKTRACKING ............................................................................................................................................................. 42
4. FORWARD CHECKING ................................................................................................................................................. 45
5.CONSTRAINT PROPAGATION .................................................................................................................................. 46
6.ARC CONSISTENCY ....................................................................................................................................................... 46
Page 3 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
LOGICAL AGENTS ....................................................................................... 51
1. PENDAHULUAN .............................................................................................................................................................. 51
2. AGEN BERBASIS PENGETAHUAN (KNOWLEDGE-BASED AGENT) ............................................................................. 52
3. AGEN BERBASIS LOGIKA ................................................................................................................................................... 54
FIRST ORDER LOGIC ................................................................................... 60
1.PENDAHULUAN................................................................................................................................................................ 60
2. FIRST ORDER LOGIC ................................................................................................................................................... 61
3. CONTOH.............................................................................................................................................................................. 66
4. PROPAGASI ...................................................................................................................................................................... 68
LOGIC PROGRAMMING .............................................................................. 69
1. PENDAHULUAN .............................................................................................................................................................. 69
2. PARADIGMA PEMROGRAMAN ............................................................................................................................................ 69
3. LOGIC PROGRAMMING IN PROLOG ................................................................................................................................. 70
4. APLIKASI PEMROGRAMAN LOGIKA ................................................................................................................................. 73
UNCERTAINTY (KETIDAKPASTIAN) ........................................................ 74
1. PENDAHULUAN .............................................................................................................................................................. 74
2.UNCERTAINTY ................................................................................................................................................................. 75
3. CONTOH.............................................................................................................................................................................. 79
BAYESIAN NETWORK ................................................................................ 82
1. PENDAHULUAN .............................................................................................................................................................. 82
2. SINTAK BAYESIAN NETWORK ............................................................................................................................... 82
KECERDASAN BUATAN:LEARNING ........................................................... 87
1.PENDAHULUAN................................................................................................................................................................ 87
2. LEARNING (PEMBELAJARAN) ................................................................................................................................ 88
3.PROPAGASI ....................................................................................................................................................................... 90
LAMPIRAN .............................................................................................. 91
Page 4 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 5 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 6 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
eksperimen psikologi. Jika kita punya cukup pengetahuan tentang teori pikiran, maka sangat memungkinkan mengekspresikan teori tersebut dalam program komputer.
Pada era 1960an muncul ilmu kognitif sebagai suatu bidang interdisipliner yang menggabungkan model komputer pada AI dengan teknik eksperimen pada psikologi untuk
membangun teori tentang cara kerja otak manusia. Ahli komputer menyatakan bahwa algoritma komputer yang berjalan baik dalam menyelesaikan suatu masalah merupakan model proses berpikir manusia. Pada akhirnya
bidang AI terpisah dari psikologi kognitif. Kedua bidang tersebut saling mendukung khususnya pada ranah computer vision dan pemrosesan bahasa alami.
3. Sistem yang berpikir rasional (think rationally)
“Seni menciptakan mesin yang dapat mengerjakan fungsi yang membutuhkan kecerdasan
jika dikerjakan oleh manusia.” (Kurzweil, 1990)
“Laws of thought” = pendekatan penalaran
Filosofis Yunani, Aristotles adalah orang pertama yang berupaya mengkodekan “berpikir dengan benar” atau melalui proses penalaran (reasoning). Proses ini dikenal dengan silogisme, yaitu suatu struktur/pola memberikan argument melalui sekumpulan premis yang
akan selalu memberikan konklusi yang benar. Contoh silogisme:
Premis 1: Socrates adalah manusia Premis 2: Semua manusia bisa mati Konklusi: Socrates bisa mati
Ilmu yang mempelajari pendekatan penalaran ini disebut Logika. Para ahli logika di abad ke-19 membangun notasi standar logika untuk menyatakn
seluruh kejadian di dunia beserta relasinya. Ada beberapa hambatan pada pendekatan logika yaitu:
1. Tidak mudah untuk memperoleh pengetahuan informal dan menyatakannya dalam
istilah formal (notasi logika). 2. Mekanisme logika membutuhkan biaya komputasi yang tinggi.
3. Pemecahan masalah "pada prinsipnya" ≠ pemecahan masalah dalam praktek.
4. Sistem yang bertindak rasional (act rationally)
“AI berfokus pada perilaku cerdas pada suatu alat.” (Nilsson, 1998)
Pendekatan agen rasional. Agen adalah sesuatu yang dapat melakukan tindakan. Agen kecerdasan buatan
diharapkan dapat melakukan tindakan yang membedakannya dari program komputer biasa. Tindakan tersebut seperti operasi otonom, mempersepsikan (merasa) lingkungannya, adaptif terhadap perubahan, dan bisa mencapai suatu tujuan. Agen rasional adalah agen yang dapat
bertindak untuk mencapai hasil yang terbaik (memaksimalkan tercapainya goal/tujuan).
3. FONDASI ILMU KECERDASAN BUATAN Ilmu kecerdasan buatan merupakan kontribusi dari berbagai disiplin ilmu, tidak eksklusif dari bidang komputer saja. Fondasi ilmu yang membentuk kecerdasan buatan yaitu:
1. Filsafat: Pikiran adalah seperti mesin Menggunakan pengetahuan untuk mengoperasikan sesuatu
Pemikiran digunakan untuk mengambil tindakan
2. Matematika Alat untuk memanipulasi pernyataan logis Memahami perhitungan
Page 7 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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)
Page 8 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
- 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
Page 9 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Kecerdasan Buatan:
AGEN CERDAS
Dian Eka Ratnawati, S.Si, M.Kom,Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc,Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya, Email : [email protected]
1. Pendahuluan 1.1. Pengantar 1.2. Tujuan
2. Konsep Agen Cerdas dan Lingkungan
3. Konsep Perancangan Agen Cerdas
4. Jenis Lingkungan 5. Jenis Agen
1. PENDAHULUAN 1.1 Pengantar
Pada bagian ini dapat kita lihat bahwa konsep rasionalitas dapat diterapkan pada lingkungan yang luas. Pembahasan pada bagian ini meliputi konsep agen dan lingkungannya. Selain itu juga akan
dipelajari prinsip mendesain agen cerdas yang benar, berdasarkan jenis lingkungan serta jenis agen.
1.2 Tujuan
Penguasaan materi dalam modul ini dirancang agar mahasiswa mampu untuk :
Mengetahui konsep agen cerdas dan lingkungan agen cerdas. Mengetahui konsep PEAS (Performance measure, Environment,
Actuators, Sensors) untuk merancang agen cerdas.
Mengetahui jenis lingkungan dan jenis agen cerdas.
2. KONSEP AGEN CERDAS DAN LINGKUNGAN Agen adalah segala sesuatu yang dapat dipandang sebagai
entitas pada suatu lingkungan yang mengamati melalui alat sensor dan bertindak melalui alat aktuator.
Sebagai perbandingan, agen manusia memiliki alat sensor:
mata, telinga, dan organ sensor lainnya; alat actuator: tangan, kaki, mulut, dan bagian tubuh lain sebagai alat gerak.
Sedangkan pada agen robot: kamera dan inframerahi untuk sensor, danlengan, serta berbagai motor sebagaiaktuator.
Agen menerima (percept) sensor dari lingkungan. Keseluruhan
percept yang diterima agen pada suatu selang waktu disebut percept sequence.
Hubungan antara agen dan lingkungan dan digambarkan seperti pada gambar 2.1.
AG
EN
CER
DA
S
MODUL
2
Page 10 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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,
Page 11 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 12 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
• Dunia nyata (tentu saja) secara parsial diamati, stokastik, sekuensial, dinamis, terus menerus, multi-agen.
5. Jenis Agen Empat jenis dasar agen terurut dari yang paling umum ke khusus:
Agen refleks sederhana: Agen memilih tindakan berdasarkan persepsi saat ini,
mengabaikan sisa sejarah persepsi. Agen reflex berbasis model: Agen mempertahankan state internal yang bergantung
pada sejarah persepsi, mencerminkan beberapa aspek teramati dari kondisi saat ini.
Agen berbasis tujuan: Agen memiliki informasi tentang tujuan dan memilih tindakan untuk mencapai tujuan
Agen berbasis utilitas: Agen menyatakan/menetapkan pengukuran kuantitatif terhadap lingkungan (ranking). Pemilihan tindakan yang rankingnya paling tinggi (paling dekat mencapai tujuan).
Agen berbasis pembelajaran: Agen belajar dari pengalaman, dapat beradaptasi untuk meningkatkan kinerja.
Penjelasan:
1. Agen refleks sederhana (Simple Reflex Agent)
Gambar 2.2. Simple Reflex Agent
Agen Refleks Sederhana:
Aturan kondisi-tindakan: Kondisi yang memicu beberapa tindakan ex. Jika mobil di depan mengerem (kondisi) kemudian memulai pengereman
(tindakan)
Agen refleks Sederhana sederhana namun sangat terbatas kecerdasannya. Menghubungkan percept ke tindakan.
keputusan yang benar dapat dibuat hanya dalam lingkungan yang penuh teramati.
Simple Reflex Agent
function SIMPLE-REFLEX-AGENT (percept) return an action
static: rules, a set of condition-action rules
state INTERPRET-INPUT (percept)
rule RULE-MATCH(state,rules)
action RULE-ACTION[rule]
return action
Page 13 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
o INTERPRET-INPUT merupakan fungsi yang menghasilkan deskripsi dari kondisi saat ini dari percept.
o RULE-MATCH merupakan fungsi yang mengembalikan aturan pertama dalam seperangkat aturan yang cocok dengan deskripsi yang diberikan oleh suatu state.
2. Agen Berbasis Model
Gambar 2.3. Model berbasis Agen
Cara yang paling efektif untuk menangani pengamatan parsial adalah melacak bagian
dari dunia yang bisa teramati saat ini (current state). Agen mempertahankan keadaan internal yang bergantung pada sejarah persepsi dan
dengan demikian mencerminkan beberapa aspek teramati dari kondisi saat ini.
Untuk memperbarui informasi keadaan internal memerlukan dua pengetahuan: o Bagaimana dunia berkembang secara independen dari agen
o Bagaimana tindakan agen memengaruhi dunia Pengetahuan tentang "bagaimana dunia bekerja" disebut model
Agen berbasis Model:
function REFLEX-AGENT-WITH-STATE (percept) return an action
static: state, a description of the current world state
rules, a set of condition-action rules
action, the most recent action, initially none
state UPDATE-STATE (state,action,percept)
rule RULE-MATCH(state,rules)
action RULE-ACTION[rule]
return action
o UPDATE-STATE menciptakan keadaan internal baru
Page 14 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
3. Agen Berbasis Goal
Gambar 2.4. Goal based agent
Mengetahui tentang keadaan saat ini saja tidak selalu cukup untuk memutuskan apa yang harus dilakukan.
Agen membutuhkan informasi tujuan (goal) yang menggambarkan situasi yang diinginkan
4. Agen berbasis Utilitas
Gambar 2.5. AgenberbasisUtilitas
Mencapai tujuan saja tidak cukup untuk menghasilkan perilaku berkualitas tinggi perilaku dalam lingkungan.
Seberapa cepat? Seberapa aman? Bagaimana murah? Dapat diukur Fungsi Utilitas memetakan state ke bilangan real (ukuran kinerja)
Page 15 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
5. Agen berbasis Pembelajaran
Gambar 2.6. AgenberbasisPembelajaran
Elemen learning bertanggung jawab untuk membuat perbaikan Elemen Kinerja bertanggung jawab untuk memilih tindakan eksternal Kritik memberikan umpan balik tentang bagaimana tindakan yang dilakukan agen
REFERENSI
Russell, Stuart; dan Norvig, Peter. 2003. Artificial Intelligence A Modern Approach.
International Edition, Edisi 2. Pearson Prentice-Hall Education International. New
Jersey
Rangkuman Agen berinteraksi dengan lingkungan melalui sensor dan aktuator
Fungsi agen menjelaskan apa yang dilakukan agen dalam segala situasi Ukuran kinerja mengevaluasi lingkungan agen
Sebuah agen rasional memaksimalkan kinerja yang diharapkan Agen program mengimplementasikan (beberapa) agen fungsi Deskripsi PEAS membantu mendefinisikan agen cerdas dan lingkungannya
Lingkungan dikategorikan menjadi beberapa dimensi bergantung pada 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!
Page 16 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Kecerdasan Buatan: Penyelesaian Problem dengan Pencarian (searching) Dian Eka Ratnawati, S.Si, M.Kom, Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc, Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya
1. Pendahuluan 1.1. Pengantar 1.2. Tujuan
2. Jenis Problem 3. Formulasi Problem
4. Algoritma Pencarian Dasar 5. Strategi Pencarian Uninformad
1. PENDAHULUAN 1.1 Pengantar
Pada bagian ini dibahas agen cerdas penyelesaian problem, serta strategi uninformed untuk memecahkan masalah. Terdapat
beberapa teknik yang termasuk dalam strategi pencarian uninformed.
1.2 Tujuan
Penguasaan materi dalam modul ini dirancang agar mahasiswa mampu untuk :
Mengetahui jenis problem/masalah Dapat memformulasi problem Mengetahui contoh penyelesaian problem
Mengetahui strategi pencarian tanpa informasi (uninformed)
2. JENIS PROBLEM
Agen penyelesaian problem adalah jenis agen berbasis tujuan/goal.
Agen berbasis tujuan memutuskan apa yang harus dilakukan dengan menemukan urutan tindakan yang mengarah ke state yang paling diinginkan.
Tahapan penting/utama adalah perumusan tujuan dan perumusan masalah.
Searching merupakan mekanisme yang menggunakan masalah sebagai masukan dan mengembalikan solusi dalam bentuk urutan tindakan.
Eksekusi didasarkan pada algoritma pencarian yang digunakan.
Pen
yele
saia
n P
ro
ble
m d
en
gan
Pen
caria
n (
search
ing
)
MODUL
3
Page 17 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 18 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
states? Letak kotoran dan lokasi robot
actions?Left, Right, Suck goal test?Tidak ada kotoran sama sekali di semua lokasi
path cost? 1 per action 2. The 8-puzzle Problem
Gambar 3.3. Problem 8-puzzle
states?Lokasi setiap kotak nomor
actions? move, blank, left, right, up, down goal test? = goal state (terdapat pada gambar) path cost? 1 per move
3. 8-Queens Problem
Gambar 3.4. 8-Queens Problem
states?Papan catur dengan n queens (n= 1…8)
actions? move, left, right, up, down goal test? = 8 queens pada posisi yang benar, tidak ada yang saling serang
path cost? 1 per move 4. Robotic assembly
Gambar 3.5. Robotic assembly
states?: Nilai riil koordinat robot joint angles actions?: gerakan kontinyu robot joints
goal test?: complete assembly path cost?: waktu eksekusi
Page 19 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
4. ALGORITMA PENCARIAN DASAR
Ide dasar: Eksplorasi secara offline , simulasi state space dengan menghasilkan turunan (successor) dari state yang sudah dieksplorasi (dikenal sebagai expanding state).
Algoritma pencarian dasar:
General tree search
Contoh Tree untuk permasalahan Tur Rumania:
Gambar 3.6. Tree untuk tur Rumania
Implementasi: state vs node
Sebuah state adalah (representasi) konfigurasi fisik
Sebuah node adalah sebuah struktur data yang merupakan bagian dari tree pencarian meliputi state, parent node, tindakan, jalur biaya g (x), dan kedalaman.
Fungsi Expand menciptakan node baru, mengisi berbagai bidang dan menggunakan SuccessorFn dari masalah untuk menciptakan state yang sesuai.
Page 20 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Gambar 3.7. Implementasi state vs node
5. STRATEGI PENCARIAN UNINFORMED
Sebuah strategi pencarian didefinisikan dengan memilih urutan ekspansi node.
Strategi dievaluasi sepanjang dimensi berikut: o kelengkapan: apakah selalu mencari solusi jika ada?
o kompleksitas waktu: jumlah node yang dihasilkan o kompleksitas ruang: jumlah maksimum node dalam memori o optimalitas: apa selalu menemukan solusi yang paling murah?
kompleksitas waktu dan ruang diukur dalam hal: b: faktor percabangan maksimum search tree
d: kedalaman solusi yang paling murah m: panjang maksimum setiap path (mungkin ∞)
Strategi pencarian uninformed hanya menggunakan informasi yang tersedia dalam definisi
masalah. Terdapat 5 teknik yang termasukstrategi uninformed, yaitu: 1. Breadth-first search
2. Uniform-cost search 3. Depth-first search
4. Depth-limited search 5. Iterative Deepening search
Penjelasan masing-masing adalah:
1. Breadth-first search (BFS)
Memperluas node terdangkal yang belum diekspansi Implementasi:
Urutan ekspansi dari node A – D : A-B-C-D
Properti BFS
Lengkap? Ya (jika b adalah terbatas)
Page 21 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Waktu? 1 1+b+b2+b3+… +bd + b(bd-1) = O(bd+1) Ruang? O(bd+1) (setiap node terus disimpan dalam memori)
Optimal? Ya (jika biaya = 1 per langkah) Ruang adalah masalah yang lebih besar (lebih dari waktu)
2. Uniform Cost Search (UCS)
Sama seperti BFS dengan tambahan pembentukan tree diurutkan berdasarkan cost
yang paling murah/least-cost Urutan ekspansi seperti BFS
Implementasi: tree/queue diurutkan berdasarkan least-cost Lengkap? Ya, jika biaya langkah ≥ ε Waktu? Jumlahnode dengan g ≤ biaya solusi optimal, O(bceiling(C*/ ε))di mana C* adalah
biaya dari solusi optimal Space? Jumlah node dengan g ≤ biaya solusi optimal, O(bceiling(C*/ ε))
Optimal? Ya - node diperluas dalam rangka peningkatan g (n) 3. Depth-first search (DFS)
Pencarian unexpanded node terdalam
Page 22 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Urutan ekspansi dari A ke M: A-B-D-H-I-E-J-K-C-F-L-M
Properti BFS:
Lengkap? Tidak: bisa gagal dalam ruang pencarian takterbatas, ruang pencarian dengan loop
Waktu? O(bm):mengerikan jika m jauh lebih besar daripada d tetapi jika solusi padat, mungkin jauh lebih cepat daripada BFS
Space? O (bm), yaitu, ruang linear!
Optimal? Tidak
4. Depth Limited Search (DLS) • Merupakan strategi DFS dengan batas kedalaman tree l yang didefinisikan sebelumnya. • Rekursif Pelaksanaan DLS:
5. Iterative Deepening Search (IDS)
• Prinsip dari strategi ini adalah melakukan pencarian DLS secara bertahap dengan nilai l yang ditambahkan pada setiap iterasinya. • Strategi ini mengkombinasikan keuntungan BFS dan DFS (kelengkapan dan kompleksitas
ruang linear dijamin). Lakukan pencarian DLS dengan l = 0,1,2, ... sampai tidak cutoff • Ilustrasi:
Page 23 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Properti IDS
Lengkap? Ya Waktu? ((d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd)
Space? O (bd) Optimal? Ya, jika step cost= 1
Ringkasan Strategi Uninformed Search
Gambar 3.8. Ringkasan strategi uninformed search
REFERENSI
Russell, Stuart; dan Norvig, Peter. 2003. Artificial Intelligence A Modern Approach. International Edition, Edisi 2. Pearson Prentice-Hall Education International. New Je rsey
Page 24 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Rangkuman
Perumusan masalah biasanya membutuhkan abstrak pergi rincian dunia nyata untuk
menentukan ruang state yang bisa dieksplorasi. Agen penyelesaian problem dapat memecahkan masalah dan mencapai tujuan melalui
strategi pohon pencarian (searching tree). Berbagai strategi pencarian uninformed: BFS, UCS, DFS, DLS, IDS IDS hanya menggunakan ruang linear dan tidak banyak waktu lebih dari algoritma
uninformed lainnya.
PROPAGASI A. Latihan (evaluasi mandiri)
Formulasikan masalah perjalanan dari Arad ke Bucharest (Lihat Peta Rumania)! desainlah
search treemasalah ini menggunakan kelima strategi uninformed search, kemudian bandingkan total step costnya!
Page 25 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
1. PENDAHULUAN 1.1 Pengantar
Pada modul 4 ini akan dibahas mengenai pencarian
heuristik. Pencarian heuristik (informed search) lebih cepat dan bagus daripada pencarian buta (uninformed search) yang sudah dibahas pada modul 3. Hal ini karena pada pencarian heuristik
ditambahkan informasi tambahan yang bisa berupa bobot, jarak atau yang lain. Informasi tambahan tersebut yang akan
mempercepat dan membantu proses pencarian. Tetapi ada kelemahan dari metode ini yaitu solusi yang dihasilkan bisa jadi
bukan yang terbaik. Ada beberapa pencarian heuristik yang akan dibahas pada modul 4 ini , diantaranya adalah pertama : Bangkitkan - dan -
Uji (Generate and Test), kedua :Pendakian Bukit (Hill Climbing)yang meliputiSimple Hill Climbing dan SteepestAscent
Hill Climbing, kemudian yang terakhir Pencarian Terbaik Pertama (Best First Search) yang meliputi Greedy Best First Search dan Algoritma A*.
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
Page 26 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 27 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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:
Page 28 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 29 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
3. (3,4) tukar urutan posisi kota ke-3 dengan kota ke-4 4. (4,1) tukar urutan posisi kota ke-4 dengan kota ke-1
5. (2,4) tukar urutan posisi kota ke-2 dengan kota ke-4 6. (1,3) tukar urutan posisi kota ke-1 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)
Page 30 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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)
Page 31 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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)
Page 32 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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*
Page 33 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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 :
Page 34 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Gambar 4.8Penyelesaian TSP Romania dengan algoritma Greedy
Properti dari greedy best-first search Complete?Tidak, dapat terjebak dalam looping,contoh: Iasi Neamt Iasi Neamt
Time?O(bm), tetapiheuristikyang baikdapat memberikanperbaikan secara dramatis
Space?O(bm) -- menyimpansemua nodedalam memori
Optimal?Tidak (memperluas jalurbiayaminimal tapitidak bisamenjadi optimal)
4.2. Algoritma A*(Admissible Heuristic )
Berbeda dengan Greedy, algoritma ini akan menghitung fungsi heuristic dengan cara
menambahkan biaya sebenarnya dengan biaya perkiraan. Heuristik adalah kriteria, metoda, atau prinsip-prinsip untuk menentukan
pilihansejumlah alternatif untuk mencapai sasaran dengan efektif.
Nilai heuristik dipergunakan untukmempersempit ruang pencarian Dengan heuristik yang benar, maka A* pasti akan mendapatkan solusi (jika memang
ada solusinya) yang dicari. Dengan kata lain, heuristik adalah fungsi optimasi yang menjadikan algoritma A* lebih
baik dari pada algoritma lainnya.
Namun heuristik masih merupakan estimasi / perkiraan biasa saja,sama sekali tidak ada rumus khususnya. Artinya, setiap kasus memiliki fungsi heuristik yang
berbedabeda. Algoritma A* ini bisa dikatakan mirip dengan algoritma Dijkstra, namun pada algoritma
Dijkstra, nilai fungsi heuristiknya selalu 0 (nol) sehingga tidak ada fungsi yang
mempermudah pencarian solusinya. Metode ini berdasarkan formula fungsi evaluasi:
f(n) = g(n) + h(n) Keterangan : h(n) = biaya estimasi dari node n ke tujuan.
g(n) = biaya path / perjalananuntuk menuju n f(n) = solusi biaya estimasi termurah node n untuk mencapai tujuan.
(Russell, Stuart J and Norvig, Peter, 2003).
Langkah Algoritma A*
1. Masukan node awal ke openlist Loop Langkah – langkah di bawah ini :
a. Cari node (n) dengan nilai f(n) yang paling rendah dalamopen list. Node ini sekarang menjadi current node.
b. Keluarkan current node dari openlist dan masukan ke close list
Page 35 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
c. Untuk setiap tetangga dari current node lakukan berikut : • Jika tidak dapat dilalui atau sudah ada dalam close list, abaikan.
• Jika belum ada di open list . Buat current node parent dari node tetangga ini. Simpan nilai f,g dan h dari node ini.
• Jika sudah ada di open list, cek bila node tetangga ini lebih baik, menggunakan nilai g sebagai ukuran. Jika lebih baik ganti parent dari node ini di openlist menjadi current node, lalu kalkulasi ulang nilai g dan f dari node ini.
Contoh 1:
Dari gambar 4.7, lalukan penemuan jalur terpendek dari Arad menuju ke Bucharet dengan menggunakan menggunakan algoritma A*
Penyelesaian TSP dengan A*
Page 36 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Gambar 4.9Penyelesaian TSP Romania dengan algoritma A*
Contoh 2
Temukan jalur terpendek dari S menuju ke G dengan menggunakan lgoritma A*, pada
Gambar 4.10
Gambar 4.10. Graph dengan informasi biaya dan jarak antar kota
Penyelesaian
Gambar 4.11. langkah 1 dan 2 penyelesaian dengan algoritma A*
Page 37 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Gambar 4.12. langkah 3 penyelesaian dengan algoritma A*
Gambar 4.13. langkah 4 dan 5 penyelesaian dengan algoritma A*
Gambar 4.14. langkah 6 penyelesaian dengan algoritma A*
Page 38 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Gambar 4.15. langkah 7 penyelesaian dengan algoritma A*
Gambar 4.16. langkah 8 penyelesaian dengan algoritma A*
Gambar 4.17. langkah 9(sudah ditemukan jarak terpendek menuju kota G) Jadi jalur terpendek untuk menuju kota G dari S adalah : S- A-B-F-K-G dengan
total jarak 95
Page 39 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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.
Page 40 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 41 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
2. KOMPONEN CSP CSP terdiri dari komponen komponen berikut:
Variabel, yang merupakan penampung dapat diisi berbagai nilai. Constraintyang merupakan suatu aturan yang ditentukan untuk mengatur nilai boleh diisikan ke variabel, atau kombinasi variabel.
Domain yang merupakan kumpulan nilai legal dapat diisi ke variabel.
Solusi/Goal test yang merupakan assignment nilai-nilai dari domain ke setiap variabel tidak ada constraint yang dilanggar.
Solusi adalah penetapan nilai (assignment) terhadap semua variabel sehingga semua syarat dipenuhi CSP dimulai dari solusi kosong dan diakhiri dengan sebuah solusi
yang memenuhi semua constraint (consistent).Pencarian solusi dilakukan dengan mencoba mengisi nilai domain pada setiap
variabel satu demi satu tanpa melanggar constraint, sampai solusi ditemukan.
Contoh CSP: Mewarnai Peta Lakukan pewarnaan pada Peta Gambar 5.1 sehingga pada kota yang
saling berbatasan tidak diperbolehkan mempunyai warna yang sama, dimana hanya disaediakan 3 waarna yang berbeda
Gambar 5.1 PETA
Ketentuan yang harus dipenuhi untuk melakukan pewarnaan PETA
pada gambar 5.1 adalah : Variabel: WA, NT, Q, NSW, V, SA, T Ranah: Di = {red, green, blue}
Syarat: 2 wilayah yang berbatasan harus berbeda warna: WA ≠ NT, NT ≠ SA, . . .
(WA, NT) Є{(red, green), (red, blue), (green, red), (green, blue), . . .}, . . .
Dari Gambar 5.1 tersebut bisa dimungkinkan ada banyak solusi , yang salah satu contoh solusinya seperti pada Gambar 5.2.
Gambar 5.2 Contoh solusi pada perawrnaan PETA
Solusi adalah pemberian nilai setiap variabel yang memenuhi syarat, mis:{WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue,
Page 42 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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.
Page 43 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Langkah tersebut berguna untuk menghindari eksplorasi lebih lanjut dari solusi partial yang salah.
Keuntungan backtracking : pemeriksaan consistency hanya perlu dilakukan terhadap assignment yang terakhir dilakukan karena
pemeriksaan terhadap assignment yang sebelumnya sudah dilakukan sebelumnya.
Pada algoritma backtracking, teknik look ahead digunakan untuk
meramalkan efek pemilihan variabel branching untuk mengevaluasi nilai-nilai variabel tersebut.
Forward checking adalah salah satu cara untuk melakukan look ahead. Forward checking mencegah terjadinya konflik dengan melarang nilai-nilai yang belum diisikan ke variabel untuk
dipakai. Ketika suatu nilai diisikan ke suatu variabel, nilai yang berada di
domain dari variabel yang konflik dengan assignment tersebut akan dihilangkan dari domain.
Backtracking search Variabel assignment berlaku komutatif, dalam arti:[WA=red lalu
NT=green] sama saja [NT=green lalu WA=red] Pada tiap level, hanya perlu meng-assign satu variabel b = d,
ada dn leaf
Depth first search pada CSP dengan assignment satuvariabel tiap level disebut backtracking search.
Algoritma uninformed standar untuk masalah CSP Algoritma Bactracking
Contoh Lakukan pewarnaan peta pada Gambar 5.1 dengan menggunakan
Bactracking
Page 44 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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.
Gambar 5.6 Contoh prinsip 2
Prinsip 3: Least Constraining Value Adalah variabel paling membebasi
Pilih nilai yang menimbulkan batasan kemungkinan nilai variabel lain (yang belum di-assign) yang paling sedikit.
Jika ketiga prinsip ini digunakan, masalah n-queens
Page 45 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
dengan n=1000 bisa diselesaikan!
Gambar 5.7 Contoh prinsip 3
4. FORWARD CHECKING
Cara termudah untuk menghindari konflik isi variabel Melalui forward checking hanya akan dievaluasi constraint antara
variabel saat ini dan variabel berikutnya. Jika suatu nilai dialokasikan untuk variabel saat ini, maka nilai apapun dari
variabel berikutnya yang dapat membawa konflik dari variabel saat ini akan disingkirkan dari domain.
Keuntungannya adalah jika domain dari variabel berikutnya
adalah kosong, maka segera dikeahui bahwa solusi yang terbentuk ternyata salah.
Dengan forward checking, maka pencabangan dari pohon pencarian akan dipangkas lebih awal, dibanding dengan backtracking.
Catat kemungkinan nilai sah untuk semua variabel yang belum 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
Page 46 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Gambar 5.9 Langkah penyelesaian untuk forward checking
5.CONSTRAINT PROPAGATION
Constraint propagation
Forward checking memberikan informasi dari variabel yang dialokasi, namun tidak dapat mendeteksi kegagalan sebelumnya
Gambar 5.10 Pengecekan untuk Constraint propagation
Pada Gambar 5.10 , diketahui NT dan SA berwarna sama yakni biru, padahal NT dan SA tetanggaan, sehingga hal ini tidak diperbolehkan.
Forward checking hanya mempertimbangkan setiap constraint secara terpisah.
Forward checking mem-propagasi (meneruskan) informasi dari variabel yang sudah di-assign ke yang belum. Secara umum, ini
disebut constraint propagation. Namun, tidak semua failure bisa di-deteksi secara dini
6.ARC CONSISTENCY
Arc consistency adalah metode constraint propagation yang lebih canggih. Konsistensi antar constraint dipertahankan.
Arc X Yadalah edge satu arah dari variable X ke Y dalam
constraint graph. Prinsip Con
Prinsip Arc Consistency X Ydikatakan konsisten jika dan hanya jika untuk setiap nilai sah x
dari X ada nilai sah y dari Y.
Page 47 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
sistency
Gambar 5.11Langkah penyelesaian untuk Arc Consistency
Algoritma AC3 Algoritma AC3 melakukan constraint propagation sbb:
Periksa semua arc dalam constraint graph
Jika untuk X Yada nilai sah x dari X sehingga tidak ada nilai sah y dari Y, buang x.
Jika ada nilai x yang dibuang, periksa ulang semua“tetangga” Xdi dalam constraint graph.
Algoritma AC3 ini bisa mendeteksi failurelebih cepat daripada forward checking.
AC3 dapat dijalankan sebagai pra-proses sebelum melakukan
backtracking, atau bisa dijalankan setelah setiap assignment.
Page 48 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Local search untuk CSP
Dalam praktek, local search cocok untuk CSP. State harus lengkap/complete (semua variable harus ter-assign)
tapi boleh melanggar constraint. Operator/action-nya: menukar nilai variabel (reassign).
Pemilihan variable: pilih secara acak variable yang melanggar sebuah constraint.
Pemilihan nilai:
gunakan heuristic minimum conflict: pilih nilai yang melanggar constraint paling sedikit.
Lakukan local search (hillclimb, simulated annealing, genetic algorithm, dll.) meminimalkan h(n) = jumlah
pelanggaran constraint
Perhatian: secara teoritis pendekatan ini tidak dijamin complete.
Contoh :
Local search untuk 4 –queen
State: 4 queen dalam 4 kolom (44= 256 state)
Operator/action: pindahkan menteri dalam kolom Goal test: tidak ada menteri saling makan
Evaluation/fitness function: h(n) = jumlah pasangan queen saling makan
Bisa menyelesaikan 1000000-queens problem!
Gambar 5.12. Langkah penyelesaian untuk Arc Consistency
Page 49 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 50 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 51 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 52 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
1.2 Tujuan Penguasaan materi dalam modul ini dirancang agar mahasiswa
mampu untuk :
Menjelaskan dan memahami tentang definisi dan konsep dasar
agen berbasis pengetahuan Menjelaskan dan memahami tentang definisi dan konsep dasar
agen berbasis logika.
Menjelaskan dan memahami tentang konsep dasar logika proporsisi baik secara sintaks maupun semantik
Menjelaskan dan memahami tentang metode pembuktian dari logika proporsisi
2. Agen Berbasis Pengetahuan (Knowledge-based Agent)
Knowledge Base menyatakan apa yang “diketahui” oleh si agent
Pendekatan deklaratif membangun agent: “beritahu” informasi yang relevan, simpan dalam KB (TELL).
Agen dapat ditanya (atau bertanya diri sendiri) apa yang sebaiknya dilakukan berdasarkan KB (ASK).
Maka sebuah agen berbasis pengetahuan harus bisa: o Mereprentasikan world, state, action, dst. o Menerima informasi baru (dan meng-update representasinya)
o Menyimpulkan pengetahuan lain yang tidak eksplisit (hidden property) o Menyimpulkan action apa yang perlu diambil
- Knowledge Base merupakan o Himpunan representasi fakta yang diketahui tentang lingkungannya o Tiap fakta disebut sentence
o Dinyatakan dalam bahasa formal sehingga bisa diolah o TELL: menambahkan sentence baru ke KB
- Inference Engine merupakan: o Menentukan fakta baru yang dapat diturunkan dari pengetahun yang sudah ada
dalam KB
o Menjawab pertanyaan (ASK) berdasarkan KB yang sudah ada. - Dalam representasi, agent dapat dipandang dari knowledge level: informasi apa yang
diketahui? Misal: sebuah robot “mengetahui” bahwa gedung B di antara gedung A dan gedung C
- Agent dapat dipandang dari implementation level: bagaimana representasi informas yang
diketahuinya? o Logical sentence: di_antara(gdB, gdA, gdC)
o Natural language: “Gedung B ada di antara gedung A dan gedung C” o Tabel posisi koordinat gedung-gedung o Gambar diagram peta (dalam bitmap atau vektor?)
- Pilihan representasi berpengaruh terhadap apa yang bisa dilakukan inference engine - Pada pendekatan deklaratif programmer memberitahu (TELL) agent informasi tentang
environment. - Kalau informasi kurang, agen bisa melengkapinya sendiri.
- Jika dibandingkan dengan pendekatan prosedural: programmer secara eksplisit memrogram agen untuk bertindak.
- Sehingga bagaimana jika program tidak benar, maka akan besar kemungkinan
menyebabkan kesalahan
Page 53 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
- Permasalahannya adalah bagaimana representasi yang tepat, sehingga ada dua hal yang harus memperhatikan dua hal:
o Expressive: bisa menyatakan fakta tentang environment o Tractable: bisa diolah/ diproses inference engine (dengan cepat?)
- Knowledge merupakan kekuatan dari pemrograman secara deklaratif. - Representasi dan penalaran membentuk suatu Intelligence.
Contoh Aturan Permainan dalam Wumpus World
- Performance measure: emas +1000, mati -1000, gerak -1, panah -10
- Environment: Matriks 4x4 ruang dengan initial state [1,1]. Ada gold, wumpus, dan pit yang lokasinya dipilih secara acak.
- Percept terdiri dari: o Breeze: kamar di samping lubang jebakan ada hembusan angin o Glitter: kamar di mana ada emas ada kilauan/ sinar.
o Smell: kamar di samping Wumpus berbau busuk - Action: maju, belok kiri 900,belok kanan 900, tembak panah (hanya 1!), ambil benda
-
Sifat dari Wumpus World:
- Fully observable? Tidak, hanya bisa berpresepsi lokal
- Deterministic? Ya, hasil tindakan jelas dan pasti - Episodic? Tidak, tergantung action sequence
- Static? Ya, gold, wumpus, pit tidak bergerak - Discrete? Ya - Single agent? Ya
Bahasa Representasi Pengetahuan (Knowledge Representation Language)
Menyatakan suatu bahasa yang digunakan untuk menyatakan fakta tentang “dunia”. Suatu bahasa representasi pengetahuan didefinisikan dalam dua aspek, yakni:
1. Sintaks dari bahasa merupakan aturan yang mendefinisikan sentence yang sah dalam bahasa
2. Semantik menyatakan aturan yang mendefinisikan “arti” sebuah sentence, misalkan:
kebenaran sentence dalam dunia ContohKRL dalam bahasa aritmetika
Page 54 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Secara Sintaks dituliskan: x + 2 ≥ y adalah kalimat sah.
x2 + y ≥ bukan kalimat sah. Secara semantik: x + 2 ≥ y benar jika dan hanya jika bilangan x + 2 tidak lebih kecil dari
bilangan y: - x + 2 ≥ y benar dalam “dunia” di mana x=7, y=1 - x + 2 ≥ y benar dalam “dunia” di mana x=0, y=6
Contoh KRL dalam bahasa Indonesia
Secara sintaks dituliskan:
- “Jakarta adalah ibukota Indonesia” adalah kalimat sah.
- “Ibu Indonesia kota Jakarta adalah” bukan kalimat sah.
Maka secara Semantik: “X adalah ibukota Y” benar jika dan hanya jika adalah pusat
pemerintahan negara Y. - “Jakarta adalah ibukota Indonesia” benar dalam “dunia” kita sekarang.
- “Jakarta adalah ibukota Indonesia” salah dalam “dunia” tahun 1948 (Yogya? Bukitinggi?)
3. Agen Berbasis Logika
Logika sebagai Bahasa Representasi Pengetahuan memiliki pengertian:
- Logika sebagai bahasa formal untuk merepresenasikan fakta sedemikian sehingga kesimpulan (fakta baru, jawaban) dapat ditarik.
- Ada banyak metode inference yang diketahui.
- Sehingga kita bisa membangun agent Wumpus World dengan logika: memanfaatkan perkembangan logika oleh ahli matematika, filsafat selama ratusan tahun!
Entailmentdapat diartikan sebagai suatu fakta bisa disimpulkan dari (kumpulan) fakta lain. - KB |= α berarti KB melakukan entailment sentence α jika dan hanya jikaa α true dalam
“dunia” di mana KB true. Contoh:
- KB mengandung dua sentence, yakni “ Anto ganteng” dan “Ani cantik”. - KB |= α1: “Anto ganteng dan Ani cantik” (artinya: hasil entailment bisa berupa kalimat
gabungan dari dua kalimat)
- KB |≠ α2 : “Anto pintar” - x + y = 4 =| 4= x+y
Inferensiatau reasoning merupakan pembentukan fakta (sentence) baru yang meng-entail fakta-fakta lama.
Reasoning bukan dilakukan pada fakta di dunia (berdasarkan semantik), melainkan representasi fakta dalam bahasa representasi pengetahuan si agent (secara sintaks)
Otak manusia melakukan proses reasoning dalam suatu bentuk sintak dapat diilustrasikan
sebagaimana gambar berikut:
Page 55 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
- Model merupakan suatu “dunia” di mana kebenaran suatu sentence bisa diuji. - m adalah model α jika dan hanya jika true di “dalam” m.
- M(α) adalah himpunan semua model dari α. - KB |= α jika dan hanya jika M(KB) subset dari M(α), sehingga bisa dilihat pada ilustrasi
gambar berikut:
Misalkan:
- KB= Anto ganteng dan Ani cantik - α = Anto ganteng
- Hal ini bisa diartikan bahwasanya sentence Anto ganteng lebih luas konotasinya dibandingkan dengan sentence Anto ganteng dan Ani cantik
Entailment dalam Wumpus World bisa diilustrasikan sebagaimana berikut, dengan melihan [1,1] OK, [2,1] Breeze:
Maka model jebakan ada 3 pilihan boolean di [2,1],[2,2],[3,1], dengan 8 kemungkinan model
Page 56 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
KB = pengamatan (percept) + aturan main Wumpus World, maka kita menyatakan apakah
kamar [1,2] aman dengan cara melakukan entailment yang mana dibuktikan dengan menggunakan model checking, yakni memeriksa semua kemungkinan M(KB), M(α1).
Sehingga dari ilustrasi tersebut diatas menunjukkan bahwasannya: M(KB) subset dari M(α1),
sehingga bisa disimpulkan bahwa kamar [1,2] aman.
Lain halnya ketika melakukan pengamatan apakah kamar [2,2] aman, dengan ditunjukkan oleh α2., sehingga terlihat sebagaimana ilustrasi berikut:
Dari gambar tersebut menunjukkan bahwasannya M(KB) bukan subset dari M(α2), sehingga
bisa disimpulkan bahwa KB |≠ α2, dengan kata lain kamar [2,2] tidak aman.
Inferensi merupakan proses atau algoritma yang “menurunkan” fakta baru dari fakta-fakta
lama.
- KB|- iα: sentence α bisa diturunkan dari KB oleh prosedur i - Soundness: idikatakan sound jika untuk semua KB |- i α, KB |= α benar - Completeness: i dikatakan complete jika untuk semua KB |= α, KB |- i α benar
Logika Proposisi
Merupakan logika yang paling sederhana. Sebuah sentence dinyatakan sebagai simbol proposional P1, P2, dst.
Sintaks dari logika proposisi - Jika S adalah kalimat, ⌐S adalah kalimat (negasi)
- Jika S1 dan S2 adalah kalimat S1Ʌ S2 adalah kalimat (conjunction)
- Jika S1 dan S2 adalah kalimat S1 V S2 adalah kalimat (disjunction) - Jika Jika S1 dan S2 adalah kalimat S1→ S2 adalah kalimat (implication)
Page 57 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
- 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:
Page 58 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
- Modus ponen pada Horn form (yang mana lengkap pada Horn KB):
- Horn form bisa digunakan dengan algoritma forward chaining atau backward chaining - Konsep dasar dari algoritma forward chaining adalah aplikasikan rule yang premise-nya
diketahui benar dalam KB, kemudian tambahkan conclusionnya ke dalam KB, ulangi sampai query (Q) terbukti. Sehingga bisa dikatakan kinerja dari forward chaining merupakan metoda bottom up dari fakta menuju konklusi
Misal:
- Sedangkan konsep dasar dari algoritma backward chaining digunakan untuk membuktikan
query q, dengan cara memeriksa q jika sudah diketahui, atau secara rekursif, dengan membuktikan semua premise rule yang conclusion-nya q (dikenal sebagai metode top
down) - Dalam backward chaining ada beberapa hal yang perlu diketahui:
o Menghindari loop: dengan cara memeriksa apakah subgoal yang baru sudah ada
di goal stack o Menghindariperulangan pekerjaan: periksa apakah subgoal yang baru sudah
dibuktikan benar atau sudah dibuktikan salah. - Perbandingan antara Forward dan backward chaining
o Forward chaining adalah pendekatan data-driven, bottom up sehingga
pemrosesan informasi secara tak sadar o Melakukan banyak usaha yang tidak relevan terhadap goal
o Backward chainingadalah pendekatan goal-driven, top-down sehingga pemrosesan inforasi secara sadar
o Kompleksitas BC bisa jauh lebih kecil dari dalam linear ukuran KB
Kesimpulan
- Agen berbasis pengetahuan menggunakan inferensi dan knowledge base untuk menghasilkan informasi baru atau untuk mengambil keputusan
- Konsep-konsep dasar logika sebagai knowledge representation language meliputi: o Sintak: struktur kalimat bahasa formal o Semantik: arti kalimat sebagai kebenaran terhadao model
o Entailment: menyimpulkan kalimat baru yang benar o Inferensi: proses menurunkan kalimat baru dari kalimat-kalimat lama
o Soundness: proses menurunkan hanya kalimat yang di-entail o Completeness: pross menurunkan SEMUA kalimat yang di-entail
- Forward, backward chaining merupakan proses inferensi complete dan linear untuk
Horn form
REFERENSI o Russell, Stuart; dan Norvig, Peter. 2003. Artificial Intelligence A Modern Approach.
International Edition, Edisi 2. Pearson Prentice-Hall Education International. New
Jersey
Page 59 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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.
Page 60 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 61 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 62 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Elemen-elemen dasar terkecil yang dimiliki oleh first order logic adalah sebagai berikut :
Constants
Dituliskan dalam huruf besar seperti A, X, NAMA. Pada simbol konstanta ini,
setiap simbol harus menyatakan secara spesifik objek yang dimaksud. Tetapi,
mungkin saja satu simbol mengacu pada beberapa nama berbeda. Misalnya,
MOBIL bisa mengacu pada MOBIL SEDAN, MOBIL JEEP, dan sebagainya. Oleh
karena itu penulisan simbol konstanta harus dilakukan secara hati-hati agar tidak
terjadi kerancuan atau ambiguitas.
Predicates
Menyatakan relasi khusus dalam suatu model yang menghubungkan antar objek
yang memiliki hubungan. Misalkan Berwarna adalah suatu predicate yang
memiliki beberapa nilai. Contoh : Berwarna(Mobil, Biru), Berwarna(Mobil, Merah),
dan sebagainya.
Functions
Menyatakan relasi yang hanya membutuhkan satu nilai. Karena setiap orang
hanya memiliki satu ayah, maka Ayah merupakan suatu function. Misalkan
Ayah(Boediono, Zaki).
Variables
Dituliskan dalam huruf kecil seperti a, x, s dan sebagainya. Variable ini
menyatakan simbol yang dapat digantikan oleh konstanta apapun dan bersifat
dinamis.
Connectives
Merupakan logika yang menghubungkan di dalam suatu kalimat kompleks seperti
: ∧∨ ¬ ⇒⇔
Equality
Merupakan logika yang membandingkan kesamaan antara dua atau lebih kalimat
yang memiliki kesamaan nilai logika. Equality disimbolkan dengan tanda =
Quantifiers
Terdapat dua quantifier secara umum yaitu Universal quantifier (∀) yang
menyatakan sesuatu yang bersifat umumdan Existential quantifier (∃) yang
menyatakan sesuatu yang berlaku sebagian saja.
2.2 Sintaks First Order Logic
Tata bahasa pada first order logic meliputi :
Terms
Merupakan ekspresi logika yang mengacu pada sebuah objek. Terms bisa berupa
constant, variable, atau function. Penulisan term dapat dilihat pada contoh di
bawah ini :
Page 63 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 64 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
order logic terdiri dari :
Objects : elemen-elemen yang nyata ada pada permasalahan (domain elements)
Relations : hubungan antara elemen-elemen / objek-objek tertentu
Sebuah interpretasi mendefinisikan referent (yang dipetakan) sebagai berikut :
Constant symbols : objects Predicate symbols : relations Functions symbols : functional relations
Kalimat first order logic memiliki maksud kalimat atomik predicate(term1,...,term2)
dikatakan bernilai true dalam model m di bawah unterpretasi i jika dan hanya jika object yang di-refer (term1, ... , term2) di bawah i terhubung oleh relation yang di refer
oleh predicate dalam m.
Ilustrasi pada gambar disamping menggambarkan
komponen-komponen yang ada pada first order
logic. Pada ilustrasi digambarkan bahwa terdapat
orang dan raja. Hubungan keduanya adalah sebagai
saudara satu dengan lainnya. Dari gambar tersebut
dapat dilihat masing-masing komponen adalah
sebagai berikut :
object
Ilustrasi menggambarkan ada seorang raja dan orang biasa, dapat kita ambil
contoh objek yang ada adalah orang, raja, kaki raja dan kaki orang. Objek
memiliki identitas tertentu yang nantinya akan melalui proses logika.
function
function merupakan hubungan yang hanya membutuhkan satu nilai untuk satu
objek, contoh pada ilustrasi adalah kaki digunakan oleh orang untuk berjalan.
relation
menyatakan hubungan antar objek yang memiliki relasi tertentu, pada gambar
ilustrasi terdapat relasi saudara antara orang dan raja.
2.4 Quantifiers
Universal quantifiers
Page 65 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Universal menyatakan logika yang digunakan untuk menunjuk sesuatu yang
bersifat umum. Simbol ∀ yang memiliki makna "untuk semua atau setiap" atau
"for all" terhadap sebuah variabel x yang disimbolkan dengan ∀x berarti bahwa kalimat tersebut berlaku untuk setiap objek x. Contoh permasalahan pada first
order logic yang menggunakan Universal Quantifiers adalah sebagai berikut : Misalkan ada kalimat "Ikhsan adalah anak kecil", kalimat ini akan dinyatakan
sebagai AnakKecil(Ikhsan), dan ada kalimat "Andi suka permen" dinyatakan sebagai Suka(Andi,Permen). Jika kita ingin membuat kalimat "Untuk setiap objek x, jika x adalah anak kecil maka x suka permen". Maka kalimat dapat kita
tuliskan pada bentuk first order logic sebagai:
∀x AnakKecil(x)⇒Suka(x,Permen) kalimat tersebut akan bernilai benar jika dan
hanya jika semua kalimat di bawah ini benar.
AnakKecil(Budi) ⇒Suka(Budi,Permen)∧
AnakKecil(Rahmad)⇒Suka(Rahmad,Permen)∧
AnakKecil(Anton) ⇒Suka(Anton,Permen)∧
Hal-hal yang harus dihindari pada penggunaan Quantifier Universal adalah
penggunaan logika ∧ pada kalimat utama karena akan menimbulkan pengertian
yang ambigu. Existential quantifiers
Existential menyatakan logika yang digunakan untuk menunjuk sesuatu yang bersifat khusus. Artinya hanya beberapa bagian atau sebagian saja dari keseluruhan himpunan. Logika ini merupakan kebalikan dari logika Universal.
Logika ini disimbolkan dengan ∃ yang memiliki makna "There Exist" atau (ada satu atau beberapa). Kita dapat menyatakan kalimat "Ada objek x, jika x adalah
anak kecil maka x suka permen" menjadi first order logic sebagai berikut:
∃x AnakKecil(x) ∧ SukaPermen(x).
Hal-hal yang harus dihindari pada penggunaan Quantifier Universal adalah
penggunaan logika⇒pada kalimat utama karena akan menimbulkan pengertian yang ambigu.
2.5Equality
Equality merupakan pembandingan terhadap dua kalimat atau term yang memiliki
nilai logika true atau false. Kedua kalimat dianggap sama jika memiliki nilai logika
yang sama. Term1 =Term2 akan diinterpretasikan benar jika dan hanya jika memiliki
nilai yang sama. Contoh bentuk dari equality adalah sebagai berikut :
Equality
x,ySaudara(x,y) [(x = y) m,f (m = f)OrangTua(m,x)OrangTua(f,x)OrangTua
(m,y) OrangTua (f,y)]
Page 66 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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.
Page 67 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
– 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 :
Page 68 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
4. PROPAGASI
a. Pertanyaan / Latihan Soal (Evaluasi Mandiri) 1. Bagaimana semantik pada first order logic ?
2. Apa perbedaan inferensi (resolusi) pada logika proposisi dan logika predikat (first order logic) ? Jelaskan !
b. Latihan Soal Pengembangan dan Diskusi
1. Representasikan permainan “Dunia Wumpus” dengan menggunakan first order logic !
2. Dika adalah adik bungsu dari Dede. Dede menikah dengan astuti, dan dari pernikahan mereka lahir anak perempuan bernama Anin. Anin hendak menikah dengan Dika. Buktikan bahwa pernikahan Anin dan Dika tidak sah, dengan
representasi first order logic!
c. PROYEK (Eksplorasi entrepreneurship, penerapan topic bahasan pada dunia nyata) Kembangkan sebuah game dengan representasi first order logic, berkelompok @ 3
orang
REFERENSI Russel &Artificial Intelligence : A Modern Approach (2nd ed.) by Russel & Norvig
Suyanto, ST., MT., Artificial Intelligent : searching, reasoning, planning and learning
Sri Kusumadewi, Artificial Intelligence : Teknik dan Aplikasinya, Graha Ilmu, Yogyakarta, 2003
Giarrantano, J and G.Riley, Expert System : Principle and Programming,4thed, PWS Kent, 2004
Page 69 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Kecerdasan Buatan: LOGIC PROGRAMMING Dian Eka Ratnawati, S.Si, M.Kom,Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc,Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya Email:[email protected]
1. PENDAHULUAN 1.1 Pengantar 1.2 Tujuan
2. Paradigma Pemrograman
3. Logic Programming pada Prolog 4. Aplikasi Logic Programming 5. Latihan
1. PENDAHULUAN 1.1 Pengantar
Logic Programming merupakan paradigma pemrograman deklaratif yang menekankan atas apa yang program lakukan
daripada bagaimana dia akan melakukan. Ketika diterapkan logic programming digunakan suatu bahasa logika untuk
menspesifikasi permasalahan dan kemudian menggunakan suatu prosedur pembuktian untuk melakukan komputasi.
1.2 Tujuan
Penguasaan materi dalam modul ini dirancang agar mahasiswa mampu untuk :
Menjelaskan dan memahami tentang konsep dari berbagai paradigma pemrograman
Menjelaskan dan memahami tentang konsep dari
pemrograman berbasis logika Mampu merancang dan mengaplikasikan program berbasis
logika dari kasus sederhana. Menjelaskan dan memahami beberapa aplikasi dari
pemrograman logika
2. Paradigma Pemrograman
Paradigma pemrograman merupakan suatu pola yang menyajikan
suatuacuan berpikirterhadap pemrograman komputer. Terdapat empat paradigma pemrograman utama:
o Paradigma imperative
o Obyek oriented paradigma o Paradigma fungsional
o Paradigma logika
8
LO
GIC
PR
OG
RA
MM
IN
G
MODUL
Page 70 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Paradigma Imperatif - Komputasi sebagai suatu urutan aksi “ pertama melakukan ini dan berikutya
melakukan itu” - Penekanan pada bagaimana daripada apa yang dikomputasi
o Ketika memecahkan suatu permasalahan, menempatkan pada metoda daripada arti dari permasalahan
- Contoh: bahasa pemrograman Pascal, C, …
Paradigma Object Oriented - Data beserta operasi-operasinya dibungkus dalam obyek
- Objek terhubung dengan cara melewatkan pesan - Objek-objek dikelompokkan dalam kelas-kelas
o Mengijinkan pemrograman atas kelas-kelas (berkebalikan atas pemrograman
objek secara individu) - Contoh: bahasa pemrograman C++, Java,…
Paradigma Fungsional - Berasal dari matematika murni, dengan disiplin ilmu: teori fungsi
o Komputasi didasarkan atas fungsi
o Fungsi memiliki status yang sama dengan yang lainnya (angka-angka, list) Fungsi merupakan nilai kelas utama
Misalkan: Haskell, LISP,... Paradigma Logika
- Mendasarkan pada matematika logika
- Secara khusus keterkaitan diantara nilai-nilai data - Menggunakan fakta dan aturan-aturan untuk mendefinisikan dasar pengetahuan
- Mengajukan pertanyaan terhadap lingkungannya.
3. Logic Programming in Prolog
Sejarah singkat - Pemrograman Logika diperkenakan oleh Robert Kowalski pada tahun 1974 - Algoritma tersusun atas Logika dan kontrol
Prolog
- Merupakan pemrograman dalam logika - Bahasa pemrograman yang menggunakan pemrograman logika untk komputasi - Diperkenalkan oleh Alain Colmerauer pada tahun 1970 an
- Imprementasi Prolog yang digunakan SWI Prolog versi 5.6.32 - Bebas melakukan download di URL: http://www.swi-prolog.org/
- Dikembangkan oleh Jan Wielenmaker, Universitas Amsterdam - Ada berbagai implementasi lain seperti: SICStus Prolog, XSB, dsb.) - Contoh 1 dari Paradigma Pemrograman Logika
o Menyiapkan database untuk koneksi penerbangan Adakah suatu penerbangan langsung dari A ke B?
Dapatkah saya terbang dari C ke D? Tujuan apa saja yang mungkin dapat saya capai dari E?
dst. o Daftar penerbangan langsung
direct(jakarta,denpasar).
direct(jakarta,surabaya).
direct(denpasar,mataram).
direct(mataram,kupang).
Page 71 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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).
Page 72 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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).
Page 73 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
animal(bird,sparrow,scavenger,small).
animal(reptile,snake,carnivore,long).
animal(reptile,lizard,scavenger,small).
Kemudian jika diberikan beberapa pertanyaan berikut: a) Temukan semua binatang yang termasuk mamalia
(mammal)? b) Temukan semua binatang karnivora yang mamalia? c) Temukan semua binatang mamalia yang berstrip?
d) Apakah ada binatang reptil yang memiliki bulu di tengkuknya (mane)?
Maka bisa diberikan bentuk perintah query dalam prolog sebagai berikut: a) animal(mammal,X,Y,Z). b) animal(mammal,X,carnivore,Z). c) animal(mammal,X,Y,stripes). d) animal(reptile,X,Y,mane).
4. Aplikasi Pemrograman Logika Beberapa aplikasi dalam pemrograman logika bisa diterapkan sebagaimana berikut:
- Reasoning Agents
- Semantic Web - Natural Language Processing
- Security Protocol Analysis - Molecular Biology
REFERENSI
Russell, Stuart; dan Norvig, Peter. 2003. Artificial Intelligence A Modern Approach. International Edition, Edisi 2. Pearson Prentice-Hall Education International. New Jersey
PROPAGASI Latihan dan Diskusi
1. Jelaskan konsep dasar dari paradigma pemrograman, jelaskan perbedaan dari
keempat paradigma tersebut! 2. Tuliskan struktur dasar dari pemrograman berbasis logika menggunakan prolog! 3. Sebutkan dan jelaskan beberapa aplikasi dari pemrograman logika!
Pertanyaan (Evaluasi mandiri)
Buatlah sebuah perancangan aplikasi yang menyatakan silsilah keluarga. Tunjukkan
rule dan faktanya.
Dari aplikasi terebut, gunakan pemrograman imperatif untuk menyelesaikannya, serta
tunjukkan apakah perbedaan di antara keduanya.
Page 74 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Kecerdasan Buatan: UNCERTAINTY (KETIDAKPASTIAN) Dian Eka Ratnawati, S.Si, M.Kom,Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc,Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya Email : [email protected]
1. PENDAHULUAN 1.1. Pengantar 1.2.Tujuan
1.3.Definisi 2. UNCERTAINTY 2.1 Definisi Ketidakpastian 2.2 Probabilitas
2.3 Teorema Bayes 2.4 Faktor Kepastian
3. CONTOH 4. PROPAGASI
4.1 Pertanyaan/Latihan Soal 4.2 Diskusi 4.3 Project
1. PENDAHULUAN 1.1 Pengantar
Sistem kecerdasan buatan dikembangkan dengan memiliki pengetahuan yang terbatas tentang permasalahan yang
ditanganinya, maka sistem tersebut dapat memiliki kesalahan dalam memberikan solusi dengan menggunakan pendekatan
logika. Sistem tidak akan pernah mempunyai pengetahuan atau fakta secara lengkap untuk permasalahan yang ditanganinya, sehingga sistem harus bekerja dalam
ketidakpastian dan kesamaran. Oleh karena itu, sistem harus menggunakan teknik-teknik khusus yang dapat menangani
ketidakpastian dan kesamaran dalam menyelesaikan permasalahan-permasalahan yang ditanganinya.
1.2 Tujuan
Setelah mempelajari Pokok Bahasan ini, diharapkan mahasiswa akan :
1. Memahami konsep ketidakpastian dalam sistem
kecerdasan buatan 2. Bisa memahami sifat-sifat ketidakpastian dalam sistem
kecerdasan buatan dan teknik penyelesaiannya 3. Menerapkan Probabilitas Bayes dalam melakukan
penyelesaian masalah ketidakpastian
4. Memiliki kreatifitas dalam penyelesaian masalah
UN
CE
RT
AIN
TY
(KE
TID
AK
PA
ST
IAN
)
MODUL
9
Page 75 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
1.3 Definisi
Uncertainty : teori ketidakpastian pada kecerdasan buatan untuk menyelesaikan permasalahan yang ada dengan pendekatan logika (mengadopsi logika manusia) dimana sistem tidak dapat mengakses
seluruh fakta yang ada. Contoh (sample point) : hasil dari percobaan
Ruang Contoh (sample space): kumpulan dari semua kemungkinan titik contoh.
Kejadian (event) : subset dari ruang contoh.
Kejadian sederhana (simple event): hanya ada satu elemen kejadian. Kejadian gabungan (compound event): terdapat lebih dari dari satu
kejadian Penalaran Deduktif dan Induktif dilihat dari populasi dan contoh (sample)
2.UNCERTAINTY
2.1 DefinisiKetidakpastian Pada sistem yang menggunakan kecerdasan buatan yang mengandalkan
fakta-fakta dalam melakukan pengambilan kesimpulan logika tidak akan menggunakan keseluruhan fakta yang ada, sehingga akan muncul
kesalahan-kesalahan dari proses pengambilan kesimpulan. Ketidakpastian dapat dianggap sebagai suatu kekurangan informasi yang memadai untuk membuat suatu keputusan. Ketidakpastian merupakan suatu permasalahan
karena mungkin menghalangi kita membuat suatu keputusan yang terbaik. Beberapa teori yang berhubungan dengan ketidakpastian adalah sebagai
berikut : Probabilitas Klasik Probabilitas Bayes
Teori Hartley yang berdasarkan pada himpunan klasik Teori Shanon yang didasarkan pada peluang
Teori Dempster-Shafer Teori Fuzzy Zadeh
Contoh aplikasi yang menggunakan ketidakpastian dalam pengambilan kesimpulan logika yang sukses adalah sistem pakar MYCIN untuk diagnosa
medis dan PROPECTOR untuk ekplorasi mineral. Salah satu contoh permasalahan yang memiliki ketidakpastian adalah
permasalahan diagnosa pasien terhadap suatu penyakit. Misalkan terdapat aturan dalam mendiagosa gejala-gejala dari suatu penyakit sebagai berikut :
IF badan_demam(pasien) AND IF badan_ruam(pasien) AND
IF badan_pegal(pasien) THEN mengalami_tifus(pasien) Berdasarkan aturan diatas, terlihat bahwa jika ada pasien yang mengalami
ketiga jenis gejala tersebut maka akan dideteksi bahwa pasien menderita penyakit tifus. Akan tetapi pada dunia nyata ketika terdapat gejala-gejala
tersebut memenuhi belum tentu penyakit yang diderita adalah tifus. Bisa jadi penyakit lain memiliki gejala yang sama sehingga bisa terjadi kesalahan diagnosa. Bagaimana jika derajat gejala yang dialami seorang pasien dengan
Page 76 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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.
Page 77 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 78 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
•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
Page 79 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 80 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 81 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
REFERENSI
1. Giarrantano, J and G.Riley, Expert System : Principle and
Programming,4thed, PWS Kent, 2004 2. Sri Kusumadewi, Artificial Intelligence : Teknik dan Aplikasinya, Graha Ilmu,
Yogyakarta, 2003
Page 82 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Kecerdasan Buatan: Bayesian Network Dian Eka Ratnawati, S.Si, M.Kom,Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc,Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya
1. PENDAHULUAN 1.3 Pengantar 1.4 Tujuan 1.5 Definisi
2. Sintak Bayesian Network 3. Semantik Bayesian Network
1. PENDAHULUAN 1.1 Pengantar
Ketika suatu permasalahan yang bisa dinyatakan dalam bentuk
sebab akibat, dimana melibatkan adanya proporsisi/ ketidakpastian dari suatu kejadian, maka kita bisa menyelesaikannya dengan bayesian network.
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
Page 83 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 84 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 85 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
- P(J|M) = P(J) ?
Apakah Peluang JohnCalls bersyarat terhadap MaryCalls
sama dengan peluang terjadinya JohnCalls? Jawabannya: Tidak, karena dari graph di atas terlihat
bahwa peluang terjadinya JohnCalls bergantung pada MaryCalls.
- P(A| J,M) = P(A | J)?P(A | J, M) = P(A)?
Dari graph di atas terlihat bahwasannya peluang
terjadinya Alarm dipengaruhi oleh adanya kejadian MaryCalls dan JohnCalls, sehingga: P(A| J,M) = P(A | J)?P(A | J, M) = P(A)? No
Kemudian diberikan pertanyaan berikutnya:
- P(B | A, J, M) = P(B | A)? - P(B | A, J, M) = P(B)?
- Maka dari gambar di atas bisa menjawab pertanyaan
sebelumnya bahwa Peluang terjadinya Burgary dipengarui oleh bunyi Alarm, sehingga:
P(B | A, J, M) = P(B | A)? Yes P(B | A, J, M) = P(B)? No
- Kemudian, jika diberikan P(E | B, A ,J, M)apakah sama
denganP(E | A)?
- Juga apakahP(E | B, A, J, M) sama dengan P(E | A, B)?
Page 86 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
- 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
Page 87 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Kecerdasan Buatan:Learning Dian Eka Ratnawati, S.Si, M.Kom,Dewi Yanti Liliana, S.Kom., M.Kom. Lailil Muflikhah,S.Kom,M.Sc,Rekyan Regasari,ST,MT Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya Email : [email protected]
1. PENDAHULUAN 1.1 Pengantar 1.2 Tujuan 1.3 Definisi
2. Learning
3. Latihan
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
Page 88 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
1.2 Tujuan
Setelah mempelajari Pokok Bahasan ini, diharapkan mahasiswa akan : 1. Memahami konsep learning dalam sistem kecerdasan buatan
2. Bisa memahami sifat-sifat learning dalam sistem kecerdasan buatan dan teknik penyelesaiannya
3. Menerapkan teknik learning dalam melakukan penyelesaian kecerdasan buatan
4. Memiliki motivasi untuk mencari ilmu dan mengembangkan ilmu yang sudah dimiliki
1.3 Definisi
Individu : menyatakan salah satu solusi yang mungkin = kromosom : kumpulan gen. Gen : sebuah nilai yang menyatakan satuan dasar yang membentuk arti tertentu
dalam satu kesatuan (kromosom). bisa biner, float, integer maupun karakter, list of rule (R1, R2,…), elemen permutasi (E1, E2,…) atau kombinatorial, struktur data lainnya
Allele : nilai dari gen
populasi : sekumpulan individu (kromosom) yang akan diproses bersama dalam satu siklus proses evolusi
Generasi : satu siklus proses evolusi atau satu iterasi dalam algoritma genetika
2. LEARNING (PEMBELAJARAN)
2.1 Jaringan Syarat Tiruan (Artificial Neural Network)
2.1.1 Sejarah Jaringan Syaraf Tiruan (JST) Perkembangan computer yang sangat pesat membuat para ahli tertantang untuk
mengembangkan computer yang mampu yang mampu melakukan hal-hal seperti yang
dilakukan manusia. Untuk perhitungan matematis, yang sulit sekalipun, computer
mampu melakukan perhitungan dengan mudah, bahkan lebih cepat dari manusia. Akan
tetapi, bagaimana dengan kemampuan manusia yang lain, terutama yang didapat dari
pengalaman ? Misal dari seorang guru, siswa belajar mengenali huruf “A”, atau
membedakan gambar penguin dengan gambar kucing, dan lain sebagainya.
Berdasar keadaan tersebut, dikembangkan suatu jaringan yang memiliki konsep
mirip dengan jaringan otak manusia. Jaringan tersebut dapat dilatih sehingga pada
akhirnya dapat mengambil keputusan seperti yang dilakukan oleh otak manusia.
Jaringan tersebutdisebut sebagai jaringan syaraf tiruan, dan computer dimanfaatkan
sebagai sarana pelatihan jaringan (artificial neural network)
2.1.2 Konsep Jaringan Syaraf Tiruan.
Seperti telah dijelaskan di atas, Jaringan syaraf tiruan merupakan sistem
pemroses informasi yang memiliki karakteristik mirip dengan jaringan syaraf biologi.
Jaringan syaraf tersebut adalah sebagaimana ditunjukkan pada gambar 1 berikut.
Gambar 1. Jaringan syaraf biologi
Page 89 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
Peniruan model otak manusia tersebut dilakukan dengan adaptasi seperti ditunjukkan
tabel 1 berikut.
Tabel 1. Model jaringan syaraf tiruan
Sehingga model neuron pada jaringan syaraf tiruan menjadi seperti pada gambar 2.
Gambar 11.1 Model neuron JST
Karakteristik JST adalah : Arsitektur Jaringan
◦ Single Layer, Multi Layer Training/Learning
◦ Perceptron,, Backpropagation
Fungsi Aktivasi ◦ Fungsi treshold (ramp function)
◦ Fungsi sigmoid ◦ Fungsi identitas
2.1.3 Pelatihan Jaringan Syaraf Tiruan
Pelatihan jaringan syaraf dimaksudkan untuk mencari bobot-bobot yang terdapat
dalam tiap layer. Ada 2 jenis pelatihan dalam sistem jaringan syaraf tiruan, yaitu proses
belajar terawasi (supervised learning) dan proses belajar tidak terawasi (unsupervised
learning).
a. Proses Belajar Terawasi
Dalam proses belajar terawasi seolah-olah ada guru yang mengajari jaringan. Cara
pelatihan jaringan tersebut adalah dengan memberikan data-data yang disebut data
training. Data training terdiri atas pasangan input dan output yang diharapkan dan
merupakan associative memory. Data-data tersebut biasanya didapat dari
pengalaman atau pengetahuan seseorang dalam menyelesaikan persoalan. Setelah
jaringan dilatih, associative memory akan mengingat suatu pola. Jika jaringan diberi
input baru, jaringan dapat mengeluarkan output seperti yang diharapkan. Beberapa
Page 90 of 98
Kecerdasan buatan / MateriKuliah 2012 Brawijaya University
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
Page 92 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
Page 93 of 98
Kecerdasan Buatan 2012 Brawijaya University
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
Nama Mata Kuliah yang diasuh
No Nama Mata Kuliah Strata
1 Kecerdasan Buatan S1
2 Pengenalan Pola S1
3 Analisis dan Desain Algoritma S1
4 Struktur Data dan Algoritma S1
Jumlah Mahasiswa yang pernah diluluskan
Strata Jumlah
S1 40
S2
S3
Pengalaman penelitian
No Tahun Topik/judul
penelitian
1 2010 Teknik Kompresi citra menggunakan dekomposisi nilai
singulir berbasis blok.
2 2012 Deteksi Wajah
menggunakan Fast Fourier Transformatioan
Page 94 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
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
Page 95 of 98
Kecerdasan Buatan 2012 Brawijaya University
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
Nama Mata Kuliah yang diasuh
No Nama Mata Kuliah Strata
1 Data Mining S1
2 Kecerdasan Buatan 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
Jumlah Mahasiswa yang pernah diluluskan
Strata Jumlah
S1 50
S2
S3
Pengalaman penelitian
No Tahun Topik/judul penelitian
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
Page 96 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
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
Page 97 of 98
Kecerdasan Buatan 2012 Brawijaya University
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
Nama Mata Kuliah yang diasuh
No Nama Mata Kuliah Strata
1 Probabilitas Statistik S1
2 Matematika Komputasi S1
3 Kecerdasan Buatan S1
Jumlah Mahasiswa yang pernah diluluskan
Strata Jumlah
S1 2
S2
S3
Pengalaman penelitian
No Tahun Topik/judul penelitian
1 2010 Decision Support System Penentuan Penerima Bantuan
Pemerintah dengan integrasi Metode Group Technology dan
Decision Table
2 2011 Sistem Informasi Kelurahan
Pengalaman publikasi di berkala ilmiah 5 tahun terakhir
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