SISTEM CERDAS

Metode Pencarian dan Pelacakan 2 (Heuristik)

Metode Pencarian Heuristic

Heuristic Search merupakan metode pencarian yang memperhatikan nilai heuristic (nilai perkiraan). Teknik pencarian heuristic (heuristic searching) merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu. Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness)

Heuristic Search memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik). Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

Jenis-jenis Heuristic Searching: 

– Generate and Test.

– Hill Climbing.

– Best First Search.

– Means-EndAnlysis, Constraint Satisfaction, dll.

Dan disini saya akan membahas Metode Pencarian dan Pelacakan (Heuristik) antara lain :

5.1 Best First Search

Metode ini adalah kombinasi dari metode depth-search first dan metode breadth-search first dengan mengambil kelebihan keduanya. Ketika pada hill climbing tidak diperkenankan untuk kembali ke node sebelumnya, pada metode ini diijinkan jika ternyata node yang lebih tinggi memiliki nilai heuristik 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)

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

Contoh: 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 dengannode 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.

5.2 Problem Reduction Dalam Teknik Pencarian Heuristik 

Dalam teori komputabilitas dan teori kompleksitas komputasi , pengurangan adalah transformasi dari satu masalah ke masalah lain.Tergantung pada transformasi yang digunakan ini dapat digunakan untuk mendefinisikan kelas kompleksitas pada serangkaian masalah.

Secara intuitif, masalah A ke B direduksi masalah jika solusi ke B ada dan memberikan solusi ke A setiap kali A memiliki solusi. Jadi, pemecahan A tidak bisa lebih sulit daripada memecahkan B. Kita menulis A ≤ m B, biasanya dengan subskrip pada ≤ untuk menunjukkan jenis pengurangan yang digunakan (m: pengurangan pemetaan, p: reduksi polinomial).

5.3 Constranint 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

5.4  Means End Analysis

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.

REPRESENTASI PENGETAHUAN

Pengetahuan dibedakan menjadi 3 klasifikasi yaitu:

1. Prodecural Knowledge adalah pengetahuan yang berkaitan dengan prosedur atau cara untuk melakukan sesuatu. Contohnya, bagaimana cara mendidihkan air dalam panci.
2. Declarative Knowledge adalah pengetahuan untuk dapat menentukan nilai benar dan salah suatu hal. Contohnya, jangan celupkan tangan anda dalam air yang mendidih.
3. Tacid Knowledge kadang disebut juga sebagai "unconscious knowledge", karena pengetahuan tidak dapat diekspresikan atau didefinisikan dengan bahasa. Contohnya, bagaimana menggerakkan tangan.

Representasi Pengetahuan

Representasi pengetahuan adalah suatu teknik untuk merepresentasikan basis pengetahuan yang diperoleh ke dalam suatu skema/diagram tertentu sehingga dapat diketahui relasi/keterhubungan antara suatu data dengan data yang lain sehingga dapat diuji kebenaran penalarannya. Representasi pengetahuan biasanya digunakan untuk pembuatan sistem pakar di mana komputer dirancang untuk dapat mengambil keputusan seperti manusia agar dapat memecahkan permasalahan. Secara singkat, representasi pengetahuan diklarifikasikan menjadi 4 kategori :

1. Representasi logika. Representasi jenis ini menggunakan ekspresi-ekspresi dalam logika formal untuk merepresentasikan basis pengetahuan.
2. Representasi prosedural. Representasi yang menggambarkan pengetahuan sebagai kumpulan instruksi untuk memecahkan suatu problema.
3. Representasi network. Representasi ini menangkap pengetahuan sebagai sebuah graf dimana simpul-simpulnya menggambarkan obyek atau konsep dari problema yang dihadapi, sedangkan edgenya menggambarkan hubungan atau asosiasi antar mereka.
4. Representasi terstruktur. Representasi terstruktur memperluas network dengan cara membuat setiap simpulnya menjadi struktur data kompleks.

Adapun bentuk representasi pengetahuan yang telah dikembangkan, yaitu :

1.       Jaringan Semantik ( Semantic nets)

Jaringan Semantik adalah tehnik representasi dalam artificial intelligence klasik untuk informasi proposional, sehingga sering kali disebut sebagai poporsional network. Proposisi adalah pernyataan yang dapat bernilai benar atau salah dan merupakan bentuk pengetahuan deklaratif. Semantic network pertama kali dikembangkan untuk AI (Artificial Intelligence) sebagai cara untuk mempresentasikan memory dan pemahaman bahasa manusia. Struktur semantic nets berupa grafik dengan node (simpul) dan arc (ruas) yang menghubungkannya.

2.       Object-Attribute-Value/Nilai (OAV)

Bentuk object-attribute-value triple dapat digunakan untuk mempresentasikan semua karakteristik pengetahuan dalam semantic net dan digunakan pada sistem pakar MYCIN untuk mendiagnosa penyakit infeksi.

3.       Bingkai (Frame)

