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