Penalaran

10.1 Ketidakpastian
Ketidakpastian adalah parameter terkait dengan hasil pengukuran, yang mencirikan dispersi dari nilai-nilai yang cukup dapat dikaitkan dengan objek yang diukur. Ketidakpastian memiliki dasar probabilistik dan mencerminkan pengetahuan yang tidak lengkap dari besaran tersebut

10.2 TEOREMA BAYES

Dalam teori probabilitas dan statistika, Pengertian Teorema Bayes adalah teorema yang digunakan untuk menghitung peluang dalam suatu hipotesis, Teorema bayes dikenalkan oleh ilmuan yang bernama Bayes yang ingin memastikan keberadaan Tuhan dengan mencari fakta di dunia yang menunjukan keberadaan Tuhan. Bayes mencari fakta keberadaan tuhan didunia kemudian mengubahnya dengan nilai Probabilitas yang akan dibandingkan dengan nilai Probabilitas. teorema ini juga merupakan dasar dari statistika Bayes yang memiliki penerapan dalam ilmu ekonomi mikro, sains, teori permain, hukum dan kedokteran.

Teorema Bayes akhirnya dikembangkan dengan berbagai ilmu termasuk untuk penyelesaian masalah sistem pakar dengan menetukan nilai probabilitas dari hipotesa pakar dan nilai evidence yang didapatkan fakta yang didapat dari objek yang diagnosa. Teorama Bayes ini membutuhkan biaya komputasi yang mahal karena kebutuhan untuk menghitung nilai probabilitas untuk tiap nilai dari perkalian kartesius. penerapan Teorema Bayes untuk mencari penerapan dinamakan inferens Bayes

FAKTOR KEPASTIAN

Tujuan utama penggunaan factor kepastian adalah untuk mengolah ketidakpastian dari fakta dan gejala dengan menghindarkan keperluan data dan perhitungan yang besar. Factor kepastian diperoleh dari pengurangan nilai kepercayaan (measure of belief)  oleh nilai ketidak percayaan.
Faktor kepastian membuat beberapa asumsi yang memudahkan tingkat kepercayaan dan beberapa persamaan aturan yang mudah untuk mengkombinasikan tingkat kepercayaan sebagai program dalam mencapai kesimpulan akhir.

Factor kepastian (certainly Factor) diperkenlakan oleh Shortliffe Buchhaman dalam pembuatan MYCIN (Weskey, 1984). Certainly Factor (CF) merupakan nilai parameter klinis yang diberikan MYCIN untuk menunjukan besarnya kepercayaan. Certainly Faktor didefinisikan sebagai berikut (Giarattano dan Riley, 1994)

-      Sistem pakar harus mampu mengatasi ketidakpastian dan menggambarkan konklusi yang valid.
-      Ketidakpastian dalam sistem berbasis kaidah dapat berasal dari 3 hal berikut :
1.       Kaidah Tunggal (individual rule)
Kaidah tunggal dipengaruhi oleh 3 hal : kesalahan (error), probabilitas dan kombinasi premis.
Kesalahan (error) disebabkan antara lain oleh :
a.       Ambiguitas, yaitu sesuatu yang didefinisikan berlebihan
b.      Ketidaklengkapan data
c.       Kesalahan informasi
d.      Kesalahan pengukuran

Probabilitas disebabkan oleh ketidakmampuan seorang pakar untuk merumuskan kaidah secara pasti. Pemberian nilai probabilitas yang menyatakan derajat kepercayaan dapat juga menyebabkan ketidakpastian.
Kombinasi premis di dalam anteseden jika premis lebih dari sebuah perlu diperhatikan. Beberapa kombinasi yang dapat dibentuk :

                                       E1 AND E2 AND E3
                              atau  E1 AND E2 OR E3
                              atau  E1 AND NOT E2 OR E3

2.       Ketidaksesuaian Antarkaidah (incompatibility of rule)
Ketidaksesuaian antarkaidah dapat disebabkan oleh : kontradiksi kaidah, subsumsi kaidah, redudansi kaidah, kehilangan kaidah dan penggabungan data.

Kontradiksi kaidah
Kontradiksi merupakan ketidaksesuaian konsekuen diantara dua kaidah yang bisa jadi disebabkan oleh anteseden yang kuran spesifik.
Contoh :
Kaidah 1 : IF terdapat api THEN siramlah dengan air
Kaidah 2 : IF terdapat api THEN jangan siram dengan air

Interpretasi kaidah 1, jika bebar-benar terdapat api seperti terbakarnya kayu, maka akan dilakukan pemadaman dengan menyiramkan air. Sedangkan pada kaidah 2 memang terdapat api yang memang sengaja untuk melakukan pembakaran (mis. Memasak) yang tidak boleh disiram air.

Subsumsi kaidah
Subsumsi kaidah terjadi jika anteseden merupakan bagian dari kaidah yang lain.
Contoh :
            Kaidah 1 : IF E1 THEN H
            Kaidah 2 : IF E1 and E2 THEN H

Interpretasinya, jika E1 yang muncul, maka tidak terdapat masalah karena kaidah 1 yang akan dijalankan, tetapi jika E1 dan E2 kedua-duanya muncul pada kaidah 1 dan kaidah 2, maka kedua-duanya akan sama-sama dijalankan sehingga konflik resolusi dibutuhkan.

Redudansi kaidah
Redudansi aturan adalah kaidah-kaidah yang mempunyai konsekuen dan evidence yang sama.
Contoh :
Kaidah 1 : IF E1 and E2 THEN H
            Kaidah 2 : IF E2 and E1THEN H

Kehilangan kaidah
Kehilangan aturan merupakan penyebab ketidaksesuaian antarkaidah yang terjadi jika seorang ahli lupa atau tidak sadar akan membuat kaidah.
Contoh :
IF E4 THEN H
Jika E4 diabaikan maka H tidak akan pernah dapat disimpulkan dengan layak.

Penggabungan data (data fussion)
Penggabungan data merujuk kepada ketidakpastian yang dihubungkan dengan perpaduan data dari tipe informasi yang berbeda. Kesemua tipe yang berbeda tersebut harus digabungkan untuk menjadikan mereka sebagai suatu informasi yang mendukung dan menjadi pertimbangan saat pengambilan keputusan akhir.
Contoh :
Dokter membuat diagnosis penyakit tidak hanya dari hasil pemeriksaan fisik, tetapi juga hasil laboratorium, riwayat penyakit pasien dsb.

