Sistem Pakar. Pertemuan-1 : Konsep Dasar

Sistem Pakar Pertemuan-1 : Konsep Dasar

1

Materi Kuliah STIKOM Surabaya

9/12/2011

Deskripsi Mata Kuliah Matakuliah ini membahas tentang :

`

` `

` ` `

2

Konsep dasar Sistem Pakar Representasi pengetahuan menggunakan : Proposional logic, predicate calculus, sistem berbasis aturan, semantic ti network t k Representasi pengetahuan samar menggunakan : Bayesian, y , certaintly y factor System Fuzzy Jaringan syaraf tiruan


9/12/2011

Target Matakuliah Memahami model-model representasi pengetahuan Memiliki kemampuan menarik kesimpulan dari fakta yang digambarkan dalam model pengetahuan Merancang g dan membuat implementasi p sistem pakar menggunakan bahasa pemrograman

` ` `

3


9/12/2011

Sumber Belajar Jusak, 2007, sistem pakar: Buku pegangan kuliah. Surabaya:STIKOM Gonzales, A.J., and Douglas, D.D. 1993. The Engineering of Knowledge Based System. New Jersey: Prentice Hall International, Inc. Durkin, John. 1994. Expert System: Design and D Development. l t N New JJersey: P Prentice ti H Hallll International, Inc. Kumar Satish. Kumar, Satish 2004. 2004 Neural Network: A Classroom Approach. New Delhi: McGraw-Hill Companies.

` `

`

`

4


9/12/2011

Kontrak Perkuliahan Pertemuan ke -

Topik Bahasan

1

Menjelaskan kontrak perkuliahan Konsep dasar Sistem Pakar Heuristic Searching

2

Propositional Logic Predicate Calculus

3

Sistem berbasis aturan: Forward Reasoning

4

Sistem berbasis aturan: Backward Reasoning

5

Membangun sistem berbasis aturan

6

Semantic Networks dan Frame

7,8 ,8

Bayesian ayes a da dan Ce Certainty ta ty Factor acto

9,10,11

System Fuzzy

12,13,14

Jaringan Syaraf Tiruan Presentasi tugas Proyek

5


9/12/2011

Presentasi Penilaian Ujian Tengah Semester (30%) Ujian Akhir Semester (30%) Tugas (40%)

` ` `

` `

6

Project Kelompok (Demo dan Presentasi, pert:12,13,14) Tugas Mandiri (pert:2,3,4,5,8)


9/12/2011

Pertemuan-1 : Konsep Dasar Sistem Pakar 7


9/12/2011

Materi Konsep Dasar Sistem Pakar Tentang Sistem Pakar Sejarah Sistem Pakar C Contoh permasalahan Sistem Berbasis Aturan Perbedaan Sistem konvensional dan sistem pakar Data, informasi dan pengetahuan Struktur sistem pakar Heuristic Searching g sebagai g dasar dari Artificial Intelegence g (AI)

` ` ` ` ` ` ` `

` ` ` ` ` ` 8

Depth-First Search Breadth-first Search Hill Cli bi S Hill-Climbing Search h Branch and Bound Search Best-first Search A* Search Materi Kuliah STIKOM Surabaya

9/12/2011

Sistem Pakar

9


9/12/2011

Defenisi Sistem Pakar 1.

`

10

Sistem pakar (expert system) adalah sistem yang berusaha mengapdosi pengetahuan manusia ke komputer, agar komputer dapat menyelesaikan y masalah seperti p yyang g biasa dilakukan oleh para ahli. Sistem pakar yang baik dirancang agar dapat menyelesaikan suatu permasalahan tertentu dengan meniru kerja dari para ahli.


9/12/2011

Sistem pakar yang terkenal ` ` ` `

Nama Program: MYCIN Paling g terkenal,, dibuat oleh Edward Shortlife of Standford University tahun 70-an Sistem pakar medical yang bisa mendiagnosa penyakit infeksi dan merekomendasi pengobatan MYCIN membantu dokter mengidentifikasi pasien yang menderita penyakit. Dokter duduk di depan komputer dan memasukkan data pasien: umur, umur riwayat kesehatan, kesehatan hasil laboratorium dan informasi terkait lainnya. Dengan informasi ini ditambah pengetahuan yang sudah ada dalam komputer, komputer MYCIN mendiagnosa selanjutnya merekomendasi obat dan dosis yang harus dimakan.

11


9/12/2011

Sistem pakar yang terkenal ` `

`

