Sistem Pakar

Bab VI

Sistem Pakar

sistem pakar menurut:
Martin dan Oxman 1998 yaitu Sistem berbasis komputer yang menggunakan pengetahuan, fakta, dan teknik penalaran dalam memecahkan masalah yang biasanya hanya dapat dipecahkan oleh seorang pakar dalam bidang tersebut.
Durkin yaitu Program komputer yang dirancang untuk memodelkan
kemampuan penyelesaian masalah yang dilakukan oleh
seorang pakar.
Giarratano dan Riley yaitu Sistem komputer yang bisa menyamai atau meniru
kemampuan seorang pakar.

Sistem Pakar (Expert System)
Sistem yang menggunakan pengetahuan
manusia yang terekam dalam komputer
untuk memecahkan persoalan yang
membutuhkan keahlian manusia
Sistem informasi berbasis komputer yang
menggunakan pengetahuan pakar untuk
mencapai performa keputusan tingkat
tinggi dalam domain persoalan yang
sempit.

biasanya sistem pakar diterapkan untuk mendukung pemecahan suatu masalah.
antara lain:
-Pembuatan Keputusan (Decicion Making)
-Pemaduan Pengetahuan (Knowledge Fusing)
-Pembuatan Desai (Designing)
-Perencanaan (Planning)
-Prakiraan (Forecasting)
-Pengaturan (Regulating)
-Pengendalian (Controlling)
-Diagnosis (Diagnosing)
-Perumusan (Prescribing)
-Penjelasan (Explaining)
-Pemberian Nasihat (Advising)
-Pelatihan (Tutoring)

Contoh Sistem Pakar:
MYCIN
Diagnosa penyakit miningitis dan infeksi
FOLIO
Membantu memberikan keputusan bagi seorang manajer
dalam hal stok broker dan investasi.
XCON & XSEL
Membantu konfigurasi sistem komputer besar.
DELTA
Pemeliharaan lokomotif listrik disel.
DENDRAL
Mengidentifikasi struktur molekular campuran yang tak
dikenal.

Ciri-ciri Sistem Pakar:
-Terbatas pada bidang yang spesifik.
-Berdasarkan pada rule atau kaidah
tertentu.
-Outputnya bersifat nasihat atau anjuran.
-Output tergantung dari dialog dengan
user.

Keuntungan Sistem Pakar
-Memungkinkan orang awam bisa
mengerjakan pekerjaan para ahli.
-Menyimpan pengetahuan dan keahlian
para pakar.
-Meningkatkan output dan produktivitas.
-Menghemat waktu dalam pengambilan.
keputusan.
-Menigkatkan kualitas.

Kelemahan Sistem Pakar
-Biaya yang diperlukan untuk
membuat dan memeliharanya
sangat mahal
-Sulit dikembangkan
-Ketersediaan pakar di bidangnya
-Tidak 100% bernilai benar

Konsep Dasar sistem pakar yaitu Keahlian, Ahli, Pengalihan keahlian, Inferensi, Aturan, Kemampuan menjelaskan.

Struktur Sistem Pakar
-Basis pengetahuan
-Mesin inferensi
-Blackboard
-Antarmuka pengguna
-Subsistem penjelasan
-Sistem penyaring pengetahuan

Representasi Pengetahuan

Bab V

Representasi Pengetahuan

> Pengetahuan di klasifikasika menjadi 3 bagian yaitu:

Procedural Knowledge

Tentang Bagaimana melakukan sesuatu

Bagaimana mendidihkan air dalam mangkok

Bagaimana memasak mie instan

Bagaimana menjalankan mobil

Declarative Knowledge

Mengetahui sesuatu itu benar atau salah

Jangan celupkan tangan anda ke dalam air mendidih

Jangan tidur di kelas

Tacit Knowledge

Suatu pengetahuan bawaan yang tidak dapat diungkapkan dengan bahasa

Bagaimana kita menggerakkan tangan

Bagaimana memejamkan mata

