Pencarian Berbentuk ( heuristik search dan eksplorasi )

1. Strategi Pencarian Berbentuk
Menurut Russell dan Norvig (2010 : 92) informed search strategy merupakan satu strategi pencarian yang menggunakan pengetahuan masalah yang spesifik di luar dari definisi masalah itu sendiri dan bisa menemukan solusi yang lebih efisien dibandingkan dengan uninformed strategy. Uninformed strategy disebut juga pencarian buta karena dalam strategi pencariannya tidak mempunyai tambahan informasi atau cost yang diperlukan dalam memecahkan masalah dan yang dilakukan adalah melakukan pengecekan pada semua node. Pendekatan pada informed search strategies yang umum digunakan adalah Best First Search atau biasa disebut dengan greedy method.

              1.1 Greedy Method

Menurut Russell dan Norvig (2010: 92) greedy merupakan nama lain dari Best First Search. Greedy dapat diartikan rakus atau serakah. Greedy memperluas node yang paling dekat dengan tujuan, dengan alasan bahwa hal ini mungkin menyebabkan solusi yang cepat dalam melakukan pencarian. Algoritma greedy ini mengevaluasi node dengan fungsi heuristic :
f (n) = h (n)
dimana h (n) merupakan estimasi biaya dari n ke tujuan
Ada beberapa elemen dalam algoritma greedy (Ichsan, 2010) :
1.     Himpunan kandidat
Himpunan yang berisi kemungkinan-kemungkinan yang bisa menjadi solusi dari permasalahan.
2.    Himpunan solusi
Himpunan yang berisi kandidat yang telah dipilih sebagai solusi.
3.    Fungsi seleksi
Fungsi untuk melakukan seleksi terhadap kandidat agar menghasilkan solusi yang diharapkan.
4.    Fungsi kelayakan
Fungsi untuk memastikan bahwa solusi yang dipilih memenuhi syarat.
5.    Fungsi obyektif
Memilih solusi paling optimal dari himpunan solusi.
Algoritma greedy membangun langkah per langkah, dan selalu memilih langkah selanjutnya yang menawarkan solusi terbaik (Dasgupta, Papadimitriou, & Vazirani, 2006: 139). Pada setiap langkah algoritma greedy mengambil pilihan terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depannya, sebagaimana prinsip algoritma greedy. Dengan demikian, secara umum algoritma greedy bekerja dengan cara melakukan pencarian himpunan kandidat dengan fungsi seleksi dan diverifikasi dengan fungsi kelayakan kemudian memilih solusi paling optimal dengan fungsi obyekif.
Sebagai contoh untuk penerapan algoritma greedy pada pencarian rute di Romania, dari Arad menuju Bucharest dengan menggunakan fungsi heuristic straight line distance atau yang biasa disebut hSLD.
Contoh penerapan algoritma greedy dapat dilihat dari gambar 2.1. pada halaman 13. Diketahui bahwa jarak dari Arad menuju Bucharest adalah 366 atau dapat dituliskan hSLD(ln(Arad)) = 366. Kemudian dari Arad menuju ke Sibiu, karena dapat dilihat bahwa jarak dari Sibiu ke Bucharest lebih dekat dibandingkan dengan Timisoara dan Zerind. Node selanjutnya yang akan dikunjungi adalah Fagaras, karena Fagaras lebih dekat dan langsung dapat menuju ke Bucharest yang merupakan tujuan akhir dibandingkan dengan Rimnicu Vilcea yang memiliki jarak yang lebih jauh dan harus melewati tempat lain sebelum sampai ke Bucharest. Algoritma greedy mencari solusi yang paling cepat sampai ke tujuan. Jika dilihat dari contoh di atas dapat diketahui bahwa jarak dari Fagaras ke Bucharest lebih jauh 32 KM dibandingkan jika melalui Rimnicu Vilcea dan Pitesti. Ini menunjukkan mengapa algoritma ini disebut greedy yang tiap langkahnya mencoba untuk mencari solusi tercepat untuk sampai ke tujuan tanpa mempertimbangkan kemungkinan selanjutnya.


             1.2   A*Searching 
         
       Algoritma A* (A Star / A Bintang) Algoritma -  A* (dibaca "A bintang"/"A star")                      adalah algoritma  pencarian graf/pohon yang mencari jalur dari satu titik awal ke sebuah titik akhir yang telah ditentukan. Algoritma A* menggunakan pendekatan heuristik h(x)  yang memberikan peringkat ke tiap-tiap titik x dengan  cara memperkirakan rute terbaik yang dapat dilalui dari titik tersebut. Setelah itu tiap-tiap titk x tersebut dicek  satu-persatu berdasarkan urutan yang dibuat dengan  pendekatan heuristik tersebut. Maka dari itulah algoritma A* adalah contoh dari best-first search. Algoritma ini pertama kali ditemukan pada tahun 1968 oleh Peter Hart, Nils Nilsson dan Bertram Raphael. Dalam tulisan mereka, algoritma ini dinamakan algoritma A. Penggunaan algoritma ini dengan fungsi heuristik yang tepat dapat memberikan hasil yang optimal, maka algoritma inipun disebut A*. Beberapa terminologi dasar yang terdapat pada algoritma ini adalah starting point, simpul (nodes), A, open list, closed list, harga (cost), halangan (unwalkable).



·         Starting point adalah sebuah terminologi posisi awal sebuah benda.
·         A adalah simpul yang sedang dijalankan algortima pencarian jalan terpendek.
·         Simpul adalah petak-petak kecil sebagai representasi  dari areapathfinding. Bentuknya dapat berupa persegi, lingkaran, maupun segitiga.
·         open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting point maupun simpul yang sedang dijalankan.
·         Closed list adalah tempat menyimpan data simpul sebelum A yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan.
·         Harga (F) adalah nilai yang diperoleh dari penjumlahan nilai G, jumlah nilai tiap simpul dalam jalur terpendek dari starting point ke A, dan H, jumlah nilai perkiraan dari sebuah simpul ke simpul tujuan.
·         Simpul tujuan yaitu simpul yang dituju.
·         Rintangan adalah sebuah atribut yang menyatakan bahwa sebuah simpul tidak dapat dilalui oleh A.


Prinsip algoritma ini adalah mencari jalur terpendek dari sebuah simpul awal (starting point) menuju simpul tujuan dengan memperhatikan harga (F) terkecil.
A* memperhitungkan cost dari current state ke tujuan denga fungsi heuristic, Algoritma ini juga mempertimbangkan cost yang telah ditempuh selama ini dari initial state ke current state. Jadi jika ada jalan yang telah ditempuh sudah terlalu panjang dan ada jalan lain yang cost-nya lebih kecil tetapi memberikan posisi yang sama dilihat dari goal, jalan yang lebih pendek yang akan dipilih.

1.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*.
Proses
Seperti A *, algoritma SMA* memperluas cabang yang paling menjanjikan menurut heuristik. Apa yang membuat SMA * terpisah adalah SMA* memangkas simpul yang ekspansinya telah diungkapkan kurang menjanjikan dari yang diharapkan. Pendekatan ini memungkinkan algoritma untuk mengeksplorasi cabang dan backtrack untuk mengeksplorasi cabang lain.

Ekspansi dan pemangkasan simpul didorong karena SMA* menjaga dua nilai f untuk setiap simpul. Simpul x menyimpan nilai f(x) yang memperkirakan biaya mencapai tujuan dengan mengambil jalan melalui simpul tersebut. Semakin rendah nilai, semakin tinggi prioritas. Seperti di A * nilai ini diinisialisasi dengan h (x) + g (x), tetapi kemudian akan diperbarui untuk mencerminkan perubahan estimasi ketika anak-anaknya diperluas. Sebuah simpul yang sudah diperluas sepenuhnya akan memiliki nilai f setidaknya setinggi dari suksesornya. Selain itu, simpul menyimpan nilai f dari suksesor terbaik yang telah dilupakan. Nilai ini dikembalikan jika suksesor yang telah dilupakan itu dinyatakan sebagai suksesor paling menjanjikan.

Dimulai dengan simpul pertama, ia mempertahankan OPEN, memerintahkan dengan leksikografi oleh f dan kedalaman. Ketika memilih simpul untuk diperluas, ia memilih yang terbaik sesuai dengan urutan itu. Ketika memilih sebuah simpul untuk dipangkas, ia memilih yang terburuk.

