IF1526 Sistem Berbasis Pengetahuan (Knowledge-Based System)

IF1526 Sistem Berbasis Pengetahuan (Knowledge-Based System)

Disusun Oleh:

Irfan Subakti

Jurusan Teknik Informatika Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya 2002

KATA PENGANTAR Kuliah Sistem Berbasis Pengetahuan di Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS), ini diberikan sebagai salah satu Mata Kuliah Pilihan yang termasuk dalam bidang minat Sistem Informasi yang memiliki bobot 3 SKS (Satuan Kredit Semester). Tujuan yang ingin didapat dari Mata Kuliah ini adalah untuk merancang/menerapkan Sistem Berbasis Pengetahuan dengan merangkai tiga komponen pokok: inference engine, basis data, dan production rules. Materi yang dibahas adalah: Sistem-sistem yang ada dalam Management Support System (MSS), penggunaan kecerdasan buatan, Sistem Pakar, akuisisi dan validasi pengetahuan, Sistem Pakar Berbasis Pengetahuan, dan Algoritma Genetika. Tak ada gading yang tak retak, demikian jugalah dalam penyusunan Buku Panduan ini. Kami mohon maaf bila ada kekurangan. Semoga Tuhan Yang Maha Pengasih memberikan segala kurnia-Nya kepada kita dalam segenap langkah-langkah kita ini. Amiin. Penyusun

[email protected]

ii

Sistem Berbasis Pengetahuan – Irfan Subakti

DAFTAR ISI Halaman KATA PENGANTAR ................................................................................................................ii DAFTAR ISI ......................................................................................................................... iii TUJUAN INSTRUKSIONAL UMUM........................................................................................... vi MATERI ............................................................................................................................ vi PRASYARAT MATA KULIAH ................................................................................................... vi BAB 1 MANAGEMENT SUPPORT SYSTEM (MSS).................................................................. 1 1.1. Manajer dan Dukungan Komputer............................................................................ 1 1.2. Managerial Decision Making & Management Information Systems (MIS)...................... 1 1.3. Kerangka Kerja Decision Support (DS). .................................................................... 1 1.4. Decision Support Systems (DSS).............................................................................. 2 1.5. Group Support Systems (GSS). ................................................................................ 2 1.6. Executive Information (atau Support) Systems (EIS atau ESS). .................................. 3 1.7. Expert Systems (ES). .............................................................................................. 3 1.8. Neural Computing (Artificial Neural Network). ........................................................... 3 1.9. Evolusi dari Alat Pengambil Keputusan Terkomputerisasi............................................ 3 1.10. Pelbagai Perbedaan diantara MIS dan DSS. .............................................................. 5 1.11. Hubungan antara Decision Support-Expert System. ................................................... 5 1.12. Dukungan dari Pengambilan Keputusan.................................................................... 6 1.13. Hybrid Support Systems.......................................................................................... 7 1.14. Computer-Based Information Systems di Departemen Personalia................................ 7 1.15. Kesimpulan. ........................................................................................................... 8 BAB 2 PENGGUNAAN ARTIFICIAL INTELLIGENCE (AI) ........................................................ 9 2.1. Definisi. ................................................................................................................. 9 3 tujuan yang diinginkan AI: ............................................................................................. 9 Beberapa kemampuan yang merupakan tanda dari kecerdasan:........................................... 9 Symbolic Processing. ........................................................................................................ 9 Heuristics. ......................................................................................................................10 Inferencing.....................................................................................................................10 Pengenalan Pola. ............................................................................................................10 2.2. AI Dibandingkan dengan Natural Intelligence...........................................................10 2.3. Knowledge pada AI. ..............................................................................................10 Data. ...........................................................................................................................10 Information. ...................................................................................................................10 Knowledge. ....................................................................................................................10 Penggunaan Knowledge...................................................................................................11 Basis-basis pengetahuan dan organisasi berbasis pengetahuan. ..........................................11 2.4. Bagaimana AI Berbeda dengan Komputasi Konvensional...........................................11 2.5. Bidang AI. ............................................................................................................12 Expert System. ...............................................................................................................13 Natural Language Processing. ..........................................................................................14 2.6. Kesimpulan. ..........................................................................................................14 BAB 3 EXPERT SYSTEM ...................................................................................................15 3.1. Konsep Dasar ES. ..................................................................................................15 Expertise/Kepakaran........................................................................................................15 Expert/Pakar...................................................................................................................15 Fakta mengenai Kepakaran. .............................................................................................15 Inferencing.....................................................................................................................16 Rules. ...........................................................................................................................16 Kemampuan Menjelaskan. ...............................................................................................16 3.2. Struktur ES. ..........................................................................................................17 Inference Engine.............................................................................................................17 Explanation Subsystem (Justifier). ....................................................................................17 Knowledge Refining System. ............................................................................................18 3.3. Elemen Manusia dalam ES......................................................................................18 3.4. Bagaimana ES Dibangun. .......................................................................................18 3.5. Bidang Permasalahan yang Ditangani ES. ................................................................18 3.6. Keuntungan ES .....................................................................................................18 3.7. Permasalahan dan Keterbatasan ES. .......................................................................19 iii


3.8. Jenis ES................................................................................................................19 3.9. Pengembangan ES. ...............................................................................................20 3.10. Kesimpulan. ..........................................................................................................25 BAB 4 AKUISISI DAN VALIDASI KNOWLEDGE ...................................................................27 4.1. Rekayasa Knowledge. ............................................................................................27 Proses Rekayasa Knowledge. ...........................................................................................27 4.2. Skup Knowledge....................................................................................................27 Sumber Knowledge. ........................................................................................................27 Akuisisi dari Database......................................................................................................28 Level Knowledge. ............................................................................................................28 Kategori Knowledge. .......................................................................................................28 4.3. Kesulitan dalam Akuisisi Knowledge. .......................................................................28 Masalah-masalah dalam transfer knowledge. .....................................................................28 Mengatasi Pelbagai Kesulitan. ..........................................................................................29 Ketrampilan yang dibutuhkan oleh Knowledge Engineer: ....................................................29 4.4. Metode Akuisisi Knowledge: Pendahuluan................................................................29 4.5. Wawancara...........................................................................................................30 Wawancara Tak Terstruktur. ............................................................................................30 Wawancara Terstruktur. ..................................................................................................31 4.6. Metode Pelacakan. ................................................................................................31 Prosedur Analisis Protokol:...............................................................................................31 Keuntungan dan Keterbatasan Analisis Protokol. ................................................................31 4.7. Pengamatan dan Metode Manual Lainnya. ...............................................................32 Pengamatan (observasi). .................................................................................................32 Pelbagai metode manual lainnnya: ...................................................................................32 4.8. Metode Expert-driven. ...........................................................................................32 Metode manual: laporan oleh sang pakar itu sendiri...........................................................32 Pendekatan bantuan komputer.........................................................................................33 4.9. Repertory Grid Analysis..........................................................................................33 Cara kerja RGA. ..............................................................................................................33 Penggunaan RGA dalam ES..............................................................................................33 4.10. Dukungan Knowledge Engineer. .............................................................................34 Alat bantu akusisi knowledge. ..........................................................................................34 Alat bantu akuisisi knowledge terintegrasi. ........................................................................34 Front-end Tools. .............................................................................................................34 4.11. Induksi Rule, Case-based Reasoning, dan Komputasi Syaraf. ....................................34 Induksi Rule Otomatis. ....................................................................................................35 Keuntungan dari induksi rule............................................................................................35 Kesulitan dalam implementasi. .........................................................................................36 Induksi interaktif. ............................................................................................................36 Case-based reasoning......................................................................................................36 Komputasi Syaraf. ...........................................................................................................36 4.12. Memilih Metode yang Sesuai. .................................................................................36 4.13. Akuisisi Knowledge dari Banyak Pakar. ....................................................................37 Skenario dari banyaknya pakar yang terlibat......................................................................37 Metode penanganan banyak pakar. ..................................................................................37 4.14. Validasi dan Verifikasi Knowledge Base....................................................................37 4.15. Analisis, Kodifikasi, Dokumentasi, dan Pendiagraman. ..............................................38 4.16. Akuisisi Knowledge Numerik dan Terdokumentasi. ...................................................38 Akuisisi knowledge numerik. ............................................................................................38 Akuisisi knowledge terdokumentasi...................................................................................38 4.17. Kesimpulan. ..........................................................................................................39 BAB 5 KNOWLEDGE-BASED EXPERT SYSTEMS ..................................................................40 5.1. Pengertian. ...........................................................................................................40 5.2. Rules dan Rule Chaining. .......................................................................................40 5.3. Forward dan Backward Chaining.............................................................................41 Forward Chaining. ...........................................................................................................41 Backward chaining. .........................................................................................................42 Mana yang dipilih, forward ataukah backward chaining? .....................................................42 Tipe sistem yang dapat dicari dengan forward chaining:.....................................................42 Tipe sistem yang dapat dicari dengan backward chaining: ..................................................42 5.4. Desain Implementasi Forward dan Backward Chaining..............................................43 iv


Forward chaining. ...........................................................................................................43 Backward chaining. .........................................................................................................43 Contoh struktur data dalam program. ...............................................................................48 Contoh Kasus..................................................................................................................49 Kasus 1. Forward Chaining...............................................................................................49 Kasus 2. Backward Chaining.............................................................................................52 5.5. Confidence Factor (CF) pada Forward dan Backward Chaining...................................57 CF untuk rule dengan kondisi AND....................................................................................57 CF untuk rule dengan kondisi OR......................................................................................57 CF untuk rule dengan kondisi AND/OR. .............................................................................57 5.6. Pengembangan Program Forward dan Backward Chaining. .......................................58 Pembagian Rule. .............................................................................................................58 Implementasi Pengembangan Program. ............................................................................59 BAB 6 ALGORITMA GENETIKA .........................................................................................61 6.1. Pendahuluan.........................................................................................................61 Struktur Umum Algoritma Genetika...................................................................................61 Eksploitasi dan Eksplorasi. ...............................................................................................62 Pencarian berdasarkan populasi. ......................................................................................62 Meta-heuristic.................................................................................................................63 Keuntungan Utama. ........................................................................................................63 Kamus GA. .....................................................................................................................63 6.2. Contoh Program Algoritma Genetika Sederhana (Simple Genetic Algorithm) ...............63 Masalah Optimasi............................................................................................................63 DAFTAR PUSTAKA...............................................................................................................67 TENTANG PENULIS .............................................................................................................68

v


TUJUAN INSTRUKSIONAL UMUM

Merancang/menerapkan Sistem Berbasis Pengetahuan dengan merangkai tiga komponen pokok: inference engine, basisdata, dan production rules.

MATERI

Sistem-sistem yang ada dalam Management Support System (MSS). Penggunaan kecerdasan buatan. Sistem Pakar. Akuisisi dan validasi pengetahuan. Sistem Pakar Berbasis Pengetahuan. Algoritma Genetika.

PRASYARAT MATA KULIAH

IF1408 IF1504

Sistem Informasi Kecerdasan Buatan

vi


Bab 1 Management Support Sistem (MSS)

BAB 1 MANAGEMENT SUPPORT SYSTEM (MSS) 1.1. 1. 2. 3. 4. 5. 6.

1.2.

Manajer dan Dukungan Komputer.

Teknologi komputer sekarang ini merupakan bagian terpenting dalam dunia bisnis, dan jelas dalam pelbagai bidang lainnya. MSS terdiri dari: Decision Support Systems (DSS). Group Support Systems (GSS), termasuk Group DSS (GDSS). Executive Information Systems (EIS). Expert Systems (ES). Artificial Neural Networks (ANN). Hybrid Support Systems.

Managerial Decision Systems (MIS).

Making

&

Management

Information

Manajemen adalah proses pencapaian tujuan organisasi melalui penggunaan resources (manusia, uang, energi, material, ruang, dan waktu). Resources sebagai input, sedangkan pencapaian tujuan adalah outputnya. Kesuksesan suatu organisasi dan kesuksesan tugas seorang manajer diukur dari produktivitas. Output ( produk , jasa ) Produktivitas = Input (resources) Faktor-faktor yang mempengaruhi pengambilan keputusan: Faktor Tren Hasil Teknologi. Meningkat. Lebih banyak alternatif pilihan. Informasi/Komputer. Meningkat. Kompleksitas struktural. Meningkat. Biaya yang lebih besar dari kesalahan Kompetisi. Meningkat. yang terjadi. Ketidakpastian berkaitan dengan masa Meningkat. Pasar Internasional. depan. Menurun. Stabilitas politik. Meningkat. Konsumerisme. Meningkat. Intervensi Pemerintah. Kecepatan perubahan luar biasa besarnya. Pendekatan manajemen trial and error menjadi lebih sulit. Manajer harus lebih canggih, harus belajar bagaimana menggunakan tool dan teknik-teknik baru yang selalu berkembang di bidangnya masing-masing. Teknik-teknik yang dipakai ini banyak yang memakai pendekatan analisis kuantitatif, dikelompokkan dalam 1 disiplin, disebut dengan Management Science (Operation Research).

1.3. Tipe Keputusan Terstruktur

Kerangka Kerja Decision Support (DS). Kontrol Operasional Account receivable, order entry

Semi terstruktur

Production schedulling, inventory control

Tak terstruktur

Selecting a cover for a magazine, buying software, approving loans MIS, management science

Dukungan yang diperlukan

Tipe Kontrol Kontrol Manajerial Perencanaan Strategis Budget analysis, short-term forecasting, personnel reports, make-or-buy Credit evaluation, budget preparation, plant layout, project schedulling, reward systems design Negotiating, recruiting an executive, buying hardware, lobbying Management science, DSS, ES, EIS 1

Financial management (investment), warehouse location, distribution systems Building new plant, mergers and acquisitions, new product planning, compensation planning, quality assurance planning R & D planning, new technology development, social responsibility planning EIS, ES, neural networks

Dukungan yang dibutuhkan MIS, operational research models, transaction processing DSS

DSS, ES, networks


neural


Proses pengambilan keputusan terdiri dari 3 fase proses: intelligence, design, dan choice. Intelligence – pencarian kondisi-kondisi yang dapat menghasilkan keputusan. Design – menemukan, mengembangkan, dan menganalisis materi-materi yang mungkin untuk dikerjakan. Choice – pemilihan dari materi-materi yang tersedia, mana yang akan dikerjakan. Proses-proses yang terjadi pada kerangka kerja DS dibedakan atas: Terstruktur, mengacu pada permasalahan rutin dan berulang untuk solusi standar yang ada. Tak terstruktur, adalah “fuzzy”, permasalahan kompleks dimana tak ada solusi serta merta. Masalah yang tak terstruktur adalah tak adanya 3 fase proses yang terstruktur. Semi terstruktur, terdapat beberapa keputusan terstruktur, tetapi tak semuanya dari fasefase yang ada. 1. 2. 3. 4. 5.

Pendekatan Management Science mengadopsi pandangan seorang manajer yang dapat mengikuti proses yang sistematik untuk penyelesaian masalah. Sehingga adalah mungkin untuk menggunakan pendekatan sains pada Managerial Decision Making. Langkahnya adalah: Definisi masalah (keputusan situasi yang berhubungan dengan pelbagai masalah atau dengan suatu kesempatan) Klasifikasi masalah ke dalam kategori standar. Membuat model matematika yang menjelaskan masalah secara nyata. Menemukan solusi potensial di model masalah tadi dan mengevaluasinya. Memilih dan merekomendasikan satu solusi dari masalah. Proses ini dipusatkan pada masalah modeling/pemodelan.

1.4.

Decision Support Systems (DSS).

Sistem berbasis komputer yang interaktif, yang membantu pengambil keputusan memanfaatkan data dan model untuk menyelesaikan masalah-masalah yang tak terstruktur. DSS mendayagunakan resources individu-individu secara intelek dengan kemampuan komputer untuk meningkatkan kualitas keputusan. Jadi ini merupakan sistem pendukung yang berbasis komputer untuk manajemen pengambilan keputusan yang berhubungan dengan masalahmasalah yang semi terstruktur. Istilah DSS kadang digunakan untuk menggambarkan sembarang sistem yang terkomputerisasi. DSS digunakan untuk definisi yang lebih sempit, dan digunakan istilah MSS sebagai payung untuk menggambarkan pelbagai tipe sistem pendukung.

Mengapa menggunakan DSS? Perusahaan beroperasi pada ekonomi yang tak stabil. Perusahaan dihadapkan pada kompetisi dalam dan luar negeri yang meningkat. Perusahaan menghadapi peningkatan kesulitan dalam hal melacak jumlah operasi-operasi bisnis. Sistem komputer perusahaan tak mendukung peningkatan tujuan perusahaan dalam hal efisiensi, profitabilitas, dan mencari jalan masuk di pasar yang benar-benar menguntungkan. 6 alasan mengapa perusahaan-perusahaan utama memulai DSS dalam skala besar: Kebutuhan akan informasi yang akurat. DSS dipandang sebagai pemenang secara organisasi. Kebutuhan akan informasi baru. Manajemen diamanahi DSS. Penyediaan informasi yang tepat waktu. Pencapaian pengurangan biaya. Alasan lain dalam pengembangan DSS adalah perubahan perilaku komputasai end-user. End-user bukanlah programer, sehingga mereka membutuhkan tool dan prosedur yang mudah untuk digunakan. Dan ini dipenuhi oleh DSS.

1.5.

Group Support Systems (GSS).

Pelbagai keputusan utama dalam organisasi dibuat oleh group secara kolektif. Mengumpulkan keseluruhan group secara bersama dalam satu tempat dan waktu adalah sulit dan mahal, sehingga pertemuan ini memakan waktu lama dan keputusan yang dibuat hasilnya sedang-sedang saja, tak terlalu baik.


2


Peningkatan kinerja group-group tadi yang dibantu oleh teknologi Informasi ini muncul dalam pelbagai istilah, seperti: groupware, electronic meeting systems, collaborative systems, dan group DSS (ini yang kita gunakan). Satu contoh dari implementasi group DSS ini adalah Total Quality Management (TQM).

1.6.

Executive Information (atau Support) Systems (EIS atau ESS).

1.7.

Expert Systems (ES).

EIS dikembangkan utamanya untuk: Menyediakan kebutuhan informasi yang diperlukan oleh pihak Eksekutif. Menyediakan antarmuka yang benar-benar user-friendly untuk Eksekutif. Mempertemukan pelbagai gaya keputusan individu para Eksekutif. Menyediakan pelacakan dan kontrol yang tepat waktu dan efektif. Menyediakan akses cepat pada informasi detil yang tersirat di teks, bilangan, atau grafik. Memfilter, memadatkan, dan melacak data dan informasi yang kritis. Identifikasi masalah (atau juga kesempatan). EIS bisa juga digunakan pada pelbagai jenis perusahaan dan melayani sejumlah manajer sebagai suatu Enterprise Wide Systems (EWS).

Semakin tak terstruktur suatu situasi, maka solusinya akan lebih spesifik. ES dibuat untuk menyerupai seorang pakar/ahli. ES adalah paket hardware dan software yang digunakan sebagai pengambil keputusan dan/atau pemecahan masalah; yang dapat mencapai level yang setara atau kadang malah melebihi seorang pakar/ahli, pada satu area masalah yang spesifik dan biasanya lebih sempit. Merupakan cabang dari aplikasi Artificial Intelligence (AI). Ide dasarnya sederhana. Kepakaran ditransfer dari seorang pakar ke komputer. Pengetahuan ini lalu disimpan disitu dan user dapat meminta saran spesifik yang dibutuhkannya. Komputer dapat mencari, mengolah dan menampilkan kesimpulan yang spesifik. Dan seperti seorang pakar, saran tersebut bisa dimanfaatkan oleh orang yang bukan pakar berikut penjelasannya yang berisi logika penalaran di balik saran itu.

1.8.

Neural Computing (Artificial Neural Network).

Teknologi sebelum Artificial Neural Network (ANN) berbasis pada penggunaan data, informasi, ataupun pengetahuan eksplisit yang tersimpan di komputer dan memanipulasi mereka menurut kebutuhan. Pada dunia nyata yang begitu kompleks, mungkin tak bisa didapatkan data, informasi, ataupun pengetahuan secara eksplisit, sedangkan keputusan harus diambil walaupun kondisinya seperti ini (informasi yang parsial, tak lengkap, atau pun tak eksak). Perubahan lingkungan yang terjadi sedemikian cepatnya. Pengambil keputusan menggunakan pengalaman yang ada untuk mengatasi hal ini; yaitu menggunakan pengalaman yang bersesuaian dan belajar dari pengalaman itu tentang apa yang harus dikerjakan dengan situasi yang serupa untuk pengalaman yang tak sesuai. Pada teknologi sebelumnya, tak ada elemen untuk proses pembelajaran oleh komputer. Teknologi yang ditujukan untuk mengisi kekurangan ini, disebut dengan Neural Computing atau ANN. Contohnya adalah pengenalan pola.

1.9. Evolusi dari Alat Pengambil Keputusan Terkomputerisasi. Dibagi dalam 7 kategori: 1. Transaction Processing Systems (TPS). 2. Management Information Systems (MIS). 3. Office Automation Systems (OAS). 4. Decision Support Systems (DSS) dan Group DSS (GDSS). 5. Expert Systems (ES). 6. Executive Information Systems (EIS). 7. Artificial Neural Network (ANN).

Berikut ini adalah pelbagai aspek pengambilan keputusan: Description Examples of Tools Compute “crunch numbers”, summarize, Calculators, early computer programs, organize. statistical models, simple management science models. Intermediate Find, organize, and display decision-relevant Database management systems, MIS, filing

Phase Early


3


Phase

Description Examples of Tools information. systems. Management science models. Current Perform decision-relevant computations on Financial models, spreadsheets, trend decision-relevant information; organize and exploration, operations research models, display the results. Query-based and user- CAD systems, DSS. friendly approach. “What-if” analysis. Interact with decision makers to facilitate ES; EIS. formulation and execution of the intellectual steps in the process of decion making. Just beginning Complex and fuzzy decisions situations, Second generation of ES, GDSS, neural expanding to collaborative decision making and computing. to machine learning. Evolusi dari MSS dan hubungannya dengan sistem yang lain umumnya dipandang sebagai: rekomendasi dan saran yang disediakan oleh MSS ke manajer dapat dipertimbangkan sebagai informasi yang diperlukan untuk keputusan akhir yang akan dibuat. Pendekatan ini berarti bahwa MSS dipandang canggih, jenis sistem informasi tingkat tinggi yang dapat ditambahkan pada sistem TPS tradisional, OAS, MIS. Hubungan antara TPS, MIS, DSS, EIS, dan ES dan teknologi-teknologi yang lain: Pelbagai teknologi ini dapat dipandang sebagai klas yang unik dari teknologi informasi. Mereka saling berhubungan, dan mereka saling mendukung satu sama lain dalam pelbagai manajemen pengambilan keputusan. Evolusi dan pembuatan tool-tool yang lebih baru membantu kinerja pengembangan teknologi informasi untuk kebaikan manajemen dalam organisasi. Keterkaitan dan koordinasi diantara tool-tool ini masih berevolusi. Atribut dari sistem pendukung terkomputerisasi Dimension Transactions Management Processing Information Systems (TPS) Systems (MIS) Production control, Applications Payroll, inventory, record sales forecasting, monitoring keeping, production and sales information Focus Data transactions Information

utama: Decision Support Systems (DSS) Long-range strategic planning, complex integrated problem areas Decisions, flexibility, user friendliness Database management systems, interactive access, factual knowledge Semistructured problems, integrated management science models, blend of judgment and modeling Numerical

Expert (ES)

System

Diagnosis strategic planning, internal control planning, strategies Inferencing, transfer of expertise Procedural and factual knowledge; knowledge base (facts, rules) The system makes complex decisions, unstructured; use of rules (heuristics)

Database

Unique to each application, batch update

Interactive access by programmers

Decision capabilities

No decisions

Structured routing problems using conventional management science tools

Manipulation

Numerical

Numerical

Type of information

Summary reports, operational

Information to support specific decisions

Advice explanations

and

Highest organizational level served Impetus

Submanagerial, low management

Scheduled and demand reports, structured flow, exception reporting Middle management

Analysts managers

Managers specialists

and

Expediency

Efficiency

Effectiveness

and

Symbolic

Effectiveness and expediency

Executive Information Systems (EIS) Support to top management decision, environmental scanning Tracking, control, “Drill down” External (online) and corporate, enterprise wide access (to all data bases) Only when combined with a DSS

Numeric (mainly); some symbolic Status access, exception reporting, key indicators Senior executives (only) Timeliness


4


1.10. Pelbagai Perbedaan diantara MIS dan DSS. Fitur dari DSS: DSS dapat digunakan untuk mengawali kerja ad hoc, masalah-masalah yang tak diharapkan. DSS dapat menyediakan representasi valid dari sistem di dunia nyata. DSS dapat menyediakan pendukungan keputusan dalam kerangka waktu yang pendek/terbatas. DSS dapat berevolusi sebagai mana halnya pengambil keputusan mempelajari tentang masalah-masalah yang dihadapinya. DSS dapat dikembangkan oleh para profesional yang tak melibatkan pemrosesan data. Karakteristik MIS: Kajiannya ada pada tugas-tugasnya yang terstruktur, dimana prosedur operasi standar, aturanaturan keputusan, dan alur informasi dapat didefinisikan Hasil utamanya adalah meningkatkan efisiensi dengan mengurangi biaya, waktu tunggu, dan lain-lain, dan dengan mengganti karyawan klerikal. Relevansinya untuk manajer pengambil keputusan biasanya tak langsung didapatkan; misalnya dengan penyediaan laporan dan akses ke data. Karakteristik Operation Research/Management Science: Kajiannya ada pada masalah-masalah yang terstruktur (dibandingkan dengan tugas-tugas), dimana tujuan, data, dan batasan-batasan dapat lebih dulu ditentukan. Hasil utamanya adalah dalam menghasilkan solusi yang lebih baik untuk masalah-masalah tertentu. Relevansinya untuk manajer ada pada rekomendasi detil dan metodologi baru untuk menangani masalah-masalah yang kompleks. Karakteristik DSS: Kajiannya ada pada keputusan-keputusan dimana ada struktur yang cukup untuk komputer dan alat bantu analitis yang memiliki nilai tersendiri, tetapi tetap pertimbangan manajer memiliki esensi utama. Hasil utamanya adalah dalam peningkatan jangkauan dan kemampuan dari proses pengambilan keputusan para manajer untuk membantu mereka meningkatkan efektivitasnya. Relevansinya untuk manajer adalah dalam pembuatan tool pendukung, di bawah pengawasan mereka, yang tak dimaksudkan untuk mengotomatiskan proses pengambilan keputusan, tujuan sistem, atau solusi tertentu. Relasi antara EDP, MIS, and DSS:

Strategic Planning

DSS

Managerial Control

MIS

Operational Control EDP Transaction Processing

1.11.

Hubungan antara Decision Support-Expert System.

DSS dan ES berbeda dan tak berhubungan dengan sistem yang terkomputerisasi. Disiplin antara ES dan DSS berkembang pararel, tapi saling tak tergantung dan berjalan sendirisendiri. Cuma sekarang kita bisa mencoba menggabungkan potensi dari keduanya. Menurut kenyataannya, disebabkan karena perbedaan kapabilitas diantara kedua tool, mereka dapat mengkomplemen satu sama lain, membuatnya menjadi powerful, terintegrasi, sistem yang berbasis komputer, yang jelas dapat meningkatkan pengambilan keputusan manajerial.


5


1.12.

Dukungan dari Pengambilan Keputusan.

Perbedaan antara DSS dan ES: DSS Objective Assist human decision maker

Who makes the recommendations (decisions)? Major orientation

The human and/or the system

Major query direction Nature of support Manipulation method Characteristics of problem area Type of problems Content of database Reasoning capability Explanation capability

Human queries the machine Personal, groups, and institutional Numerical Complex, integrated wide Ad hoc, unique Factual knowledge No Limited

Decision making

ES Replicate (mimic) human advicers and replace them The system Transfer of expertise (humanmachine-human) and rendering the advice Machine queries the human Personal (mainly), and groups Symbolic Narrow domain Repetitive Procedural and factual knowledge Yes, limited Yes

Proses pengambilan keputusan: 1. Step A. Mengerti masalah (atau kesempatan yang ada). ES dapat membantu dalam mendesain alur informasi pada eksekutif (misalnya, bagaimana untuk memonitor, kapan) dan dalam penginterpretasian informasi. Disebabkan beberapa informasi bersifat fuzzy, maka kombinasi antara ES dan ANN tentu akan membantu. Seluruh area dari proses scanning, monitoring, forecasting (misalnya, tren) dan penginterpretasian sangat dibantu oleh adanya komputerisasi. Demikian juga natural language processors (NLP) akan berguna dalam menyimpulkan informasi. 2. Step B. Analisis. Sekali suatu masalah (kesempatan) teridentifikasi, pertanyaan selanjutnya adalah apa yang harus dikerjakan dengan hal ini? Di sinilah langkah analisis berperanan. Analisis bisa bersifat kualitatif atau pun kuantitatif (atau kombinasinya). Analisis kuantitatif didukung oleh DSS dan oleh tool-tool analisis kuantitatif. Analisis kualitatif didukung oleh ES. 3. Step C. Memilih. Pada langkah ini, keputusan dibuat dengan memperhatikan masalahnya (atau kesempatan) berdasarkan hasil dari analisis. Langkah ini didukung oleh DSS (jika pengambil keputusan adalah seseorang) atau oleh GDSS (jika keputusan dibuat oleh sekelompok orang). 4. Step D. Implementasi. Pada tahap ini, keputusan untuk mengimplementasikan solusi tertentu dilakukan, dan DSS dan/atau ES bisa mendukung tahap ini.

Di bawah ini terlihat dukungan terkomputerisasi untuk proses pengambilan keputusan:


6


Sources of Information and Knowledge

People

Scanning

Newspapers

Problem identification (Definition) (Intelligence)

Decision (Choice)

No

Step D

EIS (ESS)

Step B

Qualitative analysis (Design)

Step C

1.13.

Sensors ES, NLP, ANN EIS, MIS

Step A

ES

TV

Quantitative analysis (Design)

DSS MS/ or ANN

GDSS (Groups) DSS (Individual)

Implement?

Decision (Choice)

DSS and ES

Hybrid Support Systems.

Tujuan dari Computer-Based Information System (CBIS) adalah untuk membantu manajemen dalam memanajemen penyelesaian atau mengorganisasi masalah lebih cepat dan baik daripada tanpa menggunakan komputer. Kata kuncinya adalah solusi yang tepat dari manajemen permasalahan, dan bukannya tool atau teknik yang digunakan dalam proses.

Beberapa pendekatan yang mungkin: Gunakan setiap tool dengan caranya sendiri-sendiri untuk menyelesaikan aspek yang berbeda dari suatu masalah. Gunakan pelbagai tool yang tidak begitu terintegrasi. Gunakan pelbagai tool yang secara kuat terintegrasi. Dalam hal ini tool-tool akan berlaku sebagai sistem hybrid/persilangan ke user, dimana transfer dari data dan aktivitas lain diprogram ke dalam MSS yang terintegrasi.

1.14.

Computer-Based Personalia.

Category Transaction Processing Management Information System Decision Systems

Support

Expert Systems

Information

Systems

di

Departemen

Task Keep inventory of personnel. Prepare payroll; compute salaries and incentive plans. Prepare summary reports (e.g., average salaries in each department). Conduct performance tracking of employees, labor budget. Do preparation, monitoring, and analysis. Perform short-term scheduling. Match positions and candidates. Monitor positions control systems. Do fringe benefits monitoring and control. Prepare special reports (e.g., safety records, equal opportunity achievements). Do long-range planning for human resources. Design a compensation plan. Provide quantitative support of labor-management negotiation. Obtain advice on legal and tax implications during management labor negotiations. Develop a social responsibility plan. Select training media. Design comprehensive training programs. Help in selecting new employees. Sistem Berbasis Pengetahuan – Irfan Subakti

7


Category Office Automation Executive Information System Group DSS Neural Computing

1.15.

Task Do online job interviews and recruiting, schedule meetings, maintain mailing lists, schedule training, use for electronic mail, receive labor news and statistics online, prepare training materials. Exists at the corporate level only. Will measure key performance indicators of the department (such as dollar per employee). Can be used for supporting the process of making controversial major decisions (e.g., personnel policies). Screen applicants for jobs. Analyze reasons why people leave the company (find patterns).

Kesimpulan.

Perkembangan komputer demikian cepatnya dan juga penggunaannya oleh para manajer. MSS adalah keluarga teknologi yang dapat digunakan secara mandiri atau dalam bentuk kombinasinya. Dukungan terkomputerisasi untuk para manajer sangat penting dalam pelbagai kasus untuk kelanjutan organisasinya. Manejemen pengambilan keputusan makin lama makin kompleks. Maka metode intuisi dan trial and error tak tepat lagi. Kerangka dukungan keputusan membagi kondisi keputusan dalam 9 kategori, tergantung pada derajat struktur dan aktivitas manajerial. Setiap kategori mendapat dukungan komputer sendirisendiri. Keputusan yang terstruktur didukung oleh metode analisis kuantitatif seperti: management science dan capital budgeting. DSS adalah teknologi analitis yang menggunakan model untuk solusi yang semi terstruktur dan masalah-masalah tak terstruktur. Group DSS adalah teknologi yang mendukung proses pengambilan keputusan dalam suatu group. EIS adalah teknologi yang mendukung eksekutif dengan menyediakan bagi mereka informasi yang sedia setiap saat, detil, dan mudah untuk divisualisasikan. ES adalah sistem pemberi nasehat yang mencoba menirukan para pakar. Fitur utama dari ES adalah aplikasinya untuk pengetahuan dan penggunaan reasoning (alasan suatu keputusan). Komputasi saraf (neural computing) adalah teknologi yang mencoba menampilkan proses pembelajaran dan pengenalan pola. Semua teknologi MSS adalah interaktif. Keuntungan utama dari MSS adalah ia dapat diukur. Teknologi-teknologi MSS dapat diintegrasikan diantara mereka sendiri dan dengan CBIS yang lain. Teknologi-teknologi MSS dapat diterapkan pada satu lokasi atau mereka dapat didistribusikan di keseluruhan perusahaan.


8

Bab 2 Penggunaan Artificial Intelligence (AI)

BAB 2 PENGGUNAAN ARTIFICIAL INTELLIGENCE (AI) 2.1.

Definisi.

AI didasarkan atas 2 ide dasar. Pertama, ini adalah hal yang berhubungan dengan studi proses berpikir manusia (untuk memahami apakah kecerdasan itu); yang kedua ia berhubungan dengan representasi proses-proses tadi melalui mesin (komputer, robot, dan lain-lain). AI adalah perilaku mesin, yang menampilkan perilaku manusia, yang disebut dengan kecerdasan. AI adalah studi bagaimana membuat komputer melakukan sesuatu hal pada suatu waktu, untuk manusia, secara lebih baik. AI secara dasar adalah teori bagaimana pemikiran manusia bekerja. 3 tujuan yang diinginkan AI: 1. Membuat mesin lebih pintar (tujuan utama). 2. Memahami apakah sebenarnya kecerdasasan itu (tujuan mulianya). 3. Membuat mesin lebih berguna (tujuan di sektor swasta). Beberapa kemampuan yang merupakan tanda dari kecerdasan: Belajar atau mengerti dari pengalaman. Bereaksi terhadap pesan-pesan yang memiliki makna ganda atau berlawanan. Respon sigap dan berhasil atas situasi baru (respon yang berbeda, fleksibelitas). Penggunaan alasan dalam menyelesaikan permasalahan dan memimpinnya dengan cara yang efektif. Berhubungan dengan situasi yang berubah-ubah. Mengerti dan menghasilkan dalam cara yang rasional dan umum digunakan. Menggunakan pengetahuan untuk memanipulasi lingkungan. Berpikir dan memberi alasan. Mengenali elemen-elemen yang secara relatif penting dalam situasi tertentu. Symbolic Processing. Untuk merepresentasikan hal-hal yang ingin diselesaikan dengan AI. AI merepresentasikan pengetahuan sebagai sekumpulan simbol yang berhubungan dengan konsep permasalahannya. Dalam AI, simbol adalah string dari karakter yang mencerminkan konsep dari dunia nyata. Contohnya: Product Defendant 0.8 Simbol ini dapat dikombinasikan untuk mengekspresikan hubungan yang berarti. Jika relasi ini direpresentasikan dalam suatu program AI, maka mereka disebut dengan symbol structures. Contoh: (DEFECTIVE product) (LEASED-BY product defendant) (EQUAL (LIABILITY defendant) 0.8) Struktur ini dapat diinterpretasikan untuk memahami bahwa “the product is defective”, “the product is leased by the defendant”, dan “the liability of the defendant is 0.8”. Tapi bisa juga mereka ini diinterpretasikan dengan yang lain. Dan ini merupakan salah satu masalah jika membangun suatu sistem AI. Untuk menyelesaikan suatu masalah, program AI akan memanipulasi simbol-simbol ini. Konsekuensinya adalah representasi pengetahuan – pemilihan, bentuk, dan interpretasi dari simbol yang digunakan – menjadi sangat penting. Symbolic processing adalah karakteristik penting dari AI yang merefleksikan definisi berikut ini: AI adalah cabang dari computer science yang berhubungan dengan symbolic, nonalgorithmic method dari penyelesaian suatu masalah. 1. Numeric vs. symbolic. Komputer didesain untuk memproses bilangan, sedangkan manusia lebih cenderung berpikir secara simbolik. Walaupun tak diartikan bahwa AI tak melibatkan matematika, AI ditekankan pada manipulasi simbol. 2. Algorithmic vs. nonalgorithmic. Algoritma adalah prosedur langkah demi langkah yang di dalamnya sudah ditentukan dengan baik bagaimana langkah awal dan hasil akhirnya, sehingga bisa memberikan kepastian terhadap masalah yang spesifik. Computer bekerja dengan cara ini, 9



sedangkan proses reasoning manusia bekerja dengan cara yang nonalgorithmic. Aktivitas mental lebih dari sekedar mengikuti logika ataupun prosedure langkah demi langkah tadi. Heuristics. Heuristik atau disebut juga metode aturan jempol (rule of thumb, cara bodoh-bodohan) termasuk elemen kunci dari AI dalam definisi berikut ini: AI adalah cabang dari computer science yang berhubungan dengan cara untuk merepresentasikan pengetahuan menggunakan simbol lebih daripada bilangan, dan dalam memproses informasinya menggunakan metode aturan jempol atau heuristik. Orang lebih sering menggunakan cara bodoh-bodohan ini, dengan atau tanpa sadar dalam mengambil keputusan. Dengan menggunakan heuristik, orang tak perlu berpikir dua kali apa yang harus dikerjakan setiap saat menemui masalah yang sama. Inferencing. AI melibatkan perilaku mesin dalam memberikan alasan-alasan dari suatu tindakan yang diambil. Proses pemberian alasan ini (reasoning) ini terdiri dari inferencing (penggalian/penemuan kembali) dari fakta-fakta dan aturan-aturan menggunakan heuristik atau metode pencarian lainnya. AI secara unik melakukan proses inferencing ini dengan melakukan pendekatan pengenalan pola. Pengenalan Pola. Definisi AI berikut ini berkutat pada teknik pengenalan pola: AI bekerja dengan metode pengenalan pola yang bertujuan untuk menjelaskan objects (obyek), events (kejadian), atau proses-proses pada aspek kualitatif dan logika serta hubungan komputasinya.

2.2.

AI Dibandingkan dengan Natural Intelligence.

Nilai potensial AI dapat dipahami lebih dalam dengan membandingkannya dengan kecerdasan alami manusia. AI memiliki keuntungan komersial seperti: AI lebih permanen. AI lebih mudah untuk diduplikasi dan disebarluaskan. AI lebih murah. AI lebih mudah didokumentasikan. AI lebih cepat mengerjakan beberapa tugas tertentu. AI lebih baik dalam mengerjakan beberapa tugas tertentu. Namun demikian, kecerdasan alami memiliki juga kelebihan dibandingkan AI: NI adalah kreatif, sedangkan AI agak memiliki kelemahan dalam memasukkan pengetahuan padanya, yaitu harus dalam sistem yang terbangun dengan baik. NI menjadikan manusia bisa memetik keuntungan dari use sensory experience (sensasi pengalaman yang terjadi) secara langsung, sedangkan kebanyakan AI hanya bisa bekerja dengan input-input simbolik. Yang terpenting, human reasoning mampu untuk menangani pelbagai hal pada setiap waktu dari pengalaman yang luas dan baru dibawa kepada permasalahan yang lebih individual; di sisi lain, AI mendapatkan keuntungan dari fokus yang lebih sempit.

2.3.

Knowledge pada AI.

Dalam lapangan sistem informasi, ada kebingungan dalam istilah data, informasi, dan knowledge (pengetahuan). Data. Istilah data mengacu pada string numeric (atau alphanumeric) yang tak memiliki arti apa-apa. Bisa berupa fakta-fakta atau gambar yang akan diproses. Information. Informasi adalah data yang terorganisasi sehingga memiliki arti bagi orang yang menerimanya. Knowledge. Memiliki pelbagai definisi, yaitu: Persepsi yang jelas dan pasti dari suatu hal. Pemahaman. Pembelajaran. Semua hal yang dipersepsikan atau dipegang teguh oleh hati. Pengalaman praktis, ketrampilan. Sistem Berbasis Pengetahuan – Irfan Subakti

10


Kemudahan pengaksesan atau mudah untuk dikenal. Cognizance; pengenalan. Informasi terorganisasi yang teraplikasi pada penyelesaian masalah.

Penggunaan Knowledge. Walaupun komputer tidak mempunyai pengalaman atau studi dan belajar seperti halnya yang terjadi pada batin manusia, tapi komputer dapat menggunakan knowledge yang diberikan oleh pakar manusia. Knowledge ini terdiri dari fakta, konsep, teori, metode heuristik, prosedur, dan hubungan diantaranya. Knowledge juga merupakan informasi yang diorganisasi dan dianalisis untuk membuatnya dimengerti dan dapat diaplikasikan dalam penyelesaian masalah atau pengambilan keputusan. Koleksi dari knowledge yang berelasi ke suatu masalah (atau peluang) yang digunakan dalam sistem AI disebut dengan knowledge base. Kebanyakan basis pengetahuan ini terbatas pada fokus daerah subyek atau domainnya yang spesifik, malah biasanya sempit. Sekali basis pengetahuan dibangun, teknik AI dapat digunakan untuk menghasilkan kemampuan inferensi pada komputer. Basis-basis pengetahuan dan organisasi berbasis pengetahuan. Data, informasi, dan knowledge dapat diklasifikasikan berdasarkan derajat abstraksi dan kuantitasnya. High

Knowledge Degree of Abstraction Information

Data

Low

Quantity

2.4.

Bagaimana AI Berbeda dengan Komputasi Konvensional.

Komputasi konvensional bertumpu pada suatu algoritma yang sudah didefinisikan dengan jelas, prosedur langkah demi langkah untuk menyelesaikan masalah. Bisa berupa rumus matematika atau prosedur berurutan yang menuju pada solusi. Algoritma ini dikonversikan ke dalam program komputer. Komputasi AI berbasis pada representasi simbolik dan manipulasinya. Gambar di bawah mengilustrasikan konsep komputer yang menggunakan AI pada aplikasinya: Computer

Inputs (Questions, Problems, etc.)

Knowledge Base

Inferencing Capability

Outputs (Answers, Alternative Solutions, etc.)

Sedangkan tabel di bawah ini menjelaskan pelbagai cara pengolahan data secara tradisional: Process Manipulation Calculate Perform mathematical operations such as add, substract, multiply, divide, find a square root, etc. Solve formulas. Perform logic Perform logic operations such as “and”, “or”, “invert”, etc. Store Remember facts and figures in files. Retrieve Access data stored in files as required. Translate Convert data from one form to another. Sort Examine data and put it into some desired order to format. Edit Make changes, additions, and deletions to data and change its sequence. Make structured decisions Reach simple conclusions based on internal or external conditions. Monitor Observe external or internal events and take action if certain conditions are met. Control Take charge of or operate external devices. Sistem Berbasis Pengetahuan – Irfan Subakti

11


Software AI menampilkan proses reasoning dan inferencing menggunakan teknik dasar search (pencarian) dan pattern matching (pengenalan pola). Walaupun AI menyelesaikan permasalahan tidak secara langsung menggunakan proses algoritmis, jelas algoritma diimplementasikan dalam proses search ini. Sebagai peringatan, orang percaya bahwa AI adalah magic. Jelas bukan!. AI secara mendasar berbeda dengan pendekatan pemrograman komputer, dan tentu harus diperlakukan seperti itu. Pelbagai istilah berbeda digunakan untuk AI, yang jelas AI adalah CBIS, walaupun memiliki pelbagai karakteristik seperti di bawah ini: Dimension Artificial Intelligence Conventional Programming Processing Mainly symbolic Primarily computing Nature of input Can be incomplete Must be complete Search Heuristic (mostly) Algorithms Explanation Provided Usually not provided Major interest Knowledge Data, information Structure Separation of control from knowledge Control integrated with information (data) Nature of output Can be incomplete Must be correct Maintenance and update Relatively easy, due to modularity Usually difficult Hardware Mainly workstations and personal computers All types Reasoning capability Yes No

2.5.

Bidang AI.

Dapat digambarkan dalam bentuk diagram seperti di bawah ini:


12


Natural Language Processing Speech Understanding

Automatic Programming

Intelligent Tutor Expert Systems

Robotics

Computer Vision

Machine Learning Game Playing

The AI TREE

Computer Science

Linguistics

A

B

E

C

F

D

G

Psychology

H

I

J

K

Electrical Engineering

Philosopy

L

N

M

O

P

Management and Management Science

A Psycholingustics

E Cognitive Psychology

I

Robotics

M Mathematics/Statistics

B Sociolingustics

F

J

Image Processing

N Operations Research

C Computational Lingustics

G Philosophy of Language

Philosophy

D Adaptive Systems H Logic

K Pattern Recognition

O Management Information Systems

L

P Biology

Management

Expert System. Adalah program pemberi advis/nasehat yang terkomputerisasi yang ditujukan untuk meniru proses reasoning dan pengetahuan dari pakar dalam menyelesaikan permasalahan masalah yang spesifik. Bidang ini digunakan lebih banyak daripada penggunaan bidang-bidang AI lainnya. ES menarik minat yang besar dalam suatu organisasi disebabkan kemampuannya dalam meningkatkan produktifitas dan dalam meningkatkan gugus kerja di pelbagai bidang tertentu dimana pakar manusia akan mengalami kesulitan dalam mendapatkan dan mempertahankan kemampuan itu. Pakar manusia cenderung untuk menjadi spesialis dalam bidang keahlian tertentu yang relatif sempit. Umumnya pakar memiliki karakteristik ini: mereka menyelesaikan masalah dengan cepat dan cukup akurat, menjelaskan what/apa (dan terkadang how/bagaimana) yang mereka kerjakan, mempertimbangkan reliabelitas konklusinya, mengetahui kapan jalan buntu menghadang, dan mereka berkomunikasi dengan para pakar lainnya. Mereka juga belajar dari pengalaman, mengubah cara pandangnya untuk menyesuaikan dengan masalah, juga mentransfer pengetahuan dari satu domain ke domain yang lain. Akhirnya, mereka menggunakan pelbagai tool, seperti aturan jempol, model matematis, dan simulasi detil untuk mendukung keputusan yang diambil. Knowledge adalah sumber utama, dan ini seringkali cuma dimiliki oleh sebagian kecil pakar. Tentu saja diperlukan untuk menyimpan knowledge ini sehingga orang lain dapat menggunakannya. Sang pakar bisa saja menderita sakit atau meninggal dunia dan knowledge yang biasanya ada menjadi tiada lagi. Buku dan manual bisa saja menyimpan pelbagai knowledge, tetapi ini juga memberikan persoalan lain dalam aplikasi menampilkan kembali knowledge itu kepada orang yang membutuhkannya. ES menyediakan pengertian langsung dari aplikasi kepakaran. Sistem Berbasis Pengetahuan – Irfan Subakti

13


Tujuan dari ES bukanlah menggantikan para pakar, tetapi hanya untuk membuat knowledge dan pengalaman para pakar itu tersimpan dan tersedia lebih luas dan leluasa. Umumnya, memang lebih banyak masalah yang ada yang mendesak untuk diselesaikan daripada keberadaan para pakar untuk menangani pelbagai persoalan. ES mengijinkan orang lain untuk meningkatkan produktifitas, memperbaiki kualitas keputusannya, dan menyelesaikan masalah di saat seorang pakar tidak ada. Natural Language Processing. Teknologi bahasa alami memberikan komputer kemampuan untuk berkomunikasi dengan komputer lain dengan bahasa aslinya. Teknologi ini mengijinkan suatu jenis percakapan antarmuka, yang berbeda bila dibandingkan dengan istilah, sintaks, perintah programming language. Bidang NLP ini dibagi menjadi 2 sub bidang: Natural language understanding, mempelajari metode yang menjadikan komputer memahami perintah-perintah yang diberikan dalam bahasa Inggris, sehingga komputer dapat lebih mudah memahami manusia. Natural language generation, dibuat agar komputer bisa berbahasa Inggris umum, sehingga manusia lebih mudah memahami komputer.

2.6.

Kesimpulan.

AI adalah bidang lintas disiplin yang dapat didefinisikan dengan pelbagai cara. Tujuan utama dari AI adalah untuk membangun komputer yang dapat menampilkan unjuk kerja yang berkarakter cerdas. Karakteristik utama dari AI adalah pemrosesan simbolik, menggunakan metode heuristik lebih daripada algoritma, dan merupakan aplikasi yang menerapkan teknik inferencing. AI memiliki pelbagai keuntungan buat manusia: dia permanen, mudah diduplikasi dan disebarluaskan, lebih murah dibandingkan dengan harga kecerdasan manusia, konsisten dan menyeluruh, dan dapat didokumentasikan. Natural (human) intelligence memiliki pelbagai keuntungan dibandingkan AI: dia kreatif, menggunakan sensasi pengalaman secara langsung, alasan keputusannya berasal dari pengalaman yang berkonteks luas. Dibandingkan data ataupun informasi, knowledge merupakan konsep kunci dari AI. Knowledge base adalah koleksi dari knowledge yang berhubungan dengan isu yang spesifik (masalah atau peluang). Kita bergerak ke dalam era knowledge-based organizations. Aplikasi AI dapat diprogram ke dalam bahasa pemrograman komputer konvensional seperti halnya bahasa AI khusus (misalnya LISP, PROLOG). Dalam komputasi konvensional kita memberitahu komputer bagaimana menyelesaikan masalah. Dalam AI kita memberitahu komputer apakah masalahnya itu dan memberikan kepadanya knowledge yang diperlukan untuk menyelesaikan permasalahan yang serupa dan prosedur-prosedur yang diperlukan untuk menggunakan knowledge itu. Semua komputer digital dalam operasinya bersifat algorithmic, tetapi mereka dapat diprogram untuk memanipulasi simbol. Teknik dasar dari reasoning adalah search dan pattern matching. Di samping kenyataan bahwa komputasi AI tak dapat berpikir, ia akan lebih memiliki arti dengan meningkatkan pelbagai cara bagaimana komputer digunakan. Bidang aplikasi utama AI adalah ES, NLP, speech understanding, intelligent robotics, computer vision, dan intelligent computer-aided instruction. ES, teknologi Ai yang paling banyak diaplikasikan, mencoba untuk menirukan kerja dari pakar. Mereka mengaplikasikan kepakaran ini dalam penyelesaian masalah. NLP mencoba untuk menjadikan user berkomunikasi dalam bahasa aslinya dengan komputer. Penggunaan keyboard adalah umum terjadi, tetapi sekarang dengan suara (voice) pun hal ini sudah bisa dilakukan. Speech understanding mengijinkan orang berkomunikasi dengan komputer melalui suara. Intelligent robot adalah salah satu robot yang dapat merespon pelbagai perubahan dalam lingkungannya. Pada masa ini hal ini sudah tak asing lagi. Computer vision mengijinkan interpretasi gambar atau pelbagai obyek tampak lainnya. Komputer dapat digunakan sebagai pemandu. Jika ia didukung oleh AI, maka dia dapat meningkatkan pembelajaran dan peningkatan ketrampilan. Pelbagai teknologi AI dapat diintegrasikan diantara mereka sendiri dan dengan pelbagai teknologi berbasis komputer yang lain.


14

Bab 3 Expert System

BAB 3 EXPERT SYSTEM ES diturunkan dari istilah Knowledge-Based Expert System. ES adalah sistem yang mendapatkan dan menyimpan knowledge manusia ke dalam komputer untuk menyelesaikan permasalahan yang biasanya membutuhkan kepakaran seorang ahli. Area/bidang kepakaran ini disebut dengan domain. Pengembangan ES terindikasi pada hal-hal di bawah ini: Ketersediaan pelbagai tool yang didesain untuk memudahkan pembangunan ES dan mengurangi biayanya. Penyebarluasan ES pada ribuan organisasi, beberapa diantaranya menggunakan ratusan atau malah ribuan sistem yang spesifik. Integrasi ES dengan pelbagai CBIS yang lain berkembang makin pesat, khususnya integrasi dengan database dan DSS. Penggunaan ES semakin meningkat pada pelbagai hal, mulai dari sistem help sampai ke aplikasi bidang militer dan ruang angkasa. Penggunaan teknologi ES sebagai metodologi yang mempermudah pembangunan sistem informasi reguler. Peningkatan penggunaan object-oriented programming (OOP) dalam representasi knowledge. Pengembangan sistem utuh memiliki pelbagai sumber knowledge, reasoning, dan informasi fuzzy. Penggunaan multiple knowledge base.

3.1.

Konsep Dasar ES.

Expertise/Kepakaran. Kepakaran adalah knowledge yang ekstensif, spesifik yang didapatkan dari training, membaca, dan pengalaman. Pelbagai jenis knowledge di bawah ini adalah contoh dari kepakaran: Fakta menganai area/daerah masalah. Teori mengenai area masalah. Aturan dan prosedur berkaitan dengan area masalah secara umum. Rules (heuristic) dari apa yang harus dikerjakan pada situasi masalah tertentu (contoh aturan yang berkaitan dengan penyelesaian masalah). Strategi global untuk menyelesaikan masalah tertentu. Meta-knowledge (knowledge mengenai knowledge itu sendiri). Expert/Pakar. Aktualnya adalah derajat atau level dari kepakaran. Umumnya, kepakaran seorang manusia terdiri dari aktivitas berikut ini: Mengenali dan merumuskan masalah. Menyelesaikan masalah secara cepat dan layak. Menjelaskan solusinya. Belajar dari pengalaman. Me-restrukturisasi knowledge. Breaking rules. Menentukan relevansi. Menguraikan dengan bijak (sesuai dengan keterbatasannya). Fakta mengenai Kepakaran. Kepakaran biasanya diasosiasikan dengan kecerdasan tingkat tinggi tetapi ini tidak mesti berhubungan dengan orang tercerdas. Kepakaran biasanya diasosiasikan dengan kuantitas knowledge. Pakar belajar dari keberhasilan dan kegagalan masa lalu. Knowledge dari seorang pakar disimpan dengan baik, diorganisasi, dan dapat dicari lagi dengan cepat. Pakar dapat mengenali pola yang lebih tinggi dari pengalamannya (excellent recall).

15


Bab 3 Expert System

Di bawah ini adalah diagram distribusi kepakaran: 35 30 25 %

20 15

Average

10 5 0 1 2 3 Senior experts

4

5

6

Deciles

7

8

9

10 Juniors

2 tipe knowledge yang dapat dibedakan adalah: fakta dan prosedur (biasanya rule) yang berkaitan dengan domain permasalahan. Inferencing. Fitur khas dari ES adalah kemampuan untuk reasoning. Kenyataan bahwa kepakaran disimpan dalam suatu knowledge base dan bahwa program memiliki akses ke database, maka komputer diprogram sehingga dapat berinterferensi. Intererencing ini dilakukan oleh komponen yang disebut inference engine, yang di dalamnya terdapat prosedur-prosedur yang berkaitan dengan penyelesaian masalah. Di bawah ini adalah perbedaan antara Conventional Systems dan ES: Conventional Systems Expert Systems Information and its processing are usually Knowledge base is clearly separated from the combined in one sequential program. processing (inference) mechanism (i.e., knowledge rules separated from the control). Program does not make mistakes Program may make mistakes. (programming do). Do not (usually) explain why input data are Explanation is a part of most ES. needed or how conclusions were drawn. Changes in the program are tedious. Changes in the rules are easy to accomplish. The system operates only when it is The system can operate with only a few rules (as the completed. first prototype). Execution is done on a step-by-step Execution is done by using heuristics and logic. (algorithmic) basis. Effective manipulation or large databases. Effective manipulation of large knowledge bases. Representation and use of data. Representation and use of knowledge. Efficiency is a major goal. Effectiveness is the major goal. Easily deal with quantitative data. Easily deal with qualitative data. Capture, magnify, and distribute access to Capture, magnify, and distribute access to judgment numeric data or to information. and knowledge. Rules. Kebanyakan ES komersial menggunakan sistem yang berbasis rule (rule-based system); yaitu knowledge disimpan dalam bentuk rule-rule, yang merupakan prosedur untuk menyelesaikan masalah. Kemampuan Menjelaskan. Fitur unik lain dari ES adalah kemampuan untuk menjelaskan nasehat atau rekomendasi yang diberikan. Penjelasan dan justifikasi ini dilakukan oleh subsistem yang disebut dengan justifier atau explanation subsystem. Ini menjadikan sistem dapat memeriksa reasoningnya dan menjelaskan operasi-operasi yang dilakukan. Sistem Berbasis Pengetahuan – Irfan Subakti

16

Bab 3 Expert System

3.2.

Struktur ES.

ES dibagi menjadi 2 bagian utama: development environment dan consultation (runtime) environment. Lingkungan pengembangan digunakan oleh ES builder untuk membangun komponen dan untuk membawa knowledge ke dalam knowledge base. Lingkungan konsultasi digunakan oleh orang yang bukan ahli untuk mendapatkan knowledge dan saran setara pakar. Komponen yang ada dalam ES: Knowledge acquisition subsystem [human experts, textbooks, researc reports]. Knowledge base [facts: situation & theory, heuristics or rules]. Inference engine [interpreter, scheduler, consistency enforcer]. Blackboard (workplace) [plan, agenda, solution]. User. User interface [friendly, problem oriented]. Explanation subsystem (justifier) [what, how, why]. Knowledge refining system [analyze performance, learn, improve]. Inference Engine. Otak dari ES adalah Inference engine, disebut juga control structure atau the rule interpreter (pada rule-based ES). Komponen ini sebenarnya adalah program komputer yang menyediakan metodologi untuk reasoning mengenai informasi dalam knowledge base dan dalam “blackboard”, dan digunakan untuk merumuskan kesimpulan. 3 elemen utamanya adalah: Interpreter (rule interpreter dalam kebanyakan sistem), yang mengeksekusi item agenda yang dipilih dengan mengaplikasikannya pada knowledge base rule yang berhubungan. Scheduler, yang menjaga kontrol di sepanjang agenda. Memperkirakan akibat dari pengaplikasian inference rule yang menampakkan prioritas item atau kriteria lain pada agenda. Consistency enforcer, yang mencoba menjaga konsistensi representasi solusi yang muncul. Di bawah ini adalah diagram struktur dari ES:

DEVELOPMENT ENVIRONMENT

CONSULTATION ENVIRONMENT User Facts about the Specific Incident

Knowledge Base What is Known about the Domain Area Logical Reference (e.g., Between Symptoms and Causes)

Facts: Rules:

User Interface Explanation Facility

Knowledge Engineer

Recommended Action

Inference Engine Draw Conclusions

y y y

Blackboard (Workplace) Plan Agenda Solution Problem Description

Interpreter Scheduler Consistency Enforcer

Knowledge Acquisition Expert Knowledge

Knowledge Refinement

Explanation Subsystem (Justifier). Kemampuan untuk melacak kebenaran dari kesimpulan yang didapat dari sumber-sumbernya merupakan hal yang krusial baik dalam tranformasi kepakaran maupun dalam penyelesaian masalah. Bagian ini dapat melacak kebenaran dan menjelaskan perilaku ES dengan secara interaktif menjawab pertanyaan seperti ini: Why was a certain question asked by the expert system? Sistem Berbasis Pengetahuan – Irfan Subakti

17

Bab 3 Expert System

How was a certain conclution reached? Why was a certain alternative rejected? What is the plan to reach the solution? For example, what remains to be established before a final diagnosis can be determined?

Knowledge Refining System. Dengan ini pakar dapat menganalisis kinerja mereka, belajar daripadanya, dan meningkatkannya pada konsultasi berikutnya.

3.3.

Elemen Manusia dalam ES.

Orang-orang yang terlibat dalam pengembangan dan penggunaan ES: 3. Pakar. 4. Knowledge Engineer. 5. User. Yang terdiri dari: Klien yang bukan pakar yang menginginkan nasehat langsung. Disini ES bertindak sebagai konsultan atau advisor/penasehat. Pelajar yang ingin belajar. ES disini bertindak sebagai instruktur. ES Builder yang ingin meningkatkan knowledge base-nya. Disini ES bertindak sebagai partner. Pakar. ES disini bertindak sebagai kolega atau sebagai asisten. 6. Pihak lain. Misalnya: system builder, tool builder, vendor, staf pendukung. Lengkapnya dapat dilihat pada bagan di bawah ini: TOOL BUILDER

EXPERT DOCUMENTED KNOWLEDGE

Build

TOOLS, LANGUAGES

Provide

Use

Acquire Knowledge KNOWLEDGE ENGINEER

Use

VENDOR

SUPPORT STAFF

Test

Support Tasks Build

Build

SYSTEM BUILDER

3.4.

Bagaimana ES Dibangun.

3.5.

Bidang Permasalahan yang Ditangani ES.

3.6.

Keuntungan ES

EXPERT SYSTEM

Use

Connect

END-USER

3 aktivitas pembangunan ES adalah: Pengembangan (development). Konsultasi (consultation). Peningkatan (improvement).

Pada tabel berikut disajikan kategori umum dari ES: Category Problem Addressed Interpretation Inferring situation description from observations Prediction Inferring likely consequences of given situations Diagnosis Inferring system malfunctions from observations Design Configuring objects under constraints Planning Developing plans to achieve goal(s) Monitoring Comparing observations to plans, flagging exceptions Debugging Prescribing remedies for malfunctions Repair Executing a plan to administer a prescribed remedy Instruction Diagnosing, debugging, and correcting student performance Control Interpreting, predicting, repairing, and monitoring system behaviors

Pelbagai keuntungan potensial yang bisa diperoleh dari ES adalah: Meningkatkan output dan produktivitas. Meningkatkan kualitas. Mengurangi waktu kerusakan (downtime). Sistem Berbasis Pengetahuan – Irfan Subakti

18

Bab 3 Expert System

Mengatasi kelangkaan kepakaran. Fleksibelitas. Pengoperasian peralatan lebih mudah. Menghilangkan kebutuhan akan peralatan yang mahal. Operasi pada lingkungan yang membahayakan. Akses ke knowledge dan help desk (sistem bantuan). Kehandalan. Meningkatkan kemampuan pelbagai sistem terkomputerisasi lainnya. Integrasi dari pelbagai opini para pakar. Kemampuan bekerja dengan informasi yang tidak komplit dan tak pasti. Penyediaan pelatihan (training). Peningkatan dalam hal penyelesaian masalah. Kemampuan menyelesaikan masalah yang kompleks. Transfer knowledge ke lokasi yang berbeda. Peningkatan kepada CBIS lainnya.

3.7.

Di

Permasalahan dan Keterbatasan ES.

bawah ini adalah pelbagai hal yang menghambat ES: Knowledge tak selalu tersedia. Kepakaran sulit diekstraksi dari manusia. Pendekatan untuk setiap pakar pada situasi tertentu selalu berbeda, dan tak mesti benar. Walaupun pakar tersebut memiliki ketrampilan yang tinggi, sukar untuk mengabstraksikan kepakarannya pada situasi tertentu, apalagi pakar tersebut bekerja di bawah tekanan. User dari ES memiliki batasan kognitif alamiah. ES bekerja baik hanya pada domain yang terbatas/sempit. Kebanyakan pakar tak memiliki rasa pengertian pengecekan yang independen walaupun konklusi mereka masuk akal. Kosa kata, atau jargon, yang digunakan pakar untuk mengekspresikan fakta dan relasinya biasanya jarang digunakan dan dimengerti oleh orang lain. Help seringkali dibutuhkan oleh knowledge engineer yang biasanya jarang tersedia dan mahal biayanya – sebuah fakta yang dapat membuat pembangunan ES lebih banyak memakan biaya. Kendala kepercayaan pada end-user bisa menghalangi penggunaan ES. Transfer knowledge bergantung pada persepsi dan bisa bias dalam prasangka.

3.8.

Jenis ES.

ES muncul dalam pelbagai variasi. ES vs. Knowledge-based Systems. ES mendapatkan knowledge-nya dari para pakar, sedang KBS dari sumber-sumber terdokumentasi. KBS lebih murah dan lebih cepat dibangun dibandingkan ES. Rule-based Expert Systems. Knowledge direpresentasikan sebagai serangkaian rule-rule (production rules). Frame-based Systems. Knowledge direpresentasikan sebagai frame, yaitu representasi dari pendekatan Pemrograman Berbasis Objek (OOP). Hybrid Systems. Melibatkan pelbagai pendekatan representasi knowledge, paling tidak frame dan rule, tapi biasanya lebih dari itu. Model-based Systems. Tersusun di sekitar model yang mensimulasikan struktur dan fungsi dari sistem yang dipelajari. Model digunakan untuk menghitung nilai-nilai, yang dibandingkan dengan sedang diamati. Pembandingan tersebut memicu aksi (jika diperlukan) atau diagnosis lebih lanjut. Sistem yang diklasifikasikan oleh sifat alamiahnya. Ada 3 jenis. (1) berhubungan dengan evidence gathering (pengumpulan bukti-bukti), (2) stepwise refinement system. Sistem ini berhubungan dengan sejumlah besar keluaran dari level-level detil sesudahnya. (3) stepwise assembly, dimana domain subjek dapat mempunyai jumlah yang luar biasa besar keluaran yang mungkin. Jenis khusus dari ini disebut dengan catalog selection. Sistem ini berhubungan dengan masalah seperti pemilihan bahan kimia, baja yang benar. Sistem siap pakai (Off-the-Shelf Systems). Sebagai hasil dari produksi masal membuatnya lebih murah dibandingkan dengan sistem yang memenuhi keinginan user (customized system). Sayangnya sistem ini bersifat terlalu umum, dan nasehat/advis yang dihasilkan mungkin tak bernilai pada user yang dihadapkan pada situasi yang kompleks.


19

Bab 3 Expert System

Real-time Expert Systems. Sistem ini berkenaan dengan waktu, jadi harus cukup cepat mengontrol proses terkomputerisasi. Sistem selalu menghasilkan respon sesuai waktu yang diperlukan.

3.9.

Pengembangan ES.

7 langkah yang diperlukan dalam pengembangan ES dapat dilihat pada diagram di bawah ini:

Phase 1. Front End Analysis y Identify appropriate problem y Determine cost/effectiveness y Arrange management support Phase 2. Task Analysis y Identify appropriate task y Identify behavioral sequence y Identiy knowledge required Phase 3. Prototype Development y Identify case studies (criteria) y Develop a small system to provide proof of concept and practice Phase 4. System Development y Rearrange overall structure as necessary y Add knowledge Phase 5. Field Testing y y

Test system with actual users Revise as necessary

Phase 6. Implementation y Port system to hardware to be used in the field y Train users to use system Phase 7. Maintenance y y

Establish means to update system Update system as needed

Membangun ES yang spesifik dengan suatu shell dapat digambarkan dalam diagram di bawah ini:

Symptoms, Specific Problems User Recommendation, Explanation

Inference Engine, Rule and Program Interpreters

Knowledge Base Facts

Rules

Development Engine Editor, Debugging Tools

⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭

Consultation Environment

Sample Problems (Cases) Tests

Knowledge Engineer

Expert

⎫ ⎪ Development ⎬ Environment ⎪ ⎭


20

Bab 3 Expert System

Software untuk membangun ES dapat digambarkan pada diagram berikut ini: Specific Expert Systems

Expert Systems Shells

General-Purpose Knowledge Engineering Languages

⎧ ⎪ ⎪ ⎪ T⎪ o⎪ o⎨ l ⎪ s⎪ ⎪ ⎪ ⎪ ⎩

GeneralPurposes Programming Languages

Support Facilities

Programming

Higher-Level Programming Language

System-Building Aids

Knowledge Acquisition

Explanation

General Purpose

Design

Symbol Manipulation

Tahapan-tahapan dalam mengakuisisi knowledge digambarkan dalam diagram ini: IDENTIFICATION Identify Problem Characteristics

Requierements CONCEPTUALIZATION

Find Concepts to Represent Knowledge Concepts

FORMALIZATION

Design Structure to Organize Knowledge

Rules TESTING

Validate Rules that Organize Knowledge

Redesigns

Formulate Rules to Embody Knowledge Refinements

IMPLEMENTATION

Reformulations

Structure


21

Bab 3 Expert System

Sedangkan proses pengembangan ES itu sendiri digambarkan sebagai berikut: Problem Selection (Step 1)

Select Expert(s) (Step 2)

Conceptual Planning (Step 3)

Select Software and Hardware Tools (Step 4)

Knowledge Acquisition (Step 5)

Build a Prototype ES (Step 6) Justifier

Inference Engine

Blackboard

Knowledge Base

Interface (Dialog)

Rapid Prototyping

Evaluate for Performance (Step 7)

Evaluate for Acceptance Training (Step 8)

Use in Parallel with Existing System (Step 9)

Develop Documentation and Maintenance Plans (Step 10)

System Release Full-Scale ES (Step 11)


22

Bab 3 Expert System

Salah satu contoh dari ES (IFPS) dapat digambarkan dalam diagram di bawah ini: COMPILESAVE COMPILEGET

Efficiency SPOOL RECORD OPTION DFNAME COMMANDS

MODEL *) COMBINE CONSOLIDATE

Risk Analysis

Scenario Building

WHAT IF WHAT IF SAVE MONTE CARLO Monte Carlo Options

Control Data Editing INSERT REMOVE CHANGE

Modeling Subsystem

Executive Command Level

Processing and Interrogation

Data File Subsystem DATAFILE *)

SOLVE Solve Options BASE MODEL RECOMPILE Probabilistic Value Control ANALYZE GOAL SEEKING IMPACT SENSITIVITY

Format Reports

Print Results

Store Results

Graph Results

Variable List ALL STORE STORENT STOREP Store Options PLOT Plot Options

GENREPORT

Command File Subsystem

Manipulation

CATALOG LIST COPY DELETE RESEQUENCE MERGE CONSOLDF FILE QUIT

CMDFILE *)

Entry Processor

AUTO END

Report Subsystem REPORT *)

*) Text Editor Recognized AUTO END

LIST SAVE

Editing Commands


23

Bab 3 Expert System

Di bawah ini adalah diagram Financial Decision Support Model: Growth, Penetration, and Profit Strategies

Price

Cost Reduction Required

Units

Net Sales Inventory Change

Allowable Costs

Billings

Profits Goals Return on Assets Goals

Product Rationalization

Billings Per Person Goal

People/Sales Forecast Goals

People

Depreciation

Assets Inventories Receivables Cash and Other

Net Fixed Assets Facilities Requirements

Pay/Person

Cost/sq. ft.

Payroll

Facilities Expenditure Requirements

Capital Ratios

Capital Expenditures

Cost Reduction Program

Contoh-contoh dari tindakan Heuristic: Action Sequence jobs through a machine Purchase stocks Travel Capital investment in high-tech projects Purchase of a house

Explanation Do the jobs that require the least time first. Do not buy stocks whose price-to-earnings ratio is larger than 10. Do not go on the freeway between 8 and 9 A.M. Consider only projects whose estimated payback period is less than two years. Buy only a good neighborhood, but buy there only at the lower price range.


24

Bab 3 Expert System

Di bawah ini adalah diagram Unified Architecture untuk Intelligent Decision Support System:

Data Base

Knowledge Base

Model Base

Intelligent

Model Base Management System (MBMS)

Data Base Management System (DBMS)

Inference Engine Supervisor

Knowledge Acquisition Subsystem

Natural Language Interface

Knowledge Engineer

User

D i a l o g

Central Intelligence Manager

S u b s y s t e m

Integrasi antara ES dengan software lain dapat digambarkan sebagai berikut:

Rule Base

Stats Package

Inference Engine

User Interface

3.10.

Database

Maths Package

Graphics Package

Kesimpulan.

ES menirukan proses reasoning dari pakar untuk menyelesaikan masalah yang sulit. Pendahulu ES adalah GPS (General-purpose Problem Solver). GPS dan yang serupa dengannya gagal disebabkan mereka mencoba menangani terlalu banyak dan mengabaikan pentingnya knowledge khusus yang dibutuhkan. Kekuatan ES diturunkan dari knowledge khusus yang dimiliki, dan bukan dari representasi knowledge tertentu dan skema inferencing yang dijalankan. Kepakaran adalah knowledge task khusus yang didapatkan dari pelatihan/training, membaca, dan pengalaman. Pakar dapat membuat keputusan yang cepat dan baik berkenaan dengan situasi yang kompleks. Kebanyakan knowledge dalam organisasi dimiliki oleh segelintir pakar. Teknologi ES mencoba untuk mentransfer knowledge dari pakar dan sumber-sumber terdokumentasi ke komputer dan bisa digunakan oleh yang bukan pakar. Kemampuan reasoning dalam ES disediakan oleh mesin inference (inference engine). Sistem Berbasis Pengetahuan – Irfan Subakti

25

Bab 3 Expert System

Knowledge dalam ES dipisahkan dari inferencing (pemrosesannya). ES menyediakan kemampuan menjelaskan (explanation) yang terbatas. Terdapat perbedaan diantara lingkungan pengembangan (membangun ES) dan lingkungan konsultasi (menggunakan ES). Komponen utama dari ES adalah subsistem pengakuisisian knowledge, knowledge base, inference engine, blackboard, user interface, dan explanation subsystem. Knowledge engineer menangkap knowledge dari pakar dan memprogramnya ke dalam komputer. Walaupun user utama dari ES adalah yang bukan pakar, user yang lain (seperti pelajar, ES builder, dan mungkin para pakar juga) juga menggunakan ES. Knowledge dapat berupa deklarasi (fakta) atau prosedur. ES dapat ditingkatkan dalam langkah-langkah iterasi menggunakan proses yang disebut dengan rapid prototyping (prototipe cepat). 10 kategori umum ES adalah: interpretasi, prediksi, diagnosis, desain, perencanaan, pemantauan, debugging, perbaikan, instruksi, dan kontrol. ES dapat memberikan banyak keuntungan. Yang terpenting adalah peningkatan dalam produktivitas dan/atau kualitas, penanganan kepakaran yang jarang didapatkan, peningkatan sistem yang lain, penanganan informasi yang tak lengkap, dan penyediaan training/pelatihan. Walaupun ada pelbagai keterbatasan penggunaan ES, dengan adanya perkembangan teknologi semakin lama keterbatasan tersebut akan makin hilang. ES, seperti halnya pakar, dapat membuat kesalahan. Terdapat pelbagai pembedaan diantara sistem-sistem pakar (ES), dimana kebanyakan knowledge datang dari para pakar; serta knowledge systems, dimana mayoritas knowledge datang dari sumber-sumber terdokumentasi. Pelbagai ES tersedia sebagai sistem yang siap pakai; ia mengolah dan memberikan advis/nasehat umum untuk situasi standar. ES dapat juga bekerja dalam mode real-time (waktu nyata).


26

Bab 4 Akuisisi dan Validasi Knowledge

BAB 4 AKUISISI DAN VALIDASI KNOWLEDGE 4.1.

Rekayasa Knowledge.

Rekayasa knowledge dapat dipandang dari 2 perspektif: sempit dan luas. Dalam perspektif luas, rekayasa knowledge menjelaskan keseluruhan proses pengembangan dan pengelolaan sistem AI. Dalam perspektif sempit, rekayasa knowledge berhubungan dengan akuisisi, representasi, validasi, inferencing, penjelasan, dan pengelolaan knowledge. Pengertian ini yang digunakan dalam pembahasan bab ini.

Proses Rekayasa Knowledge. Dapat dilihat pada gambar di bawah ini: Knowledge Validation (Test Cases)

Sources of Knowledge (Experts, Others) Knowledge Representation

Knowledge Base

Encoding

Knowledge Representation

Explanation, Justification

Inferencing

4.2.

Skup Knowledge.

Hal-hal yang berkenaan dengan knowledge, dapat digambarkan dalam bagan berikut ini: Uncertaint Facts

Behavior Descriptions and Beliefs

Vocabulary Definitions

Knowledge about Knowledge (Metaknowledge)

Processes

Constraints Objects and Relationships

Heuristics and Decision Rules Procedures for Problem Solving

Knowledge Base Facts about the Domain

Hypotheses (Theories)

Disjunctive Facts

General Knowledge (e.g., of the World)

Typical Situations

Sumber Knowledge. 2 sumber, terdokumentasi dan tak terdokumentasikan. Sumber tak terdokumentasikan ini yang seringkali dijumpai, ia berada dalam pikiran orang sehingga sulit didokumentasikan. 27



Knowledge dapat diidentifikasikan dan dikumpulkan menggunakan indra manusia dan juga mesin (sensor, scanner). Keragaman dan pelbagai jenis knowledge menyebabkan akuisisi knowledge menjadi lebih kompleks.

Akuisisi dari Database. Pelbagai ES dibangun dari knowledge yang diekstrak baik keseluruhan maupun sebagian dari database. Bertambahnya jumlah knowledge yang disimpan dalam database, menjadikan akuisisi lebih sulit dilakukan. Level Knowledge. Shallow knowledge (pengetahuan dangkal). Mengacu pada representasi informasi level permukaan yang berhubungan dengan situasi yang sangat spesifik. Salah satu contoh adalah aturan IF-THEN. Deep knowledge (pengetahuan dalam). Mengacu pada struktur dalam dan penyebab dari suatu sistem dan mempertimbangkan interaksi diantara komponen-komponen sistem. Ia berbasis secara penuh pada integrasi, hubungan erat kesadaran manusia yang melibatkan emosi, akal sehat, intuisi, dan lain-lain. Jenis knowledge ini sulit untuk dikomputerisasikan. Kategori Knowledge. Knowledge deklaratif. Representasi deskriptif dari suatu knowledge. Ia menceritakan kepada kita “apakah” (what) sesuatu itu. Diekspresikan dalam penyataan faktual. Menceritakan kebenaran yang didapat dan asosiasi-asosiasinya. Biasanya berjenis knowledge dangkal, atau level permukaan, informasi yang dapat diceritakan pakar secara verbal. Knowledge deklaratif ini sangat penting dalam tahap awal akuisisi knowledge. Knowledge prosedural. Mempertimbangkan perilaku dimana sesuatu bekerja di bawah keadaan-keadaan tertentu. Ia mengikutsertakan urutan langkah demi langkah dan jenis instruksi “bagaimana” (how-to); bisa juga mengikutsertakan penjelasan (explanation). Ia melibatkan tanggapan otomatis terhadap rangsangan. Ia juga menceritakan pada kita bagaimana menggunakan knowledge deklaratif dan bagaimana membuat inferences. Jadi secara implisit jenis knowledge ini menjelaskan juga pertanyaan “mengapa” (why). Metaknowledge. Berarti knowledge mengenai knowledge. Dalam ES, metaknowledge mengacu pada knowledge mengenai operasi sistem berbasis pengetahuan; yaitu, mengenai kemampuan reasoning (memberikan alasan/penjelasan).

4.3.

Kesulitan dalam Akuisisi Knowledge.

Secara umum, mentransfer informasi dari satu orang ke orang lain adalah hal yang sulit. Beberapa mekanisme dapat digunakan untuk melakukan transfer ini – menuliskan kata-kata, suara, gambar, musik – dan tak satupun dari ini yang sempurna. Masalah juga ada dalam mentransfer knowledge, walaupun cuma pesan/message yang singkat. Mentransfer knowledge dalam ES lebih sulit lagi.

Masalah-masalah dalam transfer knowledge. Mengekspresikan knowledge. Penyelesaian masalah dari para pakar ini meliputi 2 langkah proses. (1) Pakar menginputkan informasi mengenai dunia luarnya ke dalam benaknya. Informasi ini disampaikan oleh orang, komputer, atau media lain. Juga dikumpulkan melalui sensor atau dipanggil kembali dari ingatan/memory. (2) Pakar menggunakan pendekatan induktif, deduktif, atau pendekatan lain pada informasi tersebut. Hasil dari seluruh proses ini merupakan rekomendasi tentang bagaimana menyelesaikan masalah. Proses ini adalah proses internal. Knowledge engineer, saat mengumpulkan knowledge dari pakar, harus menanyakan kepada para pakar agar mereka melihat ke dalam dirinya sendiri mengenai proses pengambilan keputusan dan mengenai pengalaman-pengalaman yang terlibat di dalamnya. Sangat sulit bagi para pakar dalam mengekspresikan pengalamannya mengenai proses tadi, khususnya pada pengalaman-pengalaman yang berasal dari sensasi, pertimbangan, ingatan indrawi, dan perasaan. Pakar sering mengabaikan proses detil bagaimana ia sampai mengambil kesimpulan. Juga, pakar mungkin menggunakan aturan yang berbeda dalam menyelesaikan masalah-masalah dalam kenyataannya dibandingkan yang ia nyatakan dalam wawancara akuisisi knowledge. Transfer ke mesin. Knowledge ditransfer ke mesin dan diorganisasi dengan cara-cara tertentu. Mesin membutuhkan knowledge agar bisa mengekspresikannya secara jelas dalam Sistem Berbasis Pengetahuan – Irfan Subakti

28


1. 2. 3. 4. 5. 6. 7. 8.

level yang lebih rendah, lebih detil daripada manusia. Knowledge manusia disimpan dalam format dengan susunan tertentu. Manusia jelas sulit mengingat semua langkah-langkah antara yang digunakan otaknya dalam pentransferan atau pemrosesan knowledge. Sehingga, ada ketidaksesuaian diantara komputer dan pakar. Jumlah partisipan. Dalam transfer umum knowledge ada 2 partisipan (pengirim dan penerima). Dalam ES, bisa terdapat 4 partisipan (ditambah dengan komputer): pakar, knowledge engineer, desainer sistem (builder, pembangun), dan user. Terkadang ada partisipan lain (misal, programer dan vendor). Para partisipan ini memiliki latar belakang yang berbeda, menggunakan istilah berbeda, dan memiliki ketrampilan dan knowledge yang berbeda pula. Sebagai contoh, sang pakar, mungkin sedikit sekali mengerti tentang komputer, sedangkan knowledge engineer sangat sedikit tahu tentang wilayah permasalahan. Struktur knowledge. ES selain membutuhkan knowledge, juga berkepentingan dengan struktur dari knowledge tersebut. Knowledge harus disusun menurut aturan tertentu (misal, sebagai rules/aturan-aturan). Alasan-alasan lain. Beberapa alasan yang menambahi kerumitan transfer knowledge: Pakar mungkin memiliki keterbatasan waktu atau tak bersedia bekerja sama. Testing dan penghalusan knowledge adalah sesuatu yang rumit. Definisi yang mungkin kurang baik dari metode mendapatkan suatu knowledge. Pembangun sistem bertendensi untuk mengumpulkan knowledge dari satu sumber, namun knowledge yang relevan mungkin harus diperoleh dari pelbagai sumber. Pembangun mungkin mencoba untuk mengumpulkan knowledge terdokumentasi daripada memanfaatkan para pakar. Knowledge yang dikumpulkan mungkin tak lengkap. Adalah sulit untuk mengenali knowledge tertentu jika ia tercampur dengan data yang tak relevan. Pakar mungkin mengubah perilakunya jika ia diamati dan/atau diwawancarai. Masalah komunikasi antarpersonal yang mungkin ada diantara knowledge engineer dan pakar.

Mengatasi Pelbagai Kesulitan. Banyak usaha telah dilakukan untuk mengatasi kesulitan-kesulitan yang sudah dijelaskan tadi. Misalnya, mengembangkan program yang mampu menerima saran seperti yang sering diberikan kepada para user/pemula. Beberapa paket software pengembangan ES menyederhanakan sintaks dari rules (dalam sistem berbasis rule/aturan) untuk membuat ES builder lebih mudah membuat dan memahaminya tanpa pelatihan khusus. NLP bisa juga digunakan menerjemahkan knowledge ke struktur representasi knowledge tertentu. Lebih lanjut, beberapa kesulitan mungkin bisa dikurangi atau dihilangkan dengan tool akuisisi knowledge berbasis komputer dan dengan integrasi ekstensif dengan pelbagai usaha akuisisi. Ketrampilan yang dibutuhkan oleh Knowledge Engineer: Ketrampilan komputer (hardware, pemrograman, software). Toleransi dan ambivalensi (bisa bersikap mendua, untuk sementara). Kemampuan komunikasi yang efektif – sensitivitas, taktik, dan diplomasi. Latar belakang pendidikan yang luas. Ketrampilan verbal di bidang sosial yang canggih dan mendalam. Kemampuan untuk belajar cepat (dari bermacam-macam domain yang berbeda). Pemahaman mengenai organisasi dan individu. Pengalaman yang mumpuni dalam rekayasa knowledge. Intelijen/kecerdasan. Empati dan kesabaran. Ketekunan. Berpikir lojik. Mengetahui pelbagai hal dan suka hal-hal baru. Percaya diri.

4.4.

Metode Akuisisi Knowledge: Pendahuluan.

Teknik mendapatkan knowledge dari pakar dapat dilakukan dengan cara manual atau dengan bantuan komputer. Kebanyakan teknik manual dipinjam (tetapi seringkali dimodifikasi) dari bidang Psikologi atau dari analisis sistem. Metode manual pada dasarnya dicirikan dengan jenis wawancara terstruktur. Sistem Berbasis Pengetahuan – Irfan Subakti

29


Di bawah ini disajikan gambaran metode manual dalam akuisisi knowledge: Expert(s)

Elic

itat ion

Knowledge Engineer

Coding

Knowledge Base

Documented Knowledge

Metode semiotomatis dibagi menjadi 2 kategori: (1) yang ditujukan untuk mendukung pakar dengan mengijinkan mereka membangun basis knowledge dengan tanpa atau sedikit bantuan knowledge engineer, yang dapat digambarkan seperti ini: Coding

Expert

Computer-aided (Interactive) Interviewing

Knowledge Base

Knowledge Engineer

Dan (2) yang ditujukan untuk membantu knowledge engineer dengan mengijinkan mereka mengeksekusi task/tugas yang diperlukan dengan cara yang lebih efektif dan/atau efisien (terkadang dengan hanya partisipasi minimal sang pakar). Pada metode otomatis, peran dari pakar dan/atau knowledge engineer diminimalkan atau malah dihilangkan. Sebagai contoh, pada metode induksi yang diatur oleh sembarang builder (misal, seorang sistem analis). Pakar berperan minimal dan knowledge engineer tak diperlukan disini. Istilah otomatis mungkin salah diartikan. Pasti ada seorang/beberapa builder disitu, tapi memang tak diperlukan adanya knowledge engineer dan pakar, kalaupun ada itupun hanya sedikit. Metode induksi dapat digambarkan sebagai berikut: Case Histories and Examples

4.5.

Induction System

Knowledge Base

Wawancara.

Format akuisisi knowledge yang paling umum adalah analisis wawancara tatap muka. Dalam wawancara, pakar diberi presentasi dengan kasus simulasi atau jika mungkin dengan masalah nyata secara singkat dimana ES nantinya diharapkan bisa menyelesaikan. Lalu sang pakar ditanyai untuk “menceritakan” kepada knowledge engineer mengenai solusinya. Terkadang metode ini disebut dengan metode walkthrough. Proses wawancara bisa membosankan. Ia terlalu memusatkan diri pada sang pakar, seorang yang harus mampu tak hanya mendemonstrasikan kepakarannya tapi juga dalam mengekspresikannya. Dengan kata lain, ia hanya membutuhkan perlengkapan kecil, sangat fleksibel dan bisa dilakukan dimana saja, dan dapat menghasilkan jumlah informasi yang berarti. 2 jenis wawancara: tak terstruktur (informal) dan terstruktur.

Wawancara Tak Terstruktur. Kebanyakan wawancara akuisisi knowledge dilakukan secara informal, biasanya sebagai tahap permulaan. Memulai dengan cara informal bisa menghemat waktu; ia secara cepat membantu mendapatkan struktur dasar domain permasalahan. Lalu, umumnya hal ini akan diteruskan dengan teknik formal. Berbeda dengan anggapan banyak orang, wawancara tak terstruktur tidaklah sederhana. Kenyataannya, ini memberikan knowledge engineer bermacam-macam masalah efek berkelanjutan. Wawancara tak terstruktur jarang dapat menyediakan gambaran lengkap atau terorganisasi baik dari proses cognitif (pengenalan/pemahaman). Alasannya: 1. domain biasanya rumit. 2. pakar biasanya kesulitan dalam mengekspresikan elemen yang lebih penting dari knowledgenya. 3. domain pakar mungkin menginterpretasikan struktur yang buruk karena persiapan yang kurang sebelum diadakan wawancara itu. Sistem Berbasis Pengetahuan – Irfan Subakti

30


4. data yang didapat dari wawancara tak terstruktur sering tak berkaitan, terdiri dari bermacammacam level kerumitan, dan sulit bagi knowledge engineer untuk mengkaji ulang, menginterpretasikan, dan mengintegrasikan. 5. disebabkan kurangnya pelatihan dan pengalaman, sedikit knowledge engineer dapat melakukan wawancara tak terstruktur dengan efisien. Wawancara Terstruktur. Di bawah ini adalah prosedur untuk melakukan wawancara terstruktur: Knowledge engineer mempelajari materi yang tersedia pada domain untuk mengidentifikasi garis batas utama knowledge yang relevan. Knowledge engineer mengkaji ulang kemampuan ES yang direncanakan. Dia mengidentifikasi tujuan pertanyaan yang akan ditanyakan selama sesi akuisisi knowledge. Knowledge engineer secara formal menjadwal dan merencanakan (menggunakan form) wawancara terstruktur. Perencanaan ini termasuk juga janji bertemu secara fisik, mendefinisikan tujuan dan agenda sesi akuisisi knowledge, dan mengidentifikasi atau memperhalus wilayah utama pertanyaannya. Knowledge engineer dapat saja menuliskan contoh pertanyaan, berfokus pada jenis pertanyaan, level, dan teknik bertanya. Knowledge engineer meyakinkan pakar domain agar memahami maksud dan tujuan sesi ini dan mendorong pakar untuk bersiap-siap lebih dulu sebelum dilakukan wawancara tersebut. Selama wawancara knowledge engineer mengikuti arahan/panduan dalam melakukan wawancara. Selama wawancara knowledge engineer menggunakan kontrol arah/navigasi untuk mempertahankan struktur wawancara.

4.6.

Metode Pelacakan.

Mengacu pada teknik yang mencoba untuk melacak proses reasoning dari seorang pakar. Ia merupakan pendekatan yang populer diantara para psikolog kognitif, yaitu orang yang tertarik untuk mengetahui jalan pikiran seorang pakar saat sang pakar tersebut mencapai kesimpulan. Knowledge engineer dapat menggunakan proses pelacakan ini untuk menemukan informasi apa yang digunakan dan bagaimana penggunaannya. Metode pelacakan dapat formal maupun informal. Metode formal yang paling umum adalah analisis protokol.

Prosedur Analisis Protokol: Sediakan untuk sang pakar informasi dalam skala penuh yang berhubungan dengan suatu task/tugas. Tanyakan pada pakar untuk memverbalkan (mengucapkan secara lisan tugas) tersebut dalam cara yang sama seperti sang pakar itu menyelesaikannya secara normal, demikian juga minta sang pakar tersebut memverbalkan proses keputusannya dan catat pemverbalan ini di tape. Buatlah statemen-statemen dengan menuliskan protokol verbal tadi. Kumpulkan statemen yang kelihatannya banyak mengandung informasi. Sederhanakan dan tulis kembali statemen yang terkumpul dan susunlah tabel aturan-aturan produksi (production rules) dari statemen tadi. Buatlah serangkaian model dengan menggunakan aturan-aturan produksi tersebut. Keuntungan dan Keterbatasan Analisis Protokol. Advantage Limitations Expert consciously considers decision-making Requires that expert be aware of why he or she heuristics. makes a decision. Expert consciously considers decision Requires that expert be able to categorize major alternatives attributes, values. decision alternatives. Knowledge engineer can observe and analyze Requires that expert be able to verbalize the decision-making behavior. attributes and values of a decision alternative. Knowledge engineer can record, and later Requires that expert be able to reason about the analyze with the expert key decision points. selection of a given alternative. Subjective view of decision making. Explanations may not track with reasoning.


31


4.7.

Pengamatan dan Metode Manual Lainnya.

Pengamatan (observasi). Dalam beberapa kasus, adalah mungkin untuk mengamati pakar saat bekerja di bidangnya. Dalam banyak kasus ini adalah pendekatan yang jelas dan terang dalam akuisisi knowledge. Kesulitannya adalah ia sulit diperkirakan. Contoh, kebanyakan pakar memberikan nasehat kepada beberapa orang, dan kemungkinan bekerja pada beberapa domain secara bersamaan. Observasi yang dilakukan harus mencakup semua aktivitas sang pakar. Sehingga, data yang dikumpulkan jumlahnya besar sekali dimana sebenarnya yang dibutuhkan cuma sedikit. Dalam hal lain, jika kita merekamnya dengan tape atau video, biaya menuliskan rekaman yang panjang itu patut pula dipertimbangkan. Pengamatan yang dapat dipandang sebagai kasus khusus dari protokol, terdiri dari 2 jenis: gerakan motorik dan gerakan mata. Gerakan motorik adalah kinerja fisik sang pakar (misal, berjalan, menggapai sesuatu, berbicara) yang didokumentasikan. Gerakan mata mendokumentasikan dimana sang pakar menetapkan pandangan matanya. Pengamatan digunakan utamanya sebagai cara mendukung protokol verbal. Biasanya mahal dan memakan waktu. Pelbagai metode manual lainnnya: Case analysis. Critical incident analysis. Commentaries. Conceptual graph. Brainstorming. Prototyping. Multidimensional scaling. Johnson’s hierarchical clustering.

4.8.

Metode Expert-driven.

Ada 2 pendekatan: manual dan dibantu komputer (semiotomatis).

Metode manual: laporan oleh sang pakar itu sendiri. Terkadang dimungkinkan untuk mendapatkan knowledge dari pakar secara manual dengan menggunakan daftar pertanyaan yang dapat diatur sendiri atau laporan yang terorganisasi. Pertanyaan berjenis open-ended (bentuk jawabannya bebas) digunakan untuk mendapatkan knowledge yang memiliki konsep level tinggi. Pertanyaan berjenis close-ended (bentuk jawabannya terbatas) lebih terstruktur dan mudah diisi, tetapi knowledge yang didapat juga terbatas. Sebagai tambahan dalam daftar pertanyaan, pakar mungkin ditanya mengenai catatan aktivitas mereka, persiapan mengajar mereka, atau laporan yang dihasilkan mengenai aktivitas penyelesaian masalah mereka. Laporan pakar dan daftar pertanyaan memunculkan sejumlah masalah seperti di bawah ini: 1. Secara esensial mengharuskan pakar bertindak sebagai knowledge engineer, tanpa pelatihan untuk menjadi knowledge engineer. 2. Laporan tersebut cenderung memiliki derajat bias yang tinggi; biasanya merefleksikan opini sang pakar mengenai bagaimana suatu task/tugas seharusnya dikerjakan daripada bagaimana yang sebenarnya dikerjakan. 3. Pakar sering menjelaskan ide baru dan belum teruji, serta strategi-strategi yang telah direnungkannya tetapi hal-hal ini tak termasuk dalam perilaku pengambilan keputusan mereka. Juga mereka sering mencampuradukkan pengalaman lalu, perilaku sesungguhnya, dan perilaku “ideal” masa mendatang. 4. Laporan pakar merupakan usaha yang memakan waktu, dan para pakar akan segera kehilangan ketertarikan pada suatu hal. Kualitas informasi yang dicapai akan terus berkurang di saat laporan terus berkembang. 5. Pakar harus cakap dalam teknik diagram alur atau proses dokumentasi lainnya. 6. Pakar mungkin lupa pada bagian khusus tertentu dari suatu knowledge (yang mungkin menimbulkan kerancuan). 7. Pakar kelihatannya tak terlalu jelas dalam mengasosiasikan suatu kejadian (yang mungkin menimbulkan bias yang tak tentu).


32


Pendekatan bantuan komputer. Tujuan dari dukungan terkomputerisasi ke pakar adalah mengurangi atau menghilangkan masalah potensial yang sudah dibahas pada pendekatan manual sebelumnya, khususnya pada masalah bias dan kerancuan. Tool akuisisi knowledge yang cerdas digunakan untuk menghaluskan dan mengkoreksi knowledge yang telah ada. Teknik pemodelan visual sering digunakan untuk menyusun model domain awal.

4.9.

Repertory Grid Analysis.

Pengalaman sering berdasarkan persepsi, wawasan, dan intuisi. Sehingga banyak pakar kesulitan dalam mengekspresikan reasoning-nya. Pakar sering bingung membedakan fakta dan faktor yang sesungguhnya mempengaruhi pengambilan keputusan. Untuk mengatasinya, diturunkan dari bidang Psikologi, digunakan pendekatan yang disebut dengan classification interview (wawancara terklasifikasi). Karena terstruktur saat diaplikasikan ke teknologi, metode ini biasanya dibantu dengan komputer. Metode utamanya disebut dengan Repertory Grid Analysis (RGA). RGA berdasarkan model yang diusulkan oleh Kelly mengenai pemikiran manusia yang disebut dengan Personal Construct Theory. Berdasarkan teori ini, setiap orang dipandang sebagai “ilmuwan pribadi” yang mencari untuk memperkirakan dan mengontrol kejadian-kejadian dengan menyusun teori, mengetes hipotesis, dan menganalisis hasil percobaan. Knowledge dan persepsi mengenai dunia (atau mengenai domain atau suatu masalah) diklasifikasikan dan dikategorisasikan oleh setiap individu sebagai model personal, model perseptual. Berdasarkan model yang dikembangkan tadi, setiap individu mampu mengantisipasi dan lalu beraksi berdasarkan antisipasi ini. Model personal ini sesuai dengan cara pandang seorang pakar dalam bekerja; ia adalah gambaran dari pengembangan dan penggunaan knowledge dari sang pakar, dan selanjutnya ia layak untuk ES.

Cara kerja RGA. 1. Pakar mengidentifikasi objek-objek penting dalam domain kepakaran. Contoh: bahasa komputer (LISP, C, COBOL) adalah objek dalam kasus memilih bahasa komputer. 2. Pakar mengidentifikasi atribut penting yang diperlukan dalam pengambilan keputusan dalam domain. Contoh: ketersediaan paket komersial dan kemudahan dalam pemrograman adalah hal penting dalam kasus memilih bahasa komputer. 3. Untuk setiap atribut, pakar ditanyai untuk membuat skala bipolar dengan pembedaan karakteristik (sifat) dan lawannya. Contoh: dalam kasus memilih bahasa komputer, disajikan dalam tabel seperti di bawah ini. Attributes Trait Opposite Availability Widely available Not available Ease of programming High Low Training time Low High Orientation Symbolic Numeric 4. Pewawancara mengambil 3 objek sembarang dan bertanya: atribut dan sifat apakah yang membedakan 2 dari 3 objek ini? Jawaban ini diterjemahkan pada skala 1-3 (atau 1-5). Langkah ini diulang untuk beberapa objek trio lagi. Contoh: jika kumpulannya adalah LISP, PROLOG, dan COBOL; sang pakar mungkin menekankan pada “orientasi”. Lalu sang pakar mengatakan bahwa LISP dan PROLOG bersifat simbolik, sedangkan COBOL bersifat numerik. Dapat diisajikan dalam tabel seperti di bawah ini: Attribute Orientation Ease of Training Time Availability Programming Trait Symbolic (3) High (3) High (1) High (3) Opposite Numeric (1) Low (1) Low (3) Low (1) LISP 3 3 1 1 PROLOG 3 2 2 1 C 2 3 2 2 COBOL 1 2 1 3 Penggunaan RGA dalam ES. Contohnya adalah: Expertise Transfer System (ETS), Aquinas, dan Kriton. Sistem Berbasis Pengetahuan – Irfan Subakti

33


4.10.

Dukungan Knowledge Engineer.

Sejumlah tool akuisisi dan encoding menghemat waktu yang diperlukan (dan/atau level ketrampilan) oleh knowledge engineer. Namun demikian, knowledge engineer dalam kasus ini tetap memainkan peran penting dalam proses tersebut, seperti terlihat pada gambar di bawah ini: Expert I

Expert II Advise

Knowledge Acquisition

Manage Acquisition

Knowledge Base Edit

Encoding

Computer Knowledge Base

Manage Encoding

Knowledge Engineer

Edit

Validate ES Tools

Client I

Train

Client II

Alat bantu akusisi knowledge. Editor dan antarmuka. Fasilitas untuk menjelaskan (explanation). Revisi dari basis pengetahuan. Pictorial Knowledge Acquisition (PIKA). Contoh: TEIRESIAS, EMYCIN, dan lain-lain. Alat bantu akuisisi knowledge terintegrasi. Masing-masing alat bantu yang sudah disebut diatas, biasanya bekerja sendiri-sendiri. Namun ada kecenderungan untuk mengintegrasikan semua alat bantu tadi. Contoh: Auto-Intelligence, KADS (Knowledge Acquisition and Documentation System). Front-end Tools. Contoh: Knowledge Analysis Tool (KAT) mengkonversi knowledge ke format rule khusus untuk satu tool yang disebut Level5. NEXTRA adalah tool serupa yang membantu knowledge engineer untuk meng-kode rule dalam Nexpert Object.

4.11.

Induksi Rule, Case-based Reasoning, dan Komputasi Syaraf.

Metode untuk mendapatkan knowledge yang manual dan semiotomatis ternyata lamban dan mahal, ternyata masih ditambahi lagi dengan kekurang-kekurangan seperti ini: Sulit untuk memvalidasi knowledge yang diperoleh. Seringkali terdapat korelasi lemah diantara laporan verbal dan perilaku mental. Dalam situasi tertentu pakar tak mampu menyediakan keseluruhan hal tentang bagaimana suatu keputusan tersebut mereka buat. Sistem Berbasis Pengetahuan – Irfan Subakti

34


Kualitas suatu sistem banyak tergantung pada kualiatas pakar dan knowledge engineer. Pakar tak memahami teknologi ES. Knowledge engineer tak memahami, dalam banyak kasus, sifat dasar bisnis.

Sehingga diperlukan pengembangan metode akuisisi knowledge yang dapat mengurangi atau menghilangkan kebutuhan dari 2 partisipan ini. Metode ini disebut dengan akuisisi knowledge yang dibantu oleh komputer, atau akuisisi knowledge otomatis, dengan tujuan: Meningkatkan produktivitas pekerjaan knowledge engineer (mengurangi biaya). Mengurangi level ketrampilan yang diperlukan oleh knowledge engineer. Menghilangkan (atau mengurangi secara drastis) kebutuhan akan pakar. Menghilangkan (atau mengurangi secara drastis) kebutuhan akan knowledge engineer. Meningkatkan kualitas knowledge yang didapat. Induksi Rule Otomatis. Induksi berarti proses reasoning dari hal khusus ke hal umum. Dalam ES istilah ini mengacu pada proses dimana rule dihasilkan oleh program komputer dari contoh kasus. Sistem induksi rule menyediakan contoh-contoh masalah (disebut dengan training set/kumpulan pelatihan) dimana hasilnya diketahui. Setelah ia diberi cukup contoh, sistem induksi rule dapat membuat rule yang sesuai dengan contoh kasus. Rule ini lalu dapat digunakan untuk membantu kasus lain dimana hasilnya tak diketahui. Jantung dari sistem induksi rule adalah algoritma yang digunakan untuk menginduksi rule dari contoh-contoh. Contoh dari algoritma induksi ini adalah: ID3. Pertama kali ID3 mengkonversi matriks knowledge ke dalam pohon keputusan. Atribut yang tak relevan dihilangkan dan atribut yang relevan diorganisasi dalam cara yang efisien. Contoh dari induksi rule sederhana dapat dilihat pada pekerjaan petugas bagian pinjaman di bank. Permintaan akan pinjaman meliputi informasi peminta pinjaman, seperti tingkat pendapatan, aset, usia dan jumlah tanggungannya. Ini merupakan atribut, atau karakteristik dari peminta pinjaman. Jika kita mencatat beberapa contoh kasus, semuanya dengan keputusan final, kita akan dapatkan situasi yang dapat digambarkan seperti tabel di bawah ini: Attributes Annual Number of Applicant Income ($) Assets ($) Age Dependents Decision Mr. White 50,000 100,000 30 3 Yes Ms. Green 70,000 None 35 1 Yes Mr. Smith 40,000 None 33 2 No Ms. Rich 30,000 250,000 42 0 Yes Dari kasus diatas, adalah mudah mendapatkan 3 rule ini: 1. Jika pendapatannya $70,000 atau lebih, setujui permintaan pinjamannya. 2. Jika pendapatannya $30,000 atau lebih, umurnya paling sedikit 40 tahun, asetnya melebihi $249,000, dan ia tak mempunyai tanggungan, setujui permintaan pinjamannya. 3. Jika pendapatannya diantara $30,000 dan $50,000 dan asetnya paling sedikit $100,000, setujui permintaan pinjamannya. Keuntungan dari induksi rule. Dengan menggunakan induksi rule maka ES dapat digunakan untuk hal-hal yang lebih rumit, dan lebih menguntungkan secara komersial. Keuntungan lainnya adalah pembangun (builder) tak harus menjadi knowledge engineer. Ia bisa berasal dari seorang pakar atau analis sistem. Ini berarti tak hanya menghemat waktu dan uang, tapi juga menyelesaikan kesulitan yang berhubungan dengan knowledge engineer yang merupakan orang luar yang tak familier dengan “bisnis”. Mesin induksi juga menawarkan kemungkinan mendeduksi knowledge baru. Dimungkinkan mendaftar semua faktor yang mempengaruhi keputusan, tanpa pemahaman akan dampaknya, dan untuk menginduksi rule yang bekerja dengan baik. Sekali rule dihasilkan, maka ia dapat dikaji ulang oleh pakar dan bila diperlukan bisa dimodifikasi. Keuntungan besar dari induksi rule adalah ia meningkatkan proses pemikiran dari sang pakar.


35


Kesulitan dalam implementasi. Beberapa program induksi yang dapat menghasilkan rule, mungkin tak mudah bagi orang untuk memahaminya, disebabkan cara program mengklasifikasikan atribut masalah dan propertinya mungkin tak sesuai dengan cara manusia melakukan hal itu. Program induksi rule tak memilih atribut. Sang pakar tetap harus memilih atribut mana yang signifikan; misal, faktor penting untuk menyetujui pinjaman. Proses pencarian dalam induksi rule berdasarkan algoritma khusus yang menghasilkan pohon keputusan yang efisien, yang mengurangi jumlah pertanyaan yang harus ditanyakan sebelum suatu kesimpulan dapat dicapai. Ada beberapa alternatif algoritma yang lain dan mereka berbeda-beda dalam proses dan kemampuan. Metode ini baik hanya untuk rule-based (berbasis aturan), masalah berjenis klasifikasi, khususnya pada jenis ya0tidak. (Namun demikian, banyak masalah dapat diurai atau dipilahpilah sehingga menjadi kategori klasifikasi). Jumlah atribut harus cukup kecil. Kalau atributnya lebih dari 15, mungkin diperlukan mainframe. Batas atas jumlah atribut ini dengan adanya perkembangan hardware dan software komputer sekarang ini sudah meningkat jauh. “Kecukupan” jumlah contoh-contoh yang diperlukan bisa sangat besar. Kumpulan contoh-contoh harus di-“bersihkan”; sebagai contoh, kasus-kasus yang merupakan pengecualian dari rule harus dihilangkan dulu. Metode ini terbatas pada situasi yang tertentu (deterministik). Masalah utama dengan metode ini adalah pembangun (builder) tak tahu lebih jauh apakah jumlah contoh-contoh sudah mencukupi dan apakah algoritmanya sudah cukup baik. Induksi interaktif. Kombinasi dari pakar yang didukung oleh komputer disebut dengan induksi interaktif. Ia dapat menangkap knowledge dari pakar melalui wawancara interaktif, menyaring knowledge, dan lalu secara otomatis menghasilkan knowledge berbasis rule. Case-based reasoning. Pendekatan pembangunan ES dengan mengakses pengalaman-pengalaman penyelesaian masalah (studi kasus) untuk memperkirakan solusi dalam penyelesaian masalah di masa depan. Koleksi dari kasus-kasus historis dan penyelesaiannya membentuk knowledge base. Pengambil keputusan memanggil kembali kasus-kasus sebelumnya yang mungkin identik dengan kasus baru, walaupun dalam banyak hal tak bisa identik. Mereka mungkin menunjukkan sedikit kemiripan dengan kasus baru, tetapi walaupun sedikit hal itu tetap saja berguna. Akuisisi knowledge sangat mudah dilakukan, karena data historis berada dalam file dan hanya memerlukan sedikit verifikasi dari pakar. Komputasi Syaraf. Pendekatan penyelesaian masalah yang lain dimana data historis digunakan untuk menurunkan solusi ke masalah yang baru. Berbeda dengan case-based reasoning, komputasi syaraf bekerja dalam domain yang cukup sempit menggunakan pendekatan pengenalan pola. Untuk itu diperlukan sejumlah besar kasuskasus historis. Akuisisi knowledge menjadi sederhana, karena kasus-kasus historis dan penyelesaiannya biasanya tersedia dalam database perusahaan. Sekali lagi, konsultasi kepada pakar dapat dilakukan selama validasi dan verifikasi, tetapi peran mereka sudah jauh berkurang, dan juga usaha dan pengeluaran yang harus dilakukan untuk akuisisi knowledge.

4.12.

Memilih Metode yang Sesuai.

Tujuan sistem akuisisi knowledge ideal adalah: Mengarahkan interaksi dengan pakar tanpa intervensi knowledge engineer. Dapat diaplikasikan untuk domain masalah yang tak terbatas, atau paling tidak banyak klas. Kemampuan tutorial untuk menghilangkan kebutuhan akan pelatihan awal bagi sang pakar. Kemampuan untuk menganalisis pekerjaan yang sedang berlangsung untuk mendeteksi ketidakkonsistenan dan kesenjangan di dalam knowledge. Kemampuan untuk menggabungkan bermacam-macam sumber knowledge. Antarmuka manusia (misal, percakapan biasa) yang membuat penggunaan sistem terasa nyaman dan menarik. Sistem Berbasis Pengetahuan – Irfan Subakti

36


Kemampuan dalam antarmuka secara mudah dengan pelbagai tool ES yang berbeda yang sesuai dengan domain permasalahan.

4.13.

Akuisisi Knowledge dari Banyak Pakar.

Di bawah ini disajikan keuntungan dan masalah yang terjadi dari partisipasi banyak pakar: Benefits Problems On the average, fewer mistakes by a group of Groupthink phenomena. experts than by a single expert. Several experts in group eliminate need for Fear on the part of some domain experts of using world-class expert (who is difficult to get senior experts or a supervisor (lack of and expensive). confidentiality). Wider domain than a single expert’s. Compromising solutions generated by a group with conflicting opinions. Synthesis of expertise. Waste of time in group meeting. Enhanced quality from synergy among experts. Difficulties in scheduling the experts. Dominating experts (controlling, not letting others speak).

Skenario dari banyaknya pakar yang terlibat. Pakar individu. Pakar utama dan pakar pendamping. Grup kecil. Panel. Metode penanganan banyak pakar. Beberapa pendekatan utama dalam hal mengintegrasikan opini dari banyak pakar adalah: Padukan beberapa jalur reasoning melalui metode konsensus. Gunakan pendekatan analitis. Jagalah jalur reasoning agar selalu jelas dan pilihlah jalur reasoning yang spesifik berdasarkan situasi tertentu. Otomatisasikan prosesnya. Uraikan knowledge yang sudah didapat ke dalam sumber knowledge khusus (blackboard systems). Jadi metode yang dipakai adalah: Metode konsensus. GDSS. Pendekatan analitis. Jalur reasoning spesifik. Proses terotomatisasi. Blackboard Systems.

4.14.

Validasi dan Verifikasi Knowledge Base.

Akuisisi knowledge melibatkan aspek-aspek kontrol kualitas yang muncul dalam istilah evaluasi, validasi, dan verifikasi. Evaluasi adalah konsep yang luas. Tujuannya adalah menilai keseluruhan nilai dari ES. Sebagai tambahan untuk menilai pada level kinerja yang dapat diterima, ia menganalisis jika sistem tersebut dapat dipakai, efisien, dan efektif dalam hal biayanya. Validasi adalah bagian dari evaluasi yang berhubungan dengan kinerja dari sistem (misal, dibandingkan dengan yang dilakukan pakar). Singkatnya, validasi mengacu pada pembangunan sistem yang “benar”; sehingga, menandakan bahwa sistem bekerja dengan level akurasi yang dapat diterima. Verifikasi mengacu pada pembangunan sistem dengan “benar”; menandakan bahwa sistem diimplementasikan dengan benar sesuai dengan spesifikasinya. Di bawah ini disajikan tabel mengenai ukuran-ukuran validasi: Measure (Criteria) Description Accuracy How well the system reflects reality; how correct the knowledge is in the knowledge base Adaptability Possibilities for future development, changes Adequacy (or completeness) Portion of the necessary knowledge that is included in the knowledge base Appeal How well the knowledge base matches intuition and Sistem Berbasis Pengetahuan – Irfan Subakti

37


Measure (Criteria) Breadth Depth Face validity Generality Precision Realism Reliability Robustness Sensitivity Technical and operational validity Turing test Usefulness Validity

4.15.

Description stimulates thought and practicability How well the domain is covered Degree of the detailed knowledge Credibilitiy of knowledge Capability of a knowledge base to be used with a broad range of similar problems Capability of the system to replicate particular system parameters; consistency of advise; coverage of variables in knowledge base Accounting for relevan variables and relations; similarity to reality Fraction of the ES predictions that are empirically correct Sensitivity of conclusions to model strukture Impact of changes in the knowledge base on quality of outputs Goodness of the assumed assumptions, context, constraints, and conditions, and their impact on other measures Ability of a human evaluator to identify if a given conclusion is made by an ES or by a human expert How adequate the knowledge is (in terms of parameters and relationships) for solving correctly Knowledge base’s capability of producing empirically correct predictions

Analisis, Kodifikasi, Dokumentasi, dan Pendiagraman.

