Pencarian Heuristik
(Heuristic Search)
• Heuristik adalah sebuah teknik
yang mengembangkan efisiensi dalam proses pencarian, namum 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.
• Jenis-jenis Heuristic
Searching:
– Generate and Test.
– Hill Climbing.
– Best First Search.
– Alpha Beta
Prunning,Means-EndAnlysis,Constraint Satisfaction, Simulated Annealing, dll
PENCARIAN TERBAIK
PERTAMA (Best-First Search)
Metode ini merupakan kombinasi
dari metode depthfirst 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
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.
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 sama dengan
algoritma Best First Search, dengan mempertimbangkan adanya arc AND.
• Gambar berikut menunjukkan
bahwa untuk mendapatkan TV orang bias dengan cara singkat yaitu mencuri atau
membeli asal mempunyai uang.
• Untuk mendeskripsikan
algoritma, digunakan nilai F_UTILITY untuk biaya solusi.
Goal : Ingin Memiliki
Mencuri TV Punya Uang Membeli TV
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
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. Teknik Pencarian Heuristik 25/25
Pengantar Kecerdasan Buatan
(AK045218)
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.AA
A Priori Knowledge
•Berarti yang mendahului
(pengetahuan datang sebelumnya dan bebas dari arti)
• Kebenaran yang universal dan
tidak dapat disangkal tanpa kontradiksi
• Contoh : pernyataan
logika, hukum matematika
A Posteriori Knowledge
• Knowledge yang diturunkan dari
akal pikiran yang sehat.
• Kebenaran atau kesalahan dapat
dibuktikan dengan menggunakan pengalaman akal sehat.
• Contoh : bola mata seseorang
berwarna biru, tetapi ketika orang tersebut mengganti contactensnya, bisa jadi
bola matanya menjadi berwarna hijau.
I.1 Kategori Knowledge
• Procedural Knowledge
Bagaimana melakukan sesuatu
• Declarative Knowledge
Mengetahui sesuatu
itu benar atau salah
Tacit Knowledge
Tidak dapat
diungkapkan dengan Knowledge pada Sistem Pakar Analogi dengan ekspresi
klasik Wirth:
ALGORITMA + STRUKTUR DATA =
PROGRAM
Knowledge pada Sistem Pakar :
KNOWLEDGE + INFERENSI = SP
I.2 Hirarki Knowledge
Aturan Produksi
Sering digunakan untuk
merepresentasikan pengetahuan pada Sistem Pakar.
• Bentuk formalnya Backus
-Naus Form (BNF),
1. untuk mendefinisikan sintaks
bahasa
2. suatu grammar haruslah
lengkap dan unambiguous set dari aturan produksi untuk bahasayang spesifik
3. parse tree adalah
representasi grafis dari kalimat pada suatu bahasa
4. deskripsi sintaks
tersedia dalam bahasa
5. tidak semua kalimat
adalah benar
• Keuntungan Aturan Produksi :
– sederhana dan mudah
dipahami
– implementasi secara
straightforward sangat dimungkinkan dalam computer
–dasar bagi berbagai
variant
• Kelemahan Aturan Produksi :
–implementasi yang
sederhana sering menyebabkan inefisien
–beberapa tipe pengetahuan
sulit direpresentasikan dalam aturan produksi.
Jaringan Semantik
• Dibangun oleh M.R.Quillian,
sebagaimodel 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. AKOmerelasikan kelas individu ke kelas induk dari
kelas-kelas dimana individu tersebut merupakan kelasanak.
– HAS-A berarti
“mempunyai” yang merelasikan suatu kelas menjadi
subkelas. HAS-A berlawanandengan AKO dan sering digunakan untuk
merelasikan suatu objek ke bagian dari objek.
Triple Obyek-Atribut-Nilai
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 :
Frame
Frame (Minsky, 1975) dipandang
sebagai struktur data static yang digunakan untukmerepsentasi-kan
situasi-situasi yang telah dipahami dan stereotype.Frame digunakan untuk
merepresentasikan pengetahuan stereotype atau pengetahuan yangdidasarkan kepada
karakteristik yang sudah dikenal yang merupakan pengalaman masa lalu.Frame
berupa kumpulan slot-slot (representasi entitas sebagai struktrur objek) yangmerupakan
atribut untuk mendeskripsikan pengetahuan berupa kejadian, lokasi, situasi
ataupunelemen-elemen lain. Frame digunakan untuk representasi pengetahuan
deklaratif.
Contoh 1 :
III.1 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
III.2 Frame Pohon Perdu
Spesialisasi dari : Pohon
Jumlah batang : 3
Jenis kulit : halus
Model daun : berganti daun
Bentuk daun : sederhana, berlekuk
Representas
Script
• 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 tindakan-tindakan yang terjadi dalam suatu peristiwa.
• Elemen script yang tipikal :
– Kondisi masukan :
menggambarkan situasi yang harus dipenuhi sebelum terjadi suatu
peristiwayang ada dalam script.
– Prop : mengacu
kepada objek yang digunakandalam 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
restoranSCRIPT RestoranJalur (track) : fast food restoranPeran (roles) : tamu,
pelayanPendukung (prop) : conter, baki, makanan, uang, serbet, garam, merica,
kecap, sedotan, dllKondisi 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
perutRepresentasi
Keistimewaan Script :
• Script menyediakan
beberapa cara yang sangat alami untuk merepresentasikan “suatu informasi”yang
lazim” dengan masalah yang bersumber dari sistem AI dari mula.
• Script menyediakan struktur hirarki
untuk merepresentasikan inforamsi melalui inklusi subscriptdengan sript.
Logika dan Set Jaringan
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 premis dan satu konklusi.
Contoh :
– Premis : Semua laki-laki adalah
makhluk hidup
– Premis : Socrates adalah
laki-laki
– 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.
A ={1,3,5,7} , B =
{….,-4,-2,0,2,4,…..} , 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.
Logika Proposisi
- Disebut juga kalkulus proposisi
yang merupakanlogika simbolik untuk memanipulasi proposisi.
- Proposisi merupakan pernytaan
yang dapat bernilaibenar atau salah.
- Operator logika yang digunakan
:
(
˄ ) Konjungsi (AND/DAN)
( ˅ ) Disjungsi (OR/ATAU)
( ̴ ) Negasi (NOT/TIDAK)
(
→) Implikasi/Kondisional (IF…THEN…./ JIKA…
MAKA ….)
(
↔ ) Equivalensi/Bikondisional
- Tautologi : pernyataan gabungan yang selalubernilai benar.
- Kontradiksi : pernyataan gabungan yang selalubernilai salah.
- Contingent : pernyataan yang bukan tautologyataupun kontradiksi.
Logika Proposisi
Logika Proposisi disebut juga
kalkulus proposisi yang merupakan logika simbolik untuk memanipulasi proposisi.
Proposisi merupakan pernytaan yang dapat bernilai benar atau salah
.
SEJARAH RESOLUSI
Teknik resolusi diperkenalkan
oleh J.A.Robinson pada tahun 1965.Teknik ini sebenarnya tidak dapat digunakan
dengan mudah karena harus melalui beberapa tahap dan setiap tahap
tersebut memerlukan pengertian-pengertian dasar dari logika matemati Sebelum
resolusi diterapkan, wff harus berada dalam keadaan normal (bentuk standar)
yaitu hanya menggunakan V.
PENGERTIAN RESOLUSI
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 :
1.
conjunctive normal form
2.
clausal form
3.
subset Horn clause.
Dari pengertian dasar logika matematika tersebut,teknik resolusi tersusun
secara bertahap sampai dengan proses resolve, yakni menghapus
literal berpasangan yang asa pada setiap klausa untuk menghasilkan resolvent atau
klausa hasil proses resolve. Dan dilakukan secara terus
menerus sampai menghasilkan falsum.
Resolusi diaplikasikan ke dalam
bentuk normal wff dengan menghubungkan seluruh elemen dan quantifier yang dieliminasi.
.Resolusi pada Logika
Proposisi
Menggunakan resolusi yaitu 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.
Representasi Pengetahuan
: LOGIKA
Logika Predikat Order
Pertama
• Disebut juga kalkulus predikat, merupakan logikayang digunakan
untuk merepresentasikanmasalah yang tidak dapat direpresentasikandengan
menggunakan proposisi.
• Logika predikat dapat memberikan representasifakat-fakta
sebagai suatu pernyataan yang mapan(well form).
• Syarat-syarat symbol dalam logika predikat :
– himpunan huruf, baik huruf kecil maupun hurufbesar dalam
abjad.
– Himpunan digit (angka) 0,1,2,…9
– Garis bawah “_”
– Symbol-simbol dalam logika predikat dimulaidengan sebuah huruf
dan diikuti oleh sembarangrangkaian karakter-karakter yang diijinkan.
– Symbol-simbol logika predikat dapatmerepresentasikan 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 domain fungsi ke dalam sebuah elemen unik pada
himpunan lain yang disebut range fungsi. 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.
• 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
Universal 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”.
Existensial
Quantifier
• 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”.
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.
SUMBER :
