Pencarian Berbentuk atau Heuristik Search dan Eksplorasi

Pengertian Heuristik Search

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan.

Heuristic Search sering disebut juga dengan Informed Search. Pencarian dengan algoritma ini menggunakan knowledge base yang spesifik kepada permasalahan yang dihadapi disamping dari definisi masalahnya itu sendiri. Metode ini mampu menemukan solusi secara lebih efisien daripada yang bisa dilakukan pada metode uninformed strategy.

Pada pencarian dengan menggunakan metode Uniform Cost Search, kita membandingkan nilai pada path yang ada, dan kemudian akan melakukan ekspansi pertama kali pada path dengan nilai yang terkecil. Nilai path ini biasanya dilambangkan dengan g(n). Lebih lanjut lagi dari metode pencarian tersebut, pada Informed Search Algorithm, kita akan mengenal nilai estimasi (prediksi) dari satu node ke node yang lainnya. Nilai estimasi ini biasanya dilambangkan dengan h(n). Jika n adalah goal node, maka nilai h(n) adalah nol.

Strategi Pencarian Berbentuk atau Heuristic Search Strategy

1.      Greedy Best First Search

Metode pencarian ini melakukan ekspansi node yang memiliki jarak terdekat dengan goal. Namun, ekspansi yang dilakukan pada metode ini menggunakan evaluasi node hanya dengan melihat kepada fungsi heuristiknya. Dengan kata lain, yang dibandingkan untuk penentuan ekspansi node adalah nilai estimasi/prediksinya saja.

                     f(n) = h(n)

2.      A* Search

Bentuk dari Best First Search yang paling dikenal adalah algoritma pencarian A* (dibaca dengan “A-star”). Sedikit berbeda dengan Greedy yang hanya melihat kepada nilai h(n), pencarian dengan A* melihat kepada kombinasi nilai dari pathnya yaitu g(n) dengan nilai estimasi yaitu h(n).

                    f(n) = g(n) + h(n)

3.      Memory-bounded Heuristic Search

Memory Bounded merupakan algoritma pencarian yang dapat menggunakan semua memori yang tersedia untuk melakukan pencarian. Menggunakan lebih banyak memori hanya dapat meningkatkan efisiensi pencarian, salah satunya bisa selalu mengabaikan ruang tambahan, tetapi biasanya lebih baik untuk mengingat node daripada harus membuatnya kembali bila diperlukan.

Fungsi Pencarian Heuristik

Adalah untuk mengevaluasi keadaan-keadaan masalah individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan

Algoritma Pencarian Lokal dan Masalah Optimisasi

Dalam menjalankan proses pencarian, terdapat berbagai jenis algoritma yang digunakan. Algoritma yang digunakan ini memiliki perbedaannya masing-masing yang mempengaruhi hasil dari pencarian heuristic ini. Algoritma-algoritma tersebut adalah :

1.      Hill Climbing Search

Algoritma ini bekerja dengan feedback dari prosedur test untuk membantu pembangkit menentukan yang langsung dipindahkan dalam ruang pencarian. Algoritma Hill Climbing Search ini sering digunakan jika terdapat fungsi heuristik yang biasanya digunakan untuk mengevaluasi state atau suatu keadaan.

Sebagai contoh, anda berada di sebuah kota yang tidak dikenal, tanpa peta dan anda ingin menuju ke pusat kota. Cara sederhana adalah gedung yang tinggi. Fungsi heuristics-nya adalah jarak antara lokasi sekarang dengan gedung yang tinggi dan state yang diperlukan adalah jarak yang terpendek.

2.      Simulated Annealing

Simulated annealing adalah salah satu algoritma optimisasi yang bersifat generic yang berbasiskan probabilitas dan mekanika statistik. Algoritma ini dapat digunakan untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahan. Masalah yang membutuhkan pendekatan Simulated Annealing adalah masalah-masalah optimisasi kombinatorial, di mana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan itu.

3.      Local Beam Search

