PENCARIAN BERBENTUK / HEURISTIK SEARCH DAN EKSPLORASI

Posted by : Praditya Ivan Kamis, 05 Oktober 2017

A. STRATEGI PENCARIAN BERBENTUK / HEURISTIC SEARCH STRATEGY

Pencarian dengan algoritma ini menggunakan knowledge 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.

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)
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)
SMA* atau Simplified Memory Bounded A*
SMA* atau Simplified Memory Bounded A* adalah algoritma pencarian jalur terpendek berdasarkan dari algoritma A*. Keuntungan utama dari algo SMA* adalah dia menggunakan bounded memory, sementara algo A* mungkin membutuhkan memori exponensial. Semua karakteristik di algo SMA* diturunkan dari A*.

Seperti A *, algoritma SMA* memperluas cabang yang paling menjanjikan menurut heuristik. Apa yang membuat SMA * terpisah adalah SMA* memangkas simpul yang ekspansinya telah diungkapkan kurang menjanjikan dari yang diharapkan. Pendekatan ini memungkinkan algoritma untuk mengeksplorasi cabang dan backtrack untuk mengeksplorasi cabang lain.

Ekspansi dan pemangkasan simpul didorong karena SMA* menjaga dua nilai f untuk setiap simpul. Simpul x menyimpan nilai f(x) yang memperkirakan biaya mencapai tujuan dengan mengambil jalan melalui simpul tersebut. Semakin rendah nilai, semakin tinggi prioritas. Seperti di A * nilai ini diinisialisasi dengan h (x) + g (x), tetapi kemudian akan diperbarui untuk mencerminkan perubahan estimasi ketika anak-anaknya diperluas. Sebuah simpul yang sudah diperluas sepenuhnya akan memiliki nilai f setidaknya setinggi dari suksesornya. Selain itu, simpul menyimpan nilai f dari suksesor terbaik yang telah dilupakan. Nilai ini dikembalikan jika suksesor yang telah dilupakan itu dinyatakan sebagai suksesor paling menjanjikan.

SMA* merupakan algoritma yang:
1. Bekerja dengan heuristic, seperti A*
2. Selesai jika memori yang diperbolehkan cukup tinggi untuk menyimpan solusi terdangkal
3. Optimal jika memori yang diperbolehkan cukup tinggi untuk menyimpan solusi optimal terdangkal, jika tidak dia akan mengembalikan solusi terbaik yang ada di memori
4. Menjauhi pernyataan yang diulang-ulang selama batas memori memperbolehkannya
5. Menggunakan semua memori yang ada
6. Memperbesar batas memori dari algoritma hanya akan mempercepat perhitungan
7. Ketika memori cukup ada untuk memuat seluruh pohon pencarian, maka perhitungan mempunyai kecepatan yang optimal

B. FUNGSI HEURISTIK

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian (pencarian yang lebih simple). Namun kemungkinan juga dapat mengngorbankan kelengkapan (complateness).
Fungsi Heuristic digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan

C. ALGORITMA PENCARIAN LOKAL DAN MASALAH OPTIMISASI

HILL CLIMBING SEARCHMetode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnyayang mungkin.

Algoritma:

1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.

a) Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang : Cari operator yang belum digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.

