Pencarian Berbentuk / Heuristik Search dan Eksplorasi
Strategi
Pencarian
Terdapat empat kriteria dalam strategi
pencarian, yaitu:
- Completeness: Apakah strategi tersebut menjamin penemuan solusi jika solusinya memang ada?
- Time complexity: Berapa lama waktu yang diperlukan?
- Space complexity: Berapa banyak memori yang diperlukan?
- Optimality: Apakah strategi tersebut menemukan solusi yang paling baik jika terdapat beberapa solusi berbeda pada permasalahan yang ada?
1. Pencarian
Berbentuk Dan Eksplorasi
- Greedy Best First Search
Greedy Best-First adalah algoritma best-first yang paling
sederhana dengan hanya memperhitungkan biaya perkiraan (estimated cost) saja,
yakni f(n) = h(n). Biaya yang sebenarnya (actual cost) tidak diperhitungkan.
Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya,
maka algoritma ini menjadi tidak optimal
- A* Search
Algoritma A* merupakan algoritma best first search dengan
modifikasian fungsi heuristik, yang akan meminimumkan total biaya lintasan, dan
pada kondisi yang tepat akan memberikan solusi yang terbaik dalam waktu yang
optimal.
- 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.
2. Fungsi
Heuristic
Heuristic Search adalah pencarian bersyarat
(terbimbing). Artinya, solusi yang diperoleh adalah solusi yang terbaik, bukan
solusi sekali ketemu. Bagian-bagiannya adalah
[masalah]-[pencarian]-[syarat]-[solusi]. Misal contoh masalah pada kasus di
atas, Ambillah kelereng merah yang tidak pecah dan tidak lonjong. Sehingga
ketika ketemu kelereng merah dan ada pecahnya, itu masih bukan solusi karena
tidak sesuai dengan syarat (tidak pecah dan tidak lonjong).
Heuristic digunakan untuk mengevaluasi keadaan-keadaan
problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan
untuk mendapatkan solusi yang diinginkan.
3.
Algoritma Pencarian Local dan Masalah Optimasi, meliputi :
- Hill Climbing Search
Hill Climbing berbeda Generate-and-Test, yaitu pada feedback
dari prosedur test untuk membantu pembangkit menentukan yang langsung
dipindahkan dalam ruang pencarian. Dalam prosedur Generate & test , respon
fungsi pengujian hanya ya atau tidak. Tapi jika pengujian ditambahkan dengan atauran
fungsi-fungsi yang menyediakan estimasi dari bagaimana mendekati state yang
diberikan ke state tujuan, prosedur pembangkit dapat mengeksplorasi ini
sebagaimana ditunjukkan di bawah. HC sering digunakan jika terdapat fungsi
heuristic yang baik untuk mengevaluasi state. 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.
- Simulated Annealing
Simulated 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 mengeksplorsebuah graf dengan cara meng-expandnode anak yang
paling “menjanjikan” (yang paling optimal) dalam sebuah memori yang terbatas.
Algoritma ini merupakan optimisasi darialgortima pencarian breadth-first
searchdan best-first search dalam hal penggunaan memori.
Algoritma ini pada setiap langkahnya seakan-akan
memotong/memangkas node-node anakyang dianggap “kurang menjanjikan” (kurang
optimal) untuk mengurangi kebutuhan memoripenyimpanan yang akan digunakan.
Pemotongan atau pemangkasan node anak ini ditentukanberdasarkan nilai heuristik
yang spesifik terhadap permasalah yang dihadapi. Node-nodeanak yang disimpan
sebagai kandidat node untuk di-expandinilah yang disebut dengan beam.Local Beam
Search menggunakan algoritma breadth-first searchuntuk menelusuri(men-generate)
kemungkinan node yang akan di-expand(node-node anaknya), lalumengurutkannya
berdasarkan nilai heuristik masing-masing. Algoritma local beam searchinihanya
mengambil/meng-expand node-node anaknya dengan jumlah tertentu saja dilihat
darinilai heuristik yang paling optimum (disebut dengan beam width). Node-node
yang beradapada urutan kurang dari beam widthinilah yang nantinya akan
di-expand. Semakin banyakbeam 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.
- Genetic Algoritma
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.
4. 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.
3. 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 :
- · Membantu pemakai menetukan produk yang dibeli.
- · Mencarikan spesifikasi dan mengkajinya.
- · Membantu rekomendasi.
- · Membandingkan belanjaan untuk mendapatkam harga terbaik untuk produk yang dikehendaki.
- · Mengamati dan mengenalkan kepad pemakai penawaran dan diskon khusus.
Berbagai aplikasi yang lain antara lain untuk menyortir
surat elektronis dan mengamati hasil perbandingan suatu olahraga tertentu
(misalnya sepakbola) dari berbagai situs Web dan kemudian melaporkan hasilnya
dalam bentuk surat elektronis ke para anggota yang menginginkan hasil
tersebut.
CREDITS:
Komentar
Posting Komentar