Metode Pencarian Buta(Blind Search) & Heuristik

     1. Metode Pencarian Buta (Blind Search)
merupakan model pencarian buta atau pencarian yang tidak memiliki informasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:
-          Membangkitkan simpul berdasarkan urutan
-          Kalau ada solusi maka solusi akan ditemukan
-          Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).

Metode ini dibagi menjadi :

   a. Breadth First Search
- Breadth First Search yaitu model pencarian yang memakai metode melebar. Untuk mencari hasilnya, model BFS ini menggunakan teknik pencarian persoalannya dengan cara membuka node (titik) pada tiap levelnya.
- Pada metode breadth-first search, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1.
- Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya, demikian pula dari kiri ke kanan hingga ditemukannya solusi.

Contoh BFS :

Mencari jalur angkutan umum dari terminal senen ke terminal Kp. Rambutan

- Initial State : Senen

- Goal State : Kp. Rambutan

Penjelasan :

1. Membangkitkan anak dari terminal Senen = Terminal blok M, Terminal Pulo Gadung, Terminal Manggarai
2. Karena goal state (Terminal Kp. Rambutan) belum tercapai maka kita bangkitkan anak dari terminal senen
   Terminal Blok M = Terminal Grogol, Terminal Lebak Bulus         
   Terminal Lebak Bulus = Terminal Ciputat, Terminal Kp. Rambutan.          
   Terminal Pulo Gadung = Terminal bekasi          
   Terminal Manggarai = Terminal Cililitan, Terminal Harmoni
3. Akhirnya tercapai Goal State (Terminal Kp. Rambutan).

   b. Depth First Search
- Depth-first Search sering disebut juga pencarian mendalam.
- Pencarian Depth – First Search dilakukan pada suatu simpul dalam setiap level dari yang paling kiri.
- Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yang kiri dapat dihapus dari memori.
- Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi.
- Jika solusi  ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).

Contoh DFS :
Pada gambar terdapat Initial dan Goal State.

Penjelasan :

Metode ini akan memulai mencari simpul dari sebelah kiri dahulu, baru setelah itu ke kanan sampai semua simpul sudah mendapatkan goalnya. Disini dari simpul A kemudian ke simpul B,D,E,F,G karena sebelah kiri sudah habis, bisa dihapus atau pada gambar ditutup, maka rute dilanjutkan ke sebelah kanan tree yaitu mulai dari simpul C,H,I,J,K. Maka kita telah menemukan goal dari rute ini yakni simpul K.

   2. Metode Pencarian Heuristik
- merupakan sebuah teknik yang mengembangkan efisiensi dalam proses pencarian (pencarian yang lebih simple). Namun kemungkinan juga dapat mengorbankan kelengkapan (complateness).
- Heuristic digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

Metode ini dibagi menjadi :

   a. Generate & Test
Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju pada suatu keadaan awal.
Algoritma:
1.Bangkitkan suatu kemungkinan solusi(membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal).
2.Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.
3.Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.

Contoh Generate &Test :
 “Travelling Salesman Problem (TSP)” Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setaip kota hanya boleh dikunjungi tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar di bawah ini: 

Penjelasan :
dengan membangkitkan solusi-solusi yang mungkin dengan menyusun kota- kota dalam urutan abjad, yaitu :

• A-B-C-D
• A-B-D-C
• A-C-B-D
• dan seterusnya

 

Dari gambar diatas dapat di jelaskan sebagai berikut :

• Misalkan kita mulai dari node A. Kita pilih sebagai keadaan awal adalah lintasan ABCD dengan panjang lintasan - 19.
• Kemudian kita lakukan backtracking untuk mendapatkan lintasan ABDC dengan panjang lintasan -18.
• Lintasan ini kita bandingkan dengan lintasan ABCD. ternyata ABDC < ABCD, sehingga lintasan terpilih adalah ABDC.
• Kita lakukan lagi backtracking untuk mendapatkan lintasan ACBD (-12), ternyata ACBD < ABCD, maka lintasa terpilih sekarang adalah ACBD.
• Demikian seterusnya hingga di temukan solusi yang sebenarnya.
• Salah satu kelemahan dari metode ini adalah perlunya di bangkitkan semua kemungkinan solusi sehingga membutuhkan waktu yang cukup besar dalam pencariannya.

   b.  Hill Climbing
