Algoritma Sistem Pakar

Latar Belakang

Sistem pakar adalah sistem yang mencoba menerapkan pengetahuan manusia pada komputer sehingga komputer dapat menyelesaikan masalah seperti layaknya seorang pakar, dan sistem pakar yang baik bertujuan untuk menyelesaikan masalah tertentu dengan meniru pekerjaan pakar.

Sistem pakar pertama kali dikembangkan oleh komunitas AI pada pertengahan 1960-an. Sistem pakar pertama yang muncul adalah universal problem solver (GPS) yang dikembangkan oleh Newel & Simon.

Dasar dari sistem pakar adalah bagaimana mentransfer pengetahuan yang dimiliki oleh pakar ke komputer, dan bagaimana membuat keputusan atau menarik kesimpulan berdasarkan pengetahuan tersebut.

Teori Dasar Forward Chaining, Best First Search, Dan Depth First Search

Forward Chaining

Forward chaining adalah penalaran yang dimulai dari fakta hingga menarik kesimpulan. Forward chaining dapat dikatakan sebagai strategi penalaran yang dimulai dari banyak fakta yang diketahui. Gunakan aturan yang premisnya cocok dengan fakta yang diketahui untuk mencari dan mendapatkan fakta baru serta melanjutkan pemrosesan hingga tujuan tercapai, atau hingga tidak ada lagi aturan yang premisnya cocok dengan fakta yang diketahui dan fakta yang diperoleh.

Forward chaining juga bisa disebut tautan maju atau pencarian berdasarkan data. Oleh karena itu, pencarian dimulai dengan premis atau informasi masukan (if), dan kemudian kesimpulan atau informasi yang diturunkan (then). Forward chaining berarti menggunakan seperangkat aturan kondisi-aksi. Dalam metode ini, data digunakan untuk menentukan aturan yang akan dijalankan, atau untuk menemukan hasil dengan menambahkan data ke memori kerja untuk diproses.

Forward chaining sendiri digunakan apabila :

• Banyak aturan berbeda yang dapat menghasilkan kesimpulan yang sama.
• Ada banyak cara untuk menarik sedikit kesimpulan.
• Benar-benar telah memperoleh bermacam-macam fakta, dan berharap dapat menarik kesimpulan dari fakta-fakta ini.

Berikut merupakan beberapa sistem yang dapat menggunakan teknik pelacakan forward chaining, yaitu :

• Sebuah sistem yang dipresentasikan oleh satu atau lebih kondisi.
• Untuk setiap kondisi, sistem mencari basis pengetahuan untuk aturan yang sesuai dengan kondisi di bagian if.
• Setiap aturan dapat menarik kondisi baru dari kesimpulan yang diambil di bagian then. Ketentuan baru ini bisa ditambahkan ke ketentuan lain yang sudah ada.
• Semua kondisi yang ditambahkan ke sistem akan diproses. Jika kondisi ditemukan, sistem akan kembali ke langkah 2 dan mencari aturan di basis pengetahuan, jika tidak ada kesimpulan baru, sesi akan berakhir.

Best First Search

BFS adalah algoritma yang mengeksplorasi grafik dengan memperluas node atau simpul yang paling menjanjikan yang dipilih sesuai dengan aturan yang ditentukan. Node adalah deskripsi dari area pencarian. Grafik yang digunakan dalam BFS disebut grafik "OR", karena setiap cabang mewakili cara lain untuk menyelesaikan masalah. BFS dapat dikatakan mengembangkan sebuah simpul dari simpul sebelumnya. Dibandingkan dengan node lainnya, node yang dikembangkan merupakan node dengan skor terkecil. BFS adalah metode alternatif yang menggabungkan manfaat dari metode depth dan breadth first search.

Depth First Search

Algoritma DFS hampir sama dengan algoritma BFS, tetapi teknologi untuk menemukan node solusi berbeda. Algoritme DFS memiliki prioritas untuk mengakses node terlebih dahulu ke lapisan terdalam. Kemudian, jika ditemukan titik buta (tidak ada lagi simpul yang berdekatan), algoritme akan memeriksa simpul yang dikunjungi sebelumnya yang masih berdekatan dengan simpul lain yang belum dikunjungi, dan melacak simpul-simpul tersebut. Dengan kata lain, node cabang atau anak yang terlebih dahulu dikunjungi.

Seperti BFS, DFS juga memiliki keunggulan dalam mencapai kedalaman ruang pencarian dengan cepat. Jika diketahui bahwa jalan untuk menyelesaikan masalah akan sangat panjang, maka DFS tidak akan membuang waktu untuk menyelesaikan sejumlah besar status dangkal dalam masalah graf. Untuk ruang pencarian multi-cabang, DFS lebih efisien karena tidak perlu mengeksekusi semua node pada level tertentu pada daftar terbuka. Selain itu, DFS membutuhkan memori yang relatif kecil karena hanya banyak node di jalur aktif yang disimpan. Selain kelebihannya, DFS juga memiliki beberapa kekurangan, diantaranya kemampuan untuk menemukan tujuan yang diinginkan dan hanya satu solusi per pencarian.

Cara Perhitungan Forward Chaining, Best First Search, Dan Depth First Search

Perhitungan Forward Chaining

Saat aturan dijalankan, fakta baru akan ditambahkan ke database. Setiap pencocokan dimulai dengan aturan tertinggi, dan setiap aturan hanya dapat dijalankan satu kali. Jika tidak ada aturan lain yang dapat dijalankan, proses pencocokan akan berhenti. Contoh : Menentukan warna binatang bernama Helly. Data awal adalah Helly bermain dan berlari. Misalkan terdapat 4 aturan :

