Pertemuan Ke-6 : Pengetahuan dan Penalaran : Representasi Pengetahuan

Nama : Rezky Audiansyah Putra

Kelas : 3KA12

NPM  : 18116161


Hasil PPT : https://drive.google.com/open?id=19ykrZs_H77YIaQuWSlBc0J4oACSzQDR6
---------------------------------------------------------------------------------------------------------------------------

6.1 Rekayasa Ontologi


Ontologi merupakan salah satu kajian filsafat yang paling kuno dan berasal dari Yunani. Studi tersebut membahas keberadaan sesuatu yang bersifat konkret. Tokoh Yunani yang memiliki pandangan yang bersifat ontologis dikenal seperti Thales, Plato, dan Aristoteles . Pada masanya, kebanyakan orang belum membedaan antara penampakan dengan kenyataan. Thales terkenal sebagai filsuf yang pernah sampai pada kesimpulan bahwa air merupakan substansi terdalam yang merupakan asal mula segala sesuatu. Namun yang lebih penting ialah pendiriannya bahwa mungkin sekali segala sesuatu itu berasal dari satu substansi belaka (sehingga sesuatu itu tidak bisa dianggap ada berdiri sendiri).


Hakikat kenyataan atau realitas memang bisa didekati ontologi dengan dua macam sudut pandang:

1. Kuantitatif, yaitu dengan mempertanyakan apakah kenyataan itu tunggal atau jamak?
2. Kualitatif, yaitu dengan mempertanyakan apakah kenyataan (realitas) tersebut memiliki kualitas tertentu, seperti misalnya daun yang memiliki warna kehijauan, bunga mawar yang berbau harum.

Secara sederhana ontologi bisa dirumuskan sebagai ilmu yang mempelajari realitas atau kenyataan konkret secara kritis.

Beberapa aliran dalam bidang ontologi, yakni realisme, naturalisme, empirisme


Istilah istilah terpenting yang terkait dengan ontologi adalah:

• yang-ada (being)
• kenyataan/realitas (reality)
• eksistensi (existence)
• esensi (essence)
• substansi (substance)
• perubahan (change)
• tunggal (one)
• jamak (many)

Ontologi ini pantas dipelajari bagi orang yang ingin memahami secara menyeluruh tentang dunia ini dan berguna bagi studi ilmu-ilmu empiris (misalnya antropologi, sosiologi, ilmu kedokteran, ilmu budaya, fisika, ilmu teknik dan sebagainya).

6.2 Pengkatagorian dan Objek: Komposisi Fisik,Pengukuran,Substansi dan Objek

Komposisi fisik
Komposisi adalah tata susunan yang menyangkut
keseimbangan, kesatuan, irama, dan keselarasan dalam
suatu karya seni rupa.jadi komposisi fisik adalah susunan kesatuan dari suatu bentuk fisik / yg dapat dilihat.

Pengukuran 
Pengukuran adalah penentuan besaran, dimensi, atau kapasitas, biasanya terhadap suatu standar atau satuan ukur. Pengukuran juga dapat diartikan sebagai pemberian angka tehadap suatu atribut atau karakteristik tertentu yang dimiliki oleh seseorang, hal, atau objek tertentu menurut aturan atau formulasi yang jelas dan disepakati. Pengukuran dapat dilakukan pada apapun yang dibayangkan, namun dengan tingkat kompleksitas yang berbeda. Misalnya untuk mengukur tinggi, maka seseorang dapat mengukur dengan mudah karena objek yang diukur merupakan objek kasat mata dengan satuan yang sudah disepakati secara internasional. Namun hal ini akan berbeda jika objek yang diukur lebih abstrak seperti kecerdasan, kematangan, kejujuran, kepribadian, dan lain sebagainya sehingga untuk melakukan pengukuran diperlukan keterampilan dan keahlian tertentu.


Substansi
Watak sebenarnya,inti dari sesuatu.


Objek
Sesuatu yang sedang dibicarakan/dijadikan pokok acuan/target.



6.3 Aksi, Situasi dan Kejadian/event


Aksi 

Adalah tindakan yang dilakukan berdasarkan suatu kejadian.


Situasi

Keadaan sekitar yang sedang berlangsung.


Kejadian/event

Sesuatu yang sedang terjadi di sebuah lingkungan dimana terjadi pada waktu yang sedang berlangsung maupun yang telah terjadi.

6.4 mental objek dan mental objek : pengetahuan dan kepercayaan,pengetahuan waktu dan aksi. 


Pengetahuan dan kepercayaan 


Pengetahuan adalah informasi yang diketahui atau disadari oleh manusia, atau pengetahuan adalah berbagai gejala yang ditemui dan diperoleh manusia melalui pengamatan indrawi. Pengetahuan akan muncul ketika orang menggunakan akal atau indranya untuk mengenali benda atau peristiwa tertentu yang belum pernah dilihat atau dirasakan. Misalnya, saat pertama kali orang makan cabai maka Dia akan tahu bagaimana rasa cabai itu, bentuknya, warnanya, atau bahkan akan bertanya-tanya apa zat-zat apa yang dikandungnya.


Pengetahuan empiris menekankan pada pengamatan dan pengalaman indrawi, sedangkan pengetahuan rasional didapatkan melalui akal budi. Misalnya, orang mengetahui bahwa cabai rasanya pedas karena dia pernah memakannya. Tidak mungkin hanya dengan dipikir-pikir orang itu akan mengetahui bahwa rasa cabai adalah pedas. Nemun, pernyataan 1+1=2 adalah hasil dari pemikiran (akal) manusia, bukan merupakan suatu pengamatan empiris.


Keyakinan adalah suatu sikap yang ditunjukkan manusia saat dia merasa cukup tahu dan menyimpulkan bahwa dirinya telah mencapai kebenaran. Maksudnya adalah orang akan merasa yakin kalau apa yang mereka ketahui adalah benar. Jadi, keyakinan terjadi setelah orang percaya adanya suatu kebenaran.


Menurut teori kebenaran sebagai kesesuaian, keyakinan adalah suatu pernyataan yang tidak disertai bukti yang nyata. Misalnya, petir disebabkan oleh amukan para dewa. Pernyataan ini tidak bisa dibuktikan, sehingga hanya bisa dikatakan sebagai suatu keyakinan. Sementara pernyataan petir disebabkan kerena adanya tabrakan antara awan yang bermuatan positif dan negative adalah suatu kebenaran, karena dapat dibuktikan. Sehingga pernyataan ini disebut sebagai pengetahuan.


Ada dua istilah yang berhubungan dengan keyakinan dan pengetahuan.


1. Magic power- (kekuatan magis) –> fenomena kekuatan gaib. Orang yang lebih percaya pada sesuatu yang aneh(karena tidak tahu sebabnya) sebagai kekuatan magis


2. Naturalisme, berarti sesuatu yang alami.

6.5 Sistem Penalaran Untuk Pengkatagorian : Jaringan Semantik , Logika Deskripsi 


Jaringan semantik


Jaringan semantik adalah gambaran pengetahuan grafis yang menunjukkan hubungan antar berbagai objek, terdiri dari lingkaran-lingkaran yang dihubungkan dengan anak panah yang menunjukkan objek dan informasi tentang objek-objek tersebut.

Dalam mata kuliah Pengantar Kecerdasan Buatan script merupakan representasi pengetahuan berdasarkan karakteristik yang sudah dikenal sebagai pengalaman-pengalaman yang menggambarkan urutan peristiwa.


Terdapat enam elemen script, yaitu :


1. Kondisi input, merupakan kondisi yang harus dipenuhi sebelum terjadi


2. Track, yaitu variasi kemungkinan yang terjadi


3. Prop, yaitu objek yang digunakan dalam suatu peristiwa


4. Role, yaitu peran dalam suatu peristiwa


5. Scene, yaitu adegan dalam suatu peristiwa


6. Hasil, yaitu kondisi setelah terjadinya urutan peristiwa



Deskripsi logika


deskripsi logika (deskripsi jamak logika) (logika) Salah satu keluarga bahasa representasi pengetahuan yang dapat digunakan untuk mewakili definisi konsep domain aplikasi (dikenal sebagai pengetahuan terminologi) dalam cara yang terstruktur dan formal dipahami dengan baik.


6.6 penalaran dengan informasi default 

Manusia memecahkan masalah melalui kombinasi antara fakta dan pengetahuan (knowledge). Penalaran (reasoning) adalah proses yang berhubungan dengan pengetahuan, fakta, dan strategi pemecahan masalah (problem solving) untuk mendapatkan konklusi/penyelesaian. Berbagai metode penalaran yang lazim adalah deduksi, induksi, abduktip, analogi, dan akal sehat, berikut ini penjelasan singkatnya.


Deduksi (deduction)Manusia menggunakan deduksi untuk mendapatkan informasi baru dari informasi yang sudah diketahui (pengetahuan) yang ada relasinya. Penalaran deduksi menggunakan fakta-fakta dari masalah yang ada dan pengetahuan umum yang sesuai yang pada umumnya berbentuk aturan (rules) atau implikasi (implications), jadi dari hal yang umum, dikenakan pada hal yang khusus, model deduksi adalah:


Fakta + Rule -> Efek dengan rule dalam bentuk:


If <cause/premise> then <effect/conclusion>


Jika <sebab/premis> Maka <akibat/konklusi>


     Sebagai contoh:


Aturan/implikasi: Jika saya berdiri di hujan, maka saya akan basah.


Fakta/premis : saya berdiri di hujan


Konklusi : saya akan basah


Penalaran deduksi sangat menarik secara logika dan merupakan teknik solusi masalah yang paling umum digunakan oleh manusia. Aturan inferensi (penyimpulan) yang disebut modus ponens adalah bentuk dasar dari penalaran deduksi dengan formula sbb.:


Jika A adalah benar, dan Jika A maka B adalah benar, maka B adalah benar


Induksi (Induction) 
Manusia menggunakan induksi untuk mendapatkan kesimpulan umum (general conclusion) dari sekumpulan/himpunan fakta melalui proses generalisasi. Ini bagaikan transisi dari jumlah sedikit ke semua. Model induksi adalah:
Cause + Effect -> Rule

Proses induksi dijelaskan oleh Firebaugh (1988) sbb.:

Untuk suatu himpunan objek X = {a,b,c,d, …}, jika sifat P adalah benar untuk a, dan jika sifat P adalah benar untuk b, dan jika sifat P adalah benar untuk c, …, maka sifat P adalah benar untuk semua X.

      Sebagai contoh:

Fakta/premis : aluminium dipanaskan memuai
Fakta/premis : besi dipanaskan memuai
Fakta/premis : tembaga dipanaskan memuai

Konklusi : secara umum, semua besi bila dipanaskan akan memuai


Abduktip (Abductive)
Abduktip adalah bentuk deduksi yang memungkinkan menarik kesimpulan yang bersifat “plausible”. Plausible (masuk akal) adalah konklusi yang ditarik dari informasi yang tersedia, namun ada kemungkinan konklusi itu salah, jadi model abduktip adalah:

Jika B adalah benar, dan Jika A maka B adalah benar, maka A adalah benar?

Atau effect + rule -> cause

Sebagai contoh:

Aturan : Tanah basah jika hari hujan.

Fakta : Tanah basah.

Konklusi : Hari hujan?

Jadi, diberikan fakta satu-satunya bahwa tanah basah, penyimpulan plausible menghasilkan konklusi hari hujan. Padahal, konklusi ini bisa salah, karena ada banyak hal yang menyebabkan tanah basah, misalnya seseorang siram-siram tanaman. Abduktip, sebagai salah satu metode penalaran, sering dipakai oleh dokter dalam mendiagnose pasien, maka diagnose dapat saja salah.


Analogi
Manusia membentuk model mental tentang konsep melalui pengalaman. Manusia menggunakan model ini melalui penalaran analogi untuk membantu memahami suatu masalah/situasi. Mereka lalu menarik analogi diantara masalah dan model, mencari kesamaan dan perbedaan untuk dapat menyimpulkan.

     Sebagai contoh:

Misalkan seorang dokter yang sudah puluhan tahun praktek, maka pengalamannya dalam bentuk kasus-kasus sudah sedemikian banyaknya. Bila kasus-kasus tersebut dapat disimpan secara cerdik dalam database kasus, maka dapat dipergunakan untuk menyelesaikan masalah baru bagi pasien baru tanpa dokter itu hadir (otomasi). Pasien baru memasukan karakter berikut data-data (keluhan) dari sakitnya, kemudian sistem mencari kasus pasien lama yang serupa keluhannya untuk ditampilkan solusinya, yaitu obat beserta dosisnya. Pengalaman adalah guru terbaik, maka pengalaman perlu disimpan secara cerdik untuk memecahkan persoalan baru yang mirip!


Akal Sehat (Common-sense) 

Lewat pengalaman, manusia belajar memecahkan persoalan secara effisien. Mereka menggunakan akal sehat untuk dengan cepat menarik kesimpulan. Akal sehat lebih cenderung berdasar pada kebijakan-kebijakan (judgments) yang baik daripada logika yang eksak. Contoh akal sehat adalah: Di suatu bengkel ditemukan suara klik-klik-klik dalam mesin sepeda motor, seorang montir yang berpengalaman, tanpa membongkar mesinnya, langsung dapat menyimpulkan bahwa ring piston pada silinder mesin itu perlu diganti. Pengetahuan akal sehat ini diperoleh dari pengalamannya mengerjakan banyak sepeda motor selama bertahun-tahun. Jenis pengetahuan seperti ini disebut sebagai heuristik (heuristic) atau rule-of-thumb. Akal sehat tidak menjamin ditemukannya solusi, namun ia menjamin kecepatan menemukan solusi.


Penalaran Tidak Monoton (non-monotonic)
Penalaran pada suatu masalah pada umumnya menggunakan informasi yang statis, artinya selama melakukan penyelesaian masalah, keadaan (nilai benar atau salah) bermacam fakta dianggap tetap konstan. Penalaran semacam ini disebut sebagai penalaran monoton (monotonic reasoning). Dalam beberapa masalah, ditemukan bahwa keadaan beberapa fakta (variabel) bersifat dinamis, sebagai ilustrasi adalah aturan sbb.:


IF Angin berhembus


THEN Kursi goyang akan berayun


Kemudian coba amati kejadian berikut, lalu apa yang terjadi dengan aturan diatas:


Hei, ada angin topan! -> ada Angin berhembus -> Kursi berayun


Seiring berlalunya angin topan, kita berharap kursi berayun. Namun, saat angin topan telah berlalu, kita berharap bahwa kursi sudah berhenti berayun. Namun sistem yang menggunakan penalaran monoton akan tetap menganggap bahwa kursi tetap berayun!


Manusia dengan ke enam inderanya tidak merasa sulit untuk mengikuti perubahan status informasi variabel yang dinamis. Bila terjadi perubahan yang dinamis, mereka dengan mudah menyesuaikan diri. Gaya penalaran semacam ini disebut penalaran yang tidak monoton. Untuk bidang AI, seperti expert system, dibutuhkan suatu sistem untuk memelihara kebenaran yang dinamis bila ingin melakukan penalaran yang tidak monoton.





Sumber :
http://informatika.web.id/category/kecerdasan-buatan/
https://www.researchgate.net/publication/316972662_Ontologi_Bahan_Kuliah_S3_Fasilkom-TI_USU
http://cs.unsyiah.ac.id/~irvanizam/ai/INF303-01.pdf

http://www.sigitprabowo.id/2013/01/kecerdasan-buatan-perbandingan.html

http://pbsabn.lecture.ub.ac.id/2012/05/penalaran-manusia/

https://www.masterstudies.co.id/Master-Program-Kecerdasan-Buatan/Belanda/MU-DKE/

Pertemuan Ke-5 : Logika Orde Pertama ( First Order Logic )

Nama : Rezky Audiansyah Putra

Kelas : 3KA12

NPM  : 18116161


Hasil PPT : https://drive.google.com/open?id=15Es1MvoZtg2oYbDOa85wZWPByo_pLoMa
---------------------------------------------------------------------------------------------------------------------------

1.1. PENGENALAN LOGIKA ORDE PERTAMA (FIRST ORDER LOGIC)

First order logic adalah sebuah bahasa formal yang digunakan di ilmu matematika, philosophy, bahasa dan ilmu computer. Disebut juga kalkulus predikat, merupakan logika yang digunakan untuk merepresentasikan masalah yang tidak dapat direpresentasikan dengan menggunakan proposisi. Logika predikat dapat memberikan representasi fakat-fakta sebagai suatu pernyataan yang mapan (well form). Kalkulus predikat bisa menganalisakan kalimat-kalimat ke dalam subjek dan argumen dalam berbagai cara yang berbeda-beda, yang pada akhirnya kalkulus predikat bisa digunakan untuk memecahkan problem of multiple generality (masalah dalam berbagai keadaan umum) yang telah membingungkan sebagian besar ahli-ahli logika abad pertengahan. Dengan menggunakan logika predikat ini, untuk pertama kalinya, para ahli-ahli logika bisa memberikan quantifier yang cukup umum untuk merepresentasikan semua argumen yang terdapat pada natural language.

Pemanfaatan FOL untuk merepresentasikan fakta adalah salah satu teknik dasar yang sudah sejak lama dipakai untuk dapat mengkodekan bahasa alami ke dalam bentuk formal. Dengan menggunakan FOL, diharapkan fakta (dan juga pertanyaan) dapat direpresentasikan secara tepatke dalam konteksnya masing-masing, sehingga jawaban akhir yang dikembalikan kepada pengguna adalah jawaban yang tingkat kesasihannya (validity, di dalamnya mencakup consistency dan informativeness) sangat tinggi. Jika kita berbicara mengenai logika predikat, maka patut diperhatikan bahwa pada tahun 1879, filsuf berkebangsaan Jerman yang bernama Gottlob Frege menerbitkan sebuah risalat yang luar biasa, yang berjudul the Begriffsschrift (“Concept Script”). Monograp yang brilian ini dianggap sebagai asal muasal dari teori logika modern. Akan tetapi, dalam risalat milik Friege ini masih terdapat banyak kekurangan dalam beberapa bagian dan janggal dalam penotasiannnya. Walaupun demikian, penemuan Frege ini tetap diakui. Selain penemuan dari Frege, formulasi dari logika predikat yang sering digunakan sekarang adalah firstorder logic atau yang biasa dikenal dengan kalkulus predikat yang tercatat dalam Principle of Theorical Logic yang ditulis oleh David Hilbert dan Wilhelm Ackerman pada tahun 1928. First order logic dalam hal ini merupakan dasar pendiri logika matematika modern.

Di sini hanya akan disediakan beberapa poin penting yang membedakan kalkulus predikat dengan logika Aristotle. Beberapa poin tersebut diantaranya:
Di dalam kalkulus predikat didefinisikan bahwa subjek adalah hanya sebuah individu tidak pernah merupakan sekelompok individu. Karena subjek dalam kalkulus predikat ini hanyalah sebuah individu, maka subjek di sini lebih umum untuk disebutkan sebagai individual. Kalkulus predikat memakai banyak simbol-simbol khusus untuk menotasikan sesuatu. Huruf kecil a, b, c, d, …, z digunakan untuk menyatakan individual. Huruf kapital M, N, P, Q, R, … digunakan untuk menyatakan predikat. Jika terdapat notasi seperti Ma, maka dikatakan bahwa a adalah argument untuk M. Selain huruf kecil dan huruf kapital, kalkulus predikat juga menggunakan beberapa simbol khusus untuk menotasikan operator-operator logika. Beberapa simbol khusus itu adalah: ∧ ∨ ~ ⊃ ≡
Sebuah formula adalah ekpresi yang memiliki arti dan dibangun oleh atom-atomnya dan digabungkan dengan menggunakan operatoroperator logika. Kalkulus predikat memiliki kapabilitas yang besar dalam mengekspresikan suatu hal. Banyak pernyataan dalam natural language yang bisa direpresentasikan dengan baik oleh kalkulus predikat. Hal inilah yang kurang dimiliki oleh logika Aristoteles.

Dalam first-order logic yang paling utama adalah bahwa dunia berisi objek-objek yaitu identitas (ciri-ciri individu) dan sifat (properties) yang membedakan mereka dengan objek yang lain. Diantara objek tersebut, akan dibuat bermacam-macam relasi. Beberapa relasi adalah fungsi yaitu hubungan dimana hanya ada satu nilai untuk satu input. Jadi pada first-order logic mengasumsikan “world” memuat :
§  Objek : hal-hal yang berhubungan dengan identitas individu, misalnya : manusia, rumah, teori-teori, warna, mobil, dan lain-lain.
§  Sifat (properties): sifat benda yang membedakannya dari benda lain, misalnya: merah, bulat, tipis, dan lain-lain
§  Relasi : hubungan antara benda yang satu dengan benda yang lainnya, misalnya: lebih besar dari, lebih kecil dari, memiliki, terjadi setelah, dan lain-lain.
§  Fungsi (Functions): merupakan subset dari hubungan di mana hanya ada satu “nilai” untuk setiap “input” yang diberikan, misalnya: ayah dari, teman baik, dan lain-lain.

First Order Logic sangat penting dalam ilmu matematika, filsafat, kecerdasan buatan, karena ruang lingkupnya, sebab keberadaan manusia sehari-hari selalu berhubungan dengan obyek dan hubungan antar manusia sendiri. Sehingga kita tidak dapat menyangkal bahwa dunia ini terdiri dari obyek dan hubungan (relasi).


1.2. SINTAK DAN SEMANTIK LOGIKA ORDE PERTAMA

§  Model
Sebuah model adalah sebuah situasi yang menjelaskan hal-hal yang menjadi konteks pembicaraan. Untuk membentuk sebuah model, diperlukan adanya kosa-kata (vocabularies), yaitu daftar istilah yang membentuk model tersebut. Sebuah kosa-kata berisikan topik pembicaraan dan bahasa (simbol) yang digunakan dalam pembicaraan. Dalam contoh kalimat‘ayah dan anto makan sepiring nasi’, akan terdapat kosa-kata sebagai berikut: {(ayah,1), (anto,0),(makan,2), (nasi,1)}. Dalam kosa-kata ini akan terlihat bagaimana relasi antara fakta atauvariabel yang satu dengan lainnya di dalam representasi. Perlu dibedakan antara fakta (sebuah konstanta / non-binding variable), dengan variabel yang dapat menampung sebuah fakta (binding variable). Dalam contoh, relasi ‘makan’ menjelaskan bahwa aktivitas tersebut dapat terjadi jika melibatkan dua konstanta (relasi biner yang memiliki arity2). Angka 1 menjelaskan bahwa terjadi relasi tunggal (arity1), yang dapat diisikan (binding) dengan sebuah konstanta. Angka 0 menjelaskan sebuah konstanta, dan bukan merupakan relasi.

§  Syntax FOL: Elemen-Elemen Dasar
Elemen-elemen dasar FOL:
Constants : KingJohn, 2, UB, ITS, UI, Malang, Depok , . . .
Predicates : Brother , >, Loves, Membenci , Mengajar , . . .
Functions : Sqrt , LeftLegOf , Ayah, . . .
Variables : x , y , a, b, . . .
Connectives : ∧ ∨ ¬ ⇒ ⇔
Equality :        =
Quantifiers : ∀ ∃

§  Syntax FOL : Kalimat Atomic
Definisi atomic sentence : predicate(term1, , termn) atau term1 = term2
Definisi term :
function(term1, , termn) atau constant atau variable
Contoh :
Brother (KingJohn, RichardTheLionheart )
> (Length(LeftLegOf (Richard)), Length(LeftLegOf (KingJohn)))

§  Syntax FOL : Kalimat Kompleks
Kalimat kompleks complex sentence terdiri dari sentence yang digabungkan dengan connective.
Definisi complex sentence : ¬S, S1∧ S2, S1∨ S2, S1 ⇒ S2, S1 ⇔ S2
Contoh :
Sibling(KingJohn, Richard ) ⇒ Sibling(Richard , KingJohn)
>(1, 2) ∨ ≤(1, 2)
>(1, 2) ∧ ¬>(1, 2)
Belajar (x , SC) ⇒ Mengerti(x , AI)

§  Semantics FOL : Truth & Model
Sama halnya dengan. Proposisi Logic (PL), sebuah kalimat FOL bisa juga dikatakan true terhadap sebuah model.
Namun, sebuah kalimat bisa diinterpretasikan banyak cara dalam sebuah model.
Model berisi :
Objects : elemen-elemen di dalam dunia (domain elements).
Relations : hubungan antara elemen-elemen tersebut.
Sebuah interpretasi mendefinisikan referent (“yang dipetakan”)
Constant symbols → objects
Predicate symbols → relations
Function symbols → functional relations

§  Kemungkinan Model & Interpretasi
Entailment , validity , satisfiability , dll. Didefinisikan untuk semua kemungkinan interpretasi dari semua kemungkinan model!
Kalau mau dijabarkan semua kemungkinannya: For each number of domain elements n from 1 to ∞ For each k -ary predicate Pk in the vocabulary For each possible k -ary relation on n objects For each constant symbol C in the vocabulary For each choice of referent for C from n objects . .
Menentukan entailment berdasarkan truth-table? mustahil!
Biasanya ada satu interpretasi yang “dimaksudkan” → intended interpretation.

§  Quantifier
Selain penggunaan predikat, First Order Logic juga menawarkan quantifier untuk membuat kalimat logika yang lebih sederhana. Ada 2 jenis quantifier, yaitu universal dan existential. Quatifier ini berlaku terhadap parameter yang muncul di sebuah kalimat masih dalam bentuk variabel. Universal quantifier terhadap sebuah variabel x (disimbolkan dengan ∀x) berarti bahwa kalimat tersebut berlaku untuk setiap obyek x, sedangkan existential quantifier (disimbolkan dengan ∃x) berarti berlaku untuk sebagian obyek saja.

Contoh: Menggunakan definisi untuk p(x), r(x), dan q(x,y), berikut adalah kalimat-kalimat logika dengan menggunakan quantifier dan artinya:
§  ∀x(p(x) Λ r(rabu) → q(x,merah-putih)) : untuk setiap x, jika x adalah seorang siswa kelas II SD dan pada hari Rabu maka x akan mengenakan seragam merah-putih.

§ ∃x(p(x) → ¬q(x,merah-putih)) : ada x, jika x adalah seorang siswa kelas II SD maka x tidak mengenakan seragam merah putih.

§  Universal Quantifier
Dalam logika predikat , quantifieri universal merupakan jenis quantifier , sebuah konstanta logis yang ditafsirkan sebagai “diberi” atau “untuk semua”. Ini mengungkapkan bahwa fungsi proposisi dapat dipenuhi oleh setiapanggota dari domain wacana. Dalam istilah lain, itu adalah predikasi dari properti atau hubungan dengan setiap anggota domain. Ini menegaskanbahwa predikat dalam lingkup dari quantifier universal benar dari setiap nilai dari variabel predikat .
Hal ini biasanya dilambangkan dengan berbalik A (∀) operator logika simbol, yang bila digunakan bersama-sama dengan variabel predikat, disebut quantifier universal  (“∀x”, “∀ (x)”, atau kadang-kadang dengan “(x) “saja). Kuantifikasi Universal berbeda dari kuantifikasi eksistensial (“ada ada”), yang menegaskan bahwa properti atau relasi hanya berlaku untuk setidaknya satu anggota dari domain.
Contoh 1 :
(∀x) (x + x = 2x)
“untuk setiap x (dimana x adalah suatu bilangan), kalimat x + x = 2x adalah benar.”
Contoh 2 :
(∀x) (p) (Jika x adalah seekor kelinci -> x adalah binatang).
Kebalikan kalimat “bukan kelinci adalah binatang” ditulis :
(∀x) (p) (Jika x adalah seekor kelinci -> ~x adalah binatang)
dan dibaca :
– “setiap kelinci adalah bukan binatang”
“semua kelinci adalah bukan binantang”

§  Existential Quantifier
Dalam logika predikat , suatu quantifier eksistensial adalah jenis quantifier , sebuah konstanta logis yang ditafsirkan sebagai “ada ada,” “ada setidaknya satu,” atau “untuk beberapa.” Ini mengungkapkan bahwa fungsi proposisi dapat dipenuhi oleh setidaknya satu anggota dari domain wacana . Dalam istilah lain, itu adalah predikasi dari properti atau hubungan dengan setidaknya satu anggota dari domain. Ini menegaskan bahwa predikat dalamlingkup dari quantifier eksistensial adalah benar dari setidaknya satu nilai darivariabel predikat .
Hal ini biasanya dilambangkan dengan E berubah (∃) operator logika simbol, yang bila digunakan bersama-sama dengan variabel predikat, disebut quantifier eksistensial (“∃x” atau “∃ (x)”) Kuantifikasi eksistensial.
Contoh 1 :
(∃x) (x . x = 1)
Dibaca : “terdapat x yang bila dikalikan dengan dirinya sendiri hasilnya sama dengan 1.”
Contoh 2 :
(∃x) (panda(x) ∧ nama(Clyde))
Dibaca : “beberapa panda bernama Clyde”.
Contoh 3 :
(∀x) (jerapah(x) -> berkaki empat(x))
Dibaca : “semua jerapah berkaki empat”.
Universal quantifier dapat diekspresikan sebagai konjungsi.
(∃x) (jerapahh(x) ∧ berkaki tiga(x))
Dibaca : “ada jerapah yang berkaki tiga”
Existensial quantifier dapat diekspresikan sebagai disjungsi dari
urutan ai. P(a1) ∨ P(a2) ∨ P(a3) …∨ P(aN)

1.3. PENGGUNAAN LOGIKA ORDE PERTAMA

1. Assertions and queries in first-order logic.
2. The kinship domain.
3. Numbers, sets, and lists.


1.4. REKAYASA PENGETAHUAN PADA LOGIKA ORDE PERTAMA

1. Identify the task.
2. Assemble the relevant knowledge.
3. Decide on a vocabulary of predicates, functions, and constants.
4. Encode general knowledge about the domain
5. Encode a description of the specific problem instance.
6. Pose queries to the inference procedure and get answers.
7. Debug the knowledge base.


 1.5. LOGIKA PROPOSISI VS INFERENSI LOGIKA ORDE PERTAMA

Contoh Permasalahan
Pembuktian Logika Proposisi
Setiap manusia pasti mati. Karena Sayuti adalah manusia, maka dia pastimati.
Secara intuisi kalimattersebut bernilai Benar. Berdasarkan logika proposisi kalimat tersebut dapat
disimbolkan sebagai:
p : Setiap manusia pasti mati
q : Sayuti adalah manusia
r : Sayuti pasti mati

Berdasarkan kerangka berfikir Logika Proposisi bukanlah konsekuensi Logis dari pdan q. Pernyataan
‘Setiap manusia pasti mati’ mengandung pernyataan Himpunan, yaitu Himpunan ‘manusia’, dimana
individu yang merupakan bagian dari himpunan manusia jumlahnya tidak terhingga. Sedangkan
pernyataan ‘Sayuti adalah manusia’ secara implisit menyatakan anggota dari himpunan ‘manusia’/
universal of discourse.
Struktur sepertidiatas tidak dikenali oleh Logika Proposisi, karena apabila ingin membuktikan
kebenaran dari pernyataan ‘Setiap manusiapasti masti’ maka harus dicari nilai kebenaran dari seluruh
elemen himpunan manusia yang jumlahnya tak terhingga. Ini tidak mungkin dilakukan.