SMA* merupakan algoritma yang:


·         Bekerja dengan heuristic, seperti A*
·         Selesai jika memori yang diperbolehkan cukup tinggi untuk menyimpan solusi terdangkal
·         Optimal jika memori yang diperbolehkan cukup tinggi untuk menyimpan solusi optimal terdangkal, jika tidak dia akan mengembalikan solusi terbaik yang ada di memori
·         Menjauhi pernyataan yang diulang-ulang selama batas memori memperbolehkannya
·         Menggunakan semua memori yang ada
·         Memperbesar batas memori dari algoritma hanya akan mempercepat perhitungan
·         Ketika memori cukup ada untuk memuat  seluruh pohon pencarian, maka perhitungan mempunyai kecepatan yang optimal.




2. Fungsi Heuristic
      Fungsi ini melibatkan penggunaan bahasa untuk memperoleh ilmu pengetahuan sebanyak-banyaknya dan mempclajari seluk—beluk lingkungannya. Fungsi heuristik ini mengingatkan pada apa yang secara umum dikenal dengan pertanyaan, sebab fungsi ini sering disampaikan dalam bentuk pertanyaan-pertanyaan yang menuntut jawaban. Secara khusus, anak-anak sering memanfaatkan penggunaan fungsi heuristik ini dengan berbagai pertanyaan "apa”, "mengapa”, dan “bagaimana” yang tidak putus-putusnya mengenai dunia sekeliling atau alam sekitar mereka. Misalnya:
a. Mengapa di dunia ini ada matahari?
b. Mengapa matahari bersinar?
c. Mengapa jika matahari tenggelam hari menjadi gelap?


3. Algoritma Pencarian Local dan Masalah Optimasi

       3.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 lainnya yang mungkin. 
Algoritma Simple HillClimbing 
Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai  tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang: 
  • Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
  • Evaluasi keadaan baru tersebut : 
  • Jika keadaan baru merupakan tujuan, keluar 
  • Jika bukan tujuan, namun nilainya lebih baik dari pada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang. 
  • Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi. 

Pada simple hill climbing, ada 3 masalah yang mungkin: 
  • Algoritma akan berhenti kalau mencapai nilai optimum local 
  • Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi 
  • Tidak diijinkan untuk melihat satupun langkah sebelumnya.

3.2 Simulated Annealing Search
Merupakan metode searching yang memanfaatkan teori probabilitas untuk mencari global minimum dari suatu permasalahan optimasi. Simulated annealing umumnya digunakan untuk variabel yang bersifat categorical. Target dari metode ini adalah menemukan solusi bagus yang bisa diterima, bukan untuk mencari solusi yang terbaik. Nama annealing berasal dari keilmuan metallurgy, di mana proses tersebut akan berusaha mencari suatu posisi suhu tertentu yang optimal untuk mengurangi kerusakan dan menambah ukuran kristal di dalam suatu material.
Analogi dengan proses tersebut, metode Simulated Annealing ini juga berusaha untuk mencari solusi dengan berpindah dari solusi yang satu ke solusi yang lainnya, dan apabila solusi baru yang diuji mempunyai nilai fungsi ‘energy’ yang lebih kecil, maka solusi yang sedang diuji akan menggantikan solusi yang lama. Umumnya solusi baru yang dipilih merupakan solusi yang ada di dekat/sekitar solusi yang lama. Fungsi energi ini sangat bergantung pada parameter-parameter seperti parameter T (yang sering disebut dengan parameter “Temperature”). Metode ini merupakan adaptasi dari algoritma Metropolis-Hasting, yang merupakan suatu jenis metode Monte Carlo, untuk menciptakan sample state yang diperlukan.
Dalam metode ini, beberapa parameter terkait harus didefinisikan termasuk, the state space (umumnya berupa vector yang terdiri dari beberapa karakteristik), fungsi energy, prosedur untuk menciptakan solusi baru, fungsi probabilitas untuk menerima atau menolak, dan fungsi jadwal annealing dengan keterangan sebagai berikut:
– The state space umumnya ditentukan dengan melihat pada objek yang menjadi domain space pencarian.
– Fungsi energy umumnya menyesuaikan pada state space dan beberapa parameter kaitan lainnya.
– Prosedur untuk menciptakan solusi baru harus ditentukan seefisien mungkin dengan memikirkan karakteristik yang menjadi objek optimasi. Metode swapping antar karakteristik juga menjadi salah satu solusinya.
– Fungsi probabilitas untuk menerima atau menolak umumnya mempunyai bentuk tertentu dan bergantung pada apakah objek optimasi dapat merupakan fungsi probabilitas atau tidak. Fungsi probabilitas yang sering digunakan adalah fungsi probabilitas yang terkait dengan algoritma Metropolis-Hastings.
– Sedangkan untuk rate jadwal annealing umumnya ditentukan dengan melihat permasalahan yang ada pada objek optimasi dan ditentukan secara empiris.

        3.3 Local Beam Search
          Beam Search  adalah algoritma pencarian heuristik yang merupakan optimasi dari pencarian best-first search yang mengurangi kebutuhan memorinya. Dalam Beam Search, hanya jumlah solusi parsial 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 dari pencarian 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 optimal dan bahkan mungkin tidak mencapai tujuan sama sekali. Pada kenyataannya, algoritma beam search berakhir untuk dua kasus:  node tujuan yang diperlukan tercapai, atau node tujuan tidak tercapai dan tidak ada node tersisa untuk dieksplorasi.

