Metode Pencarian dan Pelacakan Biologi

2.4.1        Metode Pencarian dan Pelacakan

A.                Pencarian Melebar Pertama (Breadth-First Search)

Pada metode Breadth-First Search ini adalah semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. pencarian dimulai dari node akar terus ke level 1 dari kiri ke kanan, kemudian berpindah ke level berikutnya dari kiri ke kanan hingga solusi ditemukan  (Gambar 2.6 Metode Breadth-First Search).

       Gambar 2.6 Metode Breadth-First Search

Algoritma :

1.    Buat suatu variable Node_List dan tetapkan sebagai keadaan awal.

2.    Kerjakan langkah-langkah berikut ini sampai tujuan tercapai atau Node_List dalam keadaan kosong :

a)        Hapus elemen pertama dari Node_List, sebut dengan nama E. Jika Node_List kosong, keluar.

b)        Pada setiap langkah yang aturannya cocok dengan E, kerjakan :

                         i.          Aplikasikan aturan tersebut membentuk suatu keadaan baru.

                       ii.          Jika keadaan awal adalah tujuan yang diharapkan, sukses dan keluar.

                     iii.          Jika tidak demikian, tambahkan keadaan awal yang baru tersebut pada akhir Node_List.

Keuntungan :

1.        Tidak akan menemui jalan buntu

2.        Jika ada 1 solusi, maka breadth – first search solusi akan menemukannya dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.

Kelemahan :

1.        Membutuhkan memori yang cukup banyak

2.        Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1).

B.                 Pencarian Mendalam Pertama (Depth – First Search)

            Pada metode Depth – First Search, Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses diulangi terus hingga ditemukan solusi (Gambar 2.7 Metode Depth – First Search).

Gambar 2.7 Metode Depth – First Search

Algoritma :

1.    Jika keadaan awal merupakan tujuan, keluar (sukses).

2.    Jika tidak demikian, kerjakan langkah-langkah berikut ini sampai tercapai keadaan sukses atau gagal :

a)      Bangkitkan successor E dari keadaan awal. Jika tidak ada successor, maka akan terjadi kegagalan.

b)      Panggil Depth – First Search  dengan E sebagai keadaan awal.

c)      Jika sukses berikan tanda sukses. Namun jika tidak, ulangi langkah-2.

Keuntungan :

1.        Membutuhkan memori relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.

2.        Secara kebetulan, metode Depth – First Search  akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

Kelemahan :

1.        Memungkinkan tidak ditemukannya tujuan yang diharapkan

2.        Hanya mendapat satu solusi pada setiap pencarian

C.                Pencarian Terbaik Pertama (Best First Search)

            Metode Pencarian Terbaik Pertama (Best First Search) merupakan kombinasi dari metode depth first search dan metode breadth first search dengan mengambil kelebihan dari kedua metode tersebut. Pada setiap langkah proses pencarian terbaik pertama, kita memilih node-node dengan menerapkan fungsi heuristik yang memadai pada setiap node atau simpul yang kita pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan penggantinya. Pada best first search, pencarian diperbolehkan mengunjungi node di lebih rendah dan jika ternyata node dilevel lebih tinggi memiliki nilai heuristik lebih buruk.

       Untuk mengimplementasikan metode ini, dibutuhkan dua antrian yang berisi node-node, yaitu :

1. OPEN yaitu berisi node-node yang sudah dibangkitkan, sudah memiliki fungsi heuristik namun belum diuji. Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan nilai heuristik tertinggi.
2. CLOSED yaitu berisi node-node yang sudah diuji

Algoritma :

1.        Tempatkan node awal A pada antrian OPEN

2.        Kerjakan langkah-langkah berikut hingga tujuan ditemukan atau antrian OPEN sudah kosong :

a)         Ambil node terbaik dari OPEN (Gambar 2.8 Antrian OPEN)

b)        Bangkitkan semua successornya

c)         Untuk tiap-tiap successor kerjakan :

          i.          Jika node tersebut belum pernah dibangkitkan sebelumnya, evaluasi node tersebut dan masukkan ke OPEN.

        ii.          Jika node tersebut sudah pernah dibangkitkan sebelumnya, ubah parent jika lintasan baru lebih menjanjikan. Hapus node tersebut dari antrian OPEN.

        Antrian OPEN

               [ A ]

       

   [ D C B ]

   [ C F B E ]

     [G F B E H ]

            Gambar 2.8 Antrian OPEN

Diasumsikan node dengan nilai yang lebih besar memiliki nilai evaluasi yang lebih baik. Pada keadaan awal, antrian berisi A. Pengujian dilakukan di level pertama, node D memiliki nilai terbaik, sehingga menempati antrian pertama, disusul dengan C dan B. Node D memiliki cabang E dan F yang masing-masing bernilai 2 & 4. Dengan demikian C merupakan pilihan terbaik dengan menempati antrian pertama (Gambar 2.9 Metode Best First Search).

Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan :

f’ = g + h’

dimana : f’  = prakiraan cost dari initial ke goal

    g = cost dari initial state ke current state

   h’ = prakiraan cost dari current state ke goal state

Gambar 2.9 Metode Best First Search

Keuntungan :

1.        Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.

2.        Menemukan solusi tanpa harus menguji lebih banyak node.

Kelemahan :

1.        Memungkinkan terjebak pada nilai optima.

2.4.15    Metode Representasi Pengetahuan Production Rule

Metode representasi pengetahuan yang digunakan production rule kaidah produksi. Kaidah produksi ini dikatakan sebagai implikasi dua bagian yaitu bagian premise atau kondisi konklusi atau maka. Apabila bagian premise dipenuhi maka bagian koklusi akan bernilai benar. Bila bagian premise tidak dipenuhi maka akan melompat ke bagian premise lain dibawahnya. Suatu kaidah produksi dapat terdiri atas beberapa premise dan lebih dari satu konklusi. Antara premise satu dengan yang lain dapat dihubungkan dengan “atau” atau “dan”.

Production Rule secara umum terdiri dari komponen-komponen sebagai berikut :

1.      Ruang keadaan, yang berisi keadaan awal, tujuan dan kumpulan aturan yang digunakan untuk mencapai tujuan.

2.      Strategi Kontrol, yang berguna untuk  mengarahkan bagaimana proses pencarian akan berlangsung dan mengendalikanarah eksplorasi.

Proction rule ini merupakan salah satu bentuk representasi pengetahuan yang sangat popular dan banyak digunakan adalah production rule. Representasi pengetahuan dengan  production rule, pada dasarnya berupa aplikasi aturan (rule) yang berupa :

1.      Antecedent, yaitu bagian yang mengekspresikan situasi atau premis (Pernyataan berawalan IF).

2.      Konsuekuen, yaitu bagian yang menyatakan suatu tindakan tertentuatau konklusi yang diterapkan jika situasi atau premis bernilai benar (Pernyataan berawalan THEN).

Konsekuensi atau konklusi yang dinyatakan pada bagian THEN baru dinyatakan benar, jika bagian IF pada system tersebut juga benar atau sesuai dengan aturan tertentu.

Contoh :

      IF           warna teras putih AND

                corak polos AND

                 tekstur sangat halus AND

                 arah serat lurur AND

                kilap mengkilap AND

                kesan raba licin AND

                 kekerasan kayu agak lunak

THEN      Nama spesies Agathis dammara

2.4.16    Bidang-bidang Sistem Pakar

Ada banyak area atau wilayah yang menjadi daerah kerja Artificial Intelligence yaitu jaringan saraf, sistem persepsi, robotic, bahsa ilmiah, sistem pendukung keputusan, sistem informasi berbasis manajemen  dan sistem pakar.

Tiap daerah kerja Artificial Intelligence memiliki potensi dalam memecahkan masalah, tetapi keunggulan utama dalam bentuk pengetahuan dari pakar manusia secara heuristic dalam sistem pakar. Heuristic dalam sistem pakar tidak menjamin hasil mutlak sistem kecerdasan buatan lainnya, tetapi menawarkan hasil yang spesifik untuk dimanfaatkan karena sistem pakar berfungsi secara konsisten seperti seorang pakar manusia, menawarkan nasihat kepada pemakai dan menemukan solusi terhadap berbagai permasalahan yang spesifik.

Ada berbagai kategori pengembangan sistem pakar, antara lain :

1.             Kontrol. Contoh pengembangan banyak ditemukan dalam kasus pasien di rumah sakit, dimana dengan kemampuan sistem pakar dapat dilakukan control terhadap cara pengobatan dan perawatan melalui sensor data dan memberikan solusi terapi pengobatan yang tepat bagi si pasien yang sakit. 

2.             Desain. Contoh sistem pakar untuk membantu mendesain komputer dengan komponen-komponennya.

3.             Diagnosis. Contoh sistem pakar ini adalah diagnosis penyakit, kerusakan mesin kendaraan bermotor, kerusakan komponen komputer, dan lain-lain.

4.             Instruksi. Instruksi merupakan pengembangan sistem pakar yang sangat berguna dalam bidang ilmu pengetahuan dan pendidikan, dimana system pakar dapat memberikan instruksi dan pengajaran tertentuterhadap suatu topik permasalahan. Contoh pengembangan yaitu system pakar untuk pengajaran bahasa Inggris dan lain-lain.

5.             Interpretasi. Sistem pakar yang dikembangkan dalam bidang interpretasi melakukan proses pemahaman akan suatu situasi dari beberapa informasi yang direkam.

6.             Monitor. Sistem pakar ini biasanya digunakan pada kemiliteran yaitu menggunakan sensor radar.

7.             Perencanaan. Perencanaan banyak digunakan dalam bidan bisnis dan keuangan suatu proyek, dimana system pakar yang melakukan perencanaan suatu pekerjaan berdasarkan jumlah tenaga kerja dan biaya.

8.             Prediksi. Biasanya system memberikan simulasi kejadian masa mendatangtersebut, misalnya memprediksi tingkat kerusakan tanaman apabila diserang hama.

9.             Seleksi. Sistem pakar dengan seleksi mengidentifikasi pilihan terbaik dari beberapa pilihan kemungkinan solusi.

10.         Simulasi. Contoh adalah program PLANT yang menggabungkan antara prediksi dan simulasi, dimana program tersebut mampu menganalisis hama dengan berbagai kondisi suhu dan cuaca.

2.5         Pengertian Basis data

          Basis data terdiri dari dua kata yaitu basis dan data. Basis dapat diartikan sebagai gudang tempat berkumpul. Sedangkan data adalah represebtasi fakta dunia nyata yang mewakili objek seperti manusia, barang, hewan, peristiwa konsep, yang nyatakan dalam bentuk angka, huruf, simbol teks, gambar, bunyi atau kombinasinya.

          Basis data dapat didefinisikan dari beberapa sudut pandang diantaranya sebagai berikut :

1.        Sekumpulan data persistence (data disimpan defile sekunder atau data yang tahan lama) yang saling terkait, menggambarkan suatu organisasi (enterprise).

2.        Himpunan kelompok data (arsip) yang saling berhubungan yang diorganisasikan sedemikian rupa agar kelak dapat dimanfaatkan kembali dengan cepat dan mudah.

3.        Kumpulan data yang saling berhubungan yang disimpan secara bersama sedemikina rupa dan tanpa pengulangan (redudansi) yang tidak perlu, untuk memenuhi berbagai kebutuhan.

4.        Kumpulan file atau arsip yang saling berhubungan yang disimpan dalam media penyimpanan elektronis.

2.5.1   Tujuan basis data adalah sebagai berikut :

1.        Kemudahan dan kecepatan dalam pengambilan kembali data atau arsip.

2.        Efisiensi ruang dan waktu

3.        Keakuratan data

4.        Ketersediaan untuk proses pengambilan data yang diperlukan setiap saat

5.        Kelengkapan data-data yang diperlukan atau yang tersimpan

6.        Keamanan data

7.    Kebersamaan

2.5.2    Keuntungan Basis data

1.        Mereduksi redudansi yang akibatnya mengurangi inkonsistensi.

2.        Data dapat dishare antar aplikasi.

3.        Standarisasi data dapat dilakukan.

4.        Batasan security dapat diterapkan.

5.        Mengelola integritas (keterjaminan akurasi) data.

6.        Menyeimbangkan kebutuhan yang saling konflik.

Independensi data (objektif DBS) : kekebalan aplikasi terhadap perubahan struktur penyimpanan dan teknik pengaksesan data (basis data harus dapat berkembang tanpa mempengaruhi aplikasi yang telah ada).