Evolutionary Computation Komputasi Berbasis Evolusi dan Genetika

ReasoningCS3243 Kecerdasan Mesin dan Artifisial

Informatics Theory & Programming (ITP)Informatics Eng. Dept. IT TelkomOutlineInference Reasoning

Can Searching solve it?

Can Searching solve it?

Ruang PencarianPenghitungan ruang pencarian:Faktor pencabangan atau branching factor (b)Kedalaman solusi atau depth (d)8-Puzzle b = 2,13Permainan Catur rata-rata b = 35Untuk catur ruang pencarian sangat luasTeknik searching belum mungkin digunakanSolusi: gunakan teknik reasoningLima Jenis Logic [RUS95]Jenis logicApa yang ada di dunia nyataApa yang dipercaya Agent tentang faktaPropositional logicfaktabenar/salah /tidak diketahuiFirst-order logicfakta, objek, relasibenar/salah /tidak diketahuiTemporal logicfakta, objek, relasi, waktubenar/salah /tidak diketahuiProbability theoryfaktaderajat kepercayaan [0,1]Fuzzy logicderajat kebenaranderajat kepercayaan [0,1]Propositional LogicLogic yang paling sederhanaSangat mudah dipahamiMembuat kita lebih mudah membedakan teknik reasoning dengan teknik searching.BNF (Backus-Naur Form)

PQPP QP QP QP QFalseFalseTrueTrueFalseTrueFalseTrueTrueTrueFalseFalseFalseFalseFalseTrueFalseTrueTrueTrueTrueTrueFalseTrueTrueFalseFalseTrueTabel Kebenaran 5 connective

Dunia WumpusWumpus adalah seekor monster yang tinggal di sebuah gua yang terbagi dalam 16 ruangan Di dalam gua terdapat 3 lubang mematikan (Pit) yang mengeluarkan angin (breeze) sehingga sampai di ruangan-ruangan di sekitarnya. Wumpus mengeluarkan bau busuk (stench). Wumpus menjerit (scream) dan mati jika terkena panah.Dunia WumpusSebuah Agent dilengkapi dengan tiga anak panah yang hanya bisa diarahkan menuju ruangan-ruangan yang searah dengan arah agent menghadap.Agent bisa bergerak hadap kanan, hadap kiri, maju. Agent bisa memanjat keluar gua jika posisinya terjepit. Agent akan benjol (bump) jika menabrak dinding gua. Agent akan mati jika memasuki kotak yang terdapat Wumpus atau Pit. Tetapi aman jika memasuki kotak yang di dalamnya terdapat Wumpus yang telah mati.Dunia WumpusSaat permainan dimulai, Agent berada di posisi (1,1). Tugas Agent adalah menemukan emas dan membawanya kembali ke kotak start (1,1) secepat mungkin dengan jumlah aksi yang seminimum mungkin, tanpa terbunuh. Sebagai hadiah, 1.000 poin diberikan kepada agent jika berhasil keluar gua dengan membawa emas. Tetapi, Agent mendapat poin 1 untuk setiap aksi yang dilakukan dan -10.000 jika agent terbunuh.4StenchBreezePit3Wumpus StenchBreeze,Stench ,Gold (glitter)PitBreeze2StenchBreeze1STARTAgent BreezePitBreeze1234Dunia WumpusMasalah dunia Wumpus dapat dirumuskan ke dalam tiga kelompok: Percept: sesuatu yang ditangkap oleh AgentAction: aksi yang dapat dilakukan oleh AgentGoal: tujuan

PerceptPercept : [stench , breeze, glitter, bump, scream][stench , breeze, None, None, None] Ada stench dan breezeTidak ada glitter, bump, maupun scream.

ActionMove: hadap kiri, hadap kanan, atau maju.Grab: mengambil objek yang berada di kotak dimana agent berada.Shoot: memanah dengan arah lurus sesuai dengan arah Agent menghadap. Climb: memanjat keluar dari gua.GoalMenemukan emas dan membawanya kembali ke kotak start (1,1) secepat mungkin dengan jumlah action yang seminimum mungkin, tanpa terbunuh. Hadiah 1000 poin diberikan kepada Agent jika berhasil keluar gua dengan membawa emas. Tetapi Agent mendapatkan poin 1 untuk setiap action yang dilakukan dan -10000 jika Agent terbunuh.Dunia WumpusBisakah Wumpus diselesaikan dengan searching?Bisa Pertama, suatu state dinyatakan dengan 16 ruangan dengan posisi-posisi Wumpus, Pit, dan Gold. Operator atau aturan produksinya ada enam, yaitu: hadap kiri, hadap kanan, maju, memanah, mengambil objek, dan memanjat ke luar gua. Dengan mendefinisikan initial state, goal state, dan strategi searching, maka kita dapat menyelesaikan masalah tersebut. Representasi state membutuhkan memori besar.Wumpus dengan ReasoningReasoning mengunakan propositional logicPertama, kita harus merepresentasikan fakta atau keadaan ke dalam simbol-simbol propositional logic.S1,2 : ada stench di kotak (1,2)B2,1 : ada breeze di kotak (2,1)G2,3 : ada glitter di kotak (2,3)M1,4 : bump di kotak (1,4)C1,3 : ada scream di kotak (1,3)W1,3 : ada Wumpus di kotak (1,3)S1,1 : tidak ada stench di posisi (1,1)Knowledge-based System (KBS)Agent di sini dapat dikatakan sebagai knowledge-based system karena agent akan melakukan aksi berdasarkan hasil penalaran suatu percept terhadap Knowledge Based (KB) yang dimilikinya. Pada awal permainan, di dalam KB tidak ada fakta sama sekali karena Agent belum menerima percept. KB hanya berisi beberapa aturan (rule) yang merupakan pengetahuan tentang environmentR1 : S1,1 W1,1 W1,2 W2,1R2 : S2,1 W1,1 W2,1 W2,2 W3,1R3 : S1,2 W1,1 W1,2 W2,2 W1,3R4 : S1,2 W1,3 W1,2 W2,2 W1,1...R33 : B1,1 P1,1 P1,2 P2,1R34 : B2,1 P1,1 P2,1 P2,2 P3,1...Pengetahuan ttg environmentTranslationT1 : A2,1 EastA P3,1 ForwardT2 : A1,2 NorthA W1,3 Forward...Untuk melakukan aksi yang tepat, agent harus dibekali aturan untuk menerjemahkan pengetahuan menjadi aksi.T1 dibaca: Jika agent di (2,1) dan menghadap ke timur dan ada Pit di (3,1), maka jangan melangkah maju (ke posisi (3,1)). Knowledge-based System (KBS)Agent di sini dapat dikatakan sebagai knowledge-based system karena agent akan melakukan aksi berdasarkan hasil penalaran suatu percept terhadap Knowledge Based (KB) yang dimilikinya. Pada awal permainan, di dalam KB tidak ada fakta sama sekali karena Agent belum menerima percept. KB hanya berisi beberapa aturan (rule) yang merupakan pengetahuan tentang environmentInference & ReasoningInference: A process of drawing conclusion (solution) from set of facts.Reasoning: A Process of deriving new knowledge from the exist knowledge.4StenchBreezePit3Wumpus StenchBreeze,Stench ,Gold (glitter)PitBreeze2StenchBreeze1STARTAgent BreezePitBreeze1234Apakah Wumpus berada di posisi (3,1)?Bagaimana reasoning oleh manusia?Bagaimana proses reasoning oleh agent?Agent berada di posisi (1,1)Pada awalnya Knowledge Base hanya berisi Rule yang berupa pengetahuan tentang environment. Tidak ada fakta sama sekali karena agent belum melakukan percept.Pada kasus di atas, Agent menerima percept yang berupa [None, None, None, None, None] Tidak ada stench, breeze, glitter, bump, screamSelanjutnya, Agent menggunakan aturan inferensi dan pengetahuan tentang environment untuk melakukan proses inferensi.Proses inferensi di (1,1)Modus Ponens untuk S1,1 dan R1W1,1 W1,2 W2,1And-Elimination terhadap hasil di atasW1,1 W1,2 W2,1Modus Ponens untuk B1,1 dan R3P1,1 P1,2 P2,1And-Elimination terhadap hasil di atasP1,1 P1,2 P2,1Inferensi dilakukan sampai dihasilkan kalimat yang paling sederhana atau bahkan atomik.Setelah proses Inferensi di atas