1. If x melompat dan memakan rumput/buah, maka x adalah kanguru.
2. If x bermain dan memanjat, maka x adalah monyet bekantan.
3. If x adalah kanguru, maka x berwarna cokelat.
4. If x adalah monyet bekantan, maka x berwarna putih keabuan.

Yang dicari pertama adalah aturan nomor 2, karena anteseden-nya cocok dengan data kita (if Helly  bermain dan berlari).

Konsekuen (then Helly adalah anjing samoyed) ditambahkan ke data yang dimiliki If Helly adalah anjing samoyed, maka Helly berwarna putih (tujuan).

Perhitungan Best First Search

Untuk algoritma BFS sendiri memiliki rumus perhitungan seperti berikut : 

f’(n)=h’(n) 

dengan h(n) = |(Xt-Xa)+(Yt-Ya)|

Perhitungan Depth First Search

Berikut merupakan perhitungan DFS :

Contoh di atas menggunakan prioritas untuk memasukkan node anak dari kiri terlebih dahulu ke dalam antrian.

Antrian :

1. A (Cek A : A bukan solusi lalu simpan di Output)
2. B, C (Cek B : B bukan solusi lalu simpan di Output)
3. D, C(Cek D : D bukan solusi lalu simpan di Output)
4. F, C(Cek F : F adalah solusi kemudian simpan di Output dan proses selesai)

Berdasarkan tahapan-tahapan yang ada diatas, maka bisa disimpulkan bahwa dengan Depth First Search (DFS) didapat jalur yang paling optimal yaitu jalur A> B> D> F.

Langkah-Langkah Penerapan Forward Chaining, Best First Search, Dan Depth First Search

Penerapan Forward Chaining

Berikut merupakan langkah-langkah penerapan dari FC :

1. Mencari ahli yang sesuai dengan tema sistem yang akan dibuat.
2. Mendapatkan data hipotesis/kesimpulan sesuai dengan bidang keahliannya.
3. Mendapatkan data premis/gejala/bukti pada setiap hipotesis.
4. Memperoleh data aturan dari para ahli berdasarkan data premis dan kesimpulan.
5. Setelah memperoleh semua data yang diperlukan, maka langkah selanjutnya yaitu menghitung data ke dalam teori Forward Chaining, sehingga menjadi kesimpulan yang paling tepat berdasarkan premis input pengguna.

Berikut ini merupakan contoh alur diagram forward-chaining :

Hasil output dari FC adalah menelusuri semua data untuk mencapai tujuan yang diinginkan.

Penerapan Best First Search

Berikut merupakan langkah-langkah penerapan BFS :

1. Pertama, tentukan daftar OPEN dengan satu simpul sebagai simpul awal.
2. Kemudian, periksa apakah OPEN berisi atau kosong. Jika kosong, maka algoritma mengembalikan nilai yang gagal dan keluar.
3. Langkah selanjutnya, hapus node yang memiliki skor terbaik, n, dari OPEN kemudian pindahkan ke CLOSED.
4. Kemudian, perluas node n, di mana ekspansi adalah identifikasi node penerus n.
5. Selanjutnya, periksa setiap node penerus untuk melihat apakah ada node tujuan di salah satunya atau tidak. Jika ada penerus yang menjadi simpul tujuan, maka algoritma akan mengembalikan nilai sukses dan solusi, yang terdiri dari jalur yang ditelusuri kembali dari tujuan ke simpul awal. Jika tidak, lanjutkan langkah ke enam.
6. Untuk langkah selanjutnya, untuk setiap node penerus, algoritma menerapkan fungsi evaluasi f, kemudian memeriksa, untuk melihat apakah node sudah OPEN atau CLOSED. Jika node tidak ada dalam salah satu daftar, node tersebut akan ditambahkan ke OPEN.
7. Langkah selanjutnya adalah membangun struktur loop dengan mengirimkan algoritma kembali ke langkah 2. Loop ini akan berhenti jika algoritma mengembalikan nilai sukses pada langkah ke 5 atau kegagalan pada langkah ke 2.

Berikut ini merupakan contoh alur diagram dari BFS :

Hasil output dari BFS sendiri memilih simpul baru yang memiliki biaya terkecil di antara semua leaf nodes (simpul-simpul pada level terdalam) yang pernah dibangkitkan.

Penerapan Depth First Search

Dalam implementasi, DFS sendiri dapat diselesaikan secara rekursif atau dengan bantuan struktur data stack. Pada makalah ini membahas cara menggunakan stack. Stack yang digunakan adalah stack yang elemennya adalah simpul pohon. Berikut urutan algoritmanya :

1. Masukkan simpul akar ke dalam tumpukan dengan push.
2. Ambil dan simpan konten elemen (dalam bentuk simpul pohon) dari atas tumpukan.
3. Hapus konten tumpukan teratas dengan prosedur pop.
4. Periksa apakah simpul pohon yang disimpan memiliki simpul anak.
5. Jika ya, push semua node anak yang dihasilkan ke tumpukan.
6. Jika tumpukan kosong berhenti, tetapi jika tidak kembali ke langkah kedua.

Berikut merupakan contoh alur diagram DFS :

Keluaran dari DFS itu sendiri untuk mencari rute terpendek, dengan mempertimbangkan kelebihan dan kekurangan dari algoritma tersebut, maka dapat disimpulkan bahwa algoritma ini dapat membantu menemukan rute terpendek, sehingga bisa mendapatkan solusi yang efektif.