3.       Resolusi Konflik (conflict resolution)
Resolusi konflik merupakan proses menyeleksi atau memilih kaidah yang ada jika terdapat lebih dari satu kaidah yang diaktivasi dan resolusi konflik disebabkan oleh interaksi antarkaidah.
Beberapa metode untuk resolusi konflik :
a.       Memicu kaidah berdasarkan prioritas.
b.      Mempunyai kadiah yang mempunyai banyak premis yang harus dipenuhi. Metode ini dikenal denganthe longest matching strategy.
c.       Memilih kaidah yang paling banyak digunakan.
d.      Memilih kaidah yang palinga kahir ditambahkan pada sekumpulan kaidah.
e.       Memilih kaidah yang waktu eksekusinya paling singkat.
f.       Memilih semua kaidah dari sekumpulah kaidah yang ada.

10.3 FAKTOR KEPASTIAN (CERTAINTY FACTOR)
-      Faktor kepastian merupakan cara dari penggabungan kepercayaan (belief) dan ketidapercayaan (unbelief) dalam bilangan yang tunggal.
-      Dalam certainty theory, data-data kualitatif direpresentasikan sebagai derajat keyakinan (degree of belief).
-      Tahapan dalam merepresentasikan data-data kualitatif :
1.        kemampuan untuk mengekspresikan derajat keyakinan sesuai dengan metode yang sudah dibahas sebelumnya.
2.        kemampuan untuk menempatkan dan mengkombinasikan derajat keyakinan tersebut dalam sistem pakar.
-      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 kenaik-
an dari kepercayaan hipotesis H dipengaruhi oleh fakta E.
MD = Measure of Disbelief (tingkat ketidakyakinan), adalah kenaik-
an dari ketidakpercayaan hipotesis H dipengaruhi fakta E.
E = Evidence (peristiwa ataua fakta)
-      Penggabungan kepercayaan dan ketidakpercayaan dalam bilangan yang tunggal memiliki dua kegunaan, yaitu :
1.      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.
Ukuran kepercayaan dan ketidapercayaan didefinisikan dalam probabilitas sebagai berikut :
                                            1                                                          P(H) = 1
MB(H,E) =     max[P(H|E),P(H)]-P(H)                                     lainnya
                              max[1,0]-P(H)

                                            1                                                          P(H) = 0
MD(H,E) =     max[P(H|E),P(H)]-P(H)                                     lainnya
                              min [1,0]-P(H)

Karakteristik dari MB, MD dan CF
Karakteristik
Nilai
Jangkauan
0 £ MB £ 1
0 £ MD £ 1
-1 £ CF £ 1
Hipotesis pasti benar
P(H|E) = 1
MB = 1
MD = 0
CF = 1
Hipotesis pasti salah
P(H’|E) = 1
MB = 0
MD = 1
CF = -1
Kekurangan fakta
P(H|E) = P(H)
MB = 0
MD = 0
CF = 0

Faktor kepastian (CF) menunjukkan jaringan kepercayaan dalam suatu hipotesis ayng berdasarkan pada beberapa fakta.
CF Positif : mendukung hipotesis, karena MB > MD.
CF=1 : fakta secara definisi membuktikan suatu hipotesis
CF=0   :  s  CF=MB-MD = 0 , berarti tidak ada fakta
            s MD=MB, berarti kepercayaan dihapus atau ditiadakan oleh ketidakpercayaan
CF Negatif : fakta menandakan negasi dari hipotesis, karena MB < MD. Dengan kata lain menyatakan ketidakpercayaan terhadap hipotesis daripada mempercayainya.

2.      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 :
Mahasiswa lulus jika mendapatkan nilai A untuk suatu mata kuliah.
            CF(H,E) = 0,70                                   CF(H’,E) = -0,70
Seberapa kepercayaan Anda bahwa mendapatkan nilai A akan membantu Anda lulus ?
Jawab : saya pastikan 70% bahwa saya akan lulus jika saya memperoleh nilai A untuk mata kuliah ini.
Seberapa ketidakpercayaan Anda bahwa mendapatkan nilai A akan membantu Anda lulus ?
Jawab : saya pastikan  -70% bahwa saya tidak akan lulus jika saya memperoleh nilai A untuk mata kuliah ini


10.4 TEORI DEMPSTER-SHAFER

Teori Dempster-Shafer adalah teori matematika untuk pembuktian berdasarkan belief functions(fungsi kepercayaan) dan plausible reasonin (penalaran yang masuk akal). Digunakan untuk mengkombinasikan potongan informasi (fakta) yang terpisah untuk mengkalkulasi kemungkinan dari suatu peristiwa.Teori Dempster-Shafer adalah suatu teori matematika untuk pembuktian (Kusumadewi, 2003) berdasarkan belief functions and plausible reasoning (fungsi kepercayaan dan pemikiran yang masuk akal), yang digunakan untuk mengkombinasikan potongan informasi yang terpisah (bukti) untuk mengkalkulasi kemungkinan dari suatu peristiwa. Teori ini dikembangkan oleh Arthur P. Dempster dan Glenn Shafer.

Ada berbagai macam penalaran dengan model yang lengkap dan sangat konsisten, tetapi pada kenyataannya banyak permasalahan yang tidak dapat terselesaikan secara lengkap dan konsisten. Ketidakkonsistenan yang tersebut adalah akibat adanya penambahan fakta baru. Penalaran yang seperti itu disebut dengan penalaran non monotonis. Untuk mengatasi ketidakkonsistenan tersebut maka dapat menggunakan penalaran dengan teori Dempster-Shafer. Secara umum teori Dempster-Shafer ditulis dalam suatu interval:

[Belief,Plausibility]

Belief (Bel) adalah ukuran kekuatan evidence dalam mendukung suatu himpunan proposisi. Jika bernilai 0 maka mengindikasikan bahwa tidak ada evidence, dan jika bernilai 1 menunjukkan adanya kepastian. Dimana nilai bel yaitu (0-0.9).
Plausibility (Pl) dinotasikan sebagai : Pl(s) = 1 – Bel (-s) Plausibility juga bernilai 0 sampai 1. Jika yakin akan-s, maka dapat dikatakan bahwa Bel(-s)=1, dan Pl(-s)=0.

Contoh :
 Diketahui nilai belief  adalah 0,5 dan nilai plausibility adalah 0,8 untuk proposisi “the cat in the box is dead”
 Bel = 0,5
 Fakta yang mendukung proposisi tersebut memiliki nilai kepercayaan sebesar 0,5
  Pl = 0,8
  Fakta yang melawan proposisi tersebut hanya memiliki nilai kepercayaan sebesar 0,2

Pada teori Dempster-Shafer dikenal adanya frame of  discernment (θ) yaitu semesta pembicaraan dari sekumpulan hipotesis. Nilai probabilitas densitas (m) mendefinisikan elemen-elemen θ  serta semua subsetnya. Jika θ berisi n elemen, subset dari θ adalah 2n

sumber :
https://1.bp.blogspot.com/

Inferensi dalam Logika Order Pertama

9.1 Mengubah Inferensi Order Pertama Menjadi Proporsi (First Order Predicate Logic)
• Representasi 4 kategori silogisme menggunakan logika predikat
Kaidah Universal Instatiation merupakan state dasar, dimana suatu individual dapat digantikan (disubsitusi) ke dalam sifat universal. Contoh :
Misal, φ merupakan fungsi proposisi :
(∀  x) φ(x)
∴ φ(a)
merupakan bentuk yang valid, dimana a menunjukkan spesifik individual, sedangkan x adalah suatu variabe yang berada dalam jangkauan semua individu (universal). Contoh lain :
(∀  x) H(x)
∴ H(Socrates)
• Berikut ini adalah contoh pembuktian formal silogisme
All men are mortal
Socrates is a man
Therefore, Socrates is mortal
Misal : H = man, M = mortal, s = Socrates
1. (∀  x) (H (x) -> M(x))
2. H(s)                                     / ∴   M(s)
3. H(s) -> M(s)                        1 Universal Instatiation
4. M(s)                                     2,3 Modus Ponens

9.2 Unifikasi
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 dipersatukan 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).

9.3 Generalized Modus Ponens (GMP)
Dalam logika Boolean, dengan aturan `` JIKA X adalah A THEN Y adalah B '', proposisi X adalah A harus diamati untuk mempertimbangkan proposisi Yadalah B.
Dalam logika fuzzy, proposisi `` X adalah A' '', Dekat dengan premis `` X adalah A '' dapat diamati untuk memberikan kesimpulan `` Y adalah B' '' Dekat dengan kesimpulan `` Y adalah B '' .
Sebuah inferensi fuzzy sederhana dapat direpresentasikan sebagai:
Aturan
   
: JIKA
   
X adalah A THEN
   
Y adalah B
   
Fakta
   
:
   
X adalah A'
       
Kesimpulan
   
:
       
Y adalah B'
   
Untuk menyimpulkan seperti inferensi fuzzy kita menggunakan mekanisme yang disebut umum modus ponens.

Catatan: Asumsikan -> operator implikasi Brouwer-Gödel dan o operator kombinasi, rumus dapat dinyatakan dengan B' = A'o(A-->B) yang kita gunakan sekarang untuk menyederhanakan notasi.

9.4 Rangkaian Forward Chaining dan Backward Chaining
• Chain (rantai) : perkalian inferensi yang
menghubung-kan suatu permasalahan dengan
solusinya.
• Forward chaining :
– Suatu rantai yang dicari atau dilewati/dilintasi dari suatu permasalahn untuk memperoleh solusi.
– Penalaran dari fakta menuju konklusi yang terdapat
dari fakta.
• Backward chaining :
– Suatu rantai yang dilintasi dari suatu hipotesa tersebut.
– Tujuan yang dapat dipenuhi dengan pemenuhan sub tujuannya.
• Contoh rantai inferensi :
gajah(x) -> mamalia (x)
mamalia(x) -> binatang(x)

Karakteristik Forward dan Backward chaining






Sumber :
afifrahma.blogspot.com/2013/01/resolusi-untuk-logika-predikat.html
sumarna.staff.gunadarma.ac.id/Downloads/files/29148/6+Metode+Inferensi.doc

ROBOT PABRIK PENJAMIN MUTU

AI merupakan kecerdasan yang diciptakan dan dimasukkan ke dalam suatu mesin (komputer) agar dapat melakukan pekerjaan seperti yang dapat dilakukan manusia. Beberapa macam bidang yang menggunakan kecerdasan buatan antara lain sistem pakar, permainan komputer (Games), Logika Fuzzy, jaringan syaraf tiruan dan robotika.

Kali ini kita akan membahas robot pabrik penjamin mutu
Robot dalam bidang industri pada umumnya ditujukan untuk menggantikan peran manusia dalam melaksanakan tugas-tugas yang membutuhkan tenaga yang lebih besar, yang memerlukan ketelitian yang tinggi dan yang  mengandung resiko tinggi terhadap keselamatan manusia sehingga robot dapat meminimalisir Human Error (Kesalahan Manusia) pada proses pengindustrian serta dapat meningkatkan produktivitas produksi secara efisien dan efektif.
Berikut ini adalah lingkungan masalah yang harus didefinisikan dalam membangun


Performance measure : apa saja komponen pengukur keberhasilan si agent?
Environment : kondisi apa saja yang ada disekitar si agent?
Actuators : apa saja yang bisa dilakukan si agent?
Sensors : apa saja yang menjadi input si agent?

Robot pabrik penjamin mutu merupakan sebuah robot yang melakukan pemisahan komponen yang bermutu tinggi pada ban berjalan ke dalam kotak berbeda

Lingkungan masalah

Performance measure: prosentase jumlah komponen yg diletakkan pada kotak yang benar
Environment: ban berjalan, komponen yang diuji, kotak
Actuators: gerak lengan dan tangan robot
Sensors: kamera, sensor fisik


Dengan meggunakan sistem komputer robot ini secara otomatis memilih barang produksi dengan kualitas atau mutu terbaik.

Cara kerja robot :

Robot menunggu barang yang lewat melalui ban berjalan. Kemudian robot menggunkan kamera dan sensor untuk melihat dan membaca data barang yang lewat, lalu robot mengambil dan memindahkan barang yang berkualitas buruk dari ban berjalan ke tempat yang sudah di tentukan.

Keuntungan :
Kualitas atau mutu barang yang diproduksi lebih terjamin, karena menggunakan sistem cerdas
Waktu yang dibutuhkan untuk melakukan pekerjaan lebih cepat

Kerugian :
Biaya pembuatan dan perawatan cukup mahal
Peran manusia mulai tergantikan, akibatnya pengangguran bertambah

Kesimpulan dan Saran :
Robot sangat membantu manusia dalam melakukan pekerjaan industri dan manufaktur. sebaiknya tidak semua peran manusia di gantikan oleh robot. 

REPRESENTASI PENGETAHUAN : LOGIKA PREDIKAT

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).
Syarat-syarat symbol dalam logika predikat :

• himpunan huruf, baik huruf kecil maupun huruf besar dalam abjad.
• Himpunan digit (angka) 0,1,2,…9
• Garis bawah “_”
• Symbol-simbol dalam logika predikat dimulai dengan sebuah huruf dan diikuti oleh sembarang rangkaian karakter-karakter yang diijinkan.
• Symbol-simbol logika predikat dapat merepresentasikan variable, konstanta, fungsi atau predikat

Konstanta: objek atau sifat dari semesta pembicaraan. Penulisannya diawali dengan huruf kecil, seperti : pohon, tinggi. Konstanta true(benar) dan false(salah) adalah symbol kebenaran (truth symbol).
Variable : digunakan untuk merancang kelas objek atau sifat-sifat secara umum dalam semesta pembicaraan. Penulisannya diawali dengan huruf besar, seperti : Bill, Kate.
Fungsi : pemetaan (mapping) dari satu atau lebih elemen dalam suatu himpunan yang disebut domainfungsi ke dalam sebuah elemen unik pada himpunan lain yang disebut rangefungsi. Penulisannya dimulai dengan huruf kecil. Suatu ekspresi fungsi merupakan symbol fungsi yang diikuti argument.
Argumentadalah elemen-elemen dari fungsi, ditulis diapit tanda kurung dan dipisahkan dengan tanda koma.
Predikat: menamai hubungan antara nol atau lebih objek dalam semesta pembicaraan. Penulisannya dimulai dengan huruf kecil, seperti : equals, sama dengan, likes, near.
Contoh kalimat dasar :
teman(george,allen)
teman(ayah_dari(david),ayah_dari(andrew))
dimana :
argument : ayah_dari(david) adalah george
argument : ayah_dari(andrew) adalah allen
predikat : teman

Quantifier Universal
Operator logika konektif : ∧,∨, ~, →, ≡.
Logika kalkulus orde pertama mencakup symbol universal quantifier ∀dan existensial quantifier ∃.
Menunjukkan semua kalimat adalah benar untuk semua nilai variabelnya.
Direpresentasikan dengan symbol ∀diikuti satu atau lebih argument untuk suatu domain variable.
Symbol∀diinterpretasikan “untuk setiap”atau “untuk semua”.
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 kucing → x adalah binatang)
Kebalikan kalimat “bukan kucing adalah binantang” ditulis :
(∀x) (p) (Jika x adalah seekor kucing → ~x adalah binatang)
dan dibaca : -“setiap kucing adalah bukan binantang”
-“semua kucing adalah bukan binantang”

Quantifier Existensial
Menunjukkan semua kalimat adalah benar untuk suatu nilai tertentu dalam sebuah domain.
Direpresentasikan dengan symbol ∃diikuti satu atau lebih argument.
Symbol ∃diinterpretasikan “terdapat”atau “ada”, “paling sedikit satu”,“terdapat satu”, “beberapa”.
Contoh 1 :
(∃x) (x . x = 1)
Dibaca : “terdapat x yang bila dikalikan dengan dirinya sendiri hasilnya sama dengan 1.”
Contoh 2 :
(∃x) (gajah(x) ∧nama(Clyde))
Dibaca : “beberapa gajah bernama Clyde”. 
Existensial quantifier dapat diekspresikan sebagai disjungsi dari urutan ai. P(a1) ∨P(a2) ∨P(a3) …∨P(aN)


Resolusi Logika Predikat

Resolusi pada logika predikat pada dasarnya sama dengan resolusi pada logika proposisi, hanya saja ditambah dengan unufikasi. 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 ke himpunan klausa yang telah ada pada langkah 1.
3. Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan:
a. Seleksi 2 klausa sebagai klausa parent.
b. Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut dinamakan resolvent. Jika ada pasangan literal T1 dan T2 sedemikian hingga keduanya dapat dilakukan unifikasi, maka salah satu T1 atau T2 tidak muncul lagi dalam resolvent. T1 dan T2 disebut sebagai complementary literal. Jika ada lebih dari 1 complementary literal, maka hanya sepasang yang dapat meninggalkan resolvent.
c. Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada.

Contoh :
Misalkan terdapat pernyataan-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.
Kedelapan pernyataan di atas dapat dibawa ke bentuk logika predikat, dengan menggunakan operator-operator logika predikat, sebagai berikut :
9. mahasiswa(Andi).
10. Elektro(Andi).
11. ∀x:Elektro(x)→Teknik(x).
12. sulit(Kalkulus).
13. ∀x:Teknik(x) → suka(x,Kalkulus) ∨ benci(x,Kalkulus).
14. ∀x:∃y:suka(x,y).
15. ∀x:∀y:mahasiswa(x)∧sulit(y) ∧ ￢hadir(x,y)→ ￢suka(x,y).
16. ￢hadir(Andi,Kalkulus).

Kita dapat membawa pernyataan-pernyataan yang ada menjadi bentuk klausa (CNF) sebagai berikut:
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,fl(x3)).
7. ￢mahasiswa(x4) ∨ ￢sulit(y1) ∨ hadir(x4,y1) ∨ ￢suka(x4,y1).
8. ￢hadir(Andi,Kalkulus).
Apabila ingin dibuktikan apakah Andi benci kalkulus, maka kita bisa lakukan dengan membuktikan: (dibuktikan dalam gambar paling atas)


sumber :
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0ahUKEwiXmuvjqq3QAhXKvY8KHeS_DkIQFgggMAE&url=http%3A%2F%2Fsupriyan.staff.gunadarma.ac.id%2FDownloads%2Ffiles%2F11876%2F5-Representasi-Pengetahuan-LOGIKA.pdf&usg=AFQjCNGz5Owl96L1dlKqejEc6y8TDVqwow&sig2=gRnlDxO13L9iVOCNTbmG3g&cad=rja
http://slametgo-blog.blogspot.co.id/2016/01/resolusi-logika-predikat.html

REPRESENTASI PENGETAHUAN : LOGIKA PROPOSISI

Logika dan Set

• Representasi pengetahuan dengan symbol logika merupakan bagian dari penalaran eksak.
• Bagian yang paling penting dalam penalaran adalah mengambil kesimpulan dari premis.
• Logika dikembangkan oleh filusuf Yunani, Aristoteles (abad ke 4 SM) didasarkan pada silogisme, dengan dua premisdan satu konklusi.
• Contoh :

1. Premis : Semua laki-laki adalah makhluk hidup
2. Premis : Socrates adalah laki-laki
3. Konklusi : Socrates adalah makhluk hidup

• Cara lain merepresentasikan pengetahuan adalah dengan Diagram Venn. 

• Diagram Venn merepresentasikan sebuah himpunan yang merupakan kumpulan objek.
• Objek dalam himpunan disebut elemen.

1. A ={1,3,5,7}
2. B = {….,-4,-2,0,2,4,…..}
3. C = {pesawat, balon}

