Search(Cari/lacak)Dalam Bidang Artificial Intelligence


Pencarian atau pelacakan merupakan salah satu teknik untuk menyelesaikan permasalahan dalam bidang kecerdasan buatan. Permasalahan pencarian adalah merupakan yang sering dijumpai oleh peneliti di bidang kecerdasan buatan. Permasalahan ini merupakan hal penting dalam menentukan keberhasilan sistem kecerdasan buatan. :arrow:

Contoh beberapa aplikasi yang mengunakan teknik pencarian, yaitu :
– Masalah routing (travelling salesman problem)
– Parsing bahasa dan interprestasinya
– Permainan
– Logika pemrograman (pencarian fakta dan implikasinya)
– Pengenalan pola
– Sistem pakar berbasis kaidah (rule based expert system)

Metode pencarian dikatakan penting untuk menyelesaikan permasalahan karena setiap state (keadaan) menggambarkan langkah-langkah untuk menyelesaikan permasalahan.
Metode pencarian dikatakan penting untuk perencanaan karena dalam sebuah permainan akan menentukan apa yang harus dilakukan, di mana setiap state menggambarkan kemungkinan posisi pada suatu saat.
Metode pencarian adalah bagian dari kesimpulan, di mana setiap state menggambarkan hipotesis dalam sebuah rangkaian deduktif.

Menefinisikan Masalah Sebagai Suatu Ruang Keadaan
Secara umum,untuk mendeskripsikan suatu permasalahan dengan baik harus
1. Mendefinisikan suatu ruang keadaan
2. Menerapkan satu atau lebih keadaan awal
3. Menetapkan satu atau lebih tujuan
4. Menetapkan kumpulan aturan

Teknik Pencarian
Pada dasarnya ada dua teknik pencarian yaitu yang biasanya digunakan :
1. Pencarian buta (blind search)
2. Pencarian terbimbing (heuristic search)

a. Pencarian Buta
Pencarian buta merupakan sekumpulan prosedur yang digunakan dalam melacak ruang keadaan. Pencarian berlangsung sampai solusi terakhir ditemukan. Idenya adalah menguji seluruh kemungkinan yang ada untuk menemukan solusi.

  • Pencarian Melebar Pertama (Breadth-First Search)

Pada metode Breadth-First Search, 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 ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya demikian pula dari kiri ke kanan sampai ditemukannya solusi.
Algoritma :
– Buat sebuah antrian, inisialisasi node pertama dengan Root dari tree
– Bila node pertama, jika ≠ GOAL, diganti dengan anak-anaknya dan diletakkan di belakang per level
– Bila node pertama = GOAL, selesai
Keuntungan :
– Tidak akan menemui jalan buntu
– Jika ada satu solusi, maka breadth first search akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.
Kelemahan :
– Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon
– Kemungkinan ditemukan optimal local

  • Pencarian Mendalam Pertama (Depth-First Search)

Pada Depth First Search, proses pencarian akan dilaksanakan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukannya solusi.
Algoritma :
– Buat sebuah antrian, inisialisasi node pertama dengan Root dari tree
– Bila node pertama, jika ≠ GOAL, node dihapus diganti dengan anak-anaknya dengan urutan LChild
– Bila node pertama = GOAL, selesai
Keuntungan :
– Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan
– Menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan
Kelemahan :
– Kemungkinan terjebak pada optimal lokal
– Hanya akan mendapatkan 1 solusi pada setiap pencarian

  • Pencarian dengan Mendaki Bukit (Hill Climbing Search)

Algoritma :
– Buat sebuah antrian, inisialisasi node pertama dengan Root dari tree
– Bila node pertama, jika ≠ GOAL, node dihapus diganti dengan anak-anaknya dengan urutan yang paling kecil jaraknya
– Bila node pertama = GOAL, selesai
Keuntungan :
– Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan
– Metode hill climbing search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan
Kerugian :
– Algoritma akan berhenti kalau mencapai nilai optimum lokal
– Perlu menentukan aturan yang tepat

  • Pencarian dengan Best-First Search

Algoritma :
–   Bila sebuah antrian, inisialisasi node pertama dengan Root dari tree
– Bila node pertama, jika ≠ GOAL, node dhapus dan diganti dengan anak-anaknya. Selanjutnya keseluruhan node yang ada di Queu di-sort Ascending
–   Bila node pertama = GOAL, selesai
Keuntungan :
–  Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan aktif saja yang dismpan
–  Secara kebetulan, metode best first search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan
Kerugian :
– Algoritma akan berhenti kalau mencapai nilai optimum lokal
– Tidak diijinkan untuk melihat satupun langkah sebelumnya

b. Pencarian Heuristic
Kata heuristic berasal dari bahasa Yunani heuriskein dari kata dasar eureka atau heurika yang berarti mengungkap atau menemukan.
Dalam Artificial Intelligence, heuristic diperkenalkan sebagai suatu teknik yang meningkatkan efisiensi proses pencarian, yang dimungkinkan dengan mengorbankan kelengkapan.
Menggunakan heuristic kita berharap mendapatkan solusi yang baik dari masalah yang sulit.

Teknik Search
– Arah search
Dapat dilakukan :
Maju, bermula dari keadaan awal (start state)
Mundur, di awali dari keadaan tujuan (goal stat)

Topologi proses search
Ada dua macam penggambaran problem, yatiu dalam bentuk :
1. Pohon (tree)
2. Graf (graph) : graf berarah dan graf tidak berarah

a. Pohon Pencarian
Untuk menghindari kemungkinan adanya proses pencarian suatu node secara berulang, maka digunakan struktur pohon.
Struktur pohon digunakan untuk meggambarkan keadaan secara hirarkis. Pohon juga terdiri dari beberapa node. Node yang terletak pada level-0 disebut juga “akar”. Node akar menunjukkan keadaan awal yang biasanya merupakan topik atau obyek. Node akar ini terletak pada level ke-0. Node akar mempunyai beberapa percabangan yang teridri atas beberapa node successor yang sering disebut dengan nama “anak” dan merupakan node-node perantara. Namun jika dilakukan pencarian mundur, maka dapat dikatakan bahwa node tersebut memiliki predececesor. Node-node yang tidak mempunyai anak sering disebut dengan nama node “daun” yang menunjukkan akhir dari suatu pencarian, dapat berupa tujuan yang diharapkan (goal) atau jalan buntu (dead end).

b. Graf Keadaan
Graf terdiri dari node-node yang menunjukkan keadaan, yaitu keadaan awal dan keadaan baru yang akan dicapai dengan menggunakan operator. Node-node dalam graf keadaan saling dihubungkan dengan menggunakan arc (busur) yang diberi panah untuk menunjukkan arah dari suatu kedaan ke keadaan berikutnya.
Metode pencarian akan berusaha menemukan kombinasi dari item-item yang dimulai dari start menuju ke goal.

Referensi :
Modul / slide Definisi dan Masalah Artificial Intelligence – BSI, tahun pembuatan 2006.
Bab 4 Algoritma Pencarian (Searching Algorithm), oleh Entin – Gunadarma, tahun pembuatan 2007. (http://bsavitri.staff.gunadarma.ac.id).

About herman
workhard and be nice to people

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: