Backward Chaining: Contoh Penelusuran Sistem Pakar Lengkap

Backward Chaining adalah metode penalaran pada sistem pakar yang memulai proses dari tujuan atau hipotesis, kemudian menelusuri aturan secara mundur untuk mencari fakta-fakta yang dapat membuktikan tujuan tersebut.

Metode ini disebut goal-driven reasoning karena proses inferensi dimulai dari sebuah goal. Sistem tidak langsung memproses seluruh fakta, tetapi terlebih dahulu menentukan apa yang ingin dibuktikan, lalu mencari rule yang memiliki kesimpulan sesuai goal tersebut.

Pada tutorial ini, Backward Chaining dijelaskan menggunakan contoh diagnosis kerusakan laptop. Penelusuran dilakukan mulai dari hipotesis Laptop Mengalami Overheating, mencari rule yang dapat menghasilkan hipotesis tersebut, membentuk subgoal, hingga seluruh kondisi dapat dibuktikan oleh fakta yang tersedia.

Daftar Isi

• Pengertian Backward Chaining
• Konsep Goal-Driven pada Backward Chaining
• Komponen Backward Chaining
• Bentuk Aturan IF-THEN
• Cara Kerja Backward Chaining
• Algoritma Backward Chaining
• Contoh Kasus Backward Chaining
  • #01 Menentukan Hipotesis
  • #02 Menentukan Fakta
  • #03 Menentukan Basis Aturan
  • #04 Memulai Penelusuran dari Goal
  • #05 Membentuk Subgoal
  • #06 Membuktikan Subgoal
  • #07 Hasil Penelusuran
• Contoh Penelusuran Gagal
• Pseudocode Backward Chaining
• Backward Chaining vs Forward Chaining
• Kelebihan dan Kekurangan Backward Chaining
• Kapan Backward Chaining Cocok Digunakan?
• Kesalahan Umum Implementasi
• Ringkasan
• FAQ Backward Chaining
• Referensi
• Source Code Backward Chaining

Pengertian Backward Chaining

Backward Chaining adalah teknik inferensi yang bekerja dari sebuah kesimpulan yang ingin dibuktikan menuju fakta-fakta yang mendukung kesimpulan tersebut.

Jika sistem ingin membuktikan hipotesis \(H\), maka sistem akan mencari rule dengan bagian THEN yang menghasilkan \(H\). Kondisi pada bagian IF kemudian menjadi subgoal baru yang juga harus dibuktikan.

Secara sederhana:

Jika seluruh kondisi pada rule dapat dibuktikan, maka goal dianggap terbukti.

Backward Chaining banyak digunakan pada:

• sistem pakar diagnosis,
• sistem konsultasi,
• troubleshooting,
• pemeriksaan kelayakan berdasarkan rule,
• pembuktian hipotesis,
• dan sistem berbasis pengetahuan yang memiliki tujuan spesifik.

Konsep Goal-Driven pada Backward Chaining

Backward Chaining sering disebut goal-driven reasoning.

Artinya, sistem lebih dahulu menentukan pertanyaan seperti:

Apakah laptop mengalami overheating?

Setelah goal ditentukan, sistem mencari rule yang dapat menghasilkan kesimpulan tersebut.

Misalnya tersedia rule:

IF laptop sering mati sendiri
AND suhu laptop tinggi
THEN laptop mengalami overheating

Untuk membuktikan:

laptop mengalami overheating

sistem tidak perlu memeriksa seluruh rule yang ada. Sistem cukup mencari rule yang kesimpulannya adalah laptop mengalami overheating.

Selanjutnya kondisi:

laptop sering mati sendiri

dan:

suhu laptop tinggi

menjadi subgoal yang harus dibuktikan.

Komponen Backward Chaining

Backward Chaining pada sistem pakar umumnya menggunakan beberapa komponen utama.

Bentuk Aturan IF-THEN

Rule pada Backward Chaining biasanya ditulis dalam bentuk:

IF kondisi_1
AND kondisi_2
AND ...
THEN kesimpulan

Secara logika:

Artinya, jika \(A\) dan \(B\) benar, maka \(C\) dapat disimpulkan benar.

Contoh:

IF kipas tidak normal
AND ventilasi tersumbat
THEN suhu laptop tinggi

Rule tersebut dapat digunakan untuk membuktikan goal:

suhu laptop tinggi

dengan terlebih dahulu membuktikan:

kipas tidak normal

dan:

ventilasi tersumbat

Cara Kerja Backward Chaining

Secara umum, proses Backward Chaining adalah:

1. Menentukan goal atau hipotesis.
2. Memeriksa apakah goal sudah tersedia sebagai fakta.
3. Jika belum, mencari rule dengan kesimpulan yang sama dengan goal.
4. Menjadikan kondisi pada rule sebagai subgoal.
5. Memeriksa apakah setiap subgoal merupakan fakta.
6. Jika subgoal belum menjadi fakta, mencari rule lain yang dapat membuktikannya.
7. Mengulangi proses sampai seluruh subgoal terbukti atau tidak ada rule yang dapat digunakan.
8. Jika seluruh kondisi terbukti, goal dinyatakan berhasil dibuktikan.
9. Jika salah satu kondisi tidak dapat dibuktikan dan tidak ada rule alternatif, goal gagal dibuktikan.

Algoritma Backward Chaining

Secara konseptual, fungsi Backward Chaining dapat dituliskan:

Pada implementasi program, proses tersebut biasanya dilakukan secara rekursif atau menggunakan stack.

Sistem juga perlu menghindari circular dependency, yaitu kondisi ketika sebuah goal secara tidak langsung kembali membutuhkan dirinya sendiri.

Contoh Kasus Backward Chaining

Contoh berikut menggunakan kasus sistem pakar untuk menentukan apakah sebuah laptop mengalami overheating.

Goal utama:

Laptop Mengalami Overheating

Agar penelusuran lebih jelas, digunakan beberapa fakta dan rule yang saling berhubungan.

#01 Menentukan Hipotesis

Hipotesis yang ingin dibuktikan:

Goal awal:

H1

atau:

Laptop Mengalami Overheating

Backward Chaining akan memulai pencarian dari H1.

#02 Menentukan Fakta

Misalnya dari hasil konsultasi pengguna diperoleh fakta berikut:

Fakta yang diketahui benar pada working memory:

F1 = Laptop sering mati sendiri
F2 = Kipas laptop tidak normal
F3 = Ventilasi laptop tersumbat

#03 Menentukan Basis Aturan

Knowledge base memiliki rule berikut:

Keterangan:

H1 = Laptop Mengalami Overheating
S1 = Suhu Laptop Tinggi
H2 = Masalah Baterai

Jika ditulis lengkap:

R1:
IF laptop sering mati sendiri
AND suhu laptop tinggi
THEN laptop mengalami overheating

R2:
IF kipas laptop tidak normal
AND ventilasi laptop tersumbat
THEN suhu laptop tinggi

R3:
IF baterai cepat habis
AND laptop tidak dapat mengisi daya
THEN terjadi masalah baterai

#04 Memulai Penelusuran dari Goal

Goal:

H1 = Laptop Mengalami Overheating

Sistem terlebih dahulu memeriksa apakah H1 sudah menjadi fakta.

Hasil:

H1 tidak ditemukan pada basis fakta.

Karena H1 belum menjadi fakta, sistem mencari rule dengan kesimpulan H1.

Ditemukan:

R1:
IF F1 AND S1
THEN H1

Agar H1 dapat dibuktikan, sistem harus membuktikan:

F1

dan:

S1

#05 Membentuk Subgoal

Dari R1 diperoleh dua subgoal:

Memeriksa F1

F1 sudah tersedia pada basis fakta:

F1 = Benar

Maka F1 berhasil dibuktikan.

Memeriksa S1

S1 belum tersedia sebagai fakta.

Sistem kemudian mencari rule yang menghasilkan:

S1 = Suhu laptop tinggi

Ditemukan:

R2:
IF F2 AND F3
THEN S1

Karena itu muncul dua subgoal baru:

F2
F3

#06 Membuktikan Subgoal

Sekarang sistem membuktikan F2 dan F3.

Membuktikan F2

F2 adalah:

Kipas laptop tidak normal

F2 tersedia pada basis fakta:

F2 = Benar

Membuktikan F3

F3 adalah:

Ventilasi laptop tersumbat

F3 juga tersedia pada basis fakta:

F3 = Benar

Karena F2 dan F3 benar:

maka R2 terpenuhi:

sehingga:

S1 = Suhu laptop tinggi

berhasil dibuktikan.

Sekarang kembali ke R1.

R1 membutuhkan:

F1 AND S1

dan keduanya telah terbukti benar.

Maka:

sehingga:

dan H1 berhasil dibuktikan.

#07 Hasil Penelusuran

Urutan penelusuran Backward Chaining:

H1
↓
R1
↓
F1 AND S1
↓
F1 = Fakta
S1 belum diketahui
↓
R2
↓
F2 AND F3
↓
F2 = Fakta
F3 = Fakta
↓
S1 terbukti
↓
H1 terbukti

Jika disusun dalam tabel:

Kesimpulan:

Hipotesis H1 — Laptop Mengalami Overheating berhasil dibuktikan.

Contoh Penelusuran Gagal