- Pada metode ini pembangkitan keadaan berikutnya tergantung pada feedback dari prosedur pengetesan.
- Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lain yang mungkin.

Algoritma :
1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
a) Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang : Cari operator yang belum digunakan; gunakan operator 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 iterasi.

Hill Climbing dibagi menjadi :
1.     Teknik simple hill climbing
Algoritma akan berhenti kalau mencapai nilai optimum lokal. Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi. Tidak diijinkan untuk melihat satupun langkah selanjutnya.

2.     Teknik steepest – ascent hill climbing

Hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari paling kiri. Gerakan selanjutnya dicari berdasarkan nilai heuristic terbaik.

Contoh Hill Climbing :
Diketahui keadaan awal dan tujuan dari suatu permainan kotak 8 puzzle, sebagai berikut :

Penjelasan :
Jadi kotak puzzle ini diselesaikan dengan cara pengurutan seperti hal nya mendaki, atau bisa disebut secara melingkar. Kotak pertama kita isi nilai yang paling kecil, kemudian sebelahnya mengurut sesuai urutan terkecil dan besar. Begitu seterusnya sampai tercapai goal dengan nilai yang terurut.

Sumber :

http://library.binus.ac.id/eColls/eThesisdoc/Bab2HTML/2007300192IFBab2/page10.html
http://yoursknowladge.blogspot.co.id/2015/04/makalah-algoritma-breadth-first-search.html
http://yoosinhay.blogspot.co.id/2011/03/teknik-pencarian-perancangan.html
https://rinnooberta.wordpress.com/2013/10/29/pencarian-heuristik/
http://fryunfirst.blogspot.co.id/2015/06/pencarian-heuristik-heuristic-search.html

Metode Inferensi pada Sistem Berbasis Pengetahuan

 Pengertian, Definisi, Macam-Macam, dan Metode Inferensi

1.1.Pengertian Inferensi

-          Inferensi adalah tindakan atau proses yang berasal kesimpulan logis dari premis-premis yang diketahui atau dianggap benar.Kesimpulan yang ditarik juga disebut sebagai idiomatik. Hukum valid inference dipelajari dalam bidang logika .

-          Inferensi adalah membuat simpulan berdasarkan ungkapan dan konteks penggunaannya. Dalam membuat inferensi perlu dipertimbangkan implikatur. Implikatur adalah makna tidak langsung atau makna tersirat yang ditimbulkan oleh apa yang terkatakan (eksplikatur).

Kedua istilah ini tidak terlepas dalam percakapan atau tindak tutur dalam kehidupan sehari. Oleh karena itu, kita perlu memahami kedua istilah ini lebih mendalam.alam membuat inferensi perlu dipertimbangkan implikatur. Implikatur adalah makna tidak langsung atau makna tersirat yang ditimbulkan oleh apa yang terkatakan (eksplikatur). Inferensi memiliki dua jenis yaitu referensi lansung dan referensi tak lansung.

Inferensi manusia (yaitu bagaimana manusia menarik kesimpulan) secara tradisional dipelajari dalam bidang psikologi kognitif ; kecerdasan buatan para peneliti mengembangkan sistem inferensi otomatis untuk meniru inferensi manusia. inferensi statistik memungkinkan untuk kesimpulan dari data kuantitatif.

1.2. Definisi Inferensi

Proses di mana kesimpulan disimpulkan dari pengamatan beberapa disebut penalaran induktif . Kesimpulannya mungkin benar atau salah, atau benar dalam tingkat tertentu akurasi, atau yang benar dalam situasi tertentu. Kesimpulan disimpulkan dari pengamatan beberapa dapat diuji oleh pengamatan tambahan.