• Symbol epsilon εmenunjukkan bahwa suatu elemen merupakan anggota dari suatu himpunan, contoh : 1 εA . Jika suatu elemen bukan anggota dari suatu himpunan maka symbol yang digunakan ∉, contoh : 2 ∉A.
• Jika suatu himpunan sembarang, misal X dan Y didefinisikan bahwa setiap elemen X merupakan elemen Y, maka X adalah subset dari Y, dituliskan : X ⊂ Y atau Y ⊃ X.

Operasi-operasi Dasar dalam Diagram Venn:

• Interseksi (Irisan)

C = A ∩B
C = {x ∈ U | (x ∈ A) ∧(x ∈ B)}
Dimana : ∩ menyatakan irisan himpunan| dibaca “sedemikian hingga”∧operator logika AND

• Union (Gabungan) 

C = A ∪ B
C = {x ∈ U | (x ∈ A) ∨(x ∈ B)}
Dimana : ∪ menyatakan gabungan himpunan∨operator logika OR

• Komplemen

A’ = {x ∈ U | ~ (x ∈ A) }
Dimana : ’ menyatakan komplemen himpunan
~ operator logika NOT


Operator Logika
Operator logika yang digunakan :

Kondisional merupakan operator yang analog dengan production rule.
Contoh 1 :
“ Jika hujan turun sekarang maka saya tidak pergi ke pasar”
Kalimat di atas dapat ditulis : p → q
Dimana : p = hujan turun
q = saya tidak pergi ke pasar

Contoh 2 :
p = “Anda berusia 21 atau sudah tua”
q = “Anda mempunyai hak pilih”

Kondisional p → q dapat ditulis/berarti :

Tautologi, Kontradiksi dan Contingent

• Tautologi : pernyataan gabungan yang selalu bernilai benar.
• Kontradiksi : pernyataan gabungan yang selalu bernilai salah.
• Contingent : pernyataan yang bukan tautology ataupun kontradiksi.

Tabel Kebenaran untuk logika konektif :

 Tabel kebenaran untuk negasi konektif :

Resolusi Logika Proposisi
Resolusi merupakan suatu teknik pembuktian yang lebih efisien, sebab fakta-fakta yang akan dioperasikan terlebih dahulu dibawa ke bentuk standar yang sering disebut dengan nama klausa. Pembuktian suatu pernyataan menggunakan resolusi ini dilakukan dengan cara menegasikan pernyataan tersebut, kemudian dicari kontradiksinya dari pernyataan-pernyataan yang sudah ada.
Resolusi adalah suatu aturan untuk melakukan inferensi yang dapat berjalan secara efisien dalam suatu bentuk khusus conjunctive normal form (CNF). Pada logika proposisi, prosedur untuk membuktikan proposisi P dengan beberapa aksioma F yang telah diketahui, dengan menggunakan resolusi.
Algoritma resolusi :
(1) Konversikan semua proposisi F ke bentuk CNF.
(2) Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa. Tambahkan ke himpunan klausa yang telah ada pada langkah 1.
(3) Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan :
a. Seleksi 2 klausa sebagai klausa parent.
b. Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut dinamakan resolvent. Jika ada pasangan literal L dan ￢L, eliminir dari resolvent.
c. Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada.
Contoh :
Diketahui basis pengetahuan (fakta-fakta yang bernilai benar) sebagai berikut:
1. P
2. (P ∧ Q) → R
3. (S ∨ T) → Q
4. T
Buktikanlah kebenaran R!
Pertama-tama kita harus ubah dulu keempat fakta di atas menjadi bentuk CNF. Konversi ke CNF dapat dilakukan sebagai berikut:

Kemudian kita tambahkan kontradiksi pada tujuannya, R menjadi ￢R sehingga fakta-fakta (dalam bentuk CNF) dapat disusun menjadi:
1. P
2. ￢P ∨ ￢Q ∨ R
3. ￢S ∨ Q
4. ￢T ∨ Q
5. T
6. ￢R
Dengan demikian resolusi dapat dilakukan untuk membuktikan R sebagaimana terlihat pada Gambar berikut:

Contoh apabila diterapkan dalam kalimat:
P : Andi anak yang cerdas.
Q : Andi rajin belajar.
R : Andi akan menjadi juara kelas.
S : Andi makannya banyak.
T : Andi istirahatnya cukup.
Kalimat yang terbentuk (basis pengetahuan) menjadi :
1. P : Andi anak yang cerdas.
2. (P ∧ Q) → R : Jika Andi anak yang cerdas dan Andi rajin belajar, maka Andi akan menjadi juara kelas.
3. (S ∨ T) → Q : Jika Andi makannya banyak atau Andi istirahatnya cukup, maka Andi rajin belajar.
4. T : Andi istirahatnya cukup.
Setelah dilakukan konversi ke bentuk CNF, didapat:
1. P : Andi anak yang cerdas.
2. ￢P ∨ ￢Q ∨ R : Andi tidak cerdas atau Andi tidak rajin belajar atau Andi akan menjadi juara kelas.
3. ￢S ∨ Q : Andi tidak makan banyak atau Andi rajin belajar.
4. ￢T ∨ Q : Andi tidak cukup istirahat atau Andi rajin belajar.
5. T : Andi istirahatnya cukup.
6. ￢R : Andi tidak akan menjadi juara kelas.
Pohon aplikasi resolusi untuk kejadian di atas sebagai berikut :

sumber :
 https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0ahUKEwiXmuvjqq3QAhXKvY8KHeS_DkIQFgggMAE&url=http%3A%2F%2Fsupriyan.staff.gunadarma.ac.id%2FDownloads%2Ffiles%2F11876%2F5-Representasi-Pengetahuan-LOGIKA.pdf&usg=AFQjCNGz5Owl96L1dlKqejEc6y8TDVqwow&sig2=gRnlDxO13L9iVOCNTbmG3g&cad=rja
slametgo-blog.blogspot.com/2016/01/resolusi-logika-proposisi.html

REPRESENTASI PENGETAHUAN

Pengetahuan (Knowledge) :
Definisi umum : fakta atau kondisi sesuatu atau keadaan yang timbul karena suatu pengalaman.
Cabang ilmu filsafat, yaitu Epistemology, berkenaan dengan sifat, struktur dan keaslian dari knowledge.

Produksi
Kaidah nmenyediakan cara formal untuk mempresentasikan rekomendasi, arahan, atau strategi. Kaidah produksi dituliskandalam bentuk jika-maka (if-then). Kaidah if-then menghubungkan anteseden (antecedent) dengan konskuensi yang diakibatkannya. Berbagai struktur kaidah if-then yang menghubungkan obyek atau atribut adalah sebagai berikut:

• JIKA premis MAKA konklusi
• JIKA masukan MAKA keluaran
• JIKA kondisi MAKA konsekuen
• JIKA data MAKA hasil
• JIKA tindakan MAKA tujuan

Premis mengacu pada fakta yang harus benar sebelum konklusi tertentu dapat diperoleh. Masukan mengacu pada data yang harus tersedia sebelum keluaran dapat diperoleh. Kondisi mengacu pada keadaan yang harus berlaku sebelum tindakan dapat diambil. Anteseden mengacu pada situasi yang terjadi sebelum konsekuensi dapat diamati. Data mengacu pada kegiatan yang harus dilakukan sebelum hasil dapat diharapkan. Tindakan mengacu pada kegiatan yang harus dilakukan sebelum hasil dapat diharapkan (Hanifah, 1998).
Kaidah dapat diklasifikasikan menjadi dua, yaitu kaidah derajat pertama (first order rule) dan kaidah meta (meta rule) (Giarrantano dan Riley, 1994). Kaidah derajat pertama adalah kaidah sederhana yang terdiri dari anteseden dan konsekuen. Misalnya :

• JIKA bersin-bersin dan pusing
• MAKA terserang penyakit flu

Kaidah meta adalah kaidah yang anteseden atau konsekuenya mengandung informasi tentang kaidah yang lain. Misalnya :

• JIKA mengalami kehilangan kesadaran yang berlangsung singkat, sehinnga aktivitas yang sedang berjalan terhenti
• DAN terkadang disertau dengan mata yangmenatap kosong dan gerakan mioklonik dari sekelompok otot mata atau wajah, otomatisme, kehilangan tanus otot (sehingga barang yang dipegang bisa terjatuh atau bila sedang berdiri bisa jatuh).
• DAN serangan berakhirdengan diikuti oleh pulihnya kesadaran
• DAN berlangsung beberapa detik sampai setengah menit, dan dapat berlangsung puluhan kali dalam sehari
• MAKA mengalami tipe sawan lena.

Aturan 2 :

• JIKA tipe sawan umum
• ATAU tipe sawan mioklonik
• ATAU tipe sawan lena
• ATAU tipe sawan tonik-klonik
• DAN EEG tidak menunjukan adanya kelainan fokal
• DAN penyebab tidak diketahui
• DAN awitan berhubungan dengan usia
• MAKA terkenan epilepsi idiopatik

Jaringan Semantik
Dibangun oleh M.R.Quillian, sebagai model memori manusia.

Representasi grafis dari informasi Propositional.

Proposisi adalah pernyataan yang dapat bernilai benar atau salah.

Disajikan dalam bentuk graf berarah

Node merepresentasikan konsep, objek atau situasi :

•  Label ditunjukkan melalui penamaan
• Node dapat berupa objek tunggal atau kelas

Links merepresentasikan suatu hubungan :

•  Links adalah struktur dasar untuk pengorganisasian pengetahuan

Contoh jaringan semantic.

 Tipe link :

• IS-A (ISA) berarti “contoh dari” dan merupakan anggota tertentu dari kelas.
• A KIND OF (AKO) berarti “jenis dari” dan merelasikan antara suatu kelas dengan kelas lainnya. AKO merelasikan kelas individu ke kelas induk dari kelas-kelas dimana individu tersebut merupakan kelas anak.
• HAS-A berarti “mempunyai” yang merelasikan suatu kelas menjadi subkelas. HAS-A berlawanan dengan AKO dan sering digunakan untuk merelasikan suatu objek ke bagian dari objek.

Keterangan : AKO = jenis dari
ISA = adalah
Has shape = berbentuk

Perluasan Jaringan Semantik

Penambahan dapat dilakukan dalam 3 cara :

1. Objek yang sama
2. Objek yang lebih khusus
3. Objek yang lebih umum

Operasi pada Jaringan Semantik
Kasus-1:
Bertanya pada “Bird” : “How do you Travel ?”
Jawab : “Fly”
Untuk menjawab, node tersebut akan mengecek pada arc dengan label travel dan kemudian menggunakann informasi (value) yang ada pada arc tersebut sebagai jawabannya.

Kasus-2:
Bertanya pada “Tweety” : “How do you Travel ?”
Jawab : “Fly”
Jika node tidak menemukan jawaban pada local arc, maka akan mencari pada link dengan hubungan “IS A” yang dimiliki node tersebut.

Penanganan Pengecualian (Exception Handling)
Kasus-3:
Bertanya pada “Penguin” : “How do you Travel ?”
Jawab normal : “Fly”
Hal ini tidak sesuai dengan fakta sebenarnya bahwa “Penguin” travel dengan cara “WALK”.
Maka untuk mengatasi kasus tersebut bisa ditambahkan arc khusus pada node “Penguin” untuk meng-over-ride informasi yang telah diwariskan.

Pada proses over-ride, kita menambahkan arc atau sifat yang sama dengan objek induk pada node, tetapi dengan value atau karakteristik yang berbeda.

Ada 3 hal yaitu OBJECT, ATTRIBUTE, VALUE
(OAV) Triplet, yang sering digunakan untuk membangun jaringan semantic.
OBJECT : dapat berupa fisik atau konsepsi
ATTRIBUTE : karakteristik objek
VALUE : ukuran spesifik dari atribut dalam situasi tertentu

contoh :

Triplet OAV secara khusus digunakan untuk mrepresentasikan fakta dan pola guna menyesuaikan fakta dalam aturan yang antecedent. Jaringan semantic untuk beberapa sistem terdiri dari node untuk objek, atribut dan nilai yang dihubungakan dengan IS A dan HAS A.


Schemata : Frame dan Script

• Frame (Minsky, 1975) dipandang sebagai struktur data static yang digunakan untuk merepsentasi-kan situasi-situasi yang telah dipahami dan stereotype.
• Frame digunakan untuk merepresentasikan pengetahuan stereotype atau pengetahuan yang didasarkan kepada karakteristik yang sudah dikenal yang merupakan pengalaman masa lalu.
• Frame berupa kumpulan slot-slot (representasi entitas sebagai struktru objek) yang merupakan atribut untuk mendeskripsikan pengetahuan berupa kejadian, lokasi, situasi ataupun elemen-elemen lain. Frame digunakan untuk representasi pengetahuan deklaratif.

contoh :
Frame Pohon
Spesialisasi dari : Tumbuhan
Jumlah batang : integer (default 1)
Jenis kulit : halus
Model daun : jenis pohon jarum, berganti daun
Bentuk daun : sederhana, berlekuk, campuran