` `

MYCIN sebagai penasehat medis, tidak dimaksudkan untuk mengantikan kedudukan seorang dokter. J Juga untuk t k membantu b t dokter d kt dalam d l mengkonfirmasi k fi i diagnosa dan terapi yang diberikan kepada pasien Kesimpulan :sistem pakar seperti MYCIN bisa digunakan sebagai bahan pembanding dalam pengambilan solusi dan pemecahan masalah. K Keputusan terakhir khi atas pengobatan b tersebut b tetap menjadi tanggung jawab dokter.

12


9/12/2011

Sistem pakar yang terkenal `

DENDRAL `

` ` `

`

`

M Mengidentifikasi id ifik i struktur k molekular l k l campuran ki kimia i yang tak k dik dikenall

XCON & XSEL XCON M Merupakan k sistem i t pakar k untuk t k membantu b t konfigurasi k fi i sistem i t komputer besar, membantu melayani order langganan sistem komputer DEC VAX 11/780 ke dalam sistem spesifikasi final yang lengkap Komputer besar seperti VAX terbuat dari ratudan komponen yang berbeda digabung dan disesuaikan dengan konfigurasi tertentu yang diinginkan oleh para pelanggan. Ada ribuan cara dimana aseosri Pcboard Pcboard, kabel kabel, disk drive drive, periperal periperal, perangkat lunak, dan lainnya bisa dirakit ke dalam konfigurasi yang sangat rapih. Untuk mengidentifikasi hal-hal tersebut diperlukan waktu berhari-hari/berminggu-minggu agar bisa memenuhi spesifikasi yang diinginkan pemesan pemesan, tapi dengan XCON bisa dalam beberapa menit. 13


9/12/2011

Contoh Permasalahan : “Jug Jug Problem Problem” ` `

` `

Diberikan 2 ember air dg kapasitas 8 liter dan 6 liter Kita dapat mengisi satu ember dari ember lainnya dan proses penakaran hanya dengan memakai 2 ember tersebut Bagaimana bisa mendapatkan tepat 4 liter dalam ember 8 liter Solusi : `

14

(0,0) Æ (0,6) Æ(6,0)Æ(6,6)Æ(8,4)Æ(0,4)Æ(4,0)


9/12/2011

MANFAAT SISTEM PAKAR : 1. 2. 3. 4. 5. 6.

15

Memungkinkan orang awam bisa mengerjakan pekerjaan para ahli Bisa melakukan proses secara berulang secara otomatis Menyimpan y p p pengetahuan g dan keahlian p para p pakar Mampu mengambil dan melestarikan keahlian para pakar (terutama yang termasuk keahlian langka) Mampu beroperasi dalam lingkungan yang berbahaya Memiliki kemampuan untuk bekerja dengan informasi yang tidak lengkap dan mengandung ketidakpastian. Pengguna gg bisa merespon p dengan g jjawaban ’tidak tahu’ atau ’tidak yakin’ pada satu atau lebih pertanyaan selama konsultasi dan sistem pakar tetap akan memberikan jawaban. Materi Kuliah STIKOM Surabaya

9/12/2011

MANFAAT SISTEM PAKAR : 7. 8.

9.

10.

16

Tidak memerlukan biaya saat tidak digunakan Dapat digandakan (diperbanyak) sesuai kebutuhan dengan waktu yang minimal dan sedikit biaya Dapat memecahkan masalah lebih cepat daripada kemampuan manusia dengan catatan menggunakan data yang sama. Menghemat waktu dalam pengambilan keputusan


9/12/2011

MANFAAT SISTEM PAKAR : 11.

12 12.

13.

17

Meningkatkan kualitas dan produktivitas karena dapat memberi nasehat yang konsisten dan mengurangi kesalahan Meningkatkan kapabilitas sistem terkomputerisasi yang lain. Mampu p menyediakan y p pelatihan. Pengguna gg pemula yang bekerja dengan sistem pakar akan menjadi lebih berpengalaman. Fasilitas penjelas dapat berfungsi sebagai guru.


9/12/2011

KELEMAHAN SISTEM PAKAR 1. 2. 3. 4 4.

5. 6.

18

