Metode Pencarian (II)

Metode Pencarian

(Bagian II)

Pencarian dapat diartikan sebagai sebush proses pelacakan yang merupakan teknik untuk pencarian. Didalam pencarian ada dua kemungkinan hasil yang didapat yaitu menemukan dan tidak menemukan. Sehingga pencarian merupakan teknik yang penting dalam AI (Artificial Inteligen). Hal penting dalam menentukan keberhasilan sebuah sistem berdasarkan kecerdasan adalah kesuksesan dalam pencarian dan pencocokan. Pencarian adalah suatu proses mencari solusi dari suatu permasalahan agar dapat mendapat solusi melalui sekumpulan pencarian yang sudah diperoleh dengan semua kemungkinan keadaan. Untuk mengukur performansi metode pencarian, terdapat empat kriteria yang dapat digunakan:

·         Completeness (Kelengkapan)

·         Time compexity (Kekompleksan waktu)

·         Space complexity (Kekompleksan ruang)

·         Optimality (Optimal)

Ada beberapa teknik pelacakan :

·         Heuristic Search

Heuristic Search disebut sebagai model pencarian terbimbing atau sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness).

Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

Ada beberapa metode yang tesedia di dalam Heuristic Search diantaranya:

1.      Pembangkitan dan Pengujian (Generate And Test)

Generate And Test yaitu model pencarian dengan car pembangkitan dan pengujian dan merupakan pendekatan yang paling sederhana dari semua pendekatan yang lainnya.

Sebagai Contoh:

“Travelling Salesman Problem (TSP)” Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui rute terpendek dimana setaip kota hanya boleh dikkunjungi tepat  1 kali. Misalnya ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar di bawah ini: 

Sehingga penyelesaian dengan menggunakan metode Generate and Test akan seperti ini

Pendekatan ini meliputi langkah–langkah sebagai berikut :

o   Membuat/bangkitkan sebuah solusi yang memungkinkan. Untuk sebuah problema hal ini dapat berarti pembuatan sebuah titik khusus dalam ruang problema.

o   Melakukan pengujian untuk melihat apakah solusi yang dibuat benar–benar merupakan sebuah solusi, dengan cara membandingkan titik khusus tersebut dengan goal-nya (solusi).

o   Jika telah diperoleh sebuah solusi, langkah – langkah tersebut dapat dihentikan. Jika belum, kembalilah ke langkah pertama.

Jika pembangkitan atau pembuatan solusi – solusi yang dimungkinkan dapat dilakukan secara sistematis, maka prosedur ini akan dapat segera menemukan solusinya (bila ada).  Namun, jika ruang problema sangat besar, maka proses ini akan membutuhkan waktu yang lama. Metode generate and test ini kurang efisien untuk masalah yang besar atau kompleks.

                Sehingga alur pencarian dari persoalan diatas akan menjadi seperti ini:

      Contoh diatas pada pencarian ke-1 terdapat lintasan ABCD dengan panjang lintasan 19  dan lintasan yang terpilih ABCD ddengan panjang lintasan terpilih 19. Pada pencarian ke-2 terdapat lintasan ABDC dengan panjang lintasan 18  dan lintasan yang terpilih ABDC dengan panjang lintasan terpilih 18. Dan pada pencarian ke-3 terdapat lintasan ACBD dengan panjang lintasan 12  dan lintasan yang terpilih ACBD dengan panjang lintasan terpilih pun 12. Dan seterusnya.

2.      Hill Climbing

Hill Climbing disebut sebagai pencarian Pendakian Bukit. Hill Climbing merupakan salah satu variasi dari metode generate and test. Dimana umpan balik yang berasal dari prosedur uji digunakan untuk memutuskan arah gerak dalam ruang pencarian (search).

Dalam prosedur generate and test, respon fungsi uji hanyalah ya atau tidak. Tetapi di dalam prosedur Hill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan/target.

                        Berikut ini adalah contoh dari Hill Climbing:

Prosedur Hill Climbing :

o   Membuatlah solusi usulan pertama dengan cara yang sama seperti yang dilakukan dalam prosedur buat dan uji (generate and test). Periksalah apakah solusi usulan itu merupakan sebuah solusi. Jika ya, berhentilah. Jika tidak, kita lanjutkan ke langkah berikutnya.