Salah satu tipe skema yang digunakan dalam beberapa aplikasi AI adalah frame. Frame merupakan struktur yang baik untuk mempresentasikan objek yang tipikal dalam situasi tertentu. Karakteristik dasar frame adalah frame mempresentasikan pengetahuan yang terkait mengenai sebuah subjek yang sempit dan memiliki default. Sistem frame adalah pilihan yang baik untuk mendeskripsikan peralatan mekanik seperti mobil. Frame mencoba memodelkan obyek yang ada di dunia nyata menggunakan pengetahuan generik untuk atribut yang banyak dimiliki oleh obyek dan pengetahuan spesifik untuk kasus khusus.

 

4.       Aturan Produksi (Production Rule)

Aturan produksi adalah jenis representasi pengetahuan yang paling umum digunakan karena memiliki keuntungan yang lebih dibandingkan dengan kekurangannya.

REPRESENTASI PENGETAHUAN : LOGIKA PROPOSISI

Logika Proposisi disebut juga kalkulus proposisi yang merupakan logika simbolik untuk memanipulasi proposisi. Proposisi merupakan pernytaan yang dapat bernilai benar atau salah.

Operator logika yang digunakan :

• Operator Fungsi

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

Kondisional Berarti 

• p implies q : Anda berusia 21 tahun atau sudah tua implies Anda mempunyai hak pilih.
• Jika p maka q : Jika Anda berusia 21 tahun atau sudah tua, maka Anda mempunyai hak pilih.
• p hanya jika q : Anda berusia 21 tahun atau sudah tua, hanya jika Anda mempunyai hak pilih.
• p adalah (syarat cukup untuk q) : Anda berusia 21 tahun atau sudah tua adalah syarat cukup Anda mempunyai hak pilih.
• q jika p : Anda mempunyai hak pilih, jika Anda berusia 21 tahun atau sudah tua.
• q adalah (syarat perlu untuk p) : Anda mempunyai hak pilih adalah syarat perlu Anda berusia 21 tahun atau sudah tua.

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 :

REPRESENTASI PENGETAHUAN : LOGIKA PREDIKAT

Logika Predikat Order Pertama 

Logika Predikat Order Pertama 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).

Logika orde pertama adalah sistem resmi yang digunakan dalam matematika , filsafat ,linguistik , dan ilmu komputer . Hal ini juga dikenal sebagai orde pertama predikat kalkulus, semakin rendah kalkulus predikat, teori kuantifikasi, dan logika predikat. Logika orde pertama dibedakan dari logika proposisional oleh penggunaan variabel terukur.

Sebuah teori tentang beberapa topik biasanya logika orde pertama bersama-sama dengan yang ditentukan domain wacana dimana variabel diukur berkisar, finitely banyak fungsi yang memetakan dari domain yang ke dalamnya, finitely banyak predikat didefinisikan pada domain tersebut, dan satu set rekursif dari aksioma yang diyakini terus untuk hal-hal. Kadang-kadang “teori” dipahami dalam arti yang lebih formal, yang hanya satu set kalimat dalam logika orde pertama.

Kata sifat “orde pertama” membedakan orde pertama logika darilogika tingkat tinggi di mana ada predikat yang memiliki predikat atau fungsi sebagai argumen, atau di mana salah satu atau kedua bilangan predikat atau fungsi bilangan diizinkan. Dalam first teori order, predikat sering dikaitkan dengan set. Dalam ditafsirkan tingkat tinggi teori, predikat dapat ditafsirkan sebagai set set.

Ada banyak sistem deduktif untuk orde pertama logika yang sehat(semua laporan dapat dibuktikan benar dalam semua model) danlengkap (semua pernyataan yang benar dalam semua model yang dapat dibuktikan). Meskipun konsekuensi logis hubungan hanyasemidecidable , banyak kemajuan telah dibuat dalam teorema otomatis dalam logika orde pertama. Logika orde pertama juga memenuhi beberapa metalogical teorema yang membuatnya setuju untuk analisis dalam teori bukti , seperti teorema Löwenheim-Skolem dan teorema kekompakan .

Logika orde pertama adalah standar untuk formalisasi matematika menjadi aksioma dan dipelajari di dasar matematika . Teori matematika, seperti nomor teori dan teori himpunan , telah diresmikan menjadi orde pertama aksioma skema seperti Peano aritmatika dan Zermelo-Fraenkel teori himpunan masing-masing (ZF).

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.

Logika Predikat Order Pertama terdiri dari :

• Konstanta: objek atau sifat dari semesta pembicaraan. Penulisannya diawali denganhuruf 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 disebutrangefungsi. Penulisannya dimulai dengan huruf kecil. Suatu ekspresi fungsi merupakan symbol fungsi yang diikuti argument.
• Argument adalah 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.

Quantifier Universal

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 kucing -> x adalah binatang).

Kebalikan kalimat “bukan kucing adalah binatang” ditulis :

(∀x) (p) (Jika x adalah seekor kucing -> ~x adalah binatang)

dan dibaca :

– “setiap kucing adalah bukan binatang”

“semua kucing adalah bukan binantang”

• Contoh 3:

(∀x) (Jika x adalah segitiga -> x adalah polygon)

Dibaca : “untuk semua x, jika x adalah segitiga, maka x adalah polygon”.