Tidak semua goal dapat dibuktikan.

Misalnya sistem ingin membuktikan:

H2 = Masalah Baterai

Rule yang tersedia:

R3:
IF F4 AND F5
THEN H2

Tetapi fakta yang tersedia:

F4 = Salah
F5 = Salah

Karena syarat R3 tidak terpenuhi, H2 tidak dapat dibuktikan.

Urutannya:

H2
↓
R3
↓
F4 AND F5
↓
F4 = Salah
F5 = Salah
↓
R3 gagal
↓
H2 tidak terbukti

Dalam sistem nyata, status ini lebih tepat dibaca sebagai tidak berhasil dibuktikan berdasarkan fakta dan rule yang tersedia, bukan selalu berarti hipotesis tersebut pasti salah.

Pseudocode Backward Chaining

Berikut pseudocode sederhana:

function backwardChain(goal, facts, rules):

    if goal ada di facts:
        return true

    cari semua rule
    dengan conclusion = goal

    for setiap rule:
        semuaPremisBenar = true

        for setiap premise pada rule:
            if backwardChain(premise, facts, rules) == false:
                semuaPremisBenar = false
                break

        if semuaPremisBenar:
            return true

    return false

Pada implementasi nyata, sebaiknya ditambahkan daftar goal yang sedang dikunjungi agar sistem tidak masuk ke perulangan jika terdapat rule yang membentuk siklus.

Contoh:

visitedGoals = []

Sebelum memproses sebuah goal:

if goal sudah ada di visitedGoals:
    hentikan cabang penelusuran

Backward Chaining vs Forward Chaining

Backward Chaining dan Forward Chaining sama-sama digunakan pada sistem berbasis rule, tetapi arah penelusurannya berbeda.

Contoh Perbedaan Arah

Backward Chaining:

Overheating
↓
Suhu tinggi
↓
Kipas tidak normal + ventilasi tersumbat

Forward Chaining:

Kipas tidak normal + ventilasi tersumbat
↓
Suhu tinggi
↓
Overheating

Kedua metode dapat menggunakan knowledge base yang sama. Yang berbeda adalah strategi penelusurannya.

Kelebihan dan Kekurangan Backward Chaining

Kelebihan Backward Chaining

• Fokus pada goal yang ingin dibuktikan.
• Tidak perlu memproses seluruh rule jika tidak relevan dengan goal.
• Cocok untuk sistem diagnosis dengan sejumlah hipotesis yang sudah diketahui.
• Jalur penalaran relatif mudah dijelaskan kepada pengguna.
• Dapat mengurangi pencarian jika goal sangat spesifik.
• Cocok digunakan pada sistem konsultasi berbasis pertanyaan.

Kekurangan Backward Chaining

• Memerlukan goal awal yang jelas.
• Dapat membutuhkan rekursi yang dalam pada knowledge base besar.
• Circular dependency perlu ditangani agar tidak terjadi infinite loop.
• Jika banyak rule menghasilkan goal yang sama, pencarian dapat memiliki banyak cabang.
• Kualitas hasil sangat bergantung pada kelengkapan rule dan fakta.
• Tidak otomatis menghasilkan semua kemungkinan kesimpulan seperti pendekatan data-driven.

Kapan Backward Chaining Cocok Digunakan?

Backward Chaining cocok digunakan ketika:

• sistem memiliki hipotesis yang jelas;
• pengguna ingin memeriksa kemungkinan diagnosis tertentu;
• jumlah goal lebih sedikit daripada jumlah fakta;
• knowledge base tersusun dalam rule IF-THEN;
• sistem perlu menanyakan fakta yang relevan saja;
• atau proses inferensi ingin difokuskan pada pembuktian suatu kesimpulan.

Contoh penerapan:

• diagnosis kerusakan komputer,
• diagnosis penyakit berdasarkan gejala,
• identifikasi hama tanaman,
• konsultasi kerusakan kendaraan,
• sistem troubleshooting jaringan,
• pemeriksaan kelayakan,
• dan sistem pakar berbasis rule lainnya.

Kesalahan Umum Implementasi

1. Menganggap Backward Chaining menghasilkan persentase

Backward Chaining pada dasarnya menentukan apakah suatu goal dapat dibuktikan berdasarkan fakta dan rule.

Jika sistem membutuhkan tingkat keyakinan dalam bentuk angka atau persentase, Backward Chaining dapat dikombinasikan dengan metode lain seperti Certainty Factor.

2. Tidak menangani circular rule

Contoh:

R1: IF B THEN A
R2: IF A THEN B

Jika tidak ada mekanisme visited, sistem dapat terus memanggil A dan B secara berulang.

3. Menganggap goal yang gagal dibuktikan pasti salah