o   Dari solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat sekumpulan solusi usulan yang baru.

o   Untuk setiap elemen kumpulan solusi tersebut, lakukanlah hal-hal berikut ini :

1.      Kirimkanlah elemen ini ke fungsi uji. Jika elemen ini merupakan sebuah solusi, berhentilah.

2.      Jika tidak, periksalah apakah elemen ini merupakan yang terdekat dengan solusi yang telah diuji sejauh ini. Jika tidak, buanglah.

3.      Ambilah elemen terbaik yang ditemukan di atas dan pakailah sebagai solusi usulan berikutnya. Langkah ini bersesuaian dengan langkah dalam ruang problema dengan arah yang muncul sebagai yang tercepat dalam mencapai tujuan.

o   Kembalilah ke langkah 2.

Sumber:

http://www.ziddu.com/download/23183192/MetodePencariandanPelacakan.docx.html

Pengantar Inteligensia Buatan – Heuristic Searching

Metode Pencarian (I)

Metode Pencarian

(Bagian I)

Pencarian dapat diartikan sebagai sebush proses pelacakan yang merupakan teknik untuk pencarian. Didalam pencarian ada dua kemungkinan hasil yang didapat yaitu menemukan dan tidak menemukan. Sehingga pencarian merupakan teknik yang penting dalam AI (Artificial Inteligen). Hal penting dalam menentukan keberhasilan sebuah sistem berdasarkan kecerdasan adalah kesuksesan dalam pencarian dan pencocokan. Pencarian adalah suatu proses mencari solusi dari suatu permasalahan agar dapat mendapat solusi melalui sekumpulan pencarian yang sudah diperoleh dengan semua kemungkinan keadaan. Untuk mengukur performansi metode pencarian, terdapat empat kriteria yang dapat digunakan:

·         Completeness (Kelengkapan)

·         Time compexity (Kekompleksan waktu)

·         Space complexity (Kekompleksan ruang)

·         Optimality (Optimal)

Ada beberapa teknik pelacakan :

·         Blind Search

Blind Search disebut sebagai model pencarian buta atau pencarian yang tidak memiliki inforamasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:
-          Membangkitkan simpul berdasarkan urutan
-          Jika ada solusi maka solusi akan ditemukan
-          Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).

Ada beberapa metode yang tersedia di dalam Blind Search diantaranya:

1.      Breadth First Search

Breadth First Search yaitu model pencarian melebar pertama atau juga merupakan  model pencarian yang memakai metode melebar. Untuk dapat mencari hasilnya, model Breadth First Serach ini menggunakan teknik pencarian persoalan dengan cara membuka node (titik) pada tiap levelnya.

Sebagai Contoh:

Jadi, untuk pohon biner :

Maka, urutan penelusurannya adalah : a – b – c – d – e – f – g – h – i – j – k – l

Salah satu cara implementasi BFS adalah dengan bantuan struktur data queue. Sama seperti stack pada DFS, queue yang digunakan adalah queue yang isi elemennya adalah simpul pohon / tree.  Berikut ini adalah urutan algoritmanya :

o   Memasukkan simpul root ke dalam antrian.

o   Memeriksa antrian terdepan apakah memiliki anak simpul.

o   Jika ya, masukan semua anak simpul ke dalam antrian.

o   Menghapus antrian terdepan.

o   Jika antrian kosong berhenti, tapi jika tidak kembali ke langkah dua.

Untuk gambar pohon biner di atas, urutan langkah dan kondisi queue pada setiap iterasinya adalah sebagai berikut :

Contoh diatas menggunakan prioritas untuk memasukkan anak simpul dari sebelah kiri terlebih dahulu ke dalam queue. Sehingga, pada iterasi 2 elemen A dihapus lalu memasukkan anak simpulnya yaitu B dulu, baru C ke dalam stack. Untuk penelusurannya yang dilihat adalah bagian yang berwarna biru, yaitu antrian terdepan yang setiap iterasinya memiliki urutan a – b – c – d – e – f – g – h – i – j – k – l. Sama seperti DFS lagi pada iterasi ke 13 itu kondisi antrian sudah kosong.

2.      Depth First Search

Depth-first Search disebut juga pencarian mendalam pertama. Sesuai dengan namanya “pencarian mendalam”, Depth First Search tidak mencari solusi per level, namun mencari pada kedalaman sebelah kiri terlebih dahulu, kemudian bila belum ditemukan targetnya maka akan dilanjutkan ke sisi sebelah kanan dan seterusnya sampai ditemukan target. Pada DFS memori yang digunakan tidak terlalu banyak karena tidak membuka semua node.

Sebagai Contoh:

Jadi, jika ada pohon biner seperti gambar di bawah ini :

Maka, urutan penelusurannya adalah : a – b – d – h – e – i – c – f – g – j – k – l

Dalam implementasinya DFS dapat diselesaikan dengan cara rekursif atau dengan bantuan struktur data stack. Stack yang digunakan adalah stack yang isi elemennya adalah simpul pohon / tree. Berikut ini adalah urutan algoritmanya :

o   Memasukkan simpul root ke dalam tumpukan dengan push.

o   Mengambil dan menyimpan isi elemen (berupa simpul pohon) dari tumpukan teratas.

o   Menghapus isi stack teratas dengan prosedur pop.

o   Periksa apakah simpul pohon yang disimpan tadi memiliki anak simpul.

o   Jika ya, push semua anak simpul yang dibangkitkan ke dalam stack.

o   Jika tumpukan kosong berhenti, tapi jika tidak kembali ke langkah dua.

Jadi, untuk gambar pohon biner di atas urutan langkah dan kondisi stack-nya setiap iterasi adalah :

Contoh diatas menggunakan prioritas untuk memasukkan anak simpul dari sebelah kanan terlebih dahulu ke dalam stack. Sehingga, pada iterasi 2 elemen A dihapus lalu memasukkan anak simpulnya yaitu C dulu, baru B ke dalam stack. Selain itu bisa dilihat stack teratas (yang diwarna biru) pada tiap iterasi memiliki urutan a – b – d – h – e – i – c – f – g – j – k – l. Pada iterasi ke 13 kondisi stack sudah kosong karena ketika simpul J dibangkitkan tidak ada anak simpul yang dimasukkan ke stack.

Sumber:

http://www.ziddu.com/download/23183192/MetodePencariandanPelacakan.docx.html

Pengantar Inteligensia Buatan – Heuristic Searching

A I

Artificial Intelegence (A I)

Artificial Intelligence atau Kecerdasan Buatan merupakan kemampuan dari computer digital atau robot yang dikendalikan computer untuk mengerjakan tugas-tugas yang berkaitan dengan kecerdasan (Encyclopedia Britannica).

System yang benar-benar cerdas mampu menyesuaikan dirinya dengan perubahan dalam masalah (automatic learning). Kecerdasan mesin komputernya mengikuti proses penyelesaian masalah seperti yang dilakukan manusia. System cerdas menunjukkan kecerdasan level mesin, penalaran, learning dan tidak harus self-adapting.

Bidang Kecerdasan Buatan (AI)

·         Tujuan utama :

Pengembangan software yang dimaksudkan agar mesin mampu untuk menyelesaikan masalah melalui penalaran yang mirip manusia.

·         Mencoba membangun system berbasis pada model representasi pengetahuan dan pemrosesan dalam pikiran manusia.

·         Meliputi kajian mengenai otak untuk memahami struktur dan fungsi-fungsinya.

·         Hadir sebagai sebuah disiplin ilmu sejak 1956. Gagal hidup dimasa awal, karena:
Tidak cukupnya pemahan mengenai kecerdasan  dan fungsi otak.
Kompleksitas dari masalah yang akan diselesaikan

·         Expert Systems – Cerita sukses AI tahun 1980-an

·         Case Based Reasoning Systems – Sukses sebagian

Sistem Pakar (Expert Systems)

System pakar dirancang untuk menyelesaikan masalah dalam domain (area) tertentu (Spesific Domain).

            Misalnya:

·         Expert Systems untuk membantu pedagan mata uang asing.

Sistem pakar dibangun dengan :

·         Menanyai pakar-pakar di domain tersebut

·         Menyimpan pengetahuan yang diperoleh dalan suatu bentuk yang sesuai bagi penyelesaian masalah, menggunakan penalaran sederhana.

System pakar digunakan dengan :