Beam A*
Algoritma ini memberikan sedikit variasi pada A*, yaitu dengan membatasi simpul yang bisa disimpan di dalam OPEN. Ketika jumlah simpul di OPEN sudah melebihi batas tertentu, maka simpul dengan nilai fterbesar akan dihapus. Sedangkan jumlah simpul yang di dalam CLOSED tetap dibiarkan tanpa batasan karena simpul yang di dalam CLOSED memang tidak mungkin dihapus. Dengan membatasi jumlah simpul di OPEN, maka pencarian menjadi lebih terfokus seperti sinar (beam). Sehingga variasi ini dinamakan Beam A*.
Implementasi algoritma BA* sama dengan A* tetapi ada sedikit fungsi tambahan untuk pengecekan dan penghapusan simpul terburuk di OPEN.
Algoritma Beam A* menggunakan dua senarai :OPEN dan CLOSEDOPEN adalah adalah senarai (list) yang digunakan untuk menyimpan simpul-simpul yang pernah dibangkitkan dan nilai heuristiknya telah dihitung tetapi belum terpilih sebagai simpul terbaik (best node). Dengan kata lain, OPEN berisi simpul-simpul yang masih memiliki peluang (peluangnya masih terbuka) untuk terpilih sebagai simpul terbaik. Sedangkan CLOSEDadalah senarai untuk menyimpan simpul-simpul yang sudah pernah dibangkitkan dan sudah pernah terpilih sebagai simpul terbaik. Artinya, CLOSED berisi simpul-simpul yang tidak mungkin terpilih sebagai simpul terbaik (peluang untuk terpilih sudah tertutup).
Terdapat tiga kondisi bagi setiap sukseror yang dibangkitkan, yaitu : sudah berada di OPEN, sudah berada di CLOSED, dan tidak berada di OPEN maupunCLOSED. Pada ketiga kondisi tersebut diberikan penanganan yang berbeda-beda.
Jika suksesor sudah pernah berada di OPEN, maka dilakukan pengecekan apakah perlu pengubahanparent atau tidak tergantung pada nilai g-nya melaluiparent lama atau parent baru. Jika melalui parent baru memberikan nilai g yang lebih kecil, maka dilakukan pengubahan parent. Jika pengubahan parent dilakukan, maka dilakukan pula perbaruan (update) nilai dan f  pada suksesor tersebut. Dengan perbaruan ini, suksesor tersebut memiliki kesempatan yang lebih besar untuk terpilih sebagai simpul terbaik (best node).
Jika suksesor sudah pernah berada di CLOSED, maka dilakukan pengecekan apakah perlu pengubahanparent atau tidak. Jika ya, maka dilakukan perbaruan nilai dan f  pada suksesor tersebut serta pada semua “anak cucunya” yang sudah pernah berada di OPEN. Dengan perbaruan ini, maka semua anak cucunya tersebut memiliki kesempatan lebih besar untuk terpilih sebagai simpul terbaik (best node).
Jika suksesor tidak berada di OPEN maupunCLOSED, maka suksesor tersebut dimasukkan ke dalamOPEN. Tambahkan suksesor tersebut sebagai suksesornya best node. Hitung biaya suksesor tersebut dengan rumus f = g + h.

       3.4 Genetic Algorithm
      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.

Genetic Algorithm memiliki keunggulan-keunggulan dibandingkan dengan metode-metode heuristic yang lain, yaitu:
·                     Genetic Algorithm menyelesaikan masalah dengan mengkodekan permasalah menjadi chromosome, bukan dengan menyelesaikan permasalahan itu sendiri. Karena itu diperlukan pemodelan chromosome yang baik dan efektif yang dapat mewakili solusi dari permasalahan yang dihadapi.
·                     Genetic Algorithm memulai prosesnya dengan sekumpulan initial solutions, berbeda dengan metaheuristic lain seperti Simulated Annealing dan Tabu Search yang memulai proses dengan sebuah solusi tunggal, dan berlanjut ke solusi lainnya melalui suatu transisi. Karena itu GA melakukan pencarian multi-directional dalam solution space, yang memperkecil kemungkinan berhentinya pencarian pada kondisi local optimum.
·                     Hanya diperlukan sebuah fungsi evaluasi tunggal yang berbeda untuk tiap permasalahan.
·                     Genetic Algorithm merupakan algoritma yang ‘buta’, karena GA tidak mengetahui kapan dirinya telah mencapai solusi optimal.
   Seperti yang telah disebutkan sebelumnya, Genetic Algorithm dapat dengan mudah beradaptasi dengan berbagai macam permasalahan, sehingga ada banyak versi dari Genetic Algorithm, tergantung dari permasalahan yang ingin dipecahkan. Tapi secara umum Genetic Algorithm harus memenuhi kriteria-kriteria dibawah ini untuk menghasilkan solusi yang optimal:
·                     Sebuah representasi yang tepat dari sebuah solusi permasalahan, dalam bentuk chromosome.
·                     Pembangkit populasi awal. Umumnya populasi awal dibangkitkan secara acak, namun untuk beberapa kasus juga bisa dibangkitkan melalui metode-metode tertentu. Penggabungan keduanya (pembangkitan populasi awal secara acak dan menggunakan metode-metode tertentu) disebut dengan seeding. Populasi awal yang dihasilkan sebaiknya bersifat heterogen, karena jika populasi yang terbentuk terlalu homogen, Genetic Algorithm kehilangan kemampuannya untuk mencari dalam solution space, sampai populasi mempunyai variasi chromosome yang beragam melalui operasi genetik lain (mutation).
·                     Sebuah evaluation function untuk menentukan fitness value dari tiap solusi.
·                     Genetic Operator, mensimulasikan proses reproduksi (perkembangbiakan) dan mutasi.
·                     Parameter-parameter lain, seperti kapasitas populasi, probabilitas dari operasi-operasi genetik, dan semacamnya

Suatu Genetic Algorithm standar membutuhkan dua hal untuk didefinisikan, yaitu :
1.             Sebuah genetic representation dari sebuah solution domain (domain solusi)
2.            Sebuah fitness function untuk mengevaluasi sebuah domain solusi




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 :

a. 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.

b. 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 :
a. Membantu pemakai menetukan produk yang dibeli.
b. Mencarikan spesifikasi dan mengkajinya.
c. Membantu rekomendasi.
d. Membandingkan belanjaan untuk mendapatkam harga terbaik untuk produk yang dikehendaki.
e. Mengamati dan mengenalkan kepad pemakai penawaran dan diskon khusus.


c. 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.

     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. 





Daftar Pustaka



Komentar

Postingan populer dari blog ini

Jaka tarub dan 7 bidadari

Logika Orde Pertama (first-Order Logic)

Roti Buaya Lambang Kesetiaan Suku Betawi