Penyelesaian Masalah : Pencarian Berbentuk/Heuristik Search dan Eksplorasi
Heuristik
adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun
dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik
digunakan untuk mengevaluasi keadaankeadaan problema individual dan menentukan
seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang
diinginkan.
Jenisnya
adalah :
1. Generate and Test.
2. HillClimbing.
3. Best First Search.
4. Alpha
Beta Prunning,Means-End-Anlysis,Constraint Satisfaction, Simulated
Anealing, dll
Strategei pencarian berbentuk/heuristic search strategy
- 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.
2. 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.
Algoritma
A juga membutuhkan dua antrian, yaitu OPEN dan CLOSED. Selain itu, ada juga
fungsi heuristik yang memprediksi keuntungan tiap node yang di buat. Yang akan
memungkinkan algoritma untuk melakukan pencarian-pencarian lintasan yang lebih
di harapkan. Fungsi ini di sebut f’(n) sebagai pendekatan dari fungsi f(n) yang
merupakan fungsi evaluasi yang sebenarnya terhadap node n. dalam banyak
penarapan, akan lebih baik jika fungsi di definisikan sebagai kombinasi atau
jumlah dua komponen yaitu g(n) dan h(n). Fungsi g(n) merupakan ukuran biaya
yang di keluarkan dari keadaan awal sampai ke node n. Nilai yang didapat g(n)
merupakan jumlahan biaya penerapan setiap aturan yang dilakukan pada sepanjang
lintasan trbaik menuju suatu simpul dan bukan merupakan hasil estimasi.
Fungsi
h(n) merupakan pengukur biaya tambahan yang harus dikeluarkan dari node n
sampai mendapatkan tujuan. Perlu diketahui bahwa g(n), tidak negatif karena
bila negatif maka lintasan yang membalik siklus pada graf akan tampak lebih
baik dengan semakin panjangnya lintasan.
Secara
matematis,fungsi F sebagai estimasi fungsi evaluasi terhadap node
ndapat di tuliskan :
f’(n)
= g(n) + h’(n)
Dengan f’(n)
= fungsi evaluasi
g(n)
= biaya yang sudah di keluarkan dari keadaan awal sampai
keadaan
n
h’(n)
= estimasi biaya untuk sampai pada suatu tujuan mulai dari n
dari
fungsi di atas maka ada beberapa kondisi yang perlu diperhatikan, yaitu:
Jika
h = h’, berarti proses pencarian telah sampai ke tujuan ( goal ).
Jika
g = h’ = 0 maka f’ random, artinya system tidak dapat di
kendalikan.
Jika
g = k, k adalah konstanta dan biasanya bernilai 1, h’ = 0, artinya system
menggunakan
breadth first search.
3. Memory-Bounded Heuristic Search
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*.
Fungsi Heuristic
Heuristic
digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan
seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang
diinginkan.
Algoritma
pencarian lokal dan masalah optimisasi
Algoritma
pencarian lokal untuk masalah optimisasi kombinatorik biasanya
digunakan
pada pseudopolynomial running time dan algoritma polynomial-time
sering
tidak dapat menemukan solusi optimum lokal untuk masalah optimisasi
NP
−hard. Penelitian ini bertujuan mengenalkan konsep optimalitas ε-lokal dan
menunjukkan
bahwa optimum ε-lokal dapat diidentifikasi dengan waktu polynomial
pada
masalah ukuran dan 1/ε bilamana hubungan ketetanggan dapat dicari
dengan
polynomial time untuk ε > 0. Akibatnya, masalah optimisasi kombinatorial
memiliki
banyak pola pendekatan polynomial-time jika dan hanya jika
memiliki fully
polynomial-time pola tambahan (augmentation).
Hill Climbing Search
Hill Climbing ( HC ) atau pendakian
bukit merupakan salah satu metode yang masuk dalam kategori metode pencarian
heuristik. Dinamakan Hill Climbing ( HC ) atau pendakian bukit karena mempunyai
aturan produksi dengan cara menukar dua posisi kota yang saling berdekatan
seperti orang yang mendaki bukit. Hill Climbing ( HC ) dibagi menjadi dua jenis
yaitu Simple HC ( HC sederhana ) dan Steepest-Ascent HC ( HC dengan memilih
kemiringan yang paling tajam/curam ).
Simple
HC ( SHC ) bekerja dengan cara memilih secara langsung new state yang memiliki
keadaan lebih baik dari pada keadaan sebelumnya
tanpa memperhitungkan keadaan lain yang lebih “curam”.
Simulated annealing search
Simulated
Annealing adalah suatu algoritma optimasi yang mensimulasikan proses annealing
pada pembuatan materi yang terdiri dari butir kristal atau logam. 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
Local Beam Search
Dalam
ilmu komputer, beam search adalah
algoritma pencarian heuristik yang mengeksplorasi grafik dengan memperluas
simpul yang paling menjanjikan dalam rangkaian terbatas. Penelusuran beam
adalah optimalisasi pencarian terbaik pertama yang mengurangi kebutuhan memori.
Pencarian terbaik-pertama adalah pencarian grafik yang memerintahkan semua
solusi parsial (goal). Tapi dalam pencarian balok, hanya sejumlah solusi
parsial terbaik yang telah ditentukan dijaga sebagai kandidat.
Genetic Algorithm
Genetic
Algorithm(atau GA) adalah teknik pencarian dalam bidang komputasi untuk
menemukan solusi benar atau pendekatan untuk masalah optimasi dan pencarian.
Teknik dalam GA didasarkan pada biologi evolusioner seperti pewarisan, mutasi,
seleksi dancrossover.
GA
diimplementasikan sebagai proses simulasi yang dijabarkan sebagai berikut:
Populasi dari representasi abstrak (disebut kromosom, genotip, atau genom) dari
candidate solution(disebut individual, atau fenotip) dari optimasi yang berevolusi
ke solusi yang lebih baik. Biasanya solusi direpresentasikan ke dalam string
biner. Evolusi dimulai dari populasi dari individu yang dihasulkan secara
random dan terjadi dalam generasi. Di setiap generasi, fitnessdari setiap
individu dalam populasi dievaluasi, beberapa individu dipilih secara
stokastik(berdasarkan fitness) dan dimodifikasi(crossover dan kemungkinan
mutasi) untuk membentuk populasi baru. Populasi baru lalu dimanfaatkan untuk
iterasi selanjutnya. Secara umum, algoritma selesai jika telah menghasilkan
generasi maksimum atau hasil dalam populasi dirasa memuaskan (berdasarkan
berbagai parameter).
Agen Sistem 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.
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.
Comments
Post a Comment