Frame Pohon Perdu
Spesialisasi dari : Pohon
Jumlah batang : 3
Jenis kulit : halus
Model daun : berganti daun
Bentuk daun : sederhana, berlekuk

Setiap frame individual dapat dipandang sebagai struktur data yang mirip record, berisi informasi yang relevan dengan entitas-entitas stereotype.
Slot-slot dalam frame dapat berisi :
· Informasi identifikasi frame
· Hubungan frame dengan frame lain
· Penggambaran persyaratan yang dibutuhkan frame
· Informasi procedural untuk menggunakan struktur yang digambarkan
· Informasi default frame
· Informasi terbaru.

Script (Schank & Abelson, Yale univ) merupakan representasi terstruktur yang menggambarkan urutan stereotip dari kejadian-kejadian dalam sebuah konteks khusus.

- Script mirip dengan frame, perbedaannya : Frame menggambarkan objek, sedangkan Script menggambarkan urutan peristiwa.
- Dalam menggambarkan urutan peristiwa, script menggunakan serangkaian slot yang berisi informasi tentang orang, objek dan tindakantindakan yang terjadi dalam suatu peristiwa.
- Elemen script yang tipikal :
¨ Kondisi masukan : menggambarkan situasi yang harus dipenuhi sebelum terjadi suatu peristiwa yang ada dalam script.
¨ Prop : mengacu kepada objek yang digunakan dalam urutan peristiwa yang terjadi.
¨ Role : mengacu kepada orang-orang yang terlibat dalam script.
¨ Hasil : kondisi yang ada sesudah peristiwa dalam script berlangsung.
¨ Track : mengacu kepada variasi yang mungkin terjadi dalam script tertentu.
¨ Scene : menggambarkan urutan peristiwa aktural yang terjadi.
- Contoh : Script pergi ke restoran
SCRIPT Restoran
Jalur (track) : fast food restoran
Peran (roles) : tamu, pelayan
Pendukung (prop): conter, baki, makanan, uang, serbet, garam, merica, kecap, sedotan, dll
Kondisi masukan : tamu lapar –tamu punya uang
Adegan (scene) 1 : Masuk
. Tamu parkir mobil
. Tamu masuk restoran
. Tamu antri
. Tamu baca menu di list menu dan mengambil keputusan tentang apa yang akan diminta.
Adegan (scene) 2 : Pesanan
. Tamu memberikan pesanan pada pelayan
. Pelayan mengambil pesanan dan meletakkan
makanan di atas baki
. Tamu membayar
Adegan (scene) 3 : Makan
. Tamu mengambil serbet, sedotan, garam, dll
. Tamu makan dengan cepat
Adegan (scene) 4 : Pulang
. Tamu membersihkan meja
. Tamu membuang sampah
. Tamu meninggalkan restoran
. Tamu naik mobil dan pulang Hasil
. Tamu merasa kenyang
. Tamu senang
. Tamu kecewa
. Tamu sakit perut
- Keistimewaan Script :

1. Script menyediakan beberapa cara yang sangat alami untuk merepresentasikan “suatu inforamsi” yang lazim” dengan masalah yang bersumber dari sistem AI dari mula.
2. Script menyediakan struktur hirarki untuk merepresentasikan inforamsi melalui inklusi subscript dengan sript.

sumber :
https://aij1004.wordpress.com/2010/06/27/representasi-pengetahuan/
www.academia.edu/8665924/Representasi_Pengetahuan_M._Rizki_Maulidan
ibbi.ac.id/ibbiacid/bahan/sistem-pakar.pdf 

METODE PENCARIAN DAN PELACAKAN 2 (HEURISTIK)

Pencarian Heuristik(Heuristic Search)
Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness).
Fungsi heuristik digunakan untuk mengevaluasi keadaan - keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

Best-First Search (Pencarian Terbaik Pertama)
Metode ini merupakan kombinasi dari metode depth-first search dan breadth-first search. Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk.

Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan:
                                  f’(n) = g(n) + h’(n)
dimana:

   f’= Fungsi evaluasi
   g = cost dari initial state ke current state
   h’ = prakiraan cost dari current state ke goal state

Misalkan kita memiliki ruang pencarian seperti pada gambar berikut. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengan node A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di node A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara node n dengan node tujuan(jalan buntu). Kita bisa merunut nilai untuk setiap node.

 

Tabel Status Tiap Node

 

Problem Reduction (Reduksi Masalah) 

Kebanyakan solusi menggunakan pohon OR, dimana lintasan dari awal sampai tujuan tidak terletak pada satu cabang.

Bila lintasan dari keadaan awal sampai tujuan dapat terletak pada satu cabang, maka kita akan dapat menemukan tujuan lebih cepat.

• Graf AND - OR
• Graf AO*

Graf AND - OR
Pada dasarnya samadengan algoritma Best First Search, dengan mempertimbangkan adanya arc AND.
Gambar berikut menunjukkan bahwa untuk mendapatkan TV orang bisa dengan cara singkat yaitu mencuri atau membeli asal mempunyai uang.
Untuk mendeskripsikan algoritma, digunakan nilai F_UTILITY untuk biaya solusi.

Algoritma AND - OR

1. Inisialisasi graf ke node awal.
2. Kerjakan langkah 2 berikut hingganode awal SOLVED atau sampaibiayanya lebih tinggi dari F_UTILITY :

a). Telusuri graf mulai dari node awal dani kuti jalur terbaik. Akumulasikan kumpulan node yang ada pada lintasan tsb. dan belum pernah diekspansi atau diberi label SOLVED.
b). Ambil satu node dan ekspansi node tsb. Jika tidak ada successor maka set F_UTILITY sebagai nilai dari node tsb. Bila tidak demikian, tambahkan successor dari node tsb ke graf dan hitung nilai setiap f’ (hanya gunakan h’ dan abaikan g). Jika f’ = 0 tandai node tsb dengan SOLVED.
c). Ubah f’ harapan dari node baru yang diekspansi. Kirimkan perubahan ini secara backward sepanjanggraf. Jika node berisi suatu arc successor yang semua descendant nya berlabel SOLVED maka tandai node itu dengan SOLVED.

Operasi Reduksi Masalah dengan Graf AND - OR

