Teknik 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.
– Means-EndAnlysis, Constraint Satisfaction, dll.
1). PEMBANGKITAN dan PENGUJIAN
(Generate and Test)
- Metode ini merupakan
penggabungan antara depth-first search dengan pelacakan mundur
(backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.
- Algoritma :
1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu
tititk tertentu atau lintasan tertentu dari keadaan awal).
2. Uji untuk melihat apakah node tersebut benar-benar
merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari
suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.
3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali
langkah pertama.
2) PENDAKIAN BUKIT (Hill
Climbing)
- Metode ini hampir sama dengan
metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan
dengan menggunakan fungsi heuristic. 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 lainnyayang 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.
- Contoh: TSP dengan Simple Hill Climbing Disini ruang keadaan
berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk
menukar posisi kota-kota yang bersebelahan. Apabila ada n kota, dan kita
ingin mencari kombinasi lintasan dengan menukar posisi urutan 2 kota, maka
kita akan mendapatkan sebanyak n!/2!(n-2)! atau sebanyak 6
kombinasi. Fungsi heuristic yang digunakan adalah panjang lintasan
yang terjadi.
3). 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)
- 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.
- f’ = Fungsi evaluasi
- g = cost dari initial state ke current state
- h’ = prakiraan cost dari current state ke goal state
REPRESENTASI PENGETAHUAN
Representasi pengetahuan adalah cara untuk menyajikan pengetahuan yang diperoleh
ke dalam suatu skema/diagram tertentu sehingga dapat diketahui relasi antara
suatu pengetahuan dengan pengetahuan yang lain dan dapat dipakai untuk menguji
kebenaran penalarannya.
Secara teknik kita akan membahas representasi pengetahuan menjadi lima
kelompok:
1.
Representasi Logika
2.
Jaringan Semantik
3.
Frame
4.
Script (Naskah)
5.
Aturan Produksi (Kaidah Produksi)
1. Representasi Logika
Logika didefinisikan sebagai ilmu untuk berpikir dan menalar
dengan benar sehingga didapatkan kesimpulan yang absah.
Tujuan dari logika: memberikan aturan-aturan penalaran sehingga orang dapat
menentukan apakah suatu kalimat bernilai benar atau salah.
Representasi Logika dibagi menjadi dua:
- Propositional Logic (Logika Proposisi)
Suatu
Proposisi merupakan suatu statemen atau pernyataan yang menyatakan benar (TRUE) atau salah (FALSE). Dalam Propositional Logic fakta dilambangkan dengan simbol misalnya P, Q
dan R. Lambang-lambang
tersebut dihubungkan dengan relasi-relasi logika
Dengan menggunakan operator logika:
Tabel Kebenaran Logika
- Predicate Logic (Logika Predikat)
Pada logika predikat proposisi
dibedakan menjadi argumen (obyek) dan predikat (keterangan). Secara umum
penulisan proposisi dalam logika predikat dapat dinyatakan sebagai berikut:
Predikat (argumen-1, argumen-2,..., argumen-3)
Contoh:
Proposisi: “Bu Atika mencintai Pak Agus Setiawan”
Dalam logika predikat disajikan dalam bentuk:
Mencintai (Bu Atika, Pak Agus Setiawan)
P
Argumen-1 Argumen-2
Contoh Silsilah Keluarga yang
dipresentasikan dalam Prolog
Jika silsilah di atas dibentuk dalam Representasi Logika,
sebagai berikut:
Orangtua (Komarudin, Andika)
Orangtua (Komarudin, Atika)
Orangtua (Komarudin, Agus)
Orangtua (Andika, Rika)
Orangtua (Atika, Anjar)
2.
Jaringan Semantik
Pengetahuan disusun dalam
sebuah jaringan yang memiliki komponen utama:
-
Node: menyatakan obyek, konsep, atau situasi. Dinyatakan dengan kotak atau lingkaran
-
Arcs/Link: Menyatakan
hubungan antar node. Dinyatakan
dengan tanda panah.
3. Frame
Frames: merupakan semantic net dilengkapi
dengan properties. Suatu
Frame menggambarkan entitas sebagai set dari attribute dan nilai yang bersesuaian. Suatu frame dapat berelasi dengan frame
yang lainnya.
Tiga komponen utama dari frame
•
frame
name
•
attributes
(slots)
•
values
(subslots)
Book Frame
|
Slot à Subslots
|
Title à AI. A modern
Approach
Author à Russell
& Norvig
Year à 2003
|
4. script
Conceptual Dependency (ketergantungan konseptual) adalah teori tentang
bagaimana mempresentasikan pengetahuan tentang event (kejadian) yang biasanya
terkandung dalam kalimat bahasa natural.
Contoh: representasi Conceptual Dependency
“Budi memberi Atika sebuah buku”
Script adalah
skema representasi pengetahuan yang menggambarkan urutan-urutan kejadian
(sequence of events). Script dilengkapi dengan elemen-elemen agar lebih
memudahkan dalam memahami urutan kejadian.
a.
Track/Jalur: variasi yang mungkin terjadi dalam script
b.
Kondisi Input: situasi yang harus dipenuhi sebelum
sesuatu kejadian terjadi
c.
Prop/Pendukung: objek pendukung yang digunakan dalam
urutan peristiwa yang
terjadi
d.
Role/Peran: orang-orang yang terlibat dalam suatu peran
e.
Scene/Adegan: urutan peristiwa aktual
f.
Hasil: kondisi akhir yang terjadi setelah urutan
peristiwa dalam script terjadi
5. Aturan Produksi (Kaidah Produksi)
Pengetahuan dalam kaidah
produksi direpresentasikan dalam bentuk
JIKA [kondisi] MAKA [Aksi]
JIKA [premis] MAKA [Konklusi]
Aturan Produksi (kaidah produksi) adalah salah satu representasi pengetahuan yang
menghubungkan premis dengan konklusi.
Bentuknya: If Premis Then Konklusi
Konklusi pada bagian then bernilai
benar jika premis pada bagian if
bernilai benar.
Contoh:
If hari ini hujan then saya tidak kuliah.
Materi ini saya
dapatkan dari Dosen mata kuliah
Kecerdasan Buatan
Operator Logika
Operator logika digunakan untuk
membentuk suatu ekspresi pembandingan dari satu atau dua buah ekspresi
pembandingan.
Di bawah ini operator logika :
Operator
|
Keterangan
|
Operand
|
|
&&
|
AND
|
Operator
“dan”
|
Dua
buah operand
|
||
|
OR
|
Operator
“atau”
|
Dua
buah operand
|
!
|
NOT
|
Operator
“bukan”
|
Satu
buah operand
|
1.
Untuk logika && ( AND
) akan menghasilkan nilai benar jika semua operand bernilai benar, dan akan
bernilai salah jika salah satu operand bernilai salah.
2.
Untuk logika || ( OR ) akan
menghasilkan nilai benar jika hanya satu operand bernilai benar, dan akan
bernilai salah jika semua operand bernilai salah.
3.
Untuk logika ! ( NOT ) akan
menghasilkan nilai benar jika operand bernilai salah, dan akan bernilai salah
jika operand bernilai benar.
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.
•
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
Definisi
1.
Tautologi adalah suatu proporsi majemuk yang selalu
bernilai benar untuk semua kemungkinan kombinasi nilai kebenaran dari
proporsi-proporsi pembentuknya
Contoh
pada table kebenaran
p
|
 p |