Knowledge yang sudah terkumpul harus dianalisis, dikodekan, dan didokumentasikan. Langkah-langkah prosesnya adalah: transkripsi, pengindeksan frase, pengkodean knowledge, dan dokumentasi. Pendiagraman knowledge adalah pendekatan grafis untuk meningkatkan proses akuisisi knowledge. Ia terdiri dari deskripsi hirarki, top-down dari tipe-tipe utama knowledge yang digunakan untuk menjelaskan fakta dan strategi reasoning untuk penyelesaian masalah dalam ES. Tipe-tipe itu adalah objek, kejadian, kinerja, dan metaknowledge. Pendiagraman juga menjelaskan keterkaitan dan interaksi diantara pelbagai tipe knowledge.

4.16.

Akuisisi Knowledge Numerik dan Terdokumentasi.

Akuisisi knowledge numerik. Metode akuisisi knowledge tradisional didesain utamanya berhubungan dengan representasi simbolik dari suatu knowledge. Ada saran untuk mengkomplemen akuisisi knowledge simbolik dengan numerik. Metodologinya disebut dengan abduction (“penculikan”), yang menangani hubungan numerik, hubungan yang kompleks, dan tak pasti. Metodologi ini diimplementasikan ke dalam proses yang disebut proses akuisisi knowledge campuran. Akuisisi knowledge terdokumentasi. Dalam banyak kasus, knowledge dapat diperoleh dari sumber-sumber yang lain, selain dari pakar manusia. Keuntungan utama dari pendekatan ini adalah: tak diperlukan adanya seorang pakar. Pendekatan ini digunakan dalam knowledge-based systems (sistem berbasis pengetahuan) yang perhatiannya ditujukan untuk menangani informasi yang berjumlah besar atau rumit daripada kepakaran kelas dunia. Contohnya adalah pencarian diantara manual kebijakan perusahaan atau dari katalog perusahaan. Pendekatan ini memiliki potensi besar untuk otomatisasi. Knowledge terdokumentasi kebanyakan mudah (dan murah) di-scan dan ditransfer ke database komputer. Kemudian analisis dari knowledge ini dapat dilakukan secara manual, tetapi juga bisa dilakukan dengan teknologi AI (diharapkan dengan kombinasi pemahaman pembicaraan dan ES). Sehingga ES dapat digunakan untuk membangun ES yang lainnya. ES dapat men-scan database dan mendigitalkan buku, jurnal, dan majalah, dan kemampuan ini bisa ditingkatkan. Sistem Berbasis Pengetahuan – Irfan Subakti

38


Data yang tersimpan dalam sistem komputer lain dapat diambil kembali secara elektronis untuk membuat atau memperbarui knowledge base dari ES, semuanya dengan tanpa melibatkan knowledge engineer atau pakar.

4.17.

Kesimpulan.

Rekayasa knowledge melibatkan akuisisi, representasi, reasoning (inference), dan penjelasan (explanation) dari knowledge. Knowledge tersedia dari banyak sumber, baik itu yang terdokumentasi maupun yang tidak (para pakar). Knowledge bisa sempit, menjelaskan relasi input-output sempit; atau luas, menjelaskan interaksi yang rumit dan operasi sistem. Akuisisi knowledge, khususnya dari pakar manusia, adalah tugas yang sulit disebabkan masalah komunikasi dan pemrosesan informasi. Proses akuisisi knowledge terbagi atas 5 tahapan: identifikasi, konseptualisasi, formalisasi, implementasi, dan testing. Metode akuisisi knowledge dapat dibagi menjadi manual, semiotomatis, dan otomatis. Pendekatan manual utama adalah wawancara. Metode wawancara berkisar dari yang sama sekali tak terstruktur sampai yang strukturnya tinggi. Proses reasoning dari para pakar dapat dilacak dengan beberapa metode. Analisis protokol adalah metode utama yang digunakan dalam AI. Walaupun dimungkinkan untk mengamati pakar dalam pekerjaannya, pengamatan ini terbatas dalam hal skupnya. Dicoba untuk mengurangi atau menghilangkan peran knowledge engineer dengan menyediakan tool manual dan/atau tool terkomputerisasi ke pakar agar bisa mengakuisisi knowledge sendiri. RGA adalah metode yang paling banyak diaplikasikan untuk wawancara semiotomatis, digunakan dalam AI. Beberapa paket software yang menggunakan RGA dapat meningkatkan proses akuisisi knowledge. Bermacam tool produktivitas tersedia buat akuisisi knowledge (misal, editor, antarmuka, pendiagraman). Induksi rule menguji kasus-kasus historis dan menghasilkan rule yang digunakan atas dasar rekomendasi yang pasti. Induksi rule dapat digunakan oleh system engineer, pakar, atau pun pembangun (builder) sistem yang lain. Beberapa prosedur tersedia untuk memilih metode yang sesuai dalam akuisisi knowledge untuk situasi khusus tertentu. Ada keuntungan disamping ada keterbatasan dan masalah dalam penggunaan beberapa/banyak pakar untuk membangun knowledge base. 4 skenario yang mungkin dalam menggunakan banyak kepakaran adalah: pakar individu, pakar utama dan pakar pendamping, grup kecil, dan panel. Metode utama yang berkenaan dengan pelibatan banyak pakar adalah metode konsensus, pendekatan analitis, pemilihan jalur reasoning yang sesuai, otomatisasi proses, dan blackboard system. Validasi dan verifikasi knowledge base merupakan faktor penentu keberhasilan dalam implementasi ES. Lebih dari selusin ukuran-ukuran spesifik yang tersedia untuk menentukan validitas knowledge. Metode akuisisi knowledge otomatis lebih mudah untuk memvalidasi dan memverifikasi. Knowledge yang sudah didapat harus dianalisis dan dikodekan sebelum direpresentasikan dalam komputer. Case-based reasoning, komputasi syaraf, dan pelbagai tool pembelajaran mesin dapat lebih meningkatkan task/tugas dari akuisisi knowledge.


39

Bab 5 Knowledge-Based Expert Systems

BAB 5 KNOWLEDGE-BASED EXPERT SYSTEMS 5.1.

Pengertian.

5.2.

Rules dan Rule Chaining.

Knowledge-Based Expert Systems (KBS) pengertiannya serupa dengan Expert Systems (ES), yaitu program pemberi advis/nasehat yang terkomputerisasi yang ditujukan untuk menirukan atau menggantikan proses reasoning dan pengetahuan (knowledge) dari para pakar dalam menyelesaikan permasalahan masalah yang spesifik. Karakteristiknya: Dapat belajar dari pengalaman. Mentransfer knowledge dari satu domain ke domain yang lain. Dapat memberikan proses reasoning dalam pelbagai level. Menggunakan tool-tool: heuristics (rule of thumb), mathematical models, simulations.

antecedents consequents

IF (antecedents) THEN consequents Contoh: Mengidentifikasi binatang. Sebuah robot dapat mempersepsikan fitur-fitur dasar: color, size, has hair, gives milk. Tetapi, kemampuannya mengidentifikasi obyek berdasarkan fitur-fitur tersebut diatas adalah terbatas. Dia dapat membedakan binatang-binatang dari obyek yang lain, tetapi ia tak dapat menggunakan fakta bahwa sebagian binatang yang memiliki leher panjang disebut dengan jerapah. Rule-nya: Z1 IF ?x has hair THEN ?x is a mammal Z2 IF ?x gives milk THEN ?x is a mammal Z3 IF ?x has feathers THEN ?x is a bird Z4 IF ?x flies ?x lays eggs THEN ?x is a bird Z5 IF ?x is a mammal ?x eats meat THEN ?x is a carnivore Z6 IF ?x is a mammal ?x has pointed teeth ?x has claws ?x has forward-pointing eyes THEN ?x is a carnivore Z7 IF ?x is a mammal ?x has hoofs THEN ?x is an ungulate Z8 IF ?x is a mammal ?x chews end THEN ?x is an ungulate Z9 IF ?x is a carnivore ?x has tawny color ?x has dark spots THEN ?x is a cheetah Z10 IF ?x is a carnivore ?x has tawny color ?x has black strips THEN ?x is a tiger 40



Z11

Z12

Z13

Z14

Z15

IF ?x is a ungulate ?x has long neck ?x has long legs ?x has tawny color ?x has dark spots THEN ?x is a giraffe IF ?x is a ungulate ?x has white color ?x has black strips THEN ?x is a zebra IF ?x is a bird ?x does not fly ?x has long legs ?x has long neck ?x has black and white THEN ?x is a ostrich IF ?x is a bird ?x does not fly ?x swims ?x has black and white THEN ?x is a penguin IF ?x is a bird ?x is a good flyer THEN ?x is an albatross

Sistem Deduksi terdiri atas: Forward chaining. Backward chaining.

5.3.

Forward dan Backward Chaining.

Forward Chaining. has hair

Z1

fired 1st

is a mammal deduced assertion

chews end

assertions

Z8

fired 2nd

is an ungulate

has long legs has a long neck has a tawny color

Z11

fired 3rd

is a giraffe

has dark spots

Æ Identify an animal Æ Until no rule produces a new assertion or the animal is identified Æ For each rule: - Try to support each of the rule’s antecedents by matching it to known facts. - If all the rule’s antecedents are supported, assert the consequent rules there is an identical assertion already. - Report for all matching and instantiation alternatives.


41


Backward chaining. has forward-pointing eyes has claws has pointed teeth

Z6

4th rule used

is a carnivore

is a mammal has hair

eats meat

Z1

3rd rule used

Z5

2nd rule used

is a carnivore

has a tawny color has dark spots

Z9

1st rule used

is a cheetah

Æ Repeat until all hypothesis have been tried and none have been supported or until the animal is identified. Æ For each hypothesis, Æ For each rule whose consequent matches the current hypothesis, Try to support each of the rule’s antecedents by matching it to assertions. If all the rule’s antecedents are supported, announce success And conclude that the hypothesis is true. Note: The chaining ends unsuccessfully if any required antecedent assertions cannot be supported. Mana yang dipilih, forward ataukah backward chaining? Bagaimanakah hubungan antara rule dengan fakta-faktanya, sehingga didapatkan konklusinya. Jika masalah yang dihadapi lebih dekat ke fan out (sekumpulan fakta yang bisa menuju ke banyak konklusi), maka pilihlah backward chaining. Jika masalah yang dihadapi lebih dekat ke fan in (sekumpulan hipotesis yang bisa menuju ke banyak pertanyaan), maka pilihlah forward chaining. Banyak cara untuk mendapatkan sedikit konklusi Æ forward chaining. Sedikit cara untuk mendapatkan banyak konklusi Æ backward chaining. Jika kita belum mendapatkan pelbagai fakta, dan kita tertarik hanya pada satu konklusi yang mungkin, maka digunakanlah backward chaining. Jika kita benar-benar sudah mendapatkan pelbagai fakta, dan kita ingin untuk mendapatkan konklusi dari fakta-fakta itu, maka digunakanlah forward chaining. Tipe sistem yang dapat dicari dengan forward chaining: 1. Sistem yang dipresentasikan dengan satu atau beberapa kondisi. 2. Untuk setiap kondisi, sistem mencari rule-rule dalam knowledge base untuk rule-rule yang berkorespondensi dengan kondisi dalam bagian IF. 3. Setiap rule dapat menghasilkan kondisi baru dari konklusi yang diminta pada bagian THEN. Kondisi baru ini ditambahkan ke kondisi lain yang sudah ada. 4. Setiap kondisi yang ditambahkan ke sistem akan diproses. Jika ditemui suatu kondisi, sistem akan kembali ke langkah 2 dan mencari rule-rule dalam knowledge base kembali. Jika tidak ada konklusi baru, sesi ini berakhir. Tipe sistem yang dapat dicari dengan backward chaining: 1. Sistem yang dipresentasikan dengan satu atau beberapa kondisi. 2. Untuk setiap konklusi, sistem mencari rule-rule dalam knowledge base untuk rule-rule yang berkorespondensi dengan konklusi pada bagian THEN. 3. Setiap konklusi dihasilkan dari kondisi-kondisi yang terdapat pada bagian IF. Selanjutnya kondisi-kondisi tersebut menjadi konklusi baru yang dimasukkan ke stack di atas konklusi yang sudah ada. 4. Setiap konklusi yang ditambahkan ke sistem akan diproses. Jika ditemui suatu konklusi, sistem akan kembali ke langkah 2 dan mencari rule-rule dalam knowledge base kembali. Jika tidak ada konklusi baru, sesi ini berhenti. Sistem Berbasis Pengetahuan – Irfan Subakti

42


5.4.

Desain Implementasi Forward dan Backward Chaining.

Forward chaining. 1. Identifikasi kondisi. 2. Variabel kondisi ditempatkan pada Conclusion Var. Queue dan nilainya dicatat pada Variable List. 3. Diadakan pencarian pada Clause Var. List untuk variabel yang namanya sama dengan nama pada awal queue. Jika ketemu, nomor rule dan 1 diisikan pada Clause Var. Pointer. Jika tak ketemu, ke langkah 6. 4. Setiap variabel dalam IF clause dari rule yang belum diisi, selanjutnya diisi. Variabel-variabel ditempatkan dalam Clause Var. List. Jika semua clause benar kondisinya, bagian THEN dijalankan. 5. Pengisian bagian THEN pada variabelnya ditempatkan pada bagian belakang di Conclusion Var. Queue. 6. Jika tak ada lagi statemen IF yang mengandung variabel yang berada di awal Conclusion Var. Queue, maka variabel tersebut dihapus. 7. Jika tak ada lagi variabel pada Conclusion Var. Queue, pencarian berakhir; jika masih ada variabel yang lain, kembali ke langkah 3. Backward chaining. 1. Identifikasi konklusi. 2. Cari pada Conclusion List untuk pengisian pertama kali dari nama konklusi. Jika ketemu, tempatkan rule pada Conclusion Stack berdasarkan nomor rule dan 1 yang merepresentasikan nomor clause. Jika tak ketemu, beritahu user bahwa jawaban tersebut tak ada. 3. Isi IF clause (yaitu, setiap variabel kondisi) dari statement. 4. Jika satu dari variabel pada IF clause belum diisi, yang diindikasikan oleh Var. List, dan bukan merupakan variabel konklusi, yaitu tak ada dalam Conclusion List, tanyakan user untuk memasukkan suatu nilai. 5. Jika satu dari clause adalah variabel konklusi, tempatkan nomor rule dari variabel konklusi di top of stack dan kembali ke langkah 3. 6. Jika statement pada top of stack tak dapat di-instantiated menggunakan statement IF-THEN yang ada, hapus dari top of stack dan cari pada Conclusion List untuk pengisian lain dari nama variabel konklusi. 7. Jika suatu statement ditemukan, kembali ke langkah 3. 8. Jika tak ada konklusi yang tersisa pada Conclusion Stack, rule untuk konklusi sebelumnya adalah salah. Jika tak ada konklusi sebelumnya, maka beritahu user jawaban tak ditemukan. Jika ada konklusi sebelumnya, kembali ke langkah 6. 9. Jika rule pada top of stack dapat di-instantiated, hapus rule tersebut dari stack. Jika ada variabel konklusi lain di bawahnya (pada stack), increment nomor clause, dan untuk clause yang tersisa kembali ke langkah 3. Jika tak ada variabel konklusi lain di bawahnya, didapatkan jawabannya.


43


Di bawah adalah gambaran dari struktur program implementasi dari forward dan backward chaining. Base Variable List HeadBase

BaseVarList

1

2

3

RuleNumber: 10

20

50

50

Variable: interest

interest

fedint

fedmon

Symbol: =

=

=

=

Value: fall

rise

fall

add interest

TVariable: stock

stock

interest

TSymbol: =

=

=

=

TValue: rise

fall

fall

fall

ClauseNo: 1

1

1

2

Next

Conclusion Variable Queue HeadConVar

ConclusionVarQ

1

1-2-3:

2

3

Out

in :1-2-3

Conclusion Stack HeadConStack

ConclusionStack

1

2

3

in :1-2-3 out: 3-2-1 VarList FVarList BVarList

Variable List HeadVar

1

2

3

TResult HeadResult

Result

1

2

3


44


Sedangkan flowchart dari program forward dan backward chaining tersebut: Start

Scanner Rules

Buat Base Variable List Inisialisasi Variable List

Ingin Forward Chaining?

Y

Proses Forward Chaining

T

Proses Bacward Chaining

End

Catatan: Base Variable List merupakan pengembangan dari Clause Variable List, tak hanya mencatat hal-hal di bagian IF, tetapi juga mencatat hal-hal di bagian THEN.


45


Kemudian flowchat untuk proses forward chaining-nya itu sendiri dapat dilihat pada diagram ini: Pross Forward Chaining

Scanner Input

T

Proses Kesalahan

Apakah pada bagian IF Base Variable List Input tsb ada? Y Catat variabel ini di Variable List Cari variabel di Base Variable List, catat nomor rule dan jumlah clause-nya Inisial Conclusion Variable Queue

Update Clause Variable Pointer

Apakah variabel clause di Variable List sudah di-instantiated?

T

Instantiate variabel tadi di Variable List

Y

T

Apakah clause pada Base Variable List di bagian IF, sudah terpenuhi semua berdasarkan jumlah clause yang tercatat? Y Apakah variabel di variabel clause memenuhi nilainya dengan variabel di Variable List?

Y

Eksekusi bagian THEN Update Conclusion Variable Queue

Catat variabel tsb di record konklusi dan di Variable List kalau ada variabelnya di situ T

Catat nomor rule dan jumlah clausenya

Y

Apakah variabel ini ada di rule lain yang tersisa pada Base Variable List di bagian IF?

T Remove variabel pertama di Conclusion Variable Queue

Apakah variabel di Conclusion Variable Queue terdapat di Variable List?

T

Tampilkan hasil Forward Chaining dari record konklusi

Y


46

Return


Sedangkan flowchart proses backward chaining-nya adalah sebagai berikut: Proses Backward Chaining

Scanner Input

Apakah pada Base Variable List di bagian THEN, Input tsb ada?

T

Proses Kesalahan

Y

Catat nomor rule dan jumlah clause

Update Conclusion Stack

Y

Apakah variabel di nomor clause pada top of stack sudah diinstantiated di Variable List, atau, Clause Number > Jumlah Clause?

Y

Y Apakah variabel tsb memenuhi variabel di Base Variable List pada nomor rule yang tercatat?

T Apakah variabel ada di Base Variable List di bagian THEN? T

Apakah bagian THEN bisa diekseskusi berdasar jumlah clause yang tercatat?

T

Apakah ada variabel lain yang sama dengan input di Base Variable List di bagian THEN yang lain?

T

Remove variabel di top of Conclusion Stack T

Instantiate variabel tadi di Variable List

Y Catat nomor rule dan jumlah clause

Y Eksekusi bagian THEN

Update Conclusion Stack

Update di Variable List, jika variabel tersebut ada Remove Top of Conclusion Stack

Y

Apakah Conclusion Stack masih ada isinya? T

Apakah variabel di nomor clause pada top of stack sudah diinstantiated di Variable List, atau, Clause Number > Jumlah Clause?

T

Y Tampilkan hasil Backward Chaining, yaitu hasil eksekusi THEN yang terakhir

Return


47


Contoh struktur data dalam program. Type ShortString = String[2]; LongString = String[MaxString]; PTBaseVarList = ^TBaseVarList; TBaseVarList = Record RuleNumber : Word; Variable : LongString; Symbol : ShortString; Value : LongString; TVarible : LongString; TSymbol : ShortString; TValue : LongString; ClauseNo : Word; Next : PTBaseVarList End; PTVarList = ^TVarList; TVarlist = Record Variable : LongString; Sign : Boolean; Symbol : ShortString; Value : LongString; Next : PTVarList End; TClauseVarPointer = Record RuleNumber : Word; ClauseNumber: Word End; TInputUser = Record Variable : LongString; Symbol : ShortString; Value : LongString End; PTResult = ^TResult; TResult = Record Variable : LongString; Symbol : ShortString; Value : LongString; Next : PTResult End; PTConclusionVarQueue = ^TConclusionVarQueue; TConclusionVarQueue = Record Variable : LongString; Next : PTConclusionVarQueue End; PTConclusionStack = ^TConclusionStack; TConclusionStack = Record RuleNumber : Word; ClauseNumber: Word; Next : PTConclusionStack End; Struktur data diatas sesuai dengan bahasa pemrograman Pascal, tetapi mengingat perkembangan yang demikian pesat dewasa ini dalam hal pemrograman berorientasi obyek (Object-oriented Programming), maka anda bisa mengimplementasikan sendiri struktur data di atas dalam bentuk class/object sehingga lebih berdayaguna.


48


Contoh Kasus. (Berdasarkan semua flowchart yang telah diberikan dimuka) Kasus 1. Forward Chaining. Rule yang digunakan : rule 10 if interest = fall then stock = rise rule 20 if interest = rise then stock = fall rule 30 if dollar = fall then interest = rise rule 40 if dollar = rise then interest = fall rule 50 if fedint = fall and fedmon = add then interest = fall INISIALISASI Sebagai langkah awal program adalah men-scanner rule tadi, yang selanjutnya membuat Base Variable List dan meng-inisialisasi Variable List. Dalam Base Variable List, rule-rule tadi disusun sebagai berikut : 10 20 30 40 50 50 interest interest dollar dollar fedint fedmon = = = = = = fall rise fall rise fall add stock stock interest interest interest interest = = = = = = rise fall rise fall fall fall 1 1 1 1 1 2 Inisialiasi Variable List, disini yang dicatat adalah hal-hal di bagian IF (kondisi) Variable Sign Symbol Value interest NI dollar NI fedint NI fedmon NI Sign NI = Not Instantiated, I = Instantiated, Symbol dan Value masih bernilai kosong FORWARD CHAINING 1. Kemudian program akan menanyakan kepada user, hal-hal yang diketahuinya sebagai langkah awal Forward Chaining, dengan sintaks : <symbol> . Misal user menginputkan : fedmon = add 2. Apakah pada bagian IF Base Variable List, input tersebut ada? Ada (di rule nomor 50) 3. Catat variabel ini di Variable List Variable Sign Symbol interest NI dollar NI fedint NI fedmon I =

Value

add

4. Cari variabel di Base Variable List, catat nomor rule dan jumlah clause-nya RuleNumber = 50 Jumlah Clause = 2 Sistem Berbasis Pengetahuan – Irfan Subakti

49


5. Inisial Conclusion Variable Queue fedmon 6. Update Clause Variable Pointer RuleNumber = 50 ClauseNumber = 1 Berarti yang dicek sekarang adalah fedint 7. Apakah variable clause di Variable List sudah di-instantiated? fedint belum di-instantiated (Variable : fedint, Sign : NI) 8. Instantiated variable tadi di Variable List, disini ditanyakan kepada user. Misal user menginputkan : fedint = fall Maka di Variable List dilakukan updating, sebagai berikut : Variable Sign Symbol Value interest NI dollar NI fedint I = fall fedmon I = add 9. Update Clause Variable Pointer RuleNumber = 50 ClauseNumber = 2 Berarti yang dicek sekarang adalah fedmon 10. Apakah variable clause di Variable List sudah di-instantiated? fedmon sudah di-instantiated (Variable : fedmon, Sign : I) 11. Apakah clause pada Base Variable List di bagian IF, sudah terpenuhi semua berdasarkan jumlah clause yang tercatat? Ya, (Jumlah Clause = 2, ClauseNumber = 2) 12. Apakah variabel di variable clause memenuhi nilainya dengan variabel di Variable List? Ya, (fedint = fall dan fedmon = add sebagai variable clause sama nilainya dengan di Variable List : fedint = fall dan fedmon = add) 13. Eksekusi bagian THEN interest = fall 14. Update Conclusion Variable Queue fedmon interest 15. Catat variabel tersebut di record konklusi dan di Variable List kalau ada variabelnya di situ di Result dicatat : interest = fall di Variable List karena variabel interest ada, maka dicatat : Variable Sign Symbol Value interest I = fall dollar NI fedint I = fall fedmon I = add 16. Apakah variabel ini ada di rule lain yang tersisa pada Base Variable List di bagian IF? Tidak, karena RuleNumber = 50 adalah rule terakhir yang ada. 17. Remove variabel pertama di Conclusion Variable Queue fedmon (di-remove) interest Sehingga Conclusion Variable Queue menjadi : interest


50


18. Apakah variabel di Conclusion Variable Queue terdapat di Variabel List? Ya, interest di Conclusion Variable Queue terdapat di Variabel List 19. Catat nomor rule dan jumlah clause-nya RuleNumber = 10 Jumlah Clause = 1 20. Update Clause Variable Pointer RuleNumber = 10 ClauseNumber = 1 21. Apakah variable clause di Variable List sudah di-instantiated? interest sudah di-instantiated (Variable : interest, Sign : I) 22. Apakah clause pada Base Variable List di bagian IF, sudah terpenuhi semua berdasarkan jumlah clause yang tercatat? Ya, (Jumlah Clause = 1, ClauseNumber = 1) 23. Apakah variabel di variable clause memenuhi nilainya dengan variabel di Variable List? Ya, (interest = fall sebagai variable clause sama nilainya dengan di Variable List : interest = fall) 24. Eksekusi bagian THEN stock = rise 25. Update Conclusion Variable Queue interest stock 26. Catat variabel tersebut di record konklusi dan di Variable List kalau ada variabelnya di situ di Result dicatat : stock = rise di Variable List karena variabel stock tak ada, maka tidak dicatat 27. Apakah variabel ini ada di rule lain yang tersisa pada Base Variable List di bagian IF? Ya, ada di rule 20 (yaitu : interest = rise) 28. Catat nomor rule dan jumlah clause-nya. RuleNumber = 20 Jumlah Number = 1 29. Update Clause Variable Pointer RuleNumber = 20 ClauseNumber = 1 30. Apakah variable clause di Variable List sudah di-instantiated? interest sudah di-instantiated (Variable : interest, Sign : I) 31. Apakah clause pada Base Variable List di bagian IF, sudah terpenuhi semua berdasarkan jumlah clause yang tercatat? Ya, (Jumlah Clause = 1, ClauseNumber = 1) 32. Apakah variabel di variable clause memenuhi nilainya dengan variabel di Variable List? Tidak, (interest = rise sebagai variable clause tidak sama nilainya dengan di Variable List : interest = fall) 33. Apakah variabel ini ada di rule lain yang tersisa pada Base Variable List di bagian IF? Tidak


51


34. Remove variabel pertama di Conclusion Variable Queue interest (di-remove) stock Sehingga Conclusion Variable Queue menjadi : stock 35. Apakah variabel di Conclusion Variable Queue terdapat di Variabel List? stock di Conclusion Variable Queue tidak ada di Variabel List 36. Tampilkan hasil Forward Chaining dari record konklusi interest = fall stock = rise 37. Return Kasus 2. Backward Chaining. Rule yang digunakan : rule 10 if degree = no then position = no rule 20 if degree = yes then qualify = yes rule 30 if degree = yes and discovery = yes then position = research rule 40 if qualify = yes and grade < 3.5 and experience >= 2 then position = service engineering rule 50 if qualify = yes and grade < 3.5 and experience < 2 then position = no rule 60 if qualify = yes and grade >= 3.5 then position = product engineer INISIALISASI Sebagai langkah awal program adalah men-scanner rule tadi, yang selanjutnya membuat Base Variable List dan meng-inisialisasi Variable List. Dalam Base Variable List, rule-rule tadi disusun sebagai berikut : 10 20 30 30 40 40 degree degree degree discovery qualify grade = = = = = < no yes yes yes yes 3.5 position qualify position position position position = = = = = = no yes research research serv eng serv eng 1 1 1 2 1 2

40 experience >= 2 position = serv eng 3

50 qualify = yes position = no 1

50 grade < 3.5 position = no 2

50 experience < 2 position = no 3

60 qualify = yes position = prod eng 1

60 grade >= 3.5 position = prod eng 2


52


Inisialiasi Variable List, disini yang dicatat adalah hal-hal di bagian IF (kondisi) Variable Sign Symbol Value degree NI discovery NI qualify NI grade NI experience NI Sign NI = Not Instantiated, I = Instantiated, Symbol dan Value masih bernilai kosong BACKWARD CHAINING 1. Kemudian program akan menanyakan kepada user, hal-hal yang diketahuinya sebagai langkah awal Backward Chaining, dengan sintaks : . Misal user menginputkan : position 2. Apakah pada Base Variable List di bagian THEN , input tersebut ada? ada (di rule nomor 10) 3. Catat nomor rule dan jumlah clause RuleNumber = 10 Jumlah Clause = 1 4. Update Conclusion Stack RuleNumber = 10 ClauseNumber = 1 (yaitu degree = no) 5. Apakah variabel di nomor clause pada top of stack sudah di-instantiated di Variable List, atau, ClauseNumber > Jumlah Clause degree pada Variable List belum di-instantiated ClauseNumber = 1 sama dengan JumlahClause 6. Apakah variabel ada di Base Variable List di bagian THEN? Tidak (degree tidak ada di bagian THEN) 7. Instantiate variable tadi di Variable List, disini ditanyakan kepada user. Misal user menginputkan : degree = yes Maka di Variable List dilakukan updating, sebagai berikut : Variable Sign Symbol Value degree I = yes discovery NI qualify NI grade NI experience NI 8. Apakah variabel tersebut memenuhi variabel di Base Variable List pada nomor rule yang tercatat? Tidak, (degree = yes tidak sama dengan di Base Variable List : degree = no) 9. Remove variabel di top of Conclusion Stack RuleNumber = 10 (diremove) ClauseNumber = 1 (diremove) Sehingga Conclusion Stack tidak ada isinya sekarang 10. Apakah ada variabel lain yang sama dengan input di Base Variable List di bagian THEN yang lain? Ada (yaitu di rule nomor 30) 11. Catat nomor rule dan jumlah clause RuleNumber = 30 Jumlah Clause = 2


53


12. Update Conclusion Stack RuleNumber = 30 ClauseNumber = 1 (yaitu degree = yes) 13. Apakah variabel di nomor clause pada top of stack sudah di-instantiated di Variable List, atau, ClauseNumber > Jumlah Clause Ya, degree sudah di-instantiated (Variable : degree, Sign : I) 14. Apakah bagian THEN bisa dieksekusi berdasar jumlah clause yang tercatat? Tidak, ClauseNumber yang dicek baru nomor 1 sedangkan Jumlah Clause = 2 15. Update Conclusion Stack RuleNumber = 30 ClauseNumber = 2 (yaitu discovery = yes) 16. Apakah variabel di nomor clause pada top of stack sudah di-instantiated di Variable List, atau, ClauseNumber > Jumlah Clause Tidak, discovery belum di-instantiated (Variable : discovery, Sign : NI) 17. Apakah variabel ada di Base Variable List di bagian THEN? Tidak (discovery tidak ada di bagian THEN) 18. Instantiate variable tadi di Variable List, disini ditanyakan kepada user. Misal user menginputkan : discovery = no Maka di Variable List dilakukan updating, sebagai berikut : Variable Sign Symbol Value degree I = yes discovery I = no qualify NI grade NI experience NI 19. Apakah variabel tersebut memenuhi variabel di Base Variable List pada nomor rule yang tercatat? Tidak, (discovery = no tidak sama dengan di Base Variable List : discovery = yes) 20. Remove variabel di top of Conclusion Stack RuleNumber = 30 (diremove) ClauseNumber = 2 (diremove) Sehingga Conclusion Stack tidak ada isinya sekarang 21. Apakah ada variabel lain yang sama dengan input di Base Variable List di bagian THEN yang lain? Ada (yaitu di rule nomor 40) 22. Catat nomor rule dan jumlah clause RuleNumber = 40 Jumlah Clause = 3 23. Update Conclusion Stack RuleNumber = 40 ClauseNumber = 1 (yaitu qualify = yes) 24. Apakah variabel di nomor clause pada top of stack sudah di-instantiated di Variable List, atau, ClauseNumber > Jumlah Clause Tidak, qualify belum di-instantiated (Variable : qualify, Sign : NI) 25. Apakah variabel ada di Base Variable List di bagian THEN? Ya (qualify ada di bagian THEN)


54


26. Catat nomor rule dan jumlah clause RuleNumber = 20 Jumlah Clause = 1 27. Update Conclusion Stack RuleNumber = 20 ClauseNumber = 1 (yaitu degree = yes) RuleNumber = 40 ClauseNumber = 1 28. Apakah variabel di nomor clause pada top of stack sudah di-instantiated di Variable List, atau, ClauseNumber > Jumlah Clause Ya, degree sudah di-instantiated (Variable : degree, Sign : I) 29. Apakah bagian THEN bisa dieksekusi berdasar jumlah clause yang tercatat? Ya, ClauseNumber yang dicek nomor 1 sedangkan Jumlah Clause = 1 30. Eksekusi bagian THEN qualify = yes 31. Update di Variable List jika variabel tersebut ada. qualify ada di Variable List, maka Variable List di-update Variable Sign Symbol Value degree I = yes discovery I = no qualify I = yes grade NI experience NI 32. Remove Top of Conclusion Stack RuleNumber = 20 (di-remove) ClauseNumber = 1 (di-remove) RuleNumber = 40 ClauseNumber = 1 Sehingga Conclusion Stack sekarang menjadi : RuleNumber = 40 ClauseNumber = 1 33. Apakah Conclusion Stack masih ada isinya? Ya, yaitu RuleNumber = 40 ClauseNumber = 1 34. Update Conclusion Stack RuleNumber = 40 ClauseNumber = 2 (yaitu grade < 3.5) 35. Apakah variabel di nomor clause pada top of stack sudah di-instantiated di Variable List, atau, ClauseNumber > Jumlah Clause Tidak, grade belum di-instantiated (Variable : grade, Sign : NI) 36. Apakah variabel ada di Base Variable List di bagian THEN? Tidak, grade tidak ada di bagian THEN 37. Instantiate variable tadi di Variable List, disini ditanyakan kepada user. Misal user menginputkan : grade = 3.0 Maka di Variable List dilakukan updating, sebagai berikut : Variable Sign Symbol Value degree I = yes discovery I = no qualify I = yes grade I = 3.0 experience NI Sistem Berbasis Pengetahuan – Irfan Subakti

55


38. Apakah variabel tersebut memenuhi variabel di Base Variable List pada nomor rule yang tercatat? Ya, (grade = 3.0 memenuhi di Base Variable List : grade < 3.5) 39. Update Conclusion Stack RuleNumber = 40 ClauseNumber = 3 (yaitu experience >= 2) 40. Apakah variabel di nomor clause pada top of stack sudah di-instantiated di Variable List, atau, ClauseNumber > Jumlah Clause Tidak, experience belum di-instantiated (Variable : experience, Sign : NI) 41. Apakah variabel ada di Base Variable List di bagian THEN? Tidak, experience tidak ada di bagian THEN 42. Instantiate variable tadi di Variable List, disini ditanyakan kepada user. Misal user menginputkan : experience = 4.5 Maka di Variable List dilakukan updating, sebagai berikut : Variable Sign Symbol Value degree I = yes discovery I = no qualify I = yes grade I = 3.0 experience I = 4.5 43. Apakah variabel tersebut memenuhi variabel di Base Variable List pada nomor rule yang tercatat? Ya, (experience = 4.5 memenuhi di Base Variable List : experience >= 2) 44. Update Conclusion Stack RuleNumber = 40 ClauseNumber = 4 45. Apakah variabel di nomor clause pada top of stack sudah di-instantiated di Variable List, atau, ClauseNumber > Jumlah Clause ClauseNumber (4) sudah melebihi Jumlah Clause (3) 46. Apakah bagian THEN bisa dieksekusi berdasar jumlah clause yang tercatat? Ya, ClauseNumber sudah dicek semuanya, sejumlah Jumlah Clause 47. Eksekusi bagian THEN position = service engineering 48. Update di Variable List jika variabel tersebut ada. Karena position tidak ada di Variable List maka tidak terjadi updating 49. Remove Top of Conclusion Stack RuleNumber = 40 (di-remove) ClauseNumber = 4 (di-remove) Sehingga Conclusion Stack tidak ada isinya sekarang 50. Apakah Conclusion Stack masih ada isinya? Tidak, Conclusion Stack tidak ada isinya sekarang 51. Tampilkan hasil Backward Chaining position = service engineering 52. Return


56


5.5.

Confidence Factor (CF) pada Forward dan Backward Chaining.

Confidence Factor (faktor kepercayaan) adalah ukuran/tingkat kepercayaan seseorang terhadap rule yang ada. Meliputi tingkat kepercayaan terhadap suatu variabel dalam suatu rule, maupun tingkat kepercayaan terhadap rule itu sendiri. Makin tinggi CF-nya jelas makin bisa dipercaya suatu rule, sehingga diasumsikan rule tersebut berarti makin baik. Dengan adanya CF ini, urutan rule pada suatu knowledge base tidak berpengaruh pada prioritas eksekusi program. Sehingga prioritas/keutamaan suatu rule ditentukan oleh besarnya CF yang ada padanya. Berikut ini dijelaskan hal-hal yang berhubungan dengan CF (Disini CF antara 0 s/d 100, boleh juga 0 s/d 1): CF untuk rule dengan kondisi AND. Contoh: IF condition = hot CF 70 AND condition = dry CF 90 AND condition = crowd CF 85 THEN anger = rise CF 95 CF untuk kondisi di atas adalah: CF = minimum (CF1, CF2, CF3) = minimum (70, 90, 85) = 70 Lalu CF untuk rule adalah CF(rule) = 70 * 95 = 6650/100 = 67 CF untuk rule dengan kondisi OR. Contoh: IF A CF1 OR B CF2 THEN K CF5; IF dollar = naik CF 80 OR rupiah = turun CF 60 THEN krisis = naik CF 90; Maka CF = 80 + 60 – (80 * 60)/100 = 140 – 48 = 92 CF(rule) = 92 * 90 = 8280, lalu bagi dengan 100 = 8280/100 = 82,8. Setelah di-ROUND, maka didapatkan 83 IF activity OR activity OR activity THEN advice

= = = =

letters resumes notices need CF

CF 80 CF 70 CF 85 90;

CF

= 80 + 70 – (80 * 70) = 150 – 56; 56 didapat dari (80 * 70)/100 = 94; dari sini didapatkan CF untuk (activity = letters CF 80 OR activity = resumes CF 70) Lalu dilanjutkan dengan (OR activity = notices CF 85) CF = 94 + 85 – (94 * 85) = 99 Maka CF(rule) = 99 * 90 = 89; dimana 89 didapat dari (99 * 90)/100 setelah di-ROUND CF untuk rule dengan kondisi AND/OR. Bila ada rule seperti berikut ini: RULE A IF activity = letters OR activity = resumes AND cost = low THEN word_processor = D CF 90; Dari situ terlihat ada kondisi OR dan AND, maka untuk mencari CF-nya, rule seperti ini dapat dipecah menjadi: RULE A1: IF activity = letter AND cost = low THEN word_processor = D CF 90; Sistem Berbasis Pengetahuan – Irfan Subakti

57


OR IF activity = resume AND cost = low THEN word_processor = D CF 90; RULE A2:

Sebagai contoh dimisalkan bahwa CF telah diinputkan oleh user sehingga didapatkan hasil sbb: RULE A1: IF activity = letter CF 90 AND cost = low CF 80 THEN word_processor = D CF 90; OR RULE A2: IF activity = resume CF 70 AND cost = low CF 80 THEN word_processor = D CF 90; CF kondisi pada RULE A1 = minimum (90, 80) = 80 CF untuk RULE A1 = 80 * 90 = 7200/100 = 72 CF kondisi pada RULE A2 = minimum (70, 80) = 70 CF untuk RULE A2 = 70 * 90 = 6300/100 = 63 CF untuk kedua RULE didapatkan dengan rumus OR sehingga didapat: 72 + 63 – (72 * 63) = 135 – 4536/100 = 135 – 45 = 90 Jadi, CF dari rule asli pada contoh ini adalah 90.

5.6.

Pengembangan Program Forward dan Backward Chaining.

Disamping pernyataan IF .. THEN .. pada RULE yang sudah dibahas, sebenarnya masih ada format yang lebih lengkap lagi yaitu IF .. THEN .. ELSE .. BECAUSE .., seperti tertulis di bawah ini: IF condition THEN conclusion1 ELSE conclusion2 BECAUSE “ ... “; RULE 7 IF functionallity = complex THEN word_processor = product_B ELSE word_processor = product_A BECAUSE “Product B can process more complicated documents that Product A”; Program juga dapat mengenali dan menangani persamaan, pertidaksamaan, dan juga range nilai tertentu untuk nilai-nilai yang dibandingkan dengan variabel-variabelnya. Contoh: IF warna = hitam, IF warna <> hitam, IF warna < 15, IF warna IN [0..7], IF kondisi = TRUE, dsb. Pembagian Rule. Rule dibagi dalam 3 bagian: ACTION, RULE, dan STATEMENT BLOCK, seperti contoh di bawah ini: //The file finding_word_processor.kbs uses a PLURAL variable, //Activity, in a compound OR IF-THEN-ELSE-BECAUSE //ACTION BLOCK ACTIONS DISPLAY “WPHELP will advise you on whether you need a word ” + “processor or not. Press OK to start the consultation.” FIND advice //variabel yang akan dicari, langsung saja ditandai //dengan kata FIND DISPLAY “You {advice} a word processor at this time. “ + “Press OK to exit WPHELP”; //tanda {} pada {advice} berarti bahwa yang diapit oleh tanda itu //ialah variabel yang ditampilkan //setiap selesai 1 statemen maka diakhiri dengan tanda “;” titik koma


58


//RULES BLOCK RULE 1 IF activity = letters OR activity = resumes OR activity = notices OR activity = papers THEN advice = need ELSE advice = do_not_need BECAUSE “If you generate frequent letters, resumes, notices, “ + “or papers, then you need a word processor.”; //STATEMENTS BLOCK ASK activity: “Which of the following documents do you need to write “ + “for your business? Select you answers by select “ + “your desired answer. After you have made all “ + “your selections, click or press OK button. “ + “If you don’t need to write any of these documents, “ + “select none_of_these”; //Pada program begitu program membutuhkan inputan dari user, //maka ditanyakan dulu ke user //kemudian setelah pertanyaan tadi, akan langsung disajikan dari //nilai-nilai yang mungkin //ada pada variabel, setelah selesai user dapat //meng-klik/meng-enter tombol OK //Kemungkinan nilai pada variabel tadi di-declare dengan kata CHOICES //seperti di bawah ini CHOICES activity: letters, resumes, notices, papers, none_of_these; PLURAL: activity; //Reserved word PLURAL menyatakan bahwa variabel setelahnya adalah //variabel yang nilainya //jamak=PLURAL, jadi tidak hanya 1 saja, bisa 2 atau lebih Contoh file yang lain: ACTIONS FIND word_processor; DISPLAY “The value of word_processor is {word_processor}” RULE 0 IF functionality = simple AND cost = low THEN word_processor = Product_A; RULE 1 IF functionality = simple AND cost = high THEN word_processor = Product_A; RULE 2 IF functionality = complex AND cost = low THEN word_processor = none; RULE 3 IF functionality = complex AND cost = high THEN word_processor = Product_B; ASK functionality: “What is the value of Functionality?”; CHOICES functionality: simple,complex; ASK cost: “What is the value of Cost?”; CHOICES cost: low,high; Implementasi Pengembangan Program. Bisa juga dikembangkan sintaks rule menurut yang diinginkan. Semakin lengkap jelas akan semakin baik. Sebagai panduan, bisa dilihat hal-hal di bawah ini: Ada fasilitas trace/penelusuran program. User interface sebaik dan semudah mungkin digunakan. Memberikan data yang lengkap kepada user. Bisa menampilkan jendela WHAT, HOW, WHY dengan isi yang lengkap. Isi dari jendela WHAT adalah hasil dari proses forward maupun backward chaining yang paling sederhana dan yang pertama kali didapatkan dari program, bahkan sebelum tahap pengembangan ini (bisa dilihat kembali di sub bab 4.4). Ia menjawab pertanyaan mengenai apa yang dihasilkan program. Sedangkan isi dari jendela jendela HOW adalah log/catatan bagaimana suatu hasil (WHAT) Sistem Berbasis Pengetahuan – Irfan Subakti

59


didapatkan, rule-rule mana saja yang telah diproses dan ditelusuri. Sedangkan isi dari jendela WHY, lebih banyak mengacu pada alasan hasil (WHAT) tadi didapat. Tentu saja komponen CF yang banyak mengambil peranan dalam penjelasan WHY ini. Singkatnya adalah WHAT adalah hasilnya, HOW adalah bagaimana menghasilkan WHAT tadi, sedangkan alasannya diimplementasikan oleh WHY. Bisa mengeksekusi semua rule, dengan catatan mengikuti sintaks program yang ada. Bisa menganalisis rule yang ada. Pencarian berjalan dengan cepat, apalagi untuk rule-rule yang kompleks dan besar. Untuk pendekatan Forward Chaining, ada tambahan reserved word: WHENEVER.

WHENEVER cost_too_high IF cost >= 500 THEN DISPLAY “Consider volume discounts.”; Begitu kata WHENEVER ditemukan di bagian awal rule, maka rule akan dites setiap saat nilai dari variabel yang ada di kondisi (bagian IF) berubah nilainya. Jika rule yang mengandung WHENEVER ditemukan sebagai konklusi yang benar, maka bagian THEN dieksekusi. Dengan kata lain, bila ada perubahan variabel di bagian IF, rule secara otomatis dicek untuk dipilih, tanpa memperhatikan strategi pencariannya apakah Forward atau Backward Chaining. Jadi WHENEVER berlaku seperti “daemon” sebab dia akan mengawasi variabel yang diacu oleh kondisi IF, dan mengeksekusinya setiap waktu kondisinya true/benar. Adanya reserved word FIND untuk mengidentifikasikan variabel tujuan. Reserved word FIND dalam rule hanya boleh ada dalam bagian THEN saja, tidak boleh di bagian IF. Contoh: RULE Networking IF Environment = Networked THEN Network = Yes FIND Networked_word_processor

FIND tidak bisa digabungkan dengan WHENEVER, sebab WHENEVER mengindikasikan rule, sedang FIND mengidentifikasikan variabel tujuan.

Contoh yang salah: WHENEVER Networking IF Environment = Networked THEN Network = Yes FIND Networked_word_processor Untuk nilai dari variabel yang belum diketahui, ada satu nilai khusus yaitu UNKNOWN, yang berarti program memang tidak tahu harus mengisikan apa pada variabel yang ditanyakan. Jadi cukup diisi saja dengan UNKNOWN bila kita memang tidak tahu jawaban apa yang harus diberikan. RULE 7 IF Document = UNKNOWN THEN Word_processor = wait_for_now DISPLAY “Examine your busines functions for word processing before buying”; RULE 8 IF Cost = UNKNOWN THEN Word_processor = none_for_now DISPLAY “Consult your manager or boss to determine your budget.”;


