Strategi pencarian berbentuk/heuristic search stragegy
Heuristic Search
merupakan metode pencarian yang memperhatikan nilai heuristik (nilai
perkiraan).Teknik pencarian heuristik (heuristic searching) merupakan suatu
strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu
problema secara selektif, yang memandu proses pencarian yang kita lakukan di
sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan
mengesampingkan usaha yang bodoh dan memboroskan waktu.
Heuristik adalah
sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan
kemungkinan mengorbankan kelengkapan (completeness). Heuristic Search
memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik). Fungsi
heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual
dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan
solusi yang diinginkan.
Jenis-jenis Heuristic Searching :
1. 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
A* adalah algoritma
best-first search yang menggabungkan Uniform Cost Search dan Greedy Best-First
Search. Biaya yang diperhitungkan didapat dari biaya sebenarnya ditambah dengan
biaya perkiraan. Dalam notasi matematika dituliskan sebagai f(n)= g(n) + h(n). Dengan
perhitungan biaya seperti ini, algoritma A* adalah complete dan optimal.
3. SMA (Simplified
Memory-Bounded A*)
SMA* adalah contoh
dari sebuah mekanisme pencarian “lossy“. Dalam rangka untuk mengurangi konsumsi
memori, hal ini membuang informasi, dengan asumsi bahwa informasi yang dibuang
itu tidak penting. Bagaimanapun, tidak ada jaminan bahwa hal itu tidak penting.
Dalam semua kasus dengan SMA*, jalur yang ditemukan tidak memiliki jaminan
menjadi jalur yang optimal. Pada awal pencarian, node yang tidak menjanjikan
bisa saja dibuang.
Menetapkan limit yang
besar pada ukuran open list dapat membantu meringankan masalah ini, namun
fungsi untuk mengurangi penggunaan memori menjadi terbuang. Pada kasus ekstrem
yang lain, dengan memberi limit 1 simpul pada open list, ini bisa mempercepat
sekaligus mengurangi penggunaan memori dalam pencarian, namun jalur yang
ditemukan bisa tidak optimal .
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
1. Hill Climbing Search
Metode 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.
2. Simulated Annealing
Search
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.
3. Local Beam Search
Local 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 penelusuran grafik yang memerintahkan
semua solusi parsial (negara bagian) menurut beberapa heuristik yang mencoba
memprediksi seberapa dekat solusi parsial dengan solusi lengkap (goal state). Tapi
dalam pencarian balok, hanya sejumlah solusi parsial terbaik yang telah
ditentukan dijaga sebagai kandidat.
4. Genetic Algorithm
Genetic Algorithm (GA) adalah metaheuristik yang terinspirasi oleh proses
seleksi alam yang termasuk dalam kelas yang lebih besar dari algoritma
evolusioner (EA). Algoritma genetika biasanya digunakan untuk menghasilkan
solusi berkualitas tinggi untuk optimasi dan masalah pencarian dengan
mengandalkan operator terinspirasi bio seperti mutasi, crossover dan seleksi.
Agen pencarian online dan lingkungan
yang tidak diketahui.
Agen cerdas adalah
(intelligent agent) kian populer seiring dengan perkembangan internet. Berbagai
nama lain yang juga menyatakan agen cerdas yaitu software agent, wizard,
knowbot, dan softbot.
Russel dan norving
(1995, hal 31) mendefinisikan agent sebagai “segala sesuatu yang dapat
dipandang menangkap lingkungan melalui efektor.” Sensor adalah bagian yang
merangsang tindakan agen, sedangkan efektor adalah bagian yang di gunakan oleh
agen untuk melakukan tindakan.
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
· Agen spreadsheet
· Agen perdagangan
elektronis
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.
Daftar Pustaka:
Tidak ada komentar:
Posting Komentar