·         Pengguna meminta (melakukan query) untuk masalah yang ditetapkan oeh system (spesifik)

·         Menggunakan informasi query tersebut untuk menggambarkan inferensi dari basis pengetahuan

·         Memberikan jawaban atau menyarakankan cara-cara untuk menghimpun masukan lebih lanjut

Biasanya bentuk dari basis pengetahuan system pakar adalah suatu himpunan aturan IF …. THEN ….
*catatan : bukan pernyataan IF dalam kode program.

Area dari aplikasi Expert Systems:

·         Perbankan dari keuangan (penilaian kredit, kelangsungan proyek)

·         Pemeliharaan (diagnose kegagalan mesin)

·         Retail (saran pola membeli yang optimal)

·         Layanan Darurat (konfigurasi peralatan)

·         Hukum (aplikasi hokum dalam scenario kompleks)

Arsitektur Sistem Pakar

Sumber :

https://komputasi.files.wordpress.com/2012/09/kecerdasan-buatan-01.pdf

Fuzzy Logic

Fuzzy Logic

Logika fuzzy adalah suatu cara yang tepat untuk memetakan suatu ruang input kedalam suatu ruang output. Titik awal dari konsep modern mengenai ketidakpastian adalah paper yang dibuat oleh Lofti A Zadeh (1965), dimana Zadeh memperkenalkan teori yang memiliki objek-objek dari himpunan fuzzy yang memiliki batasan yang tidak presisi dan keanggotaan dalam himppunan fuzzy, dan bukan dalam bentuk logika benar (true) atau salah (false) tetapi dinyatakan dalam derajat (degree). Konsep seperti ini disebut dengan Fuzziness dan teorinya dinamakan Fuzzy Set Theory. Fuzziness dapat didefinisikan sebagai logika kabur berkenaan dengan semantic dari suatu kejadian, fenomena atau pernyatan itu sendiri. Sebagai contoh :

·         Manager pergudangan mengatakan pada manajer produksi seberapa banyak persediaan barang pada akhir minggu ini, kemudian manajer produksi akan menetapkan jumlah barang yang harus diproduksi esok hari.

Logika fuzzy adalah peningkatan dari logika Boolean yang berhadapan dengan konsep kebenaran sebagian. Logika fuzzy menggantikan kebenaran Boolean dengan tingkat kebenaran dan memungkinkan nilai keanggotaan antara 0 dan 1, tingkat keabuan dan juga hitam putih dan dalam bentuk linguistic.

Ada beberapa alasan mengapa orang menggunakan logika fuzzy (Kusumadewi S, Purnomo H, 2010) yaitu

·         Konsep logika fuzzy mudah dimengerti

·         Logika fuzzy sangat fleksibel

·         Logika fuzzy memiliki toleransi terhadap data-data yang tidak tepat.

·         Logika fuzzy mampu memodelkan fungsi-fungsi nonlinear yang sangat kompleks.

·         Logika fuzzy didasarkan pada bahasa alami.

Himpunan fuzzy memiliki 2 atribut, yaitu :

·         Linguistic yaitu penamaan suatu grup ysng mewakili suatu keadaan atau kondisi tertentu dengan menggunakan bahasa alami seperti : MUDA, PAROBAYA, TUA.

·         Numeris yaitu suatu nilai (angka) yang menunjukkan ukuran dari suatu variable seperti : 40, 25, 50 dsb.

Ada beberapa hal yang perlu diketahui dalam memahami system fuzzy (Aplikasi logika fuzzy untuk pendukung keputusan, Sri Kusumadewi, Hari Purnomo, Edisi kedua, Graha Ilmu, 2000) yaitu :

·         Varibel fuzzy
variable fuzzy merupakan variable yang hendak dibahas dala suatu system fuzzy. Contoh : umur, temperature, permintaan, dsb.

·         Himpunan fuzzy
himpunan fuzzy merupakan suatu grup yang mewakili suatu kondisi atau keadaan tertentu dalam suatu variable fuzzy.

Fungsi keanggotaaan

Fungsi keanggotaan adalah suatu kurva yang menunjukkan pemetaan titik-titik input kedalam nilai keanggotaannya sering juga disebut derajat keanggotaan yang memiliki interval antara 0 sampai 1. Ada beberapa fungsi yang bisa digunakan