Local Beam Search adalah sebuah algoritma pencarian heuristik yang mengeksplorasi sebuah graf dengan cara meng-expand node anak yang paling ‘menjanjikan’ (yang paling optimal) dalam sebuah memori yang terbatas. Algoritma ini merupakan optimisasi dari algortima pencarian breadth-first search dan best-first search dalam hal penggunaan memori.

            Algoritma ini pada setiap langkahnya seakan-akan memotong/memangkas node-node anak yang dianggap “kurang menjanjikan” (kurang optimal) untuk mengurangi kebutuhan memori penyimpanan yang akan digunakan. Pemotongan atau pemangkasan node anak ini ditentukan berdasarkan nilai heuristik yang spesifik terhadap permasalah yang dihadapi. Node-node anak yang disimpan sebagai kandidat node untuk di-expandinilah yang disebut.Local Beam yang dimana Local Beam ini menggunakan algoritma breadth-first search untuk menelusuri kemungkinan node yang akan di-expand, lalu mengurutkannya berdasarkan nilai heuristik masing-masing. Algoritma local beam search ini hanya mengambil node-node yang memiliki jumlah tertentu saja. Jumlah ini dilihat dari nilai heuristik yang paling optimum (disebut dengan beam width). Node-node yang berada pada urutan kurang dari beam widthinilah yang nantinya akan di-expand. Semakin banyak beam width, maka semakin sedikit node-node anak yang akan dieliminasi. Untuk kasusdengan nilai beam widthsama dengan tak terhingga (infinite), maka algoritma ini sama saja dengan algoritma breadth-first search.

4.      Genetic Algorithm

Genetic Algorithm merupakan metode pembelajaran heuristic yang adaptif, karena itu bisa jadi terdapat beberapa versi dari Genetic Algorithm, yang menyesuaikan dengan permasalahan yang dihadapi. Genetic Algorithm juga merupakan algoritma yang efektif dan sederhana dan relatif mudah untuk diimplementasikan.

Algoritma genetik yang dilaksanakan dalam simulasi komputer dimana sebuah populasi representasi abstrak (disebut kromosom atau genotipe dari genom) dari solusi-solusi calon (disebut individu, makhluk, atau fenotip) untuk sebuah masalah optimasi berkembang menuju solusi yang lebih baik. Secara tradisional, solusi direpresentasikan dalam biner sebagai benang dari 0s dan 1s, tapi encoding lain juga mungkin.

Agen Pencarian Online dan Lingkungan yang Tidak diketahui

Agen yang berupa perangkat lunak atau biasa disebut agen cerdas, adalah perangkat lunak yang dapat bertindak seperti orang yang mampu berinteraksi dengan pencarian online dan lingkungan. Contohnya yang sedang banyak digunakan :

1.      Agen Sitem Operasi

Agen sistem operasi digunkan untuk membantu penggunaan sistem operasi. Contoh, Microsoft memiliki sejumlah agen yang dinamakan Wizard pada sistem operasi yang dibuatnya, misalnya Windows NT. Agen ini digunakan antara lain untuk menambah nama pemakaki, mengelola grup pemakai, dan manajemen berkas.

2.      Agen Spreadsheet

Agen spreadsheet digunakan untuk membuat program spreadsheet menjadi lebih mudah digunakan oleh pemakai. Contoh : Office Assistant pada Excel dapat “mengamati” pemakai dan jika terjadi sesuatu yang dipandang perlu untuk dibantu, agen cerdas ini akan memberikan saran.

1.      Agen Perdagangan Elektronis

Agen untuk perdagangan elektronis digunakan untuk membantu pemakai yang akan melakukan belanja secara online. Perangkat lunak seperti ini dapat membantu pemakai dengan berbagai cara berikut :

a.       Membantu pemakai menetukan produk yang dibeli.

b.      Mencarikan spesifikasi dan mengkajinya.

c.       Membantu rekomendasi.

d.      Membandingkan belanjaan untuk mendapatkam harga terbaik untuk produk yang dikehendaki.

e.       Mengamati dan mengenalkan kepad pemakai penawaran dan diskon khusus.

Presentasi atau PPT dari Materi ini.