60

Bab 6 Algoritma Genetika

BAB 6 ALGORITMA GENETIKA 6.1.

Pendahuluan.

Pelbagai masalah optimasi baik di dunia rekayasa industri, utamanya pada sistem manufakturing, begitu kompleksnya untuk ditangani dengan teknik optimasi konvensional. Mulai tahun 1960-an mulai banyak studi yang berusaha untuk menirukan perilaku kehidupan dalam rangka menyelesaikan masalah optimasi yang pelik seperti contoh di atas. Simulasi proses evolusioner alamiah manusia menghasilkan teknik optimasi stokastik yang disebut algoritma evolusioner, yang seringkali dapat menampilkan kinerja yang lebih baik daripada metode konvensional ketika diaplikasikan pada permasalahan dunia nyata yang sulit. Ada tiga jalan utama dalam riset tersebut: Genetic Algorithms (GA, algoritma genetika), Evolutionary Programming (EP, pemrograman evolusioner), dan Evolution Strategies (ESs, Strategistrategi Evolusi). Diantara ketiganya, algoritma genetika dikenal sebagai algoritma yang paling banyak dipakai pada saat ini. Penerapan algoritma genetika yang sudah diterapkan di bidang rekayasa industri adalah dalam hal: penjadwalan dan prioritas urutan, desain kehandalan, rute dan penjadwalan kendaraan, group technology, layout dan lokasi fasilitas, transportasi, dan lain-lain. Dalam hubungannya dengan Sistem Berbasis Pengetahuan, GA ini diharapkan dapat mengoptimasi pencarian baik dalam Forward maupun Backward Chaining, dan harapan selanjutnya adalah bersama-sama dengan jaringan syaraf tiruan/logika fuzzy dapat lebih mengoptimalkan sistem dalam hal kecepatan pembelajaran, kecepatan berfikir, dan kecepatan memberikan solusi untuk menjawab semua pertanyaan yang berkaitan dengan WHAT, HOW, dan WHY. Struktur Umum Algoritma Genetika. Dapat digambarkan seperti bagan di bawah ini: crossover 110010 1010

Solusi

encoding

kromosom

101110 1110

1100101010 1011101110 0011011001 1100110001

110010 1110 101110 1010 mutasi 00110 11001

00110 01001 seleksi

evaluasi offspring

populasi baru

110010 1110 101110 1010 001100 1001

roulette wheel

decoding

Solusi

komputasi fitness

Struktur umum dari algoritma genetika di atas dapat dijelaskan sebagai berikut: Prosedur: Algoritma Genetika begin t ← 0; initialize P(t); 61



evaluate P(t); while (not termination condition) do recombine P(t) to yield C(t); evaluate C(t); select P(t+1) from P(t) and C(t); t ← t + 1; end

end Sebenarnya, cuma ada 2 jenis operasi dalam algoritma genetika: 1. Operasi genetika: crossover dan mutasi 2. Operasi evolusi: seleksi Algoritma genetika berbeda dengan optimasi konvensional dan prosedur pencarian dalam pelbagai hal, seperti hal-hal di bawah ini: 1. GA bekerja dengan koding dari kumpulan solusi, bukan solusi itu sendiri. 2. GA mencari dari populasi solusi, bukan solusi tunggal. 3. GA menggunakan informasi hasil (fungsi fitness), bukan penurunan atau knowledge bantuan lainnya. 4. GA menggunakan rule transisi probabilistik, bukan rule deterministik. Eksploitasi dan Eksplorasi. 2 isu penting dalam strategi pencarian: eksploitasi solusi terbaik dan eksplorasi ruang pencarian. GA merupakan metode pencarian umum yang mengkombinasikan elemen-elemen pencarian terarah dan stokastik yang dapat membuat keseimbangan diantara eksplorasi dan eksploitasi dari ruang pencarian. Pada awal pencarian dalam pencarian genetika, terdapat populasi yang berbeda dan sangat acak, lalu operator crossover cenderung untuk menampilkan pencarian melebar untuk mengeksplorasi semua ruang solusi. Dari hasil pengembangan solusi yang memiliki fitness tinggi, operator crossover menampilkan eksplorasi pada tetangga dari setiap solusi tersebut. Dengan kata lain, jenis apapun pencarian (eksploitasi atau eksplorasi) kinerja crossover ditentukan oleh lingkungan sistem genetika (keanekaragaman populasi), tetapi bukan oleh operator itu sendiri. Sebagai tambahan, operator-operator genetika sederhana didesain sebagai metode pencarian umum (metode pencarian yang tak tergantung domain); mereka menampilkan secara esensial pencarian “buta” dan tak dapat menjamin untuk menghasilkan offspring yang makin baik. Pencarian berdasarkan populasi. Perbandingan antara pendekatan konvensional dan genetika dapat dilihat pada gambar berikut:

conventional method initial single point

genetic algorithm initial population

improvement (problem-specific) improvement (problem-independent) terminal?

Yes

No

terminal?

end

No

Yes end


62


Meta-heuristic. GA sederhana sulit diaplikasikan secara langsung dan berhasil dalam banyak masalah optimasi yang “sulit”. Pelbagai implementasi yang tak standar dibuat untuk bermacam-macam masalah tertentu dimana GA digunakan sebagai meta-heuristic. GA + Stuktur Data = Program Evolusi. Keuntungan Utama. Ada 3 keuntungan utama dalam mengaplikasikan GA pada masalah-masalah optimasi: 1. GA tak memerlukan kebutuhan matematis banyak mengenai masalah optimasi. 2. Kemudahan dan kenyamanan dan pada operator-operator evolusi membuat GA sangat efektif dalam melakukan pencarian global (dalam probabilitas). 3. GA menyediakan banyak fleksibelitas untuk digabungkan dengan metode heuristic yang tergantung domain, untuk membuat implementasi yang efisien pada masalah-masalah khusus. Kamus GA. Genetic Algorithms Chromosome (string, individual) Genes (bits) Locus Alleles Phenotype Genotype

6.2.

Explanation Solution (coding) Part of solution Position of gene Values of gene Decoded solution Encoded solution

Contoh Program Algoritma Genetika Sederhana (Simple Genetic Algorithm)

Masalah Optimasi. Diberikan fungsi di bawah ini: Maksimalkan 21.5 + x1 sin(4πx1) + x2 sin(20πx2) f(x1, x2) = -3.0 <= x1 <= 12.1 4.1 <= x2 <= 5.8 Domain dari variabel xj adalah [aj, bj] dan presisinya adalah 4 tempat di belakang koma, maka range dari setiap variabel dapat dibagi dalam (bj – aj) x 104 unit. Bit yang dibutuhkan (dilambangkan dengan mj) untuk variabel tadi dapat dihitung dari: 2

mj − 1

< (bj - aj) x 104 <= 2

mj

-1

Variabel keputusan (decision variable) xj = aj + decimal(substringj) x

bj − a j m

2 j −1 Dimana decimal (substringj) merepresentasikan nilai desimal dari substringj untuk xj. Dimisalkan presisinya adalah 4 tempat di belakang koma. Bit yang dibutuhkan untuk variabel x1 dan x2 adalah: (12.1 – (-3.0)) x 10,000 = 151,000 217 < 151,000 <= 218, m1 = 18 (5.8 – 4.1) x 10,000 = 17,000 m2 = 15 214 < 17,000 <= 215, m = m1 + m2 = 18 + 15 = 33 Æ Panjang total kromosom adalah 33 bit yang direpresentasikan sbb:

33 bit vj 000001010100101001 101111011111110 18 bit 15 bit Nilai yang bisa didapatkan untuk variabel x1 dan x2 adalah sbb: Biner Desimal 5417 x1 000001010100101001 x2 101111011111110 24318 12.1 − (−3.0) = -2.687969 x1 = -3.0 + 5417 x 218 − 1 Sistem Berbasis Pengetahuan – Irfan Subakti

63


x2 = 4.1 + 24318 x

5.8 − 4.1 215 − 1

= 5.361653

Prosedur-prosedur yang ada dalam program. Terdapat beberapa prosedur dalam GA seperti di bawah ini: Initial Population. Generate secara random (pop_size misalnya 10 berarti generate 10 populasi awal), misal sbb: v1=[000001010100101001101111011111110]Æ nilai desimal v1=[x1,x2]= [-2.687969,5.361653] v2=[001110101110011000000010101001000]Æ nilai desimal v2=[x1,x2]= [ 0.474101,4.170144] v3=[111000111000001000010101001000110]Æ nilai desimal v3=[x1,x2]= [10.419457,4.661461] v4=[100110110100101101000000010111001]Æ nilai desimal v4=[x1,x2]= [ 6.159951,4.109598] v5=[000010111101100010001110001101000]Æ nilai desimal v5=[x1,x2]= [-2.301286,4.477282] v6=[111110101011011000000010110011001]Æ nilai desimal v6=[x1,x2]= [11.788084,4.174346] v7=[110100010011111000100110011101101]Æ nilai desimal v7=[x1,x2]= [ 9.342067,5.121702] v8=[001011010100001100010110011001100]Æ nilai desimal v8=[x1,x2]= [-0.330256,4.694977] v9=[111110001011101100011101000111101]Æ nilai desimal v9=[x1,x2]= [11.671267,4.873501] v10=[111101001110101010000010101101010]Æ nilai desimal v10=[x1,x2]=[11.446273,4.171908] Evaluation. Dalam proses ini evaluasi nilai fitness dari kromosom yang terdiri dari 3 langkah: Konversikan genetipe kromosom ke fenotipe-nya, artinya mengkonversikan string biner ke nilai real relatif dari xk = ( x1 , x 2 ), dengan k = 1,2, ..., pop_size. Evalusi fungsi obyektifnya: f(xk). Konversikan nilai dari fungsi obyektifnya ke fitness. Untuk kasus memaksimalisasikan, fitness-nya adalah sama dengan nilai fungsi obyektifnya: eval(vk) = f(xk), k = 1,2, ..., pop_size. eval(v1) = f(-2.687969,5.361653) = 19.805119 eval(v2) = f( 0.474101,4.170144) = 17.370896 eval(v3) = f(10.419457,4.661461) = 9.590546 eval(v4) = f( 6.159951,4.109598) = 29.406122 eval(v5) = f(-2.301286,4.477282) = 15.686091 eval(v6) = f(11.788084,4.174346) = 11.900541 eval(v7) = f( 9.342067,5.121702) = 17.958717 eval(v8) = f(-0.330256,4.694977) = 19.763190 eval(v9) = f(11.671267,4.873501) = 26.401669 eval(v10) = f(11.446273,4.171908) = 10.252480 Terlihat disitu bahwa kromosom v4 adalah kromosom terkuat dan kromosom v3 adalah yang terlemah. k

k

Selection. Dalam kebanyakan kasus, pendekatan roulette wheel (roda rolet) sering digunakan untuk prosedur seleksi; ini dimiliki oleh seleksi fitness-proportional dan dapat memilih populasi baru yang berhubungan dengan distribusi probabilitas pada nilai fitness-nya. Roda rolet ini dapat dijelaskan sbb: Hitung nilai fitness eval(vk) untuk setiap kromosom vk: eval(vk) = f(x), k = 1,2, ..., pop_size. Hitung total fitness untuk populasi: pop _ size

F=

∑ eval (v k =1

k

)

Hitung probabilitas seleksi pk untuk setiap kromosom vk: pk =

eval (v k ) , k = 1,2, ..., pop_size. F

Hitung probabilitas kumulatif qk untuk setiap kromosom vk: k

qk =

∑p j =1

j

, k = 1,2, ..., pop_size

Prosedur selection dimulai dengan memutar roda rolet sebanyak pop_size kali; setiap waktu satu kromosom dipilih untuk populasi baru selanjutnya, dengan langkah sbb: Generate bilangan random r dengan range [0,1]. Jika r <= q1, maka pilih kromosom pertama: v1; jika tidak, pilih kromosom ke-k: vk(2 <= k <= pop_size) sehingga qk-1 < r <= qk. Sistem Berbasis Pengetahuan – Irfan Subakti

64


Total fitness F dari populasi adalah: F =

10

∑ eval (v k =1

k

) = 178.135372

Probabilitas seleksi pk untuk setiap kromosom vk(k = 1, ..., 10) adalah sbb: p1 = 0.111180 p2 = 0.097515 p3 = 0.053839 p4 = 0.165077 p5 = 0.088057 p6 = 0.066806 p7 = 0.100815 p8 = 0.110945 p9 = 0.148211 p10 = 0.057554 Probablitas kumulatif qk untuk setiap kromosom vk(k = 1, ..., 10) adalah sbb: q1 = 0.111180 q2 = 0.208695 q3 = 0.262534 q4 = 0.427611 q5 = 0.515668 q6 = 0.582475 q7 = 0.683290 q8 = 0.794234 q9 = 0.942446 q10 = 1.000000 Sekarang marilah kita coba memutar roda rolet sebanyak 10 kali, dan setiap waktu kita memilih 1 kromosom untuk populasi baru selanjutnya. Diasumsikan misalnya 10 bilangan random dengan range [0,1] adalah sbb: 0.301431 0.322062 0.766503 0.881893 0.350871 0.583392 0.177618 0.343242 0.032685 0.197577 Bilangan pertama r1: 0.301431 lebih besar daripada q3 dan lebih kecil daripada q4, yang berarti bahwa kromosom q4 dipilih untuk populasi baru berikutnya; bilangan kedua r2: 0.322062 lebih besar daripada q3 dan lebih kecil daripada q4, yang berarti bahwa kromosom q4 lagi-lagi dipilih untuk populasi baru berikutnya; dan demikian seterusnya. Akhirnya populasi baru yang terbentuk adalah sbb: v’1 = [100110110100101101000000010111001] (v4) v’2 = [100110110100101101000000010111001] (v4) v’3 = [001011010100001100010110011001100] (v8) v’4 = [111110001011101100011101000111101] (v9) v’5 = [100110110100101101000000010111001] (v4) v’6 = [110100010011111000100110011101101] (v7) v’7 = [001110101110011000000010101001000] (v2) v’8 = [100110110100101101000000010111001] (v4) v’9 = [000001010100101001101111011111110] (v1) v’10= [001110101110011000000010101001000] (v2) Crossover. Digunakan sebagai metode pemotongan kromosom, yang secara random memilih titik potong pada kromosom dan menggantinya dengan bagian kanan dari 2 kromosom induk (parent) untuk menghasilkan kromosom anak (offspring). Pada contoh di bawah ini terdapat 2 kromosom induk, dan titik potongnya secara random dipilih pada posisi gen ke-17: v1 = [100110110100101101000000010111001] v2 = [001011010100001100010110011001100] Didapatkan hasil Offspring dengan menggantikan bagian kanan dari kromosom induk sebagai berikut: v’1 = [10011011010010110 0010110011001100] v’2 = [00101101010000110 1000000010111001] Probabilitas crossover di set sebagai pr = 0.25, maka kita dapat berharap bahwa sekitar 25% dari kromosom yang ada akan mengalami crossover. Crossover dapat dilakukan dengan langkah sbb: procedure: Crossover begin k ← 0; while (k <= 10) do rk ← random number from [0,1]; if (rk < 0.25) then select vk as one parent of crossover; end k ← k + 1; end end Diasumsikan bahwa urutan bilangan random-nya adalah sbb: 0.625721 0.266823 0.288644 0.295114 0.163274 0.567461 0.085940 0.392865 0.770714 0.548656 Dari situ bisa kita lihat bahwa kromosom v’5 dan v’7 akan dipilih untuk dilakukan crossover padanya. Kita generate bilangan integer pos secara random dengan range [1,32] (sebab 33 adalah panjang dari kromosom) sebagai titik potong atau dengan kata lain adalah posisi titik crossover. Sistem Berbasis Pengetahuan – Irfan Subakti

65


Diasumsikan bahwa bilangan pos yang dihasilkan sama dengan 1, dua kromosom dipotong setelah bit ke-1, dan offspring dihasilkan dengan menggantikan bagian kanan dari kromosom yang bersangkutan sbb: v’5 = [100110110100101101000000010111001] v’7 = [001110101110011000000010101001000] menjadi: v’5 = [101110101110011000000010101001000] v’7 = [000110110100101101000000010111001] Mutation. Mutasi mengubah satu atau lebih gen dengan probabilitas sama dengan angka mutasi. Diasumsikan bahwa gen ke-18 dari kromosom v1 dipilih untuk bermutasi. Karena gen di posisi itu (posisi ke-18) bernilai 1, maka setelah bermutasi nilainya menjadi 0. Maka setelah bermutasi, kromosom menjadi: v1 = [100110110100101101000000010111001] v1 = [100110110100101100000000010111001] Probabilitas mutasi diset sebagai pm = 0.01, sehingga diharapkan bahwa sekitar 1% total bit dari populasi akan bermutasi. Ada m x pop_size = 33 x 10 = 330 bit dalam keseluruhan populasi; diharapkan 3.3 mutasi terjadi setiap generasi. Setiap bit memiliki kesempatan yang sama untuk bermutasi. Maka kita perlu meng-generate serangkaian bilangan random rk (k= 1, ..., 330) dengan range [0,1]. Dimisalkan bahwa gen-gen berikut ini akan bermutasi: bit_pos chrom_num bit_no random_num 105 4 6 0.009857 164 5 32 0.003113 199 7 1 0.000946 329 10 32 0.001282 Setelah mutasi, didapatkan populasi baru sebagai generasi berikutnya, sebagai berikut: v’1=[100110110100101101000000010111001]Æ nilai desimal f( 6.159951,4.109598) = 29.406122 v’2=[100110110100101101000000010111001]Æ nilai desimal f( 6.159951,4.109598) = 29.406122 v’3=[001011010100001100010110011001100]Æ nilai desimal f(-0.330256,4.694977) = 19.763190 v’4=[111111001011101100011101000111101]Æ nilai desimal f(11.907206,4.873501) = 5.702781 v’5=[101110101110011000000010101001010]Æ nilai desimal f( 8.024130,4.170248) = 19.91025 v’6=[110100010011111000100110011101101]Æ nilai desimal f( 9.342067,5.121702) = 17.958717 v’7=[100110110100101101000000010111001]Æ nilai desimal f( 6.159951,4.109598) = 29.406122 v’8=[100110110100101101000000010111001]Æ nilai desimal f( 6.159951,4.109598) = 29.406122 v’9=[000001010100101001101111011111110]Æ nilai desimal f(-2.687969,5.361653) = 19.805119 v’10=[001110101110011000000010101001010]Æ nilai desimal f( 0.474101,4.170248) = 17.370896 Baru saja tadi kita sudah menyelesaikan satu iterasi dari algoritma genetik (GA). Program nantinya akan dihentikan setelah 1000 iterasi (1000 generasi). Didapatkan kromosom terbaik pada generasi ke-419 sbb: v* = (111110000000111000111101001010110) eval(v*) = f(11.631407,5.724824) = 38.818208 = 11.631407 x*1 = 5.724824 x*2 f(x*1,x*2) = 38.818208 Dari sini dapat dibuat program yang mengimplementasikan hal-hal diatas, dan sebagai inputnya, minimal adalah jumlah populasi awal pop_size, probabilitas crossover pr, probabilitas mutation pm, banyak iterasi, kromosom terbaik dan nilai-nilai yang ada padanya.


66

DAFTAR PUSTAKA 1. Turban, Efraim, Decision Support and Expert Systems: Management Support Systems, Fourth Edition, Prentice-Hall, Inc., United States of America, 1995. 2. Gonzalez, Avelino J. and Dankel, Douglas D., The Engineering of Knowledge-Based Systems: Theory and Practice/Book, 1993. 3. Ignizio, James P., Introduction to Expert Systems: The Development and Implementation of Rule-based Expert Systems, McGraw-Hill International Editions, 1991. 4. Baur Gregory R., Pigford D.V., Expert Systems for Business: Concepts and Applications, Boyd & Fraser Publishing Company, Boston-USA, 1990. 5. Gen, Mitsuo and Cheng, Runwei, Genetic Algorithms and Engineering Design, John Wiley & Sons., Inc., United States of America, 1997.

67


ABOUT THE AUTHOR

Assalamu'alaikum and my warm greeting to you all ^__^ My name is Irfan Subakti. I graduated from SD Magetan III (Elementary School degree) at Magetan city in 1986, then I continued to study at SMPN 1 Magetan (Junior High School degree) at the same city - I graduated in 1989. The senior high school degree is accomplished at SMA 1 Magetan in 1992. Through UMPTN (National University Entrance Test), I accepted at Computer Engineering Study Program (Undergraduate Program), Faculty of Industrial Technology, Institute Technology of Sepuluh Nopember (ITS) at Surabaya city. In 1994, the name of Department of Computer Engineering (Jurusan Teknik Komputer), via the government (i.e., Ministry of Education) decree changed into the Department of Informatics. That's why I graduated at undergraduate program in 1999 at these department, no longer at Computer Engineering Study Program, Faculty of Industrial Engineering, ITS. I got the degree: Bachelor of Science (B.Sc.) in Informatics field at this moment (a.k.a. Sarjana Komputer - S.Kom. in Indonesian). In 2001, the Department of Informatics no longer under the coordination of Faculty of Industrial Engineering, but it became the independent faculty, i.e., Faculty of Information Technology (FTIF). FTIF now on consist of 2 departments, namely: Department of Informatics and Information System Study Program. I got the scholarship from the government of Taiwan (Republic of China - R.O.C.) through National Taiwan University of Science and Technology (NTUST - www.ntust.edu.tw) in 2003, to pursue my master degree study. I accepted at Department of Computer Science and Information Engineering (CSIE - www.csie.ntust.edu.tw), College of Electrical and Computer Engineering, as an International Program student at Graduate Program. By the thesis entitled: A Variable-Centered Intelligent Rule System, I graduated from NTUST and I got M.Sc.Eng. degree (Master of Science in Engineering) in 2005. The fields of interest that I do love are: •

•

Fuzzy Information Systems o Fuzzy Logics o Fuzzy Systems o Fuzzy Knowledge-Based Systems Artificial Intelligence Agent Technology o Expert Systems o Rule-Based Systems o Knowledge Systems o Knowledge-Based Systems o Decision Support Systems o Variable-Centered Intelligent Rule System (VCIRS) - it's my own method! ^__^

68


After wandering for years since in the studying in the undergraduate program (i.e., that's why I could not graduate on time - 4 years from 1992, it should be in 1996 I had to graduate from undergraduate degree, but in fact I just graduated at 1999) until the graduation day and having fun trying the training jobs and works; either work by my own and work under the owner of some companies, then I continuing my hobby and my desire, that's teaching!. I decided to be a teacher in my alma mater. As the hobby, teaching is also the tradition from my brothers and sisters, parents, grand parents and my family. Now, I am a teacher in my alma mater, Department of Informatics, Faculty of Information Technology, Institute Technology of Sepuluh Nopember, at Surabaya city, Indonesia. You can contact me at: [email protected] Wassalamu'alaikum and sincerely yours ^__^ Irfan Subakti, S.Kom., M.Sc.Eng.

69


IF1526 Sistem Berbasis Pengetahuan (Knowledge-Based System)

Recommend Documents