b) Evaluasi keadaan baru tersebut :
- Jika keadaan baru merupakan tujuan, keluar
- Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
- Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
SIMULATED ANNEALING SEARCHSimulated annealing adalah salah satu algoritma untuk untuk optimisasi yang bersifat generik. Berbasiskan probabilitas dan mekanika statistik, algoritma ini dapat digunakan untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahan. Masalah yang membutuhkan pendekatan SA adalah masalah-masalah optimisasi kombinatorial,
di mana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan itu. Annealing adalah satu teknik yang dikenal dalam bidang metalurgi, digunakan dalam mempelajari proses pembentukan kristal dalam suatu materi. Agar dapat terbentuk susunan kristal yang sempurna, diperlukan pemanasan sampai suatu tingkat tertentu, kemudian dilanjutkan dengan pendinginan yang perlahan-lahan dan terkendali dari materi tersebut. Pemanasan materi di awal proses annealing, memberikan kesempatan pada atom-atom dalam materi itu untuk bergerak secara bebas, mengingat tingkat energi dalam kondisi panas ini cukup tinggi. Proses pendinginan yang perlahan-lahan memungkinkan atom-atom yang tadinya bergerak bebas itu, pada akhirnya menemukan tempat yang optimum, di mana energi internal yang dibutuhkan atom itu untuk mempertahankan posisinya adalah minimum.
LOCAL BEAM SEARCH
Local Beam Search adalah sebuah algoritma pencarian heuristik yang mengeksplor 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- expand inilah yang disebut dengan beam.
Local Beam Search menggunakan algoritma breadth-first search untuk menelusuri
(men- generate ) kemungkinan node yang akan di- expand (node-node anaknya), lalu mengurutkannya berdasarkan nilai heuristik masing-masing. Algoritma local beam search ini hanya mengambil/meng- expand node-node anaknya dengan jumlah tertentu saja dilihat dari nilai heuristik yang paling optimum (disebut dengan beam width ). Node-node yang berada pada urutan kurang dari beam width inilah yang nantinya akan di- expand . Semakin banyak beam width , maka semakin sedikit node-node anak yang akan dieliminasi. Untuk kasus dengan nilai beam width sama dengan tak terhingga ( infinite ), maka algoritma ini sama saja dengan algoritma breadth-first search .
GENETIC ALGORITHM
Genetic Algorithm adalah Teknik pencarian yang di dalam ilmu komputer untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian. Algoritme genetik adalah kelas khusus dari algoritme evolusioner dengan menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan, mutasi, seleksi alam dan rekombinasi (atau crossover)
- Mutasi : Mencoba kombinasi proses secara acak dan mengevaluasi hasilnya.
- Crossover : Mengombinasi bagian dari hasil yang baik dengan harapan dapat memperoleh hasil yang lebih baik.
- Seleksi : memilih proses-proses yang baik dan membuang yang jelek.
Algoritme Genetik pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York, Amerika Serikat. Dia beserta murid-murid dan teman kerjanya menghasilkan buku berjudul "Adaption in Natural and Artificial Systems" pada tahun 1975.

Algoritme Genetik khususnya diterapkan sebagai simulasi komputer dimana sebuah populasi representasi abstrak (disebut kromosom) dari solusi-solusi calon (disebut individual) pada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai string '0' dan '1', walaupun dimungkinkan juga penggunaan penyandian (encoding) yang berbeda. Evolusi dimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam generasi-generasi. Dalam tiap generasi, kemampuan keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritme.

D. AGEN PENCARIAN ONLINE DAN LINGKUNGAN YANG TIDAK DIKETAHUI

Agen yang berupa perangkat lunak, atau bisa disebut agen cerdas, adalah perangkat lunak yang dapat bertindak seperti orang yang mampu berinteraksi dengan lingkungan. Contoh:

Agen sistem operasi digunakan untuk membantu penggunaan sistem operasi digunakan untuk membantu penggunaan sistem operasi. Contoh, microsoft memiliki sejumlah agen yang dinamakan wizard pada sistem operasi yang di buatnya; misalnya Windows NT. Agen ini digunakan antara lain untuk menambah nama pemakai, mengelola grup pemakai, dan manajemen berkas.
Agen spreadsheet digunakan untuk membuat program spreadsheet menjadi lebih mudah digunakan oleh pemakai. Contoh, Office Assistant pada excel dapat “mengamati” pemakaidan jika terjadi sesuatu yang perlu untuk dibantu, agen cerdas akan memberikan saran.
Agen untuk perdagangan elektronis digunakan untuk membantu pemakai yang akan melakukan belanja secara online.