Biaya yang diperlukan untuk membuat, memelihara, dan mengembangkannya sangat mahal Sulit dikembangkan Sistem pakar tidak 100% benar Pendekatan oleh setiap pakar untuk suatu situasi atau problem bisa berbeda-beda, meskipun sama-sama benar. T Transfer f pengetahuan h dapat d b if subjektif bersifat bj k if d dan bi bias Kurangnya rasa percaya pengguna dapat menghalangi pemakaian sistem p p pakar.


9/12/2011

KONSEP DASAR SISTEM PAKAR `

Konsep dasar sistem pakar mengandung ` ` ` ` ` `

19

keahlian, keahlian ahli/pakar, pengalihan keahlian, Mengambil keputusan, aturan, k kemampuan menjelaskan. j l k


9/12/2011

Keahlian `

`

Keahlian bersifat luas dan merupakan penguasaan pengetahuan dalam bidang khusus yang diperoleh dari pelatihan, membaca atau p g pengalaman. Contoh bentuk pengetahuan yang termasuk keahlian : ` `

20

Teori, fakta, aturan-aturan pada lingkup permasalahan tertentu St t i global Strategi l b l untuk t k menyelesaikan l ik masalah l h


9/12/2011

Ahli / Pakar `

Seorang ahli adalah seseorang yang mampu menjelaskan suatu tanggapan, mempelajari hal-hal hal hal baru seputar topik permasalahan, menyusun kembali pengetahuan jika dipandang perlu, memecahkan hk masalah l hd dengan cepat d dan tepat

21


9/12/2011

Pengalihan keahlian `

`

Tujuan dari sistem pakar adalah untuk mentransfer keahlian dari seorang pakar ke dalam komputer kemudian ke masyarakat. Proses ini meliputi 4 kegiatan, yaitu ` ` ` `

22

perolehan pengetahuan (dari para ahli atau sumbersumber lainnya), representasi pengetahuan ke komputer, kesimpulan dari pengetahuan dan pengalihan pengetahuan ke pengguna pengguna.


9/12/2011

Mengambil keputusan `

`

Hal yang unik dari sistem pakar adalah kemampuan untuk menjelaskan j dimana keahlian tersimpan p dalam basis pengetahuan. Kemampuan komputer untuk mengambil kesimpulan dilakukan oleh komponen yang dikenal dengan mesin inferensi yaitu meliputi prosedur tentang pemecahan masalah.

23


9/12/2011

Aturan `

`

Sistem pakar yang dibuat merupakan sistem yang berdasarkan pada aturan – aturan dimana program disimpan dalam bentuk aturan-aturan sebagai prosedur pemecahan masalah. Aturan tersebut bi biasanya b berbentuk b k IF – THEN. THEN .

24


9/12/2011

Kemampuan menjelaskan `

Keunikan lain dari sistem pakar adalah kemampuan dalam menjelaskan atau memberi saran/rekomendasi serta juga menjelaskan mengapa beberapa tindakan/saran tidak di k direkomendasikan d ik

25


9/12/2011

PERBEDAAN SISTEM KONVENSIONAL DENGAN SISTEM PAKAR

`

Sistem Konvensional ` ` `

Focus pada solusi Programmer g bekerja j sendiri Sequencial

` Sistem Pakar ` Fokus pada problem ` Team-work ` Iterative

26


9/12/2011

ELEMEN MANUSIA YANG TERKAIT DALAM PENGGUNAAN DAN PENGEMBANGAN SISTEM PAKAR 1. 2.

Pakar Perekayasa y pengetahuan p g `

3.

27

Perekayasa pengetahuan adalah orang yang membantu pakar dalam menyusun area permasalahan dengan p g menginterpretasikan g p dan mengintegrasikan jawaban-jawaban pakar atas pertanyaan yang diajukan, menggambarkan analogi, mengajukan counter example dan menerangkan kesulitan-kesulitan konseptual.

Pemakai


9/12/2011

Pemakai `

` `

`

Pemakai awam : dalam hal ini sistem pakar bertindak sebagai g konsultan untuk memberikan saran dan solusi kepada pemakai Pelajar yang ingin belajar : sistem pakar b ti d k sebagai bertindak b i iinstruktur t kt Pembuat sistem pakar : sistem pakar sebagai partner dalam pengembangan basis pengetahuan. Pakar : sistem p pakar bertindak sebagai g mitra kerja/asisten

28


9/12/2011

AREA PERMASALAHAN APLIKASI SISTEM PAKAR `

Interpretasi `

`

Prediksi `

`

Yaitu p pengambilan g keputusan p dari hasil observasi,, diantaranya y : pengawasan, pengenalan ucapan, analisis citra, interpretasi sinyal, dan beberapa analisis kecerdasan Memprediksi akibat-akibat yang dimungkinkan dari situasi-situasi tertentu, diantaranya : peramalan, prediksi demografis, peralaman ekonomi prediksi lalulintas ekonomi, lalulintas, estimasi hasil hasil, militer militer, pemasaran pemasaran, atau peramalan keuangan.

Diagnosis `

29

Menentukan sebab malfungsi dalam situasi kompleks yang didasarkan pada gejala-gejala yang teramati, diantaranya : medis, elektronis, mekanis, dan diagnosis perangkat lunak


9/12/2011

AREA PERMASALAHAN APLIKASI SISTEM PAKAR `

Desain `

`

Perencanaan `

`

Menentukan konfigurasi komponen-komponen sistem yang cocok dengan tujuan-tujuan kinerja tertentu dan kendala-kendala tertentu, diantaranya : layout sirkuit, perancangan bangunan Merencanakan serangkaian tindakan yang akan dapat mencapai sejumlah tujuan dengan kondisi awal tertentu, diantaranya : perencanaan keuangan, komunikasi, militer, pengembangan politik routing dan manajemen proyek politik, proyek.

Monitoring `

30

Membandingkan tingkah laku suatu sistem yang teramati dengan tingkah laku yang diharapkan darinya darinya, diantaranya : Computer Aided Monitoring System


9/12/2011

STRUKTUR SISTEM PAKAR `

2 bagian utama sistem pakar : `

`

31

lingkungan pengembangan (development environment) : digunakan untuk memasukkan pengetahuan pakar ke dalam lingkungan sistem pakar li k lingkungan kkonsultasi lt i ((consultation lt ti environment) i t) : digunakan oleh pengguna yang bukan pakar untuk memperoleh pengetahuan pakar


9/12/2011

32


9/12/2011

Komponen-komponen yang terdapat dalam arsitektur/struktur sistem pakar : ` ` ` ` ` ` `

1. Antarmuka Pengguna (User Interface) Merupakan p mekanisme yyang g digunakan g oleh p pengguna gg dan sistem pakar untuk berkomunikasi. 2. Basis Pengetahuan Basis pengetahuan mengandung pengetahuan untuk pemahaman, formulasi, dan penyelesaian masalah. Komponen sistem pakar ini disusun atas 2 elemen dasar, yaitu i : - fakta : informasi tentang obyek dalam area permasalahan tertentu p - aturan : informasi tentang cara bagaimana memperoleh fakta baru dari fakta yang telah diketahui.

33


9/12/2011

Komponen-komponen yang terdapat dalam arsitektur/struktur sistem pakar : ` `

2. Akuisisi Pengetahuan (Knowledge Acquisition) Akuisisi pengetahuan adalah akumulasi akumulasi, transfer transfer, dan transformasi keahlian dalam menyelesaikan masalah dari sumber pengetahuan ke dalam program komputer..

34


9/12/2011

Komponen-komponen yang terdapat dalam arsitektur/struktur sistem pakar : ` `

` `

3. Mesin/Motor Inferensi (inference engine) Komponen ini mengandung mekanisme pola pikir dan penalaran yang digunakan oleh pakar dalam menyelesaikan suatu masalah. 4. Workplace / Blackboard Workplace merupakan area dari sekumpulan memori kerja (working memory), memory) digunakan untuk merekam kejadian yang sedang berlangsung g g termasuk keputusan p sementara.

`

35


9/12/2011

Komponen-komponen yang terdapat dalam arsitektur/struktur sistem pakar : ` ` ` `

5. Fasilitas Penjelasan j Adalah komponen tambahan yang akan meningkatkan kemampuan sistem pakar. 6. Perbaikan Pengetahuan Pakar memiliki kemampuan untuk menganalisis dan meningkatkan i k tk ki kinerjanya j serta t kkemampuan untuk t k belajar dari kinerjanya.

36


9/12/2011

BASIS PENGETAHUAN (KNOWLEDGE BASE) `

`

Basis p pengetahuan g berisi p pengetahuan-pengetahuan g p g dalam penyelesaian masalah. Ada 2 bentuk pendekatan basis pengetahuan : a Penalaran berbasis aturan (rule-based a. (rule based reasoning) Pengetahuan direpresentasikan dengan menggunakan aturan berbentuk IF-THEN. Contoh : aturan identifikasi hewan ` ` ` ` 37

Rule 1 : IF hewan berambut dan menyusui THEN hewan mamalia Rule 2 : IF hewan mempunyai p y sayap y p dan bertelur THEN hewan jenis burung Rule 3 : IF hewan mamalia dan memakan daging THEN hewan karnivora Dst... Materi Kuliah STIKOM Surabaya

9/12/2011

BASIS PENGETAHUAN (KNOWLEDGE BASE) b. Penalaran berbasis kasus (case-based reasoning) ` Pada penalaran berbasis kasus, kasus basis pengetahuan akan berisi solusi-solusi yang telah dicapai sebelumnya, kemudian akan diturunkan suatu solusi untuk keadaan yang terjadi sekarang (fakta yang ada).

38


9/12/2011

MESIN INFERENSI (INFERENCE ENGINE) Ada 2 cara penalaran yang dapat dikerjakan dalam melakukan inferensi : ` a. Forward Chaining Pencocokan fakta atau pernyataan dimulai dari bagian sebelah kiri dulu (IF dulu). Dengan kata lain penalaran dimulai dari fakta terlebih dahulu g j kebenaran hipotesis. untuk menguji ` b. Backward Chaining Pencocokan fakta atau pernyataan dimulai dari bagian g sebelah kanan ((THEN dulu). ) Dengan g kata lain penalaran dimulai dari hipotesis terlebih dahulu, dan untuk menguji kebenaran hipotesis tersebut harus dicari fakta-fakta yang ada dalam b i pengetahuan. basis t h 39


9/12/2011

40


9/12/2011

JENIS KERUSAKAN A1 = MONITOR RUSAK A2 = MEMORI RUSAK A3 = HDD RUSAK A4 = VGA RUSAK A5 = SOUND CARD RUSAK A6 = OS BERMASALAH A7 = APLIKASI RUSAK A8 = PSU RUSAK A9 = PROSESOR RUSAK A10 = MEMORY KURANG (PERLU UPGRADE MEMORY) A11 = MEMORY VGA KURANG ((PERLU UPGRADE VGA)) A12 = CLOCK PROSOR KURANG TINGGI (PERLU UPGRADE PROSESOR) A13 = KABEL IDE RUSAK A14 = KURANG DAYA PADA PSU (PERLU UPGRADE PSU) A15 = PERANGKAT USB RUSAK A16 = KEYBOARD RUSAK A17 = MOUSE RUSAK

41


9/12/2011

42


9/12/2011

Heuristic Searching

43


9/12/2011

Heuristic Searching ` ` ` ` `

Penyelesaian masalah yang tidak menggunakan metode komputasi konvensional Harus ditemukan teknik baru yang digunakan manusia utk menyelesaikan masalah Salah satu metode tersebut adalah metode searching Metode searching pada AI merupakan searching terhadap problem space bukan searching data Menggambarkan keadaan awal masalah menuju penyelesaian masalah yang diinginkan.

44


9/12/2011

Contoh representasi problem space : Masalah komputer

45


9/12/2011

Heuristic Searching ` ` ` ` ` `

Depth-First Search Breadth-first Search Hill-Climbing Search Branch and Bound Search Best-first Search A* Search A

46


9/12/2011

Depth First Search `

` `

` `

Proses searching sistematis buta yang melakukan ekpansi sebuah path menuju penyelesaian masalah sebelum melakukan explorasi terhadap path yang lain. lain Proses searching mengikuti sebuah path tunggal sampai menemukan goal atau dead end A bil proses searching Apabila hi menemukan k dead d d end, d DFS akan melakukan penelusuran balik ke node terakhir utk melihat apakah node tsb memiliki cabang yg belum diekplorasi. diekplorasi Apabila cabang ditemukan, DFS akan melakukan cabang tersebut. Apabila tdk ada lagi cabang yg dpt diekplorasi, diekplorasi DFS akan kembali ke node parent dan melakukan proses seaching terhadap cabang yg belum di ekplorasi dari node parent sampai menemukan penyelesaian masalah 47


9/12/2011

Bagan dan Contoh DFS

Contoh DFS : youtube t b 48


9/12/2011

Breadth First Search `

`

Melakukan proses searching pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses searching pada level berikutnya. Contoh BFS `

49

youtube


9/12/2011

Hill-Climbing Search ` `

`

`

50

Metoda Hill-climbing merupakan variasi dari depth-first search. Dengan metoda ini, eksplorasi terhadap keputusan dilakukan dengan cara depth-first search dengan mencari path yang bertujuan menurunkan cost untuk menuju j kkepada d goal/keputusan. l/k t Sebagai contoh kita mencari arah menuju Tugu Monas, setiap kali sampai dipersimpangan jalan kita berhenti dan mencari arah mana yang kira kira-kira kira akan mengurangi jarak menuju Tugu Monas, Dengan cara demikian sebetulnya kita berasumsi bahwa secara umum arah tertentu semakin dekat ke Tugu Monas.


9/12/2011

Hill Climbing g `

51

Terdapat dua jenis HC yang sedikit berbeda, yakni : y 1.

Simple HC (HC Sederhana) • Algoritma akan berhenti kalau mencapai nilai optimum lokal • Urutan U t penggunaan operator t akan k sangatt berpengaruh b h pada penemuan solusi. • Tidak diijinkan untuk melihat satupun langkah selanjutnya. j y

2.

Steepest-Ascent HC (HC dengan memilih kemiringan yang paling tajam / curam) • Hampir sama dengan Simple HC, HC hanya saja gerakan pencarian tidak dimulai dari paling kiri. Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik.


9/12/2011

HEURISTIC / INFORMED SEARCH Studi Kasus : Game 8-puzzle p

Terdapat 4 operator yang dapat kita gunakan untuk menggerakkan dari satu keadaan ke keadaan yang baru. o o o o

kosong kosong kosong k kosong

2 8

3 4 5

Keadaan Awal

1 7 6 9/12/2011

Ubin Ubin Ubin Ubi Ubin

digeser digeser digeser di s digeser

ke ke ke k ke

kiri kanan atas b bawah h

1 8 7

Tujuan

2 6


3 4 5 52

HEURISTIC / INFORMED SEARCH

Informasi khusus yang dapat diberikan antara lain : 1.

2.

3.

9/12/2011

Untuk jumlah ubin yang menempati posisi yang BENAR : jumlah yang lebih TINGGI adalah yang lebih diharapkan (lebih baik). baik) Untuk jumlah ubin yang menempati posisi yang SALAH : jumlah yang lebih KECIL adalah yang lebih diharapkan (lebih baik). baik) Menghitung TOTAL GERAKAN yang diperlukan untuk mencapai tujuan: jumlah yang lebih KECIL adalah yang lebih diharapkan (lebih baik) baik).


53

HEURISTIC / INFORMED SEARCH - Simple Hill Climbing Keadaan Awal

1

2

3

1

7

8

4

8

5

7

6

kiri

Tujuan

kanan

2

3

1

2

3

1

7

8

4

7

8

4

7

6

5

6

5

4 6

5

2

3 4

8

5

H b= 5

atas

1

2

3

7

8

4

6

6

H b= 4

kanan

3

atas

1

H b= 6

2

5 H9/12/2011 b= 5

1

7

2

3

8

4

6

5

H b= 7


54

HEURISTIC / INFORMED SEARCH - Simple Hill Climbing atas

1

7

2

3

8

4

6

5

H b= 7 kanan

1

2

8 7

6

atas

3

bawah

2

3

1

2

3

7

8

4

6

5

4

1

8

4

5

7

6

5

H b= 8

H b= 6

H b= 6

Jadi urutan penyelesaian game 8-puzzle diatas dengan menggunakan metode Simple Hill Climbing dan menghitung nilai heuristik berupa jumlah ubin yang menempati posisi yang BENAR adalah ubin kosong bergeser ke KIRI, ATA ATAS, KANAN dengan d nilai il i heuristik h i ik terakhir khi adalah d l h 8. 8 9/12/2011


55

HEURISTIC / INFORMED SEARCH - Steepest Steepest-Ascent Ascent Hill Climbing Keadaan Awal

1

2

3

1

7

8

4

8

5

7

6