Pengetahuan merupakan kunci utama dalam sistem pakar (AI). Tanpa kita beri pengetahuan, AI tidak dapat bekerja dengan baik dan berguna untuk kita. Untuk itu, dapat di analogikan apabila Algoritma + Struktur Data dapat menjadi Program kemudian berdasar pengetahuan yang ada serta Inferensi yang pasti menjadi suatu Sistem Pakar.

Representasi Pengetahuan merupakan metode yang digunakan untuk mengodekan pengetahuan dalam sebuah sistem pakar. Hal ini dimaksudkan untuk menangkap sifat-sifat penting problema, membuat informasi itu dapat diakses oleh prosedur pemecahan problema.

• Dua bagian dasar sistem kecerdasan

buatan (menurut Turban) :

+ Basis pengetahuan

+ Inference Engine

• Karakteristik representasi pengetahuan

Dapat diprogram dengan bahasa komputer dan disimpan dalam memori

Fakta dan pengetahuan lain yang terkandung di dalamnya dapat digunakan untuk melakukan penalaran.

Pengetahuan dapat direpresentasikan dalam bentuk yang sederhana atau kompleks, tergantung dari masalahnya. (Schnupp, 1989). Beberapa model representasi pengetahuan

: Logika (logic)

: List & Tree

: Jaringan semantik (semantic nets)

: Bingkai (frame)

: Tabel Keputusan (decision table)

: Pohon Keputusan (decision tree)

: Naskah (script)

: Kaidah/Sistem produksi (production rule)

Logika

Suatu pengkajian ilmiah tentang serangkaian penalaran, sistem kaidah, dan prosedur yang membantu penalaran. Komputer harus dapat menggunakan proses penalaran deduktif dan induktif ke dalam bentuk yang sesuai dengan manipulasi komputer, yaitu logika simbolik atau matematika, atau dapat disebut Logika Komputasional

Logika Proporsional

• Proposisi merupakan suatu statemen atau pernyataan yang menyatakan benar (TRUE) atau salah (FALSE)

Logika Predikat

• Suatu logika yang lebih canggih yang seluruhnya menggunakankonsep 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 = Rojali

y = Juleha

Maka proposisinya menjadi Suka(x,y)

Predikat kalkulus membolehkan penggunaan simbol untuk mewakili fungsi-fungsi

Misalnya

ayah(Juleha) = Jojon

ibu(Rojali) = Dorce

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

 Premis Mayor

• Contoh : Jika hujan turun saya tidak akan kuliah

 Premis Minor

• Contoh : Pagi ini hujan turun

 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 (∀)

 Untuk semua

 Kuantitas eksistensial (∃)

 Ada / terdapat

• Contoh:

 Semua sapi berkaki empat

 (∀x)[Sapi(x), berkaki empat(x)]

 Beberapa sapi berwarna putih

 (∃x)[Sapi(x), berwarna putih(x)]

List

• Struktur sederhana untuk representasi pengetahuan berupa daftar dari rangkaian materi yang terkait. List digunakan untuk objek yang dikelompokkan, dikategorikan atau digabungkan.

Tree / Pohon

• Struktur sederhana untuk representasi pengetahuan dan merupakan struktur grafik hirarki

Jaringan Semantik

• Struktur sederhana untuk representasi pengetahuan grafis yang menunjukkan hubungan antar berbagai objek.

Frame

• Frame berupa kumpulan pengetahuan tentang suatu objek tertentu, peristiwa, lokasi, situasi,

berdasarkan pengalaman. Frame memiliki slot yang menggambarkan rincian (atribut) dan karakteristik objek. Hirarki Frame merupakan susunan hirarki dari frame mengijinkan pewarisan frame.

Tabel Keputusan (Decision Table)

• Tabel keputusan dalam bentuk format tabel

• Tabel dibagi 2  bagian pertama untuk atribut &

bagian kedua untuk nilai & kesimpulan

Pohon Keputusan (Decision Tree)

• Pohon keputusan  mudah dikonversi ke dalam bentuk aturan (rule)

Naskah (Script)

• Naskah  sama dengan frame, bedanya menggambarkan urutan peristiwa

• Elemen script meliputi :

1. Kondisi input > kondisi yang harus dipenuhi

2. Track > variasi yang mungkin terjadi

3. Prop > berisi objek-objek pendukung

4. Role > peran yang dimainkan oleh seseorang

5. Scene > adegan yang dimainkan

6. Hasil > kondisi yang ada setelah urutan peristiwa dalam script terjadi.

Sistem/Aturan Produksi (Production Rules)

• Representasi pengetahuan yang berupa aturan (rule) :

- Antecedent > mengekspresikan situasi / premis (berawalan if)

- Konsekuen > menyatakan tindakan tertentu jika premis

benar (berawalam THEN)

• Contoh :

IF lalulintas pagi ini padat

THEN saya naik sepeda motor saja.

Aturan dapat ditulis dalam beberapa bentuk :

1. IF premis THEN kesimpulan

Jika pendapatan tinggi MAKA pajak yang harus dibayar

juga tinggi

2. Kesimpulan IF premis

Pajak yang harus dibayar tinggi JIKA pendapatan tinggi

3. Inclusion of ELSE

IF pendapatan tinggi OR pengeluaran tinggi,

THEN pajak yang harus dibayar tinggi ELSE pajak

yang harus dibayar rendah

4. Aturan yang lebih kompleks

IF rating kredit tinggi AND gaji lebih besar dari

$30,000 OR aset lebih dari $75,000 AND sejarah

pembayaran tidak miskin THEN pinjaman diatas $ 10,000

disetujui dan daftar pinjaman masuk kategori “B”

Ada 2 metode penalaran yang menggunakan aturan :

+ Forward Reasoning (penalaran maju)

+ Penalaran dimulai dari tujuan atau hipotesa, baru

dicocokkan dengan keadaan awal atau fakta-fakta yang

ada.

+ Gunakan jika jumlah keadaan awal lebih kecil daripada

tujuan & kejadian itu berupa fakta baru

+ Backward Reasoning (Penalaran mundur)

+ Penalaran dimulai dari tujuan atau hipotesa, baru

dicocokkan dengan keadaan awal atau fakta-fakta yang ada.

+ Jika jumlah keadaan awal lebih banyak daripada tujuan

+ Jika kejadian itu berupa query

Pencarian

Bab IV

Pencarian Heuristik ada 4 metode pencarian heuristik yaitu sebagai berikut:

1. Pembangkit & Pengujian (Generate and Test)
2. Pendakian Bukit (Hill Climbing)
3. Pencarian Terbaik Pertama (Best First Search)
4. Simulated Annealing

Hill Climbing

Gambar di bawah ini merupakan pencarian dengan menggunakan hill climbing

Pencarian Terbaik Pertama (Best First Search)

> Dengan metode pencarian hill climbing diatas maka kita akan melakukan pencarian terbaik
pertama (Best First Search) yaitu sebagai berikut:

• Metode best-first search ini merupakan kombinasi dari metode depth-first search dan metode breadth-first search dengan mengambil kelebihan dari kedua metode tersebut.

• Apabila pada pencarian dengan metode hill climbing tidak diperbolehkan untuk kembali ke node pada level yang lebih rendah meskipun node pada level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik, lain halnya dengan metode best-first search ini.

• Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada lebih yang lebih tinggi ternyata memiliki nilai heuristik yang lebih buruk.

• Penentuan node berikutnya adalah node yang terbaik yang pernah dibangkitkan.

• Menggunakan informasi
  – biaya perkiraan
  – biaya sebenarnya

• Terdapat 2 jenis
  – Greedy Best First Search
  • biaya perkiraan f(n) = h(n)
  – A*
  • biaya perkiraan + biaya sebenarnya
  • f(n) = g(n) + h(n)

• Untuk mengimplementasikan metode ini menggunakan graph keadaan, dibutuhkan 2 antrian yang berisi node- node, yaitu:
  – OPEN, berisi node,node yang sudah dibangkitkan, namun belum diuji. Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan nilai heuristik tertinggi
  – CLOSED berisi node-node yang sudah diuji

