Pada tahun 1979, Charles R. Forgy, pada Carnie-Mellon University mengembangakan algoritma Rete yang merupakan solusi dari algoritma Markov dimana masalah yang timbul jika sistem mempunyai aturan/baris yang banyak, maka algoritma Markov tidak akan efesien.
Algoritma Rete sendiri yaitu algoritma yang mengetahui tentang seluruh aturan/baris seluruh sistem dan dapat menerapkan suatu baris tampa harus mencoba setiap baris tampai berangkai (mencari perubahan dalam gabungan setiap cycle). Merupakan gabungan pola yang sangat cepat, yang mendapatkan kecepatannya dengan menyimpan informasi tentang baris dalam jaringan.
Implementasi algoritma Rete yaitu dengan membuat hubungan antar Node yang membentuk suatu jaringan. Hubungan tersebut dirangcang sedemikian rupa agar bisa menghemat keadaan proses dari suatu siklus ke siklus selanjutnya dan menghitung ulang perubahan hanya untuk fakta-fakta yang akan dimodifikasi. Status proses pencocokann hanya akan diperbarui sebagai fakta yang di tambahkan dan di hapus. Apabila fakta-fakta yang ditambahkanatau dihapus berurang jumlahnya, maka proses pencocokan akan terjadi lebih cepat.
Sebagai contoh, misalkan kita mempuyai sebuah aturan demikian:
If age > 60 or age < 5 or income < 36000 then concession = 50/100
Dimana age adalahvariabel Java dan income adalah variabel XML.
Pada jaringan Rete di atas, ada dua jenis node yang merepresentasikan dua tipe fakta: Java dan XML.
Node ‘Kind 1’ menunjukkan tipe Java dan node ‘Kind 2’ menunjukkan tipe XML. Sesuai dengan gambar
di atas, maka dikenali 3 pola yaitu ‘age>5’, ‘age>60’, dan ‘income<36000’, yang masing-masing
membentuk 3 node alpha. ‘Alpha 1’ dan ‘Alpha 2’ menunjukkan dua pola pertama yang terhubung ke
‘Kind 1’, sedangkan ‘Alpha 3’ menunjukkan pola ketiga yang terhubung ke ‘Kind 2’. Kemudian dua
alpha pertama akan terhubung ke ‘Beta 1’. Node alpha ketiga dan ‘Beta 1’ terhubung ke ‘Beta 2’.
Node ‘Kind 1’ menunjukkan tipe Java dan node ‘Kind 2’ menunjukkan tipe XML. Sesuai dengan gambar
di atas, maka dikenali 3 pola yaitu ‘age>5’, ‘age>60’, dan ‘income<36000’, yang masing-masing
membentuk 3 node alpha. ‘Alpha 1’ dan ‘Alpha 2’ menunjukkan dua pola pertama yang terhubung ke
‘Kind 1’, sedangkan ‘Alpha 3’ menunjukkan pola ketiga yang terhubung ke ‘Kind 2’. Kemudian dua
alpha pertama akan terhubung ke ‘Beta 1’. Node alpha ketiga dan ‘Beta 1’ terhubung ke ‘Beta 2’.
Ketika suatu nilai untuk ‘age’ dimasukkan ke dalam root, maka sebuah token akan dibuat. Salinan
token tersebut akan dilewatkan untuk mencari node. ‘Kind 1’ akan menerimanya sebagai tipe fakta
Java. Token tersebut akan dilewatkan melalui ‘Alpha 1’ dan ‘Alpha 2’. Jika nilainya memuaskan
batasan (constraint), maka token akan dilewatkan ke ‘Beta 1’ dan kemudian ‘Beta 2’. Pada saat yang
sama, nilai ‘income’ masuk ke dalam root dan diterima oleh ‘Kind 2’. ‘Alpha 3’ menerima token tersebut
dan mengecek apakah nilainya memuaskan constraint, ‘income <36000’. Jika ya, maka akan
menginjinkan token melalui ‘Beta 2’. Jika fakta, yang berupa nilai, sesuai dengan kondisi pada ‘Beta 2’,
maka aturan akan ditambahkan ke dalam daftar untuk disimpan.
token tersebut akan dilewatkan untuk mencari node. ‘Kind 1’ akan menerimanya sebagai tipe fakta
Java. Token tersebut akan dilewatkan melalui ‘Alpha 1’ dan ‘Alpha 2’. Jika nilainya memuaskan
batasan (constraint), maka token akan dilewatkan ke ‘Beta 1’ dan kemudian ‘Beta 2’. Pada saat yang
sama, nilai ‘income’ masuk ke dalam root dan diterima oleh ‘Kind 2’. ‘Alpha 3’ menerima token tersebut
dan mengecek apakah nilainya memuaskan constraint, ‘income <36000’. Jika ya, maka akan
menginjinkan token melalui ‘Beta 2’. Jika fakta, yang berupa nilai, sesuai dengan kondisi pada ‘Beta 2’,
maka aturan akan ditambahkan ke dalam daftar untuk disimpan.
Keuntungan :
Keuntungan utama dari algoritma Rete adalah kecepatannya dalam mengambil keuntungan dari
kemiripan struktural dalam aturan. Banyak aturan seringkali mengandung satu atau sekumpulan pola
yang sama. Algoritma Rete mengumpulkan komponen umum sehingga tidak perlu dikomputasi ulang.
Keuntungan utama dari algoritma Rete adalah kecepatannya dalam mengambil keuntungan dari
kemiripan struktural dalam aturan. Banyak aturan seringkali mengandung satu atau sekumpulan pola
yang sama. Algoritma Rete mengumpulkan komponen umum sehingga tidak perlu dikomputasi ulang.
Kelemahan :
Kelemahan algoritma Rete adalah penggunaan memori yang intensif. Untuk menyimpan keadaan
sistem menggunakan pencocokan pola dan pencocokan parsial membutuhkan banyak memori.
Kompleksitas ruang untuk algoritma Rete adalah urutan O(RFP), dimana R adalah banyaknya aturan,
F adalah banyaknya fakta, dan P adalah jumlah pola rata-rata per aturan.
Dalam kasus terburuk, aturan-aturan yang ditulis secara tidak tepat akan berjalan lambat. Apalagi jika
semua fakta tersebut harus dibandingkan dengan semua pola, akibatnya kecepatan proses maksimal
tidak dapat tercapai.
Referensi:
1. Anonim. “Markov Algorithms”, diunduh dari web.cecs.pdx.edu/~sheard/course/
…/OtherTuringComputAlg.pdf.
2. Charles, Weddle. “An Introduction to Expert Systems and CLIPS”, diunduh dari
www.charlesweddle.com/s-ca/doc/caddie-presentation.ppt.
3. Noran, Ovidiu S. “The Evolution of Expert Systems”, School of Computing and Information
Technology, Griffith University, diunduh dari www.ict.griffith.edu.au/noran/Docs/ES-Evolution.pdf.
4. Selvamony, Robinson. “Introduction to Rete Algorithm”, diunduh dari
www.cse.iitd.ernet.in/~parags/papers/thesis.pdf.
5. http://www.adityarizki.net/2012/10/model-production-system-dalam-sistem-pakar/
6. http://en.wikipedia.org/wiki/Markov_algorithm.
Tidak ada komentar:
Posting Komentar