Dapat pula ditulis : (∀x) (segitiga(x) -> polygon(x))

(∀x) (T(x) -> P(x))

• Contoh 4 :

(∀x) (H(x) -> M(x))

Dibaca : “untuk semua x, jika x adalah manusia (human), maka x melahirkan (mortal)”.

Ditulis dalam aturan : IF x adalah manusia THEN x melahirkan.

Quantifier Exsistensial

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) (gajah(x) ∧ nama(Clyde))

Dibaca : “beberapa gajah bernama Clyde”.

• Contoh 3 :

(∀x) (gajah(x) -> berkaki empat(x))

Dibaca : “semua gajah berkaki empat”.

Universal quantifier dapat diekspresikan sebagai konjungsi.

(∃x) (gajah(x) ∧ berkaki tiga(x))

Dibaca : “ada gajah yang berkaki tiga”

Existensial quantifier dapat diekspresikan sebagai disjungsi dari

urutan ai. P(a1) ∨ P(a2) ∨ P(a3) …∨ P(aN)

Quantifier dan Set / Jaringan

Set Expression Logical Equivalent

A = B ∀x (x ∈A ↔ x ∈B)

A ⊆ B ∀x (x ∈A -> x ∈B)

A ∩ B ∀x (x ∈A ∧x ∈B)

A ∪ B ∀x (x ∈A ∨x ∈B)

μ(universe) T (True)

φ(empty set) F (False)

Relasi A proper subset dari B ditulis A ⊂ B, dibaca “semua elemen A ada pada B”, dan “paling sedikit satu elemen B bukan bagian dari A”.

Hukum de Morgan berlaku untuk analogi himpunan dan bentuk logika :

Himpunan Logika

(A∩B)≡A’∪B’ ~(p∧q) ≡p∨~q

(A∪B)≡A’∩B’ ~(p∨q) ≡p ∧~q

Contoh :

Diketahui :

E = elephant

R = reptile

G = gray

F = four legged

D = dogs

M = mammals

Set expression Berarti

E ⊂M “elephant termasuk mammals”, tetapi tidak semua mammals adalah elephant

(E ∩G ∩F) ⊂M “elephant yang berwarna gray dan memiliki four legged termasuk mammals”

E ∩R = φ “tidak ada elephant yang termasuk reptile”

E ∩G ≠φ “beberapa elephant berwarna gray”

E ∩G = φ “tidak ada elephant yang berwarna gray”

E ∩G’≠φ “beberapa elephants tidak berwarana gray”

E ⊂(G ∩F) “semua elephants berwarna gray dan memiliki four legged”

(E ∪D) ⊂M “semua elephants dan dogs termasuk mammals”

(E ∩F ∩G) ≠φ “beberapa elephants memiliki four legged dan berwarna gray”

Batasan Logika Predikat

Logika proposisional sudah cukup untuk menangani pernyataan-pernyataan yang sederhana.

Pernyataan yang mengandung kata, semua, ada atau kata yang lain tidak bisa diselesaikan.

Untuk pernyataan yang lebih rumit, misal:

A = semua mahasiswa pandai.

B = Badu seorang mahasiswa.

C = Dengan demikian, Badu pasti pandai.

bentuk ekspresi logika

(A ∧ B) → C : tidak bisa dibuktikan!

Bila menginginkan diselesaikan dengan logika proposisi, pernyataan pernyataannya harus dirubah menjadi

A → B = Jika Badu mahasiswa, maka ia pasti pandai.

A = Badu seorang mahasiswa.

B = Dengan demikian, ia pasti pandai

(( A → B) ∧ A) → B

Logika predikat merupakan pengembangan dari logika proposisional dengan masalah pengkuantoran dan menambah istilah-istilah baru.

Istilah dalam Logika Predikat:

Term : kata benda atau subjek

Predikat : properti dari term

Fungsi proposisional=fungsi

Kuantor

– Universal: yang selalu bernilai benar (∀).

Contoh :

Semua gajah mempunyai belalai

G(x) = gajah

B(x) = belalai

Bentuk logika predikat

(∀x)(G(x)→B(x))

Dibaca: untuk semua x, jika x seekor gajah, maka x mempunyai belalai.

– Eksistensial: bisa bernilai benar atau salah(∃).

Contoh :

Ada bilangan prima yang bernilai genap.

P(x) = bilangan prima

G(x) = bernilai genap

Bentuk logika predikat

(∃x)(P(x)∧G(x))

Dibaca: ada x, yang x adalah bilangan prima dan x bernilai genap.

Contoh Logika Predikat:

Nani adalah ibu dari Ratna.

Term=nani , ratna

Predikat=adalah ibu dari

Fungsi=ibu(nani,ratna) ; M(n,r)

Bentuk logika predikat:

M(n,r)→¬M(r,n)

SOURCE

http://slideplayer.info/slide/3764086/

http://larasdewilaras.blogspot.co.id/2016/11/metode-pencarian-dan-pelacakan-2.html

http://bagusnunu.blogspot.co.id/2014/09/representasi-pengetahuan.html

http://sumarna.staff.gunadarma.ac.id/Downloads/files/29146/4+Representasi+Pengetahuan.pdf