• Algoritmanya sebagai berikut:
  – Tempatkan node awal A pada antrian OPEN.
  – Kerjakan langkah-langkah berikut hingga tujuan ditemukan atau antrian OPEN sudah kosong:
  – Ambil node terbaik dari OPEN;
  – Bangkitkan semua successornya;
  – Untuk tiap-tiap successor kerjakan:
  – Jika node tersebut belum pernah dibangkitkan sebelumnya, evaluasi node tersebut dan masukkan ke OPEN;
  – Jika node tersebut sudah pernah dibangkitkan sebelumnya, ubah parent jika lintasan baru lebih menjanjikan. Hapus node tersebut dari antrian OPEN.

> Contohnya sebagai berikut:

Greedy Best First Search

> Contoh Pencarian menggunakan Greedy Best First Search sebagai berikut:

CLOSED = [S] OPEN = [A,B,C,D,E]

S Terbagi Menjadi A(yg memiliki nilai f=80), B(yg memiliki nilai f=60), C(yg memiliki nilai f=70),

D(yg memiliki nilai f=85), E(yg memiliki nilai f=74)

Kemudian S menutup dirinya dan digantikan oleh A,B,C,D,E

OPEN = [A,C,D,E,F,K]
CLOSED = [S,B]

Kemudian dengan cara mencari nilai terendah dan terpendek pertama yaitu pada B, karena nilai A adalah 80 , sedangkan B 60, Maka B Menutup dan Membagi dirinya menjadi F(yg memiliki nilai f=70)dan K(yg memiliki nilai f=30).

OPEN = [A,C,D,E,F,G]
CLOSED = [S,B,K]
HASIL = S,B,K,G

Karena jarak ke F =70 sedangkan K= 30 , maka yg dipilih adalah K yg memiliki nilai yg lebih kecil dari dan K menutup dirinya yg digantikan oleh G (yg memiliki nilai f=0). Karena G sudah bernilai 0 dan tidak emiliki percabangan lagi,maka hasil yg diperoleh adalah S,B,K,dan G karena menggunakan metode pencari Best First Search.

> Contoh di atas merupakan pencarian menggunakan Greedy Best First Search

A*

> Ini merupakan Pencarian dengan menggunakan A*, contohnya sebagai berikut:

OPEN = [A,B,C,D,E]
CLOSED = [S]

S Menutup dirinya dan membagi dirinya menjadi A(yg memiliki nilai f=90),B(yg memiliki nilai f=85),C(yg memiliki nilai f=100),D(yg memiliki nilai f=120)dan E(yg memiliki nilai f=84).

OPEN = [A,B,C,D,J]
CLOSED = [S,E]

Karena Nilai E adalah nilai terkecil dengan nilai 84 +10 =94 sedangkan nilai A adalah 90+10=100 ,B =85+25=110, C= 100+30 =130, D= 120 +35=155 , maka yg terpilih adalah E yg kemudian terbagi menjadi D(yg memiliki nilai f=110) dan J(yg memiliki nilai f=130)

OPEN = [A,C,D,F,J,K]
CLOSED = [S,E,B]

Setelah dilihat dari nilai jumlah jarak kesuluruhan maka yg dipilih adalah B karana memiliki nilai jarak terkecil, Kemudian B menutup dirinya dan membagi menjadi F(yg memiliki nilai f=100) dan K( yg memiliki nilai

f=105).

OPEN = [C,D,F,G,J,K]
CLOSED = [S,E,B,A]

Kemudian dilihat kembali jumlah jarak terpendek dan A adalah nilai jarak terpendek maka A dipilih dan A menutup dirinya. A membuka dirinya menjadi G(yg memiliki nilai f=100).

OPEN = [C,D,G,J,K]
CLOSED = [S,E,B,A,F]

Dilihat kembali nilai jarak terkecil , dan ditemukan nilai dari S-A-B-F lebih kecil dalu nilai F dipilih dan F menutup dirinya dan digantikan oleh nilai K(yg memiliki nilai f=95).

OPEN = [C,D,G,J]
CLOSED = [S,E,B,A,F,K]
HASIL = S,A,B,F,K,G

Hasilnya adalah jarak dari S-A-B-F-K-G adalah jarak dengan nilai terpendek dengan menggunakan metode A*.
> Dengan menggunakan kedua pencarian di atas ternyata pencarian dengan menggunakan A* lebih baik dibandingkan dengan Greedy Best First Search.

Pencarian

Bab III

Pencarian

Pencarian Heuristik

• Pencarian buta tidak selalu dapat diterapkan dengan baik

• Waktu aksesnya yang cukup lama

• Besarnya memori yang diperlukan

• Metode heuristic search diharapkan bisa menyelesaikan

permasalahan yang lebih besar.

• Metode heuristic search menggunakan suatu fungsi yang

menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu

menuju ke simpul tujuan ➔ disebut fungsi heuristic

• Aplikasi yang menggunakan fungsi heuristic : Google, Deep Blue

Chess Machine

Pencarian Heuristik

• Operator

• Ubin kosong geser ke kanan

• Ubin kosong geser ke kiri

• Ubin kosong geser ke atas

• Ubin kosong geser ke bawah

Langkah Awal hanya 3 operator yang bisa digunakan

• Ubin kosong digeser ke kiri, ke kanan dan ke atas.

• Jika menggunakan pencarian buta, tidak perlu

mengetahui operasi apa yang akan dikerjakan

(sembarang)

• Pada pencarian heuristik perlu diberikan informasi

khusus dalam domain tersebut

Informasi yang bisa diberikan

Untuk jumlah ubin yang menempati posisi yang benar jumlah yang

lebih tinggi adalah yang lebih diharapkan (lebih baik)

Untuk jumlah ubin yang menempati posisi yang salah jumlah yang

lebih kecil adalah yang diharapkan (lebih baik).

Menghitung total gerakan yang diperlukan untuk mencapai tujuan

jumlah yang lebih kecil adalah yang diharapkan (lebih baik).

Ada 4 metode pencarian heuristik

• Pembangkit & Pengujian (Generate and Test)

• Pendakian Bukit (Hill Climbing)

• Pencarian Terbaik Pertama (Best First Search)

• Simulated Annealing

-Pembangkit & Pengujian (Generate and Test)

Pada prinsipnya metode ini merupakan penggabungan antara depthfirst search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.

Algoritma:

• Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik

tertentu atau lintasan tertentu dari keadaan awal).

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

• Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah

yang pertama.

Kelemahan

• Perlu membangkitkan semua kemungkinan sebelum

dilakukan pengujian

• Membutuhkan waktu yang cukup lama dalam

pencariannya

-Pendakian Bukit (Hill Climbing)

Metode ini hampir sama dengan metode pembangkitan & pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik, Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan.

-Simple Hill Climbing

Algoritma

• Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika

tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

• Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada

operator baru yang akan diaplikasikan pada keadaan sekarang:

• Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan

keadaan yang baru.

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

-Steepest Ascent Hill Climbing

Steepest-ascent hill climbing sebenarnya hampir sama dengan simple hill climbing, hanya

saja gerakan pencarian tidak dimulai dari posisi paling kiri. Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik.

Algoritma

Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika

tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

• Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan

sekarang.

• Tentukan SUCC sebagai nilai heuristic terbaik dari successor-successor.

• Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang:

• Gunakan operator tersebut dan bentuk keadaan baru.

• Evaluasi keadaan baru tersebut. Jika merupakan tujuan, keluar. Jika bukan, bandingkan nilai

heuristiknya dengan SUCC. Jika lebih baik, jadikan nilai heuristic keadaan baru tersebut sebagai

SUCC. Namun jika tidak lebih baik, nilai SUCC tidak berubah.

• Jika SUCC lebih baik daripada nilai heuristic keadaan sekarang, ubah node SUCC menjadi

keadaan sekarang.