kiri

Tujuan

kanan

2

3

1

2

3

1

7

8

4

7

8

4

7

6

5

6

5

4 6

5

2

3 4

8

5

H b= 5

atas

1

2

3

7

8

4

6

6

H b= 4

kanan

3

atas

1

H b= 6

2

5 H9/12/2011 b= 5

1

7

2

3

8

4

6

5

H b= 7


56

HEURISTIC / INFORMED SEARCH - Steepest Steepest-Ascent Ascent Hill Climbing atas

1

7

2

3

8

4

6

5

H b= 7 kanan

1

2

8 7

6

atas

3

bawah

2

3

1

2

3

7

8

4

6

5

4

1

8

4

5

7

6

5

H b= 8

H b= 6

H b= 6

Jadi urutan penyelesaian game 8-puzzle diatas dengan menggunakan metode SteepestSteepest -Ascent Hill Climbing dan menghitung nilai heuristik berupa jumlah ubin yang menempati posisi yang BENAR adalah ubin kosong b bergeser k KIRI, ke KIRI ATAS, ATA KANAN dengan d nilai il i heuristik h i ik terakhir khi adalah d l h 8. 9/12/2011


57

Branch and Bound Search `

58

Perhatikan Gambar di bawah ini. Bagaimana menggunakan metoda branch and bound untuk mencari terpendek dari kota Semarang menuju kota Probolinggo?


9/12/2011

59


9/12/2011

60


9/12/2011

A* Search ` ` `

61

A* Search merupakan gabungan antara bestfi t dan first d b branch h and db bound d search. h Misalkan kita memberikan estimasi setiap node terhadap solusi yang diinginkan diinginkan. Maka proses searching untuk mencari jarak terpendek dilakukan dengan melakukan komputasi terhadap total estimasi:


9/12/2011

Best-First Search `

`

62

Best-First Search melakukan proses searching dengan cara memberikan estimasi berapa jauh node asal dari solusi yang diinginkan diinginkan. Dengan metoda ini, proses dilakukan dengan melakukan ekspansi p terhadap p setiap p node yyang g memiliki estimasi terpendek.


9/12/2011

63


9/12/2011

`

Perhatikan diagram jaringan kota pada Gambar Branch and Bound p Search yang sudah dilengkapi dengan estimasi setiap kota menuju node tujuan (probilinggo) seperti ditunjukkan dalam tabel estimasi jarak ini:

64


9/12/2011

65


9/12/2011

66


9/12/2011

Tugas: 8-Puzzle Diberikan konfigurasi awal 8 numbered tiles on a 3 x 3 board, move the tiles in such a way so as to produce d a desired d i d goall configuration fi ti off the th tiles. til

67


9/12/2011

Best First Search

`

`

`

Metode M t d b bestt fifirstt search h merupakan k kkombinasi bi id darii metode t d depth first search dan breadth first search dengan mengambil kelebihan dari kedua metode tersebut. Hill climbing li bi tid tidak k di diperbolehkan b l hk untuk t k kkembali b li kke node d pada d lebih rendah meskipun node tersebut memiliki nilai heuristik lebih baik. P d best Pada b t first fi t search, h pencarian i diperbolehkan di b l hk mengunjungi j i node di lebih rendah, jika ternyata node di level lebih tinggi memiliki nilai heuristik lebih buruk.

68


9/12/2011

`

Untuk mengimplementasikan metode ini, dibutuhkan 2 antrian yang berisi node-node, yaitu : ` OPEN : berisi node-node node node yang sudah dibangkitkan dibangkitkan, sudah memiliki fungsi heuristik namun belum diuji. Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan g nilai heuristik tertinggi. gg ` CLOSED : berisi node-node yang sudah diuji

69


9/12/2011

A A* Perbaikan dari best-first search dengan memodifikasi fungsi heuristiknya. ` Meminimumkan total biaya lintasan lintasan. ` Fungsi f’ sebagai estimasi fungsi evaluasi terhadap node n: f’(n) = g(n) + h(n) dimana: f’(n) = fungsi evaluasi yang sebenarnya terhadap node n g(n) = Biaya yang di keluarkan dari keadaan awal sampai node n h(n) = Estimasi biaya dari node n sampai tujuan `

70


9/12/2011

Sistem Pakar. Pertemuan-1 : Konsep Dasar

Recommend Documents