Misalkan Agent ke posisi (2,1)Percept [None, Breeze, None, None, None] Ada breeze, tidak ada stench, glitter, bump dan screamS2,1, B2,1, G2,1, M2,1, dan C2,1Proses inferensi di (2,1)Modus Ponens untuk S2,1 dan R2W1,1 W2,1 W2,2 W3,1And-Elimination terhadap hasil tersebutW1,1 W2,1 W2,2 W3,1Modus Ponens untuk B2,1 dan R34P1,1 P2,1 P2,2 P3,1Unit Resolution terhadap hasil tersebut dengan P1,1 kemudian P2,1, sehingga didapatP2,2 P3,1Setelah proses Inferensi di atas

Misalkan Agent ke posisi (1,2)Percept [Stench, None, None, None, None] Ada stench, tidak ada breeze, glitter, bump dan scream.S1,2, B1,2, G1,2, M1,2, dan C1,2Proses inferensi di (1,2)Modus Ponens untuk S1,2 dan R4W1,3 W1,2 W2,2 W1,1Unit Resolution terhadap hasil di atas dengan W1,1W1,3 W1,2 W2,2Unit Resolution terhadap hasil di atas dengan W2,2W1,3 W1,2Unit Resolution terhadap hasil di atas dengan W1,2W1,3Langkah SelanjutnyaKetika lokasi Wumpus sudah diketahui, agent bisa menggunakan panah untuk membunuhnya atau fokus pada pencarian emas dengan menghindari lokasi Wumpus. Kita bisa membuat berbagai strategi sehingga bisa membawa emas kembali ke posisi (1,1) dengan jumlah aksi yang seminimum mungkin.

Kelebihan PLPada kasus Wumpus tersebut, agent harus dibekali aturan yang merupakan pengetahuan tentang environment dan aturan untuk menerjemahkan pengetahuan menjadi aksi Untuk 16 ruangan yang ada di dalam gua, diperlukan sangat banyak aturan tentang environment dan aturan penerjemah. Pada kasus Wumpus ini, teknik manakah yang lebih efisien dalam representasi masalah, searching atau reasoning? Tentu saja reasoning lebih efisien.

Kelemahan PLBagaimanapun, untuk kasus yang lebih kompleks seperti permainan catur, propositional logic akan sulit digunakan. Terdapat sangat banyak aturan pada permainan catur sedangkan propositional logic merepresentasikan fakta hanya dalam simbol-simbol sederhana. Oleh karena itu, kita akan membahas satu logic yang lebih tinggi tingkatannya, yaitu First-Order Logic yang juga disebut sebagai Predicate Logic atau Predicate Calculus.First-Order Logic (FOL)Objects: sesuatu dengan identitas individual (people, houses, colors, )Properties: sifat yang membedakannya dari object yang lain (red, circle, )Relations: hubungan antar object (brother of, bigger than, part of, ...)Functions: relation yang mempunyai satu nilai (father of, best friend, )

Constantbiasanya dituliskan dalam huruf besar seperti: A, X1, Budi. Pada simbol konstanta ini, setiap simbol harus menyatakan secara spesifik objek yang dimaksud. Tetapi, mungkin saja satu simbol mengacu pada beberapa nama berbeda. Misalnya, Budi bisa mengacu ke Budi Arifianto, Budi Prasojo, Budi Raharjo, dan sebagainya. Penulisan simbol konstanta harus dilakukan secara hati-hati agar tidak terjadi kerancuan atau ambiguitas.VariableBiasanya dituliskan dalam huruf kecil seperti: a, x, s Menyatakan simbol yang dapat digantikan oleh konstanta apapun.PredicateMenyatakan relasi khusus dalam suatu model.Misalkan Berwarna adalah suatu predicate yang memiliki beberapa nilai. Berwarna(Tasku,Hijau)Berwarna(Tasmu,Putih) FunctionMenyatakan relasi yang hanya mempunyai satu nilai. Karena setiap orang hanya punya satu ibu kandung, maka IbuKandung adalah suatu function. IbuKandung(Anawati,Budi)AyahKandung(Roni,Budi)

TermsEkpresi logika yang mengacu pada sebuah objek. Terms bisa berupa constant, variable, atau function.Atomic sentencesDibentuk dari Predicate(Term, ...) atau Term = Term.Sepatu(Budi)Saudara(Andi,Budi)Memberi(Andi,Budi,KueCoklat)Saudara(Andi) = Budi, dan sebagainya.Complex sentencesSentence yang dibangun menggunakan connective.Contoh:Saudara(Andi,Budi) Memberi(Andi,Budi,Kue)Universal quantifiers ()Menyatakan sesuatu yang bersifat umum. Simbol (huruf A terbalik) dibaca For Allx AnakKecil(x) Suka(x,Permen). Kalimat tersebut benar jika dan hanya jika semua kalimat di bawah ini benarAnakKecil(Andi) Suka(Andi,Permen) AnakKecil(Anto) Suka(Anto,Permen) AnakKecil(Budi) Suka(Budi,Permen) ...Existential quantifiers ()Menyatakan sesuatu yang berlaku sebagian. Simbol (huruf E menghadap ke kiri) dibaca There Exist (ada satu atau beberapa). x AnakKecil(x) Suka(x,Permen). Kalimat ini adalah benar jika dan hanya jika ada kalimat di bawah ini yang bernilai benar.AnakKecil(Andi) Suka(Andi,Permen) AnakKecil(Anto) Suka(Anto,Permen) AnakKecil(Budi) Suka(Budi,Permen) ...Nested quantifiersDigunakan untuk menyatakan kalimat kompels yang menggunakan quantifiers ganda. Misalkan: Untuk semua x dan semua y, jika x adalah orangtua y maka y adalah anak dari x dapat dinyatakan sebagai:x,y OrangTua(x,y) Anak(y,x)Hubungan antara dan dan memiliki hubungan yang kuat melalui sebuah negasi (). Misalkan, Semua anak kecil suka permen adalah ekivalen dengan Tidak ada anak kecil yang tidak suka permen. x Suka(x,Permen) x Suka(x,Permen)

Hukum De Morganx P x PP Q (P Q)x P x P(P Q) P Qx P x PP Q (P Q)x P x PP Q (P Q)Inferensi pada First-Order LogicFOL menggunakan 7 aturan propositional logicDitambah tiga aturan tambahan yang lebih kompleks (berhubungan dengan quantifier), yaitu:Universal EliminationExistential EliminationExistential Introduction

Universal EliminationUntuk setiap sentence , variabel v, dan ground term (atau term yang tidak berisi variabel) g:

Dari x Suka(x,Permen), dapat digunakan substitusi {x/Andi} Suka(Andi,Permen)

Existential EliminationUntuk setiap sentence , variabel v, dan simbol konstanta k yang tidak ada di dalam basis pengetahuan:

Dari x Saudara(x,Budi), kita dapat menyimpulkan Saudara(Andi,Budi), selama Andi tidak ada di dalam basis pengetahuan.

Existential IntroductionUntuk setiap sentence , variabel v yang tidak terjadi pada , dan ground term g yang terjadi pada :

Dari Suka(Budi,Permen) kita dapat menyimpulkan x Suka(x,Permen)

Masalah: Hukum PernikahanHukum pernikahan menyatakan bahwa suatu pernikahan adalah tidak sah jika kedua mempelai memiliki hubungankeponakan.Saudara kandungSaudara Se Ibu / Se ayahIbuAyahAnak dari Saudara laki-laki Ayah/ saudara laki-laki Ibu Wati menikah dengan Andi. Dimana Wati adalah anak kandung Budi yang merupakan saudara kembar Andi.