• Langkah-1 semula hanya ada satu node, A. Node A diekspansi menjadi node B, C dan D. Node D memiliki biaya yang lebih rendah(6) jika dibandingkan dengan B dan C (9).
• Langkah-2 mengekspansi node D menjadi E dan F dengan biaya estimasi sebesar 10. f’ dari D menjadi 10.
• Ternyata level sebelumnya, node B dan C memiliki biaya yang lebih rendah dari D (9 < 10).
• Pada langkah-3 telusuri arc dari A ke B dan C bersama 2. Jika B dieksplore dahulu maka akan menurunkan G dan H. Nilai f’ baru dari B adalah 6 (G = 6 lebih baik dari H = 8) sehingga biaya AND arc B - C menjadi 12 (6 + 4 + 2).
• Dengan demikian nilai node D kembali menjadi lebih baik (10 < 12). Sehingga ekspansi dilakukan kembali terhadap D. dst.

Algoritma AO*
Menggunakan struktur graf. Tiap node pada graf memiliki nilai h’ yang merupakan biaya estimasi jalur dari node itu sendiri sampai suatu solusi.
Algoritma
1. Diketahui graf yang berisi node awal (sebut saja INIT). Hitung h’ (INIT)
2. Kerjakan langkah berikut hingga INIT bertanda SOLVED atau sampai nilai h’ (INIT) > FUTILITY :
    a.) Ekspan INIT dan ambil salah satu node yang belum pernah diekspan (sebutNODE)
    b.) Bangkitkan successor 2 NODE. Jika tidak memiliki successor maka set FUTILITY dengan nilai h’ (NODE). Jika ada successor maka untuk setiap successor (sebut SUCC) yang bukan ancestor dari NODE kerjakan:
         i. Tambahkan SUCC ke graf
         ii. Jika SUCC adalah terminal node tandai dengan SOLVED dan set nilai h’ = 0
         iii.Jika SUCC bukan terminal node, hitung nilai h’.

    c.) Kirimkan informasi baru tsb ke graf dengan cara : tetapkan S adalah node yang ditandai dengan SOLVED atau node yang nilai h’-nya baru saja diperbaiki, dan sampaikan nilai ini ke parent-nya. Inisialisasi S = NODE. Kerjakan langkah berikut ini hingga S kosong:
         i. Jika mungkin, seleksi dari S node yang tidak memiliki descendant dalam gra fyang terjadi pada S. Jika tidak ada, seleksi sembarang node dari S (sebut CURRENT) dan hapus dari S.
         ii. Hitung biaya tiap tiap arc yang muncul dari CURRENT. Biaya ini samadengan jumlah h’ untuk tiap tiap node pada akhir arc ditambah dengan biaya arc itu sendiri. Set h’ (CURRENT) dengan biaya minimum yang baru saja dihitung dari setiap arc yang muncul tadi.
         iii. Tandaijalurterbaikyang keluardariCURRENT denganmenandaiarc yang memilikibiayaminimum.
         iv. Tandai CURRENT dengan SOLVED jika semua node yang dihubungkan dengannya hingga arc yang baru saja ditandai tadi telah ditandai dengan SOLVED.
         v. Jika CURRENT telah ditandai dengan SOLVED atau jika biaya CURRENT telah berubah maka status baru ini harus disampaikan ke graf. Kemudian tambahkan semua ancestor dari CURRENT ke S.

• JalurmelaluiC selalulebihbaikdariB. Tetapijikabiayanode E munculdanpengaruhperubahanyang diberikan ke node B tidak sebesar pengaruhnya terhadap node C maka jalur melalui B bisa lebih baik.
• Hasil ekspan E, misalkan 10, maka biaya node C menjadi 11 (10 + 1), dengan demikian biaya node A apabila melewati C adalah 12 (11 + 1). Tentu saja akan lebih baik memilih melalui node B (11).
• Tapi tidak demikian halnya jika kemudian node D diekspan. Bisa jadi jalur dengan melalui node B akan lebih buruk lagi ketimbang jalur yang melalui node C.

Constraint Satisfaction
Problem search standard :- state adalah "black box“ – setiap struktur data yang mendukung fungsi successor, fungsi heuristik dan tes goal.
CSP:
- state didefinisikan sebagai variabel Xi dengan nilai dari domain Di
- Tes goal adalah sekumpulan constraint yang menspesifikasikan kombinasi dari nilai subset variabel.
Contoh sederhana adalah bahasa representasi formal.
CSP ini merupakan algoritma general-purpose dengan kekuatan lebih daripada algoritma pencarian standar.

Contoh : Pewarnaan Peta

• Variabel WA, NT, Q, NSW, V, SA, T
• Domain Di = {red,green,blue}
• Constraints : daerah yang bertetangga dekat harus memiliki warna yang berbeda.
• Contoh WA ≠ NT, atau (WA,NT) {(red,green),(red,blue),(green,red), (green,blue),(blue,red),(blue,green)}
• Solusi lengkap dan konsisten, contoh : WA = red, NT = green,Q = red,NSW = green,V = red,SA = blue,T = green

Constraint Graf

• Binary CSP biner : setiap constraint merelasikan dua variabel
• Graf Constraint : node adalah variabel, arc adalah constraint

 

MEA (Means-Ends Analysis)

• MEA adalah strategi penyelesaian masalah yang diperkenalkan pertama kali dalam GPS (General Problem Solver) [Newell & Simon, 1963].
• Proses pencarian berdasarkan ruang masalah yang menggabungkan aspek penalaran forward dan backward.
• Perbedaan antara state current dan goal digunakan untuk mengusulkan operator yang mengurangi perbedaan itu.
• Keterhubungan antara operator dan perbedaan tsb disajikan sebagai pengetahuan dalam sistem (pada GPS dikenal dengan Table of Connections) atau mungkin ditentukan sampai beberapa pemeriksaan operator jika tindakan operator dapat dipenetrasi.
• Contoh OPERATOR first-order predicate calculus dan operator2 tertentu mengijinkan perbedaan korelasi task-independent terhadap operator yang menguranginya.
• Kapan pengetahuan ada tersedia mengenai pentingnya perbedaan, perbedaan yang paling utama terpilih pertama lebih lanjut meningkatkan rata-rata capaian dari MEA di atas strategi pencarian Brute-Force.
• Bagaimanapun, bahkan tanpa pemesanan dari perbedaan menurut arti penting, MEA meningkatkan metode pencarian heuristik lain (di rata-rata kasus) dengan pemusatan pemecahan masalah pada perbedaan yang nyata antara current state dengan goal-nya.

Contoh :

• http://www.rci.rutgers.edu/~cfs/ 472_html/Planning/GPS_472.h tml
• Giarratano – hal 261-262
• Luger – hal 430 - 433.

sumber :
https://aiukswkelasgkelompok7.wordpress.com/metode-pencarian-dan-pelacakan/
slideplayer.info/slide/3764086/
www.slideshare.net/ahmadhaidaroh/modul-3-pencarian-heuristik