Sebuah pekerjaan bagai pendengar (pembaca) yang selalu terlibat dalam tindak tutur selalu harus siap dilaksanakan ialah inferensi. Inferensi dilakukan untuk sampai pada suatu penafsiran makna tentang ungkapan-ungkapan yang diterima dan pembicara atau (penulis). Dalam keadaan bagaimanapun seorang pendengar (pembaca) mengadakan inferensi. Pengertian inferensi yang umum ialah proses yang harus dilakukan pembaca (pendengar) untuk melalui makna harfiah tentang apa yang ditulis (diucapkan) samapai pada yang diinginkan oleh saorang penulis (pembicara).

Inferensi atau kesimpulan sering harus dibuat sendiri oleh pendengar atau pembicara karena dia tidak mengetahui apa makna yang sebenarnya yang dimaksudkan oleh pembicara/penulis. Karena jalan pikiran pembicara mungkin saja berbeda dengan jalan pikiran pendengar, mungkin saja kesimpulan pendengar meleset atau bahkan salah sama sekali. Apabila ini terjadi maka pendengar harus membuat inferensi lagi. Inferensi terjadi jika proses yang harus dilakukan oleh pendengar atau pembaca untuk memahami makna yang secara harfiah tidak terdapat pada tuturan yang diungkapkan oleh pembicara atau penulis. Pendengar atau pembaca dituntut untuk mampu memahami informasi (maksud) pembicara atau penulis.

1.3 Macam-Macam Inferensi

1.      Inferensi Langsung

Inferensi yang kesimpulannya ditarik dari hanya satu premis (proposisi yang digunakan untuk penarikan kesimpulan). Konklusi yang ditarik tidak boleh lebih luas dari premisnya.

Contoh:          

Bu, besok temanku berulang tahun. Saya diundang makan malam. Tapi saya tidak punya baju baru, kadonya lagi belum ada”.

Maka inferensi dari ungkapan tersebut: bahwa tidak bisa pergi ke ulang tahun temanya.

2.      Inferensi Tak Langsung

 Inferensi yang kesimpulannya ditarik dari dua / lebih premis. Proses akal budi membentuk sebuah proposisi baru atas dasar penggabungan proposisi-preposisi lama.

Contoh:

A:Anak-anak begitu gembira ketika ibu memberikan bekal makanan.
B : Sayang gudegnya agak sedikit saya bawa.

Inferensi yang menjembatani kedua ujaran tersebut misalnya (C) berikut ini.
C : Bekal yang dibawa ibu lauknya gudek komplit.

1.4 Metode Inferensi

I.            TREES. LATTICE dan GRAPH

Tree (pohon) adalah suatu hierarki struktur yang terdiri dari Node (simpul/veteks) yang menyimpan informasi atau pengetahuan dan cabang (link/edge) yang menghubungkan node. Binary tree mempunyai 0,1 atau 2 cabang per-node.

o   Node tertinggi disebut root

o   Node terendah disebut daun

Tree merupakan tipe khusus dari jaringan semantic, yang setiap nodenya kecuali akar, mempunyai satu node orang tua dan mempunyai nol atau lebih node anak. Tree adalah kasus khusus dalam Graph. Graph dapat mempunyai nol atau lebih link di antara node dan tidak ada perbedaan antara orangtua dan anak.

Dalam graph, link dapat ditunjukkan berupa panah atau arah yang memadukan node dan bobot yang merupakan karakteristik beberapa aspek dari link.

II.            SPASI STATA dan SPASI PERMASALAHAN

State adalah kumpulan karakteristik yg dapat digunakan untuk menentukan status. State Space adalah rangkaian pernyataan yg menunjukkan transisi antara state dimana objek dieksprerimen.

III.            AND-OR TREE dan GOALS

Dalam SP, untuk menemukan solusi problem dapat menggunakan rangkaian backward yaitu dengan tree AND-OR dan AND-OR-NOT

-       Banyak tipe system pakar menggunakan backward chaining untuk mendapatkan solusi dari permasalahan.

-       Salah satu tipe dari tree atau lattice yang digunakan dalam masalah representasi backward chaining adalah Pohon AND-OR.

IV. LOGIKA DEDUKTIF DAN SYLLOGISMS

Tipe-tipe Inferensi :

a.      Deduction

Pemberian alasan logikal dimana kesimpulan harus mengikuti premis

b.      Induction

Inferensi dari khusus ke umum

c.       Intuition

Tidak ada teori yg menjamin. Jawabannya hanya muncul, mungkin dengan penentuan pola yg ada secara tidak disadari.

d.      Heuristic

Aturan yg didasarkan pada pengalaman

e.       Generate & Test

Trial dan error. Digunakan dgn perencanaan.

f.        Abduction

Pemberian alasan kembali dari kesimpulan yg benar ke premis .

g.      Default

Diasumsikan pengetahuan umum sebagai default

h.      Autoepistemic

Self-knowledge

i.        Nonmonotonic

Pengetahuan yg sebelumnya mungkin tdk benar jika bukti baru didapatkan

j.        Analogy

Kesimpulan yg berdasarkan pada persamaan untuk situasi yg lainnya.

Penalaran deduktif umumnya terdiri dari tiga bagian : premis mayor, premis minor dan konklusi. Premis disebut juga antecedent. Konklusi/kesimpulan disebut juga consequent. Silogisme dapat direpresentasikan ke dalam bentuk aturan JIKA…..MAKA….. (IF…THEN…..),

Silogisme klasik disebut categoricall syllogism (silogisme yang pasti). Premis dan konklusi didefinisikan sebagai statement yang pasti dari empat bentuk berikut :

Bentuk	Skema	Arti
A	Semua S adalah P	Universal Afirmative
E	Tidak S adalah P	Universal Negative
I	Beberapa S adalah P	Particular Afirmative
O	Beberapa S bukan P	ParticularNegative

Subjek dari konklusi S disebut bagian minor bila predikat konklusi P adalah bagian mayor. Premis terdiri dari premis mayor dan premis minor.

V.            ATURAN DARI INFERENSI

                Diagram Venn tidak sesuai untuk argumen yang lebih kompleks karena sulit dibaca pada decision tree untuk silogisme. ogika proposisi memberikan pengertian lain dari penggambaran argumen.

VI.            LOGIKA PEMBATASAN DARI PROPORSIONAL

Perhatikan bahwa tidak ada hubungan di dalam premises atau kesimpulan sehingga setiap premises dan setiap kesimpulan harus mempunyai variable logical yang berbeda. Juga , logika preposisional tidak mempunyai provisi untuk quantifier sehingga tidak ada cara  untuk menunjukkan quantifier “semua“ di dalam premise pertama. Satu-satunya representasi argument ini di dalam logoka proporsional adalah di atas dari tiga variable yang bebas.

Untuk menentukan argument tersebut valid, perhatikan table kebenaran dari tiga variable bebas untuk keseluruhan kemungkinan kombinasi dari T dan F yang ditunjukkan dalam table berikut :

Tabel Kebenaran untuk skema p,q;

p	q	r
T T T T F F F F	T T F F T T F F	T F T F T F T F

Baris kedua dari table benar ini menunjukkan argumen untuk tidak valid karena premises benar sementara kesimpulan salah.

Validitas dari argumen ini harus “tidak” diinteprestasikan seperti arti kesimpulan yang tidak benar. Seseorang akan menentukannya sebagai argumen yang benar, Ketidak-valid-an sederhana berarti bahwa “argument tidak dapat dibuktikan dibawah logika proporsional”. Misalnya, kita akan memberi atribut pada beberapa arti “semua” dan mempertimbangkan “men” sebagai bentuk jaman dari “man”. Namun demikian, syllogism dan kalkulus proporsional tidak memungkinkan struktur preposisi internal untuk diuji. Batasan ini dibatasi oleh logika predikat dan argumen valid di bawah logika predikat. Kenyataannya, seluruh logika syllogistic  merupakan subset yang valid dari order pertama logika predikat dana dapat dibuktikan dengan valid dibawahnya.