·         Representasi liniear
Pemetaan input ke derajat keanggotaannya digambarkan sebagai suatu garis lurus. Bentuk ini paling sederhana dan menjadi pilihan yang baik untuk suatu konsep yang kurang jelas.

·         Representasi kurva segitiga
Kurva segitiga pada dasarnya merupakan gabungan antara 2 garis (linear).

·         Representasi kurva trapezium
Kurva trapezium pada dasarnya seperti bentuk segitiga hanya saja ada titik yang memiliki nilai keanggotaan.

Riset-riset terkait

Ada beberapa riset yang telah dilakukan yang berkaitan dengan penelitian ini diantaranya adalah:

            Kusumadewi, S (2004) dalam jurnalnya yang berjudul fuzzy quantification theory I untuk analisis hubungan antara penilaian kinerja dosen oleh mahasiswa, kehadiran dosen, dn nilai kelulusan mahasiswa, menjelaskan bahwa fuzzy quantification theory I adalah suatu metode untuk menentukan hubungan antar variable kualitatif yang diberikan dengan nilai antara 0 sampai 1, dengan variable-variabel numeris dalam fuzzy group yang diberikan pada sampel. Pada penelitian tersebut, fuzzy quantification theory akan digunakan untuk menentukann seberapa besar factor-faktor kualitatif penilaian mahasiswa terhadap kinerja dosen jurusan Teknik Informatika Universitas Islam Indonesia, mempengaruhi hubungan antara kehadiran dosen dan nilai akhir mahasiswa. Hasil penelitian menunjukan bahwa factor kemampuan dosen mendorong mahasiswa untuk berperan aktif, memiliki pengaruh yang paling tinggi diantara factor-faktor yang lainnya, dalam kaitannya dengan pengaruh antara kehadiran dosen mengajar denga nilai kelulusan mahasiswa > ‘B’. Pengaruh ini akan sangat kuat apabila kehadiran dosen mengajar lebih dari sepuluh kali.

Contoh Aplikasi Logika fuzzy :

1.      Pengontrol kereta bawah tanah disendai, Jepang.

2.       Pengatur mekanisme otofocus pada kamera

3.      Sistem pengeraman mobil (nissan)

4.       Penghematan konsumsi daya listrik pada AC

5.       Otomatisasi kecepatan putar mesin cuci terhadap tebal-tipis atau banyak-sedikit jenis pakaian dalam mesin cuci

6.       Penentuan prestasi mahasiswa berdasarkan great IPK

7.       Kontrol jumlah produksi barang berdasarkan permintaan konsumen

8.      Penentuan karyawan terbaik berdasarkan indeks kinerja

9.      Kontrol kecepatan kendaraan berdasarkan cuaca terkini

Contoh-Contoh problem yang dapat dipetakan dengan fuzzy:

1.      Manager-gudang mengatakan kepada manager produksi “kita telah mendapat pesanan lebih besar dalam minggu ini. Tolong dicekkan, berapa banyak jumlah persediaan kita di gudang. Dan berapa besara barang yang harus akan diproduksi”.

2.      Seseorang mengatakan kepada kita “Seberapa sejuk ruangan yang saudara inginkan ? Saya akan mengatur putaran kipas dalam ruang ini.

3.      Bila seseorang mengatakan “Jika saat ini cuacanya cerah dan panas, saya akan mengemudi dengan cepat“

Arsitektur Logika Fuzzy :

1. Fuzzifikasi, Proses konversi input-input (masukan) yang bersifat tegas (crips) ke dalam bentuk (fuzzy) variabel linguistik menggunakan fungsi keanggotaan
2. Sistem Inferensi, Proses pengkonversian input-fuzzy menggunakan aturan-aturan “If-Then” menjadi Output-Fuzzy
3. Defuzzifikasi, Proses konversi Output-Fuzzy dari sistem inferensi ke dalam bentuk tegas (crips) menggunakan fungsi keanggotaan serupa (sebelumnya) menjadi sebuah nilai

Sumber :

http://repository.usu.ac.id/bitstream/123456789/31373/3/Chapter%20II.pdf

https://yusronrijal.wordpress.com/category/artificial-intellegence/fuzzy-logic/