Dengan FOL, buktikan bahwa pernikahan Andi dan Wati adalah tidak sah.Langkah2 FOLPertama, representasikan fakta ke dalam ekspresi FOL Ke dua, gunakan 10 aturan inference di atas sehingga dihasilkan urutan-urutan inferensi sampai dihasilkan suatu kesimpulan.Langkah pertamax,y Keponakan(x,y) Menikah(x,y) Sah(Menikah(x,y))(3.1)Menikah(Wati,Andi)(3.2)AnakKandung(Wati,Budi)(3.3)SaudaraKembar(Budi,Andi)(3.4)x,y SaudaraKembar(x,y) SaudaraKandung(x,y)(3.5)x,y,z AnakKandung(x,y) SaudaraKandung(y,z) Keponakan(x,z)(3.6)Langkah ke duaDari (3.5) dan Universal Elimination:SaudaraKembar(Budi,Andi) SaudaraKandung(Budi,Andi) (3.7)Dari (3.4), (3.7), dan Modus Ponens:SaudaraKandung(Budi,Andi) (3.8)Dari (3.6) dan Universal Elimination:AnakKandung(Wati,Budi) SaudaraKandung(Budi,Andi) Keponakan(Wati,Andi) (3.9)Dari (3.3), (3.8), dan And-Intoduction:AnakKandung(Wati,Budi) SaudaraKandung(Budi,Andi) (3.10)Langkah ke duaDari (3.9), (3.10), dan Modus Ponens:Keponakan(Wati,Andi) (3.11)Dari (3.1) dan Universal Elimination:Keponakan(Wati,Andi) Menikah(Wati,Andi) Sah(Menikah(Wati,Andi)) (3.12)Dari (3.11), (3.2) dan And-Intoduction:Keponakan(Wati,Andi) Menikah(Wati,Andi) (3.13)Dari (3.12), (3.13), dan Modus Ponens:Sah(Menikah(Wati,Andi)) (3.14)DiskusiProses penalaran di atas memerlukan 8 proses inferensi yang sangat efisien. Tetapi, bagaimana komputer tahu bahwa urutan pembuktian paling efisien adalah 8 proses inferensi. Pada kenyataannya, komputer hanya tahu urutan dari sepuluh aturan dan urutan dari enam kalimat yang ada. Tanpa strategi pemilihan aturan dan kalimat yang jelas, komputer akan melakukannya secara sekuensial dari aturan ke-1 sampai ke-10 dan dari kalimat ke-1 sampai ke-9.Dunia WumpusRepresentasi FOL jauh lebih sederhana dibandingkan Proporsitional Logic.s,b,u,c,t Percept([s,b,Glitter,u,c],t) Action(Grab,t)b,g,u,c,t Percept([Stench,b,g,u,c],t) Stench(t)s,g,u,c,t Percept([s,Breeze,g,u,c],t) Breeze(t)s,b,u,c,t Percept([s,b,Glitter,u,c],t) AtGold(t)t AtGold(t) Action(Grab,t)Permainan Catur

Awalnya, langkah untuk Putih1. a2(PP) Kosong(a3) Gerakkan(PP,a2,a3)2. a2(PP) Kosong(a3) Kosong(a4) Gerakkan(PP,a2,a4) 6. c2(PP) Kosong(c3) Kosong(c4) Gerakkan(PP,c2,c4)19. g1(KP) Kosong(f3) Gerakkan(KP,g1,f3)20. g1(KP) Kosong(h3) Gerakkan(KP,g1,h3)Logical ProgrammingBahasa pemrograman logis yang paling populer adalah PROLOG (PROgramming in Logic). Di dalam PROLOG, suatu program dituliskan sebagai kumpulan kalimat dalam Horn clause.Pekerjaan kita hanyalah membangun knowledge base yang sesuai dan lengkap untuk suatu masalah. Proses reasoning sampai dihasilkan suatu kesimpulan ditangani oleh PROLOG.Tetapi, membangun knowledge base yang benar dan lengkap bukanlah hal yang mudah. FOL dan PROLOGFOLMenikah(Wati,Andi)x,y SaudaraKembar(x,y) SaudaraKandung(x,y)x,y,z AnakKandung(x,y) SaudaraKandung(y,z) Keponakan(x,z)

PROLOGMenikah(wati,andi).SaudaraKandung(X,Y) :- SaudaraKembar(X,Y).Keponakan(X,Z) :- AnakKandung(X,Y), SaudaraKandung(Y,Z).KB yang benar & lengkapPada masalah Hukum PernikahanTerdapat tiga kalimat bahasa Indonesia yang direpresentasikan menjadi 6 kalimat First Order Logic (3 fakta dan 3 aturan). Jika aturan x,y SaudaraKembar(x,y) SaudaraKandung(x,y) tidak kita definisikan, maka proses reasoning akan gagal.

KB yang benar & lengkapMisalkan, kita ingin membagun suatu knowledge-based agent yang berfungsi seperti dokter untuk menentukan jenis penyakit. Bagaimana cara membangun knowledge base yang berasal dari buku-buku kedokteran yang tebal atau dari pengetahuan seorang dokter? Bagaimana mengubah ribuan kalimat bahasa manusia menjadi kalimat-kalimat First Order Logic yang benar dan lengkap?KB yang benar & lengkapPada permainan catur, bagaimana cara membangun fakta dan aturan yang benar dan lengkap? Bagaimana merepresentasikan strategi permainan catur menjadi aturan-aturan dalam First Order Logic?Knowledge engineeringSeorang knowledge engineer harus memiliki pengetahuan yang cukup tentang tiga hal berikut ini:domain pertanyaan, untuk merepresentasikan objek dan hubungan antar objek bahasa representasi, untuk mengkonversi fakta-fakta yang adaimplementasi prosedur inferensi, sehingga proses reasoning bisa dilakukan dengan cepat.Lima Langkah KE1. Tentukan domain masalah secara jelas. Pahami domain dengan baik sehingga mengetahui objek-objek dan fakta-fakta mana yang perlu dibicarakan dan mana yang bisa diabaikan2. Tentukan kosakata untuk predicates, function, dan constants. Terjemahkan konsep yang ada pada bahasa manusia ke dalam kosakata bahasa logic. Dalam hal ini, gunakan nama-nama yang sesuai dan mudah diingat. Misalnya, Kecil sebaiknya menjadi suatu constant atau predicate?Lima Langkah KE3. Ubah pengetahuan yang bersifat umum menjadi lebih spesifik. x Binatang(x) b Otak(x) = bKalimat di atas menyatakan bahwa ada suatu objek yang nilai dari fungsi Otak diaplikasikan terhadap Binatang. Kita bisa membenarkan kalimat tersebut dengan Otak(b). Jika binatang yang dimaksud adalah binatang bersel tunggal, maka kita bisa mengganti Binatang menjadi Vertebrata. Sehigga kalimat yang benar adalah: x Vertebrata(x) b Otak(b)Lima Langkah KE4. Kodekan contoh-contoh yang bersifat khusus. Pada permainan catur:Pion Putih dikodekan sebagai PP, Kuda Putih sebagai KPPosisi (a,2) dikodekan sebagai a2 karena hanya terdapat 64 posisi (a1, b1, c1, ..., h8)posisi (a,3) kosong dapat direpresentasikan sebgai Kosong(a3), dsb. Sehigga aturan menjadi sederhana. Misal:a2(PP) Kosong(a3) Gerakkan(PP,a2,a3)Lima Langkah KE5. Buat query-query untuk prosedur inferensi. Hal ini akan membuat prosedur inferensi fokus pada aksioma-aksioma (pernyataan yang benar) dan fakta-fakta yang ada untuk menurunkan fakta-fakta baru yang kita inginkan. Lima Langkah KEApakah Budi adalah saudara kandung Andi?x,y SaudaraKembar(x,y) SaudaraKandung(x,y)Jawabannya adalah: SaudaraKandung(Budi,Andi)Apakah Wati adalah keponakan Andi? x,y,z AnakKandung(x,y) SaudaraKandung(y,z) Keponakan(x,z)Jawabannya adalah: Keponakan(Wati,Andi)KesimpulanDaftar Pustaka[SUY07] Suyanto. 2007. Artificial Intelligence: Searching, Reasoning, Planning and Learning. Informatika, Bandung Indonesia. ISBN: 979-1153-05-1.[RUS95] Russel, Stuart and Norvig, Peter. 1995. Artificial Intelligence: A Modern Approach. Prentice Hall International, Inc.[SUY08b] Suyanto. 2008. Soft Computing: Membangun Mesin Ber-IQ Tinggi. Informatika, Bandung Indonesia. ISBN: 978-979-1153-49-2.