VII.            LOGIKA PREDIKAT ORDER PERTAMA KALI

Representasi 4 kategori silogisme menggunakan logika predikat

Bentuk	Skema	Representasi Predikat
A	Semua S adalah P	("x) (S(x)àP(x))
E	Tidak S adalah P	("x) (S(x)à~P(x))
I	Beberapa S adalah P	($x) (S(x)àP(x))
O	Beberapa S bukan P	($x) (S(x)à~P(x))

Kaidah Universal Instatiation merupakan state dasar, dimana suatu individual dapat digantikan (disubsitusi) ke dalam sifat universal.

VIII.            SISTEM LOGIKA

Sistem logika adalah kumpulan objek seperti kaidah (rule), aksioma, statement dan lainnya yang diatur dalam cara yang konsisten.

Sistem logika mempunyai beberapa tujuan :

1.       Menentukan bentuk argumen.

Awalnya argumen logika tidak memiliki arti dalam semantic sense, bentuk yang valid pada dasarnya dapat dicapai jika validitas dari argumen tersebut dapat ditentukan.

Fungsi terpenting dari logika sistem adalah menentukan well formed formulas (wffs) dari argumen yang digunakan.

2.   Menunjukkan kaidah inferensi yang valid.

3.   Mengembangkan dirinya sendiri dengan menemukan kaidah baru inferensi dan memperluas jangkauan argumen yang dapat dibuktikan.

IX.            SHALLOW DAN CASUAL REASONING

Sistem pakar menggunakan rantai inferensi, dimana rantai yang panjang merepresentasikan lebih banyak causal atau pengetahuan yang mendalam. Sedangkan shallow umumnya menggunakan kaidah tunggal atau inferensi yang sedikit.

Kualitas inferensi juga faktor utama dalam penentuan kedalaman dan pendangkalan dari penalaran. Shallow knowledge disebut juga experiment knowledge.

Pada penalaran shallow, tidak ada atau hanya terdapat sedikit pemahaman dari subjek, dikarenakan tidak ada atau hanya terdapat sedikit rantai inferensi.

Keuntungan dari penalaran shallow :

-  Kemudahan dalam pemograman, yang berarti waktu pengembangan program menjadi singkat,

-  Program menjadi lebih kecil,

-  Lebih cepat

-  Biaya pengembangan menjadi murah.

  X.                RANGKAIAN FORWARD DAN BACKWARD

Chain (rantai) : perkalian inferensi yang menghubung-kan suatu permasalahan dengan solusinya.

Forward chaining :

- Suatu rantai yang dicari atau dilewati/dilintasi dari suatu permasalahan untuk memperoleh solusi.

-  Penalaran dari fakta menuju konklusi yang terdapat dari fakta.

Backward chaining :

-  Suatu rantai yang dilintasi dari suatu hipotesa kembali ke fakta yang mendukung hipotesa tersebut.

-  Tujuan yang dapat dipenuhi dengan pemenuhan sub tujuannya.

Karakteristik Forward dan Backward chaining

Forward chaining	Backward chaining
Perencanaan, monitoring, kontrol	Diagnosis
Disajkan untuk masa depan	Disajikan untuk masa lalu
Antecedent ke konsekuen	Konsekuen ke antecedent
Data memandu, penalaran dari bawah ke atas	Tujuan memandu, penalaran dari atas ke bawah
Bekerja ke depan untuk mendapatkan solusi apa yang mengikuti fakta	Bekerja ke belakang untuk mendapatkan fakta yang mendukung hipotesis
Breadth first search dimudahkan	Depth first search dimudahkan
Antecedent menentukan pencarian	Konsekuen menentukan pencarian
Penjelasan tidak difasilitasi	Penjelasan difasilitasi

  Sumber :

- http://karmila.staff.gunadarma.ac.id/Downloads/files/19087/METODE+INFERENSI.doc

- Pengantar Sistem Berbasis Pengetahuan, Seri Diktat Kuliah, PenerbitGunadarma

-  mufidnilmada.staff.gunadarma.ac.id