Goal yang gagal dibuktikan dapat berarti:

• fakta tidak tersedia,
• rule tidak lengkap,
• premis tidak terpenuhi,
• atau memang hipotesis tidak didukung.

Karena itu istilah tidak terbukti lebih aman daripada langsung menyatakan salah.

4. Mencampur arah Forward dan Backward Chaining

Pada Backward Chaining, titik awal adalah goal.

Pada Forward Chaining, titik awal adalah fakta.

5. Rule terlalu umum

Rule yang terlalu luas dapat membuat sistem menghasilkan banyak cabang pencarian dan sulit ditelusuri.

Ringkasan

Backward Chaining adalah metode inferensi goal-driven yang memulai pencarian dari hipotesis, kemudian menelusuri rule ke arah premis sampai ditemukan fakta yang mendukung.

Pada contoh diagnosis laptop:

Goal:
Laptop Mengalami Overheating

dibuktikan melalui:

R1:
Laptop sering mati sendiri
AND Suhu laptop tinggi
→ Overheating

Suhu laptop tinggi kemudian dibuktikan dengan:

R2:
Kipas tidak normal
AND Ventilasi tersumbat
→ Suhu laptop tinggi

Karena semua fakta pendukung tersedia, hipotesis Laptop Mengalami Overheating berhasil dibuktikan.

FAQ Backward Chaining

Apa itu Backward Chaining?

Backward Chaining adalah metode inferensi yang memulai proses dari goal atau hipotesis, kemudian mencari fakta yang dapat membuktikan goal tersebut melalui rule IF-THEN.

Mengapa Backward Chaining disebut goal-driven?

Karena proses pencarian dimulai dari tujuan yang ingin dibuktikan, bukan dari seluruh fakta yang tersedia.

Apa yang dimaksud goal?

Goal adalah hipotesis atau kesimpulan yang ingin dibuktikan oleh sistem.

Apa yang dimaksud subgoal?

Subgoal adalah kondisi antara yang harus dibuktikan agar rule yang menghasilkan goal dapat terpenuhi.

Apa perbedaan Backward Chaining dan Forward Chaining?

Backward Chaining bergerak dari goal menuju fakta, sedangkan Forward Chaining bergerak dari fakta menuju kesimpulan.

Apakah Backward Chaining termasuk metode sistem pakar?

Ya. Backward Chaining adalah salah satu strategi inferensi yang banyak digunakan pada sistem pakar berbasis rule.

Apakah Backward Chaining menghasilkan nilai persentase?

Tidak secara langsung. Backward Chaining berfokus pada proses pembuktian goal. Jika dibutuhkan tingkat keyakinan, metode ini dapat dikombinasikan dengan Certainty Factor atau metode ketidakpastian lainnya.

Apakah Backward Chaining dapat digunakan bersama Certainty Factor?

Bisa. Backward Chaining dapat digunakan untuk menentukan jalur rule yang relevan, sedangkan Certainty Factor digunakan untuk menghitung tingkat keyakinan terhadap hasil diagnosis.

Apa yang terjadi jika terdapat beberapa rule untuk goal yang sama?

Sistem dapat mencoba setiap rule sebagai jalur alternatif. Goal dianggap terbukti jika setidaknya satu jalur rule berhasil membuktikan seluruh premis yang diperlukan.

Bagaimana jika sebuah fakta belum diketahui?

Sistem dapat mencari rule lain yang menghasilkan fakta tersebut atau, pada sistem konsultasi interaktif, menanyakan kondisi tersebut kepada pengguna.

Bagaimana mencegah infinite loop pada Backward Chaining?

Gunakan daftar goal yang sedang atau sudah ditelusuri. Jika sebuah goal muncul kembali pada jalur yang sama, cabang tersebut dapat dihentikan.

Kapan Backward Chaining lebih cocok daripada Forward Chaining?

Backward Chaining cocok ketika sistem memiliki target atau hipotesis yang spesifik dan hanya perlu memeriksa fakta yang relevan untuk membuktikan target tersebut.

Referensi

1. Buchanan, B. G., & Shortliffe, E. H. (1984). Rule-Based Expert Systems: The MYCIN Experiments of the Stanford Heuristic Programming Project. Addison-Wesley.
2. Giarratano, J. C., & Riley, G. D. (2005). Expert Systems: Principles and Programming. Thomson Course Technology.
3. Russell, S. J., & Norvig, P. (2021). Artificial Intelligence: A Modern Approach. Fourth Edition. Pearson.

Source Code Backward Chaining

Berikut source code yang menggunakan metode Backward Chaining pada RumahSourceCode.

Source Code Sistem Pakar Metode Backward Chaining PHP

Rp350,000