p
 p |
B
S
|
S
B
|
B
B
|
Definisi
2.
Kontradiksi
adalah suatu proporsi majemuk yang selalu bernilai salah untuk semua
kemungkinan kombinasi nilai kebenaran dari proporsi-proporsi pembentuknya.
Contoh
pada table kebenaran
p
|
p |
p
 p |
B
S
|
S
B
|
S
S
|
Definisi
3.
Kontingensi
adalah suatu proporsi majemuk yang bukan termasuk tautologi dan bukan juga
kontradiksi
Contoh
pada table kebenaran
p
|
q
|
p
 q |
B
B
S
S
|
B
S
B
S
|
B
B
B
S
|
Definisi
4.
Dua
buah proporsi dikatakan ekivalen (ekivalen logis), jika kedua proporsi tersebut
memiliki nilai kebenaran yang sama. Proporsi p dan q ekivalen dinotasikan
dengan p 
q atau sering disederhanakan p = q.
q atau sering disederhanakan p = q.
Definisi
ekivalen di atas, dapat juga dirumuskan sebagai berikut :
Proporsi p dan q
ekivalen jika dan hanya jika p 
q merupakan
suatu tautolog
q merupakan
suatu tautologLogika Predikat
• Suatu logika yang lebih canggih yang seluruhnya menggunakan konsep dan kaidah proporsional yang sama. Disebut juga kalkulus predikat, yang memberi tambahan kemampuan untuk merepresentasikan pengetahuan dengan sangat cermat dan rinci. Memungkinkan memecah statemen ke dalam bagian komponenyang disebut obyek, karakteristik obyek atau beberapa keterangan obyek. Suatu proposisi atau premis dibagi menjadi dua bagian
Argumen (atau obyek)
Individu atau obyek yang membuat keterangan
Predikat (keterangan)
Keterangan yang membuat argumen dan predikat
Dalam suatu kalimat, predikat dapat berupa kata kerja atau bagian kata kerja
• PREDIKAT (individu[obyek]1, individu[obyek]2)
• Misalnya proposisi:
Mobil berada dalam garasi
• Dinyatakan menjadi
Di dalam (mobil, garasi)
Di dalam = produk (keterangan)
Mobil = Argumen (obyek)
Garasi = Argumen (obyek)
• Contoh lain
Proposisi : Rojali suka Juleha
Kalkulus Predikat : SUKA (Rojali, Juleha)
Proposisi : Pintu Terbuka
Kalkulus Predikat : BUKA (pintu)
Proposisi : Sensor cahaya aktif
Kalkulus Predikat : AKTIF (sensor cahaya)
Pengetahuan diekspresikan dalam kalkulus predikat yang dapat dimanipulasi agar dapat diinferensi/dinalar. Pangkalan pengetahuan dibentuk dengan menggunakan variabel sebagai simbol-simbol untuk merancang obyek, misalnya
x = Rojaliw
y = Julehaw
Maka proposisinya menjadi Suka(x,y)w
Predikat kalkulus membolehkan penggunaan simbol untuk mewakili fungsi-fungsi
Misalnya
ayah(Juleha) = Jojonw
ibu(Rojali) = Dorcew
Fungsi dapat digunakan bersamaan dengan predikat. Misalnya predikat berikut menjelaskan bahwa Jojon dan Dorce adalah berteman, teman(ayah(Juleha),ibu(Rojali))=teman(Jojon,Dorce)
Penalaran Deduktif bergerak dari penalaran umum menuju ke konklusi khusus atau pernyataan premis dan inferensi
w Premis Mayor
• Contoh : Jika hujan turun saya tidak akan kuliah
w Premis Minor
• Contoh : Pagi ini hujan turun
w Konklusi
• Contoh : Oleh karena itu pagi ini saya tidak akan kuliah
Penalaran Induktif bergerak dari masalah khusus ke masalah umum
• Menggunakan sejumlah fakta atau premis yang mantap untuk menarik kesimpulan umum
• Contoh
+ Premis 1 : Aljabar adalah pelajaran yang sulit
+ Premis 2 : Geometri adalah pelajaran yang sulit
+ Premis 3 : Kalkulus adalah pelajaran yang sulit
+ Konklusi : Matematika adalah pelajaran yang sulit
+ Konklusi tidak selalu mutlak, dapat berubah jika ditemukan fakta baru
• Contoh
• Premis 4 : AI adalah pelajaran yang sulit
Pengukuran Kuantitas
Adalah simbol yang mengijinkan untuk menyatakan suatu rangkaian atau cakrawala variabel dalam suatu ekspresi logika. Dua pengukuran kuantitas, yaitu:
Kuantitas universal (∀)w
Untuk semua§
Kuantitas eksistensial (∃)w
Ada / terdapat§
• Contoh:
Semua sapi berkaki empatw
(∀x)[Sapi(x), berkaki empat(x)]w
Beberapa sapi berwarna putihw
(∃x)[Sapi(x), berwarna putih(x)]w
Tidak ada komentar:
Posting Komentar