Untuk mengatasi permasalahan diatas diperlukan kerangka berfikir lain selain Logika Proposisi yaitu
Logika First-Order (Kalkulus Predikat). Maka dapat didefinisikan bahwa Logika First-Order adalah
perluasan dari konsep Logika Proposisi untuk mengatasi permasalahan yang tidak dapat dipecahkan
melalui kerangka berfikir Logika Proposisi dengan penambahan 3 komponen logika yaitu: Term
(suku), Predicate dan Quantifier.

Pembuktian pada Logika First-Order
Pembuktian Logika First-Order hampir sama dengan pembuktian pada Logika Proposisi. Hanya saja
pada Logika First-Order pembuktian menggunakan Aturan Inferensi lebih mungkin untuk dilakukan.

Contoh:
Buktikan bahwa “Setiap manusia pasti mati. Sayuti adalah manusia, Karenanya Sayuti pasti mati.”
Jawab:
Misal dideklarasikan predikat berikut:
MAN(x)        :x adalah manusia
MORTAL(x) :x pasti mati
Maka pernyataan pada soal menjadi:
P1                  :(x) (MAN(x) MORTAL(x))
P2                  :MAN(Sayuti)
Untuk membuktikan bahwa kesimpulan “Sayuti pasti mati”harus dibuktian bahwa MORTAL(Sayuti)
adalah konsekuensi logis dari P1dan P2. Maka;
Dilakukan pembuktian langsung:
P1P2             : (x) (MAN(x) MORTAL(x)) MAN(Sayuti)
Karena (MAN(x)  MORTAL(x)) bernilai Benar untuk semua x maka;
(MAN(Sayuti)  MORTAL(Sayuti)) juga Benar
(x) (MAN(x)MORTAL(x))
MAN(Sayuti)
(MAN(Sayuti)MORTAL(Sayuti))

MORTAL(Sayuti)
Premis P1
Premis P2
Langkah 1 dan 2
P1: x Sayuti


1.6. UNIFIKASI DAN LIFTING
Unifikasi adalah usaha untuk mencoba membuat dua ekspresi menjadi identik (mempersatukan keduanya) dengan mencari substitusi-substitusi tertentu untuk mengikuti peubah-peubah dalam ekspresi mereka tersebut. Unifikasi merupakan suatu prosedur sistematik untuk memperoleh peubah-peubah instan dalam wffs. Ketika nilai kebenaran predikat adalah sebuah fungsi dari nilai-nilai yang diasumsikan dengan argumen mereka, keinstanan terkontrol dari nilai-nilai selanjutnya yang menyediakan cara memvalidasi nilai-nilai kebenaran pernyataan yang berisi predikat. Unifikasi merupakan dasar atas kebanyakan strategi inferensi dalam Kecerdasan Buatan. Sedangkan dasar dari unifikasi adalah substitusi.
Suatu substitusi (substitution) adalah suatu himpunan penetapan istilah-istilah kepada peubah, tanpa ada peubah yang ditetapkan lebih dari satu istilah. Sebagai pengetahuan jantung dari eksekusi Prolog, adalah mekanisme unifikasi.

Aturan-aturan unifikasi :
1.     Dua atom (konstanta atau peubah) adalah identik.
2.     Dua daftar identik, atau ekspresi dikonversi ke dalam satu buah daftar.
3.  Sebuah konstanta dan satu peubah terikat dipersatukan, sehingga peubah menjadi terikat kepada konstanta.
4.     Sebuah peubah tak terikat diperssatukan dengan sebuah peubah terikat.
5.  Sebuah peubah terikat dipersatukan dengan sebuah konstanta jika pengikatan pada peubah terikat dengan konstanta tidak ada konflik.
6.   Dua peubah tidak terikat disatukan. Jika peubah yang satu lainnya menjadi terikat dalam upa-urutan langkah unifikasi, yang lainnya juga menjadi terikat ke atom yang sama (peubah atau konstanta).
7.    Dua peubah terikat disatukan jika keduanya terikat (mungkin melalui pengikatan tengah) ke atom yang sama (peubah atau konstanta).


1.7. FORWARD & BACKWARD CHAINING

§  FORWARD CHAINING
Forward chaining merupakan metode inferensi yang melakukan penalaran dari suatu masalah kepada solusinya. Jika klausa premis sesuai dengan situasi (bernilai TRUE), maka proses akan menyatakan konklusi. Forward chaining adalah data-driven karena inferensi dimulai dengan informasi yang tersedia dan baru konklusi diperoleh. Jika suatu aplikasi menghasilkan tree yang lebar dan tidak dalam, maka gunakan forward chaining.

Contoh :
Terdapat 10 aturan yang tersimpan dalam basis pengetahuan yaitu :
R1 : if A and B then C
R2 : if C then D
R3 : if A and E then F
R4 : if A then G
R5 : if F and G then D
R6 : if G and E then H
R7 : if C and H then I
R8 : if I and A then J
R9 : if G then J
R10 : if J then K

Fakta awal yang diberikan hanya A dan E, ingin membuktikan apakah K bernilai benar.

§  BACKWARD CHAINING
Menggunakan pendekatan goal-driven, dimulai dari harapan apa yang akan terjadi (hipotesis) dan kemudian mencari bukti yang mendukung (atau berlawanan) dengan harapan kita. Sering hal ini memerlukan perumusan dan pengujian hipotesis sementara. Jika suatu aplikasi menghasilkan tree yang sempit dan cukup dalam, maka gunakan backward chaining.


1.8. RESOLUSI LOGIKA PREDIKAT

Resolusi pada logika predikat pada dasarnya sama dengan resolusi pada logika proposisi, hanya saja ditambah dengan unifikasi.Pada logika predikat, prosedur untuk membuktikan pernyataan P dengan beberapa pernyataan F yang telah diketahui, dengan menggunakan resolusi, dapat dilakukan melalui algoritma sebagai berikut :

1.     Konversikan semua proposisi F ke bentuk klausa
2.     Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa.Tambahkan   kehimpunan klausa yang telah ada pada langkah
3.     Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan :
§  Seleksi 2 klausa sebagai klausa parent
§  Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut  resolvent. Jika ada pasangan literal T dan ¬T2 sedemikian hingga keduanya dapat dilakukan unifikasi, maka salah satu T1 dan T2 disebut sebagai complementary literal. Jika ada lebih dari 1 complementary literal, maka hanya sepasang yang dapat meninggalkan resolvent
§  Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada

Contoh kasus :
Misalkan terdapat pernyataan-pernyataan sebagai berikut :
1.     Fajar adalah seorang mahasiswa
2.     Fajar masuk Jurusan Elektro
3.     Setiap mahasiswa elektro pasti mahasiswa Teknik
4.     Kalkulus adalah matakuliah yang sulit
5.     Setiap mahasiswa teknik pasti akan suka kalkulus atau akan membencinya
6.     Setiap mahasiswa pasti akan suka terhadap suatu matakuliah
7.     Mahasiswa yang tidak pernah hadir pada kuliah matakuliah sulit, maka mereka pasti tidak   suka terhadap matakuliah tersebut
8.     Fajar tidak pernah hadir kuliah matakuliah kalkulus


Maka harus terlebih dahulu diubah ke dalam bentuk klausa sebagai berikut :
1.     Mahasiswa (Fajar)
2.     Elektro (Fajar)
3.     Elektro (x1) v Teknik (v1)
4.     Sulit (Kalkulus)
5.     Teknik (x2) v suka (x2, Kalkulus) v benci (x2, Kalkulus)
6.     Suka (x3, f1 (x3))
7.     Mahasiswa (x4) v ¬ sulit (y1) v hadir (x4, y1) v ¬ suka (x4, y1)
8.     Hadir (Fajar, Kalkulus)



 


Referensi:

        http://imamcs.lecture.ub.ac.id/tag/logika-order-pertama-first-order-logic/
        http://troublemackr.binusian.org/2014/03/30/first-order-logic/
        http://dinus.ac.id/repository/docs/ajar/slide_8_log_inf.pptx
        http://otnaites.co.id/2015/10/logika-first-order.html

Pertemuan ke-4 : Pengetahuan dan Penalaran - Agent Logika

Nama : Rezky Audiansyah Putra
NPM  : 18116161
Kelas : 3KA12

Hasil PPT : https://drive.google.com/open?id=1xA8GgSZ9GgktRB70p1ElVVMNbzJz329K

Pengetahuan Berbasis Agent Logika

Representasi pengetahuan adalah cara untuk menyajikan pengetahuan yang diperoleh ke dalam suatu skema/diagram tertentu sehingga dapat diketahui relasi antara suatu pengetahuan dengan pengetahuan yang lain dan dapat dipakai untuk menguji kebenaran penalarannya.
 Logika sebagai Bahasa Representasi Pengetahuan memliki pengertian Logika sebagai bhasa formal untuk memrepresentasikan fakta sedemikian sehinga kesimpulan (fakta baru,jawaban) dapat ditarik.
Ada banyak metode inference yang diketahui sehingga kata bias mebangun  agent Wumpus Wold dengan logika. Memanfaatkan perkembangan logika oleh ahli metematika, filsafat selama ratusan tahun.

Inferensi merupakan proses atau algoritma yang “merunkan” fakta baru dari fakta-fakta yang lama. Reasong bukan dilakukan pada fakta di dunia (berdasarkan semantic), melainkan representasi fakta dalam bahasa representasi pengetahuan si agent (secara sintaks). Otak manusia melakukan proses reasoning dalam suatu bentuk sintak dapat di ilustrasikan.

Agen berbasis pengetahuan menggunakan inferensi dan knowledge base untuk menghasilkan informasi baru atau untuk mengambil keputusan.

Logika

Logika didefinisikan sebagai ilmu untuk berpikir dan menalar dengan benar sehingga didapatkan kesimpulan yang absah.
Tujuan dari logika: memberikan aturan-aturan penalaran sehingga orang dapat menentukan apakah suatu kalimat bernilai benar atau salah.
Representasi Logika dibagi menjadi dua:
Propositional Logic (Logika Proposisi)
Suatu Proposisi merupakan suatu statemen atau pernyataan yang menyatakan benar (TRUE) atausalah (FALSE). Dalam Propositional Logic fakta dilambangkan dengan simbol misalnya P, Q dan R.Lambang-lambang tersebut dihubungkan dengan relasi-relasi logika
Dengan menggunakan operator logika:

Tabel Kebenaran Logika

Predicate Logic (Logika Predikat)
Pada logika predikat proposisi dibedakan menjadi argumen (obyek) dan predikat (keterangan). Secara umum penulisan proposisi dalam logika predikat dapat dinyatakan sebagai berikut:
Predikat (argumen-1, argumen-2,..., argumen-3)
Contoh:
Proposisi: “Bu Atika mencintai Pak Agus Setiawan”
Dalam logika predikat disajikan dalam bentuk:
Mencintai (Bu Atika, Pak Agus Setiawan)
      P         Argumen-1            Argumen-2



1.         Logika Proposisi
Proposisi adalah suatu pernyataan yang dapat bernilai Benar atau Salah. Simbol-simbol seperti P dan Q menunjukkan proposisi. Dua atau lebih proposisi dapat digabungkan dengan menggunakan operator
logika :

a.Konjungsi : ∧ (and)      
b. Disjungsi : ∨ (or)         
c. Negasi : ¬ (not)           
d.Implikasi : Æ (if then)  
e. Ekuivalensi : ↔ (if and only if)

2.         Logika Predikat

Representasi Fakta Sederhana
Misal diketahui fakta-fakta sebagai berikut :

Andi adalah seorang laki-laki : A
Ali adalah seorang laki-laki : B
Amir adalah seorang laki-laki : C
Anto adalah seorang laki-laki : D
Agus adalah seorang laki-laki : E

Jika kelima fakta tersebut dinyatakan dengan menggunakan proposisi, maka akan terjadi pemborosan, dimana beberapa pernyataan dengan predikat yang sama akan dibuat dalam proposisi yang berbeda. Logika predikat digunakan untuk merepresentasikan hal-hal yang tidak dapat direpresentasikan dengan menggunakan logika proposisi. Pada logika predikat kita dapat merepresentasikan fakta-fakta sebagai suatu pernyataan yang disebut dengan wff (well –formed formula). Logika predikat merupakan dasar bagi bahasa AI seperti bahasa pemrograman PROLOG Pada contoh diatas, dapat dituliskan :

laki-laki(x)
dimana x adalah variabel yang disubstitusikan dengan Andi, Ali, Amir, Anto, Agus, dan laki-laki yang lain. Dalamlogika predikat, suatu proposisi atau premis dibagi menjadi 2 bagian, yaitu argumen (objek) dan predikat (keterangan). Argumen adalah individu atau objek yang membuat keterangan. Predikat adalah keterangan yang membuat argumen dan predikat.

Misal terdapat pernyataan sebagai berikut :

1.Andi adalah seorang mahasiswa
2.Andi masuk jurusan Elektro
3.Setiap mahasiswa elektro pasti mahasiswa teknik
4.Kalkulus adalah matakuliah yang sulit
5.Setiap mahasiswa teknik pasti akan suka kalkulus atau akan membencinya
6.Setiap mahasiswa pasti akan suka terhadap suatu matakuliah
7.Mahasiswa yang tidak pernah hadir pada kuliah matakuliah sulit, maka mereka pasti tidak suka terhadap matakuliah tersebut.
8.Andi tidak pernah hadir kuliah matakuliah kalkulus

 Logika Proposisi/Logika Sederhana

Sistem logis paling sederhana. Kita harus mendefinisikan sehimpunan simbol proposisi, misal: P, Q. Kemudian definisikan semantik dari simbol tersebut.

Contoh:
P berarti “Minggu adalah hari libur”.
Q berarti “Sekarang adalah hari minggu”.

Himpunan operator digunakan dalam proses penalaran terhadap nilai-nilai kebenaran.

Operator Logika

Operator Dasar
–And, Dan ∧
–Or, Atau ∨
–Not, Tidak￢
–Implies, Maka, Menyebabkan ⇒
–Iff(if and only if), Jika dan hanya jika ⇔

Contoh Logika Proposisi:
–        R: Sekarang Hujan
–        D: Sekarang Gelap
–        C: Sekarang Dingin

Pola Penalaran (reasoning pattern) pada logika proposi

Resolusi
Diperkenalkan oleh Robinson (1965). Resolusi merupakan kaidah inferensi utama dalam bahasa PROLOG. PROLOG menggunakan notasi “quantifier-free”.•PROLOG didasarakan pada logika predikat urutan pertama.
Sebelum resolusi diaplikasikan, wff harus berada dalam bentuk normal atau standard.

Tiga tipe utama bentuk normal : conjunctive normal form, clausal form dan subset Horn clause. Resolusi diaplikasikan ke dalam bentuk normal wff dengan menghubungkan seluruh elemen dan quantifier yang dieliminasi.




Backward
Chain (rantai) : perkalian inferensi yang menghubung-kan suatu permasalahan dengan solusinya.
Backward chaining.
 Suatu rantai yang dilintasi dari suatu hipotesa kembali ke fakta yang mendukung hipotesa tersebut. Tujuan yang dapat dipenuhi dengan pemenuhan sub tujuannya.

Forward chaining
Suatu rantai yang dicari atau dilewati/dilintasi dari suatu permasalahn untuk memperoleh solusi. –Penalaran dari fakta menuju konklusi yang terdapat dari fakta.

Iterferensi Proporsi yang Efektif :

Algoritma Backtracking, Algoritma Pencarian Lokal.
1.      Algoritma Backtracking
Algoritma backtrack pertama kali diperkenalkan oleh D.H. Lehmer pada tahun 1950[10]. Dalam perkembangan algoritma ini, beberapa ahli seperti Rwalker, Golomb, dan Baumert menyajikan uraian umum tentang backtrack dan penerapannya dalam berbagai persoalan dan aplikasi. Algoritma backtracking adalah sebuah algoritma yang berbasis depth-first search (DFS) dalam pencarian solusi pada pohon ruang status yang dibangun secara dinamis. Algoritma ini membangun solusi parsial (partial solution) dari sebuah kandidat solusi dan mengevaluasi solusi parsial tersebut pada suatu waktu. Jika solusi parsial yang dibangun tidak memenuhi syarat, maka kandidat solusi tersebut tidak akan dibangun lebih lanjut dan dilakukan backtrack ke kandidat solusi lain yang memenuhi syarat. Algoritma backtracking dilakukan secara berulangulang hingga menemukan sebuah solusi yang sesuai dengan syarat.
Langkah-langkah pencarian solusi pada algoritma backtracking adalah sebagai berikut.
 1. Solusi dicari dengan membentuk lintasan dari akar ke daun. Simpul yang telah dilahirkan dinamakan simpul hidup dan simpul hidup yang diperluas dinamakan simpul-E (Expand node).
2. Jika lintasan yang diperoleh dari perluasan simpul-E tidak mengarah ke solusi, maka simpul itu akan menjadi simpul mati yang tidak dapat diperluas lagi.
3. Jika posisi terakhir ada di simpul mati, maka pencarian dilakukan dengan membangkitkan simpul anak yang lainnya dan jika tidak ada simpul anak maka dilakukan backtracking ke simpul induk.
4. Pencarian dihentikan jika kita telah menemukan solusi atau tidak ada simpul hidup yang dapat ditemukan.

2.      Algoritma Pencarian Lokal
Pencarian lokal terdiri dari:
Hill-Climbing Search
• Pemilihan state berdasarkan nilai objektifnya 
Genetic Algorithm
• Pemilihan state berdasarkan aturan seleksi alam yang diterapkan pada state collection (sering disebut sebagai populasi)

Agen Berbasis Logika Proposisi

q  Logika Proposisi
o   Merupakan logika yang paling sederhana. Sebuah sentence dinyatakan sebagai simbol proposional P1, P2, dst.
o   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)
§  Jika  S1 dan S2 adalah kalimat, S1 ↔ S2 adalah kalimat (biconditional)











Referensi:




https://dokumen.tips/download/link/intelijensia-buatan-03-agen-pencarian-searching-agent
https://www.slideshare.net/RamlaLamantha/modul-bahanajarkecerdasanbuatanptiikfinal
http://e-learning.kaputama.ac.id/pluginfile.php/83/mod_resource/content/1/kecerdasanbuatanv2bab1-4.pdf
https:/educa.id/download/link/intelijensia-buatan-03-agen-pencarian-searching-agent
http://www.academia.edu/9763118/Metode_Inferensi_1_54_Pengantar_Kecerdasan_Buatan_AK045218
http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2007-2008/Makalah2008/MakalahIF2251-2008-083.pdf
http://blog.ub.ac.id/ucupucup/files/2013/10/09-Agen-Logika_AI_EFIK_V3.4.ppt

Pertemuan Ke-3 : Pencarian Berbentuk/ Heuristik Search Dan Eksplorasi

Nama  : Rezky Audiansyah Putra
Kelas  : 3KA12
NPM   : 18116161

Hasil PPT : https://drive.google.com/open?id=1cB1XbmcKjU2DJlwazSyUdLZBXkn4sUF8 

Strategi pencarian berbentuk / heuristik 

search strategy  

      Teknik Dasar Pencarian  Pencarian adalah proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space). Pencarian atau pelacakan merupakan salah satu teknik untuk menyelesaikan permasalahan AI. Teknik pencarian terbagi atas dua teknik, yaitu pencarian buta (blind search) dan pencarian heuristik (heuristic search).

      Penelitian yang pernah dilakukan mengenai permainan pergeseran angka dalam bentuk bintang yaitu dengan menggunakan algoritma breadth first search. Pada penelitian ini penulis menggunakan algoritma Best First Search untuk penyelesaian permainan pergeseran angka pada bentuk bintang ini. Algoritma best first search adalah salah satu algoritma pencarian heuristik yang merupakan kombinasi dari dua algoritma pencarian buta (blind search), yaitu breadth first search dan depth first.

•      Pencarian Heuristik (Heuristic Search)

     Pencarian terbimbing (heuristic search) dibutuhkan karena pencarian buta (blind search) tidak selalu dapat diterapkan dengan baik, hal ini dikarenakan waktu aksesnya yang cukup lama serta besarnya memori yang diperlukan.

      Kelemahan ini dapat diatasi jika ada informasi tambahan (fungsi heuristik) dari domain yang bersangkutan. Pada pencarian heuristik, sebuah fungsi heuristik digunakan untuk mengevaluasi keadaan permasalahan tersendiri dan menentukan bagaimana fungsi ini diperlukan dalam memecahkan suatu permasalahan. Sebuah fungsi heuristik adalah sebuah fungsi yang memetakan keadaan permasalahan, yang menjelaskan daya tarik dan digambarkan dalam sebuah angka.

      

      Beberapa heuristik lebih baik dari pada heuristik lainnya, dan semakin baik suatu heuristik, maka semakin sedikit node yang diperlukan untuk diperiksa dalam pohon pencarian untuk menemukan solusi. Oleh karena itu, seperti memilih representasi yang tepat, memilih heuristik yang tepat dapat membuat perbedaan yang signifikan dalam membantu kita untuk memecahkan masalah.

     

      Dalam tugas akhir ini, fungsi heuristik yang akan dipakai sebagai fungsi evaluasi untuk menuntun arah pencarian solusi, adalah Gaschnig’s heuristic. Gaschnig’s heuristic mengukur jumlah pergeseran (swap) dengan tempat/ubin kosong untuk menghasilkan keadaan tujuan (goal state).

•       Algoritma Best First Search

      Apabila pada pencarian dengan algoritma hill climbing tidak diperbolehkan untuk kembali ke node pada level yang lebih rendah meskipun node di level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik, lain halnya pada algoritma best first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node di level yang lebih tinggi memiliki nilai heuristik yang lebih buruk.Setiap sebuah node dikembangkan, algoritma akan menyimpan setiap successor node n sekaligus dengan harga (cost) dan petunjuk pendahulunya (parent). Algoritma akan berakhir pada node tujuan, dan tidak ada lagi pengembangan node. “Best first” mengacu pada algoritma mengeksplorasi node dengan "nilai" terbaik pertama. Sebuah fungsi evaluasi digunakan untuk menetapkan nilai untuk setiap calon node. Dalam algoritma ini, ruang pencarian dievaluasi menurut fungsi heuristik yang dinyatakan dengan persamaan berikut:

f(n) = h(n) (1.1)

dimana:

f(n) = fungsi heuristik

h(n) = fungsi evaluasi yang dipakai untuk mengestimasi seberapa baik setiap node dibangkitkan.

•       Memory-bounded A* (SMA)

      adalah salah satu algoritma searching yang menjanjikan solusi yang optimal jika memori yang tersedia setidaknya sebesar jumlah node pada jalur solusi optimal. Heuristic additive digunakan sebagai biaya perkiraan agar algoritma ini dapat diimplementasikan ke dalam planning. Ada dua strategi dalam Planning, yaitu Forward Planning dan Backward Planning. Pada Forward Planning, pencarian jalur solusi akan dilakukan dari initial state menuju goal state, sementara pada Backward Planning pencarian jalur solusi akan dilakukan terbalik dari goal state menuju initial state. Planning sebagai heuristic search adalah cara yang menggabungkan heuristic search dengan planning untuk menemukan jalur solusi.

Dalam tugas akhir ini algoritma SMA dengan menggunakan heuristic additive sebagai biaya estimasi digunakan untuk menyelesaikan permasalahan planning pada studi kasus dunia balok. Pembatasan memori pada algoritma ini aka disimulasikan dalam array of node. Sistem ini akan menampilkan output berupa aksi-aksi yang dilakukan oleh sistem untuk mencapai goal state, menampilkan jumlah aksi yang dilakukan, menghitung jumlah iterasi yang diperlukan, serta menampilkan waktu proses yang dibutuhkan sistem untuk menyelesaikan problem.

•       Heuristic Best First Search

       Fungsi heuristic h(n) merupakan estimasi cost dari n ke simpul tujuan. Sangat penting untuk memilih fungsi heuristic yang baik. Misalkan h*(n) merupakan cost sebenarnya dari simpul n ke simpul tujuan, maka pada algoritma A* terdapat beberapa kemungkinan yang terjadi pada pemilihan fungsi heuristic yang digunakan, yaitu (Amit Gaming) :

1.  Jika h(n) = 0, sehingga hanya g(n) yang terlibat maka A* akan bekerja seperti halnya algoritma Dijkstra.

2.  Jika h(n) < h*(n), maka A* akan mengembangkan titik dengan nilai paing rendah dan algoritma A* menjamin ditemukannya lintasan terpendek. Nilai h(n) terendah akan membuat algoritma mengembangkan lebih banyak simpul. Jika h(n) < h*(n), maka h(n) dikatakan heuristic yang admissible.

3.  Jika h(n) = h*(n), maka A* akan mengikuti lintasan terbaik dan tidak akan mengembangkan titik-titik yang lain sehingga akan berjalan cepat. Tetapi hal ini tidak akan terjadi pada semua kasus. Informasi yang baik akan mempercepat kinerja A*.

4.  Jika h(n) > h*(n), maka A* tidak menjamin pencarian rute terpendek, tetapi berjalan dengan cepat.

5.  Jika h(n) terlalu tinggi relative dengan g(n) sehingga hanya h(n) yang bekerja maka A* berubah jadi Greedy Best First Search.

Fungsi Heuristik

      Dalam metode pencarian heuristik, digunakan suatu metode yang digunakan untukmengevaluasi keadaan-keadaan masalah individual dan menentukan seberapa jauhhal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Fungsi heuristik berbeda untuk setiap tujuan, sehingga fungsi ini sering dijadikan sebagai parameter penting dalam menyelesaikan fungsi heuristik diimplementasikan untuk mencari jarak dari dua buah verteksyang biasanya menggunakan euclidean dan manhattan distance.

      Suatu fungsi heuristik dapat dikatan baik, apabila dapat memberikan biaya perkiraan yang mendekati biaya sebenarnya. semakin mendekati biaya sebenarnya, fungsi heuristik tersebut semakin baik. Dalam masalah pencarian rute terpendek dengan graph, fungsi heuristik yang dapat digunakan adalah Manhattan Distance.

Algoritma pencarian lokal dan masalah 

optimisasi

3.3.1 Metode Hill Climbing Search

Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik.

Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin(Sri Kusumadewi 2003, h. 34).

Ada dua macam metode Hill

Climbing Search, yaitu

1.   Simple Hill Climbing ,

2.   Steepest-ascent Hill Climbing (Sri Kusumadewi 2003, h. 39).

Algoritma untuk Hill Climbing Search adalah sebagai berikut :

1.    Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

2.    Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada node baru yang akan diaplikasikan pada keadaan sekarang :

a.    Cari node yang belum pernah digunakan; gunakan node ini untuk mendapatkan keadaan yang baru.

b.    Evaluasi keadaan baru tersebut.

- Jika keadaan baru merupakan tujuan, keluar.

- Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.

- Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan pencarian.

3.3.2 simulated annealing search

Merupakan ialah suatu algoritma optimasi yang mensimulasikan proses annealing pada pembuatan materi yang terdiri dari butir keristal/logam. Algoritma unt untuk optimalisasi yang bersifat generic. Berbasiskan probabilitas dan mekanika statistic,algoritma ini dapat dipakai untmencari pendekatan terhadap solusi optimum global dari suatu permasalahn. Masalah yang membutuhkan pendekatan simulated annealing ialah masalah-masalah optimisasi kombinatorial, dimana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahn itu.

Secara umum ada 3 hal pokok pada simulated annealing, yaitu:

1.      Nilai awal

Unt temperature (T0). Nilai T0 biasanya ditetapkan cukup besar (tidak mendekati 0), karena jika T mendekati 0 maka gerakan simulated annealing akan sama dengan hill climbing. Biasanya temperature awal ini ditetapkan sebesar 2 kali panjang suatu jalur yang dipilih secara acak

2.      Kriteria

Yang dipakai unt memutuskan apakah temperature sistem seharusnya dikurangi.

3.      Berapa besarnya pengurangan temperature dalam setiap waktu

3.3.3 local beam search

Local beam search adalah algoritma pencarian heuristik yangmerupakan optimasi dari pencarian best-first search yang mengurangikebutuhan memorinya. Dalam Beam Search, hanya jumlah solusiparsial terbaik yang telah ditetapkan yang disimpan sebagai kandidat.

Beam Search membutuhkan tiga komponen sebagai inputnya, yaitu :

 a.      Masalah yang akan di selesaikan

Biasanya di tampilkan dalam bentuk grafik dan berisi kumpulan node yang tiap satu atau lebih node mengarah ke goal/hasil.

 b.      Kumpulan aturan-aturan heuristik untuk pemangkasan

Adalah aturan-aturan spesifik yang mengarah ke ruang masalah dan memangkas node yang tidak menguntungkan dari memori yang berhubungan dengan ruang masalah.

 c.      Memori dengan kapasitas yang terbatas

         Adalah memori tempat menyimpan beam, dimana ketika memori dalam keadaan penuh dan node akan di tambahkan ke beam, maka node yang nilainya paling besar yang dihapus, jadi  tidak  akan melebihi memori yang tersedia.

      Beam Search memiliki keuntungan yang berpotensi mengurangi perhitungan dan waktu pencarian. Selain itu, pemakaian memori daripencarian ini jauh lebih sedikit daripada metode yang mendasari mtode pencarian ini.  Kelemahan utama Beam Search adalah metode pencarian ini mungkin  tidak dapat mencapai tujuan/hasil yang optimaldan bahkan mungkin tidak mencapai tujuan sama sekali. Padakenyataannya, algoritma beam search berakhir untuk dua kasus:  nodetujuan yang diperlukan tercapai, atau node tujuan tidak tercapai dantidak ada node tersisa untuk dieksplorasi.

3.3.4 Genetic Algorithm

Genetic Algorithm(atau GA) adalah teknik pencarian dalam bidang komputasi untuk menemukan solusi benar atau pendekatan untuk masalah optimasi dan pencarian. Teknik dalam GA didasarkan pada biologi evolusioner seperti pewarisan, mutasi, seleksi dan crossover.

Dalam GA biasanya ada 2 hal yang harus didefinisikan:

Representasi genetis dari domain solusi

Fungsi fitness untuk mengevaluasi solusi domain.

Hal-hal yang harus dilakukan untuk menggunakan algoritma genetika

1. Mendefinisikan individu, dimana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat
2. Mendefinisikan nilai fitness, yang merupakan ukuran baik tidaknya sebuah individu atau baik tidaknya solusi yang didapatkan
3. Menentukan proses pembangkitan solusi awal. Hal ini biasanya dilakukan dengan menggunakan pembangkitan acak seperti random walk.
4. Menentukan proses seleksi yang akan digunakan
5. Menentukan proses perkawinan silang (cross over) dan mutasi gen yang akan digunakan

Agen pencarian online dan lingkungan 

yang tidak diketahui.

Pencarian buta (uninformed/blind search) : tidak ada informasi awal yang digunakan dalam proses pencarian

Pencarian melebar pertama (Breadth – First Search) 

Pencarian mendalam pertama (Depth – First Search)

Referensi :

https://stackoverflow.com/questions/32909833/what-is-the-difference-between-local-beam-search-and-stochastic-beam-search

https://piptools.net/algoritma-sa-simulated-annealing/