TUGAS PENG.TEKNOLOGI SISTEM CERDAS
Nama IRZAN ADITIA NOVIANDI
Kelas 3KA10
Dosen Essy Malaysari Sakti
Strategi Pencarian Berbentuk/heuristic Search Strategy
Kata Heuristic berasal dari sebuah kata kerja Yunani, heuriskein, yang berarti „mencari‟ atau „menemukan‟. Dalam dunia pemrograman, sebagian orang menggunakan kata heuristic sebagai lawan kata dari algoritmik, di mana kata heuristic ini diartikan sebagai suatu proses yang mungkin dapat menyelesaikan suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari selalu dapat ditemukan. Heuristic memperbaiki proses pencarian solusi walaupun tidak harus sampai mengatasi kasus terburuk (worst case scenario). Heuristik ini mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Algoritma ini biasanya mencari solusi yang dekat dengan solusi terbaik dan proses pencariannya cepat dan mudah. Terkadang algoritma ini dapat menjadi akurat dan menemukan solusi terbaik, tetapi algoritma ini tetap disebut heuristic hingga solusi terbaik itu terbukti untuk menjadi yang terbaik.
- Greedy best First Search
Algoritma Greedy Best-First Search menggunakan sebuah evaluation function berupa fungsiestimasi jarak atau biaya dari sebuah node n ke goal (heuristic function). Node yang di-expandadalah node-node yang terlihat paling dekat ke goal.
Karakteristik dari Greedy Best-First Search adalah sebagai berikut:
1.Algoritma ini belum tentu dapat menghasilkan solusi (belum tentu complete) karena bisamenghasilkan infinite loop.
2.Solusi yang diberikan belum tentu optimal. Misalnya untuk kasus Peta Rumania padagambar dibawah ini dimana dicari path terdekat dari Arad ke Bucharest.
- 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)
- Fungsi Heuristik
Fungsi heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state,yang dinyatakan dengan :
Ket:
f’ = Fungsi evaluasi
g = cost dari initial state ke current state
h’ = prakiraan cost dari current state ke soal state
- Algoritma Pencarian Lokal dan Masalah Optimisasi
Hill Climbing (Pendaki Bukit)
Hill Climbing (mendaki bukit) merupakan salah satu variasi metode buat dan uji (generate and test) dimana umpan balik yang berasal dari prosedur uji digunakan untuk memutuskan arah gerak dalam ruang pencarian (search).Dalam prosedur buat dan uji yang murni, respon fungsi uji hanyalah iya atau tidak. Dalam prosedur Hill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan (goal).
SimulatedAnnealingSearch
SimulatedAnnealingSearch 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.
contoh :
1. Simulated Annealing padaTSP digunakan untuk menelusuri dan mencari setiap rute yang mungkin, kemudian mendapatkan rute yang jaraknya paling pendek.
2. Model Simulated Annealing untuk menyelesaikan TSP adalah model state yang dibangun untuk menyatakan rute yang mungkin dan definisi energi yang dinyatakan dengan total jarak yang ditempuh.
3. Berapa besarnya pengurangan temperature dalam setiap waktu
Local beam search
Local beam search adalah algoritma pencarian heuristik yangmerupakan optimasi dari pencarian best-first search yang mengurangikebutuhan memorinya. Dalam Beam Search, hanya jumlah solusiparsial terbaik yang telah ditetapkan yang disimpan sebagai kandidat.
Beam Search membutuhkan tiga komponen sebagai inputnya, yaitu :
a.Masalah yang akan di selesaikan
Biasanya di tampilkan dalam bentuk grafik dan berisi kumpulan node yang tiap satu atau lebih node mengarah ke goal/hasil.
b.Kumpulan aturan-aturan heuristik untuk pemangkasan
Adalah aturan-aturan spesifik yang mengarah ke ruang masalah dan memangkas node yang tidak menguntungkan dari memori yang berhubungan dengan ruang masalah.
c.Memori dengan kapasitas yang terbatas
Adalah memori tempat menyimpan beam, dimana ketika memori dalam keadaan penuh dan node akan di tambahkan ke beam, maka node yang nilainya paling besar yang dihapus, jadi tidak akan melebihi memori yang tersedia.
Beam Search memiliki keuntungan yang berpotensi mengurangi perhitungan dan waktu pencarian. Selain itu, pemakaian memori daripencarian ini jauh lebih sedikit daripada metode yang mendasari mtode pencarian ini. Kelemahan utama Beam Search adalah metode pencarian ini mungkin tidak dapat mencapai tujuan/hasil yang optimaldan bahkan mungkin tidak mencapai tujuan sama sekali. Padakenyataannya, algoritma beam search berakhir untuk dua kasus: nodetujuan yang diperlukan tercapai, atau node tujuan tidak tercapai dantidak ada node tersisa untuk dieksplorasi.
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 dan crossover.
Dalam GA biasanya ada 2 hal yang harus didefinisikan:
- Representasi genetis dari domain solusi
Standar representasi dari sebuah solusi adalah sebuah array bits. Properti utama yang membuat representasi genetika ini nyaman adalah bagian-bagiannya yang mudah untuk diubah sehubungan dengan ukuran tetapnya, yang mengfasilitasi operasi crossover.
- Fungsi fitness untuk mengevaluasi solusi domain.
Fungsi fitness didefinisikan representasi genetika dan mengukur kualitas solusi yang telah direpresentasikan. Fungsi fitness selalu berdasarkan atas masalah.
Kelebihan - kelebihan yang dimiliki GAa adalah menurut http://hunch.net/?p=65
- GA memiliki kemampuan untuk mencari nilai optimal secara paralel, melalui proses kerjasama antara berbagai unit, yang disebut kromosom individu.
- GA tidak memerlukan perhitungan matematika yang rumit seperti differensial yang diperlukan oleh algoritma optimisasi yang lain.
Sementara, Genetic Algorithm pun memiliki beberapa kekurangan, yaitu :
- Tidak memiliki rumusan yang pasti, bagaimana mentransfer parameter permasalahan ke dalam kode genetik. Dengan kata lain, hal ini memerlukan pengalaman dan wawasan dari desainer.
Agen pencarian online dan lingkungan yang tidak diketahui.
- Pencarian buta (uninformed/blind search) : tidak ada informasi awal yang digunakan dalam proses pencarian
- Pencarian melebar pertama (Breadth – First Search)
- Pencarian mendalam pertama (Depth – First Search)
Referensi :
Tidak ada komentar:
Posting Komentar