Pencarian Berbentuk /heuristik search dan Eksplorasi

Pencarian  Berbentuk /heuristik search dan Eksplorasi

3.1 Strategi pencarian berbentuk/heuristic search stragegy meliputi :

Ø greedy best-first search

Algoritma ini Merupakan jenis Best First Search yang hanya mempertimbangkan harga perkiraan (estimated cost) yaitu f(n) = h(n). Sedangkan harga sesungguhnya tidak digunakan. Sehingga solusi yang dihasilkan tidak optimal.  Algoritma greedy ini membentuk solusi langkah per langkah (step by step). Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.

Proses ekspansi dengan menggunakan algoritma Greedy Best First Search adalah dengan merujuk pada nilai estimasinya yaitu h(n). Berbeda halnya dengan nilai g(n) yang diakumulasikan, nilai h(n) tidak diakumulasikan. Proses eksplorasi akan berjalan seperti berikut ini:

f = {S};

f = {A, C, K};       // 2, 4, 5

f = {B, C, K};       // 3, 4, 5

f = {G, C, H, K};    // 0, 4, 4, 5

f = {C, H, K};       // 4, 4, 5

Proses yang dilakukan pada Greedy Best First Search sama seperti Uniform Cost Search, namun parameter yang digunakan hanya nilai estimasinya.

Dari proses di atas, maka dihasilkan jumlah ekspansi node sebanyak 4 kali, dan path yang dilalui dengan menggunakan algoritma Greedy Best First Search adalah S-A-B-G.

Ø A* search

Bentuk dari Best First Search yang paling dikenal adalah algorima pencarian A*(Dibaca dengan A-Star). Tidak jauh 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)

Ø  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

Implementasi

Implementasi dari SMA* sangat mirip dengan implementasi A*, hanya perbedaannya adalah ketika tidak ada ruang yang tersisa, simpul dengan nilai f tertinggi akan dipangkas dari antrian. Karena simpul-simpul tersebut dihapus, SMA* juga harus mengingat nilai f terbaik dari anak yang dilupakan dengan simpul orangtua. Ketika terlihat jika semua jalur yang dieksplorasi lebih buruk dari jalur yang telah dilupakan, maka jalur meregenerasi.

 

3.2 Fungsi Heuristic

Heuristic digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

3.3 Algoritma pencarian lokal dan masalah optimisasi meliputi:

Ø hill climbing search

1.      PENDAKIAN BUKIT (Hill Climbing)

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.

 

Ø simulated annealing search

Simulated annealing (SA) 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. Publikasi tentang pendekatan ini pertama kali dilakukan oleh S. Kirkpatrick, C. D. Gelatt dan M. P. Vecchi, diaplikasikan pada desain optimal hardware komputer, dan juga pada salah satu masalah klasik ilmu komputer yaitu Traveling Salesman Problem.

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.

Simulated Annealing berjalan berdasarkan analogi dengan proses annealing yang telah dijelaskan di atas. Pada awal proses SA, dipilih suatu solusi awal, yang merepresentasikan kondisi materi sebelum proses dimulai. Gerakan bebas dari atom-atom pada materi, direpresentasikan dalam bentuk modifikasi terhadap solusi awal/solusi sementara. Pada awal proses SA, saat parameter suhu (T) diatur tinggi, solusi sementara yang sudah ada diperbolehkan untuk mengalami modifikasi secara bebas.

Kebebasan ini secara relatif diukur berdasarkan nilai fungsi tertentu yang mengevaluasi seberapa optimal solusi sementara yang telah diperoleh. Bila nilai fungsi evaluasi hasil modifikasi ini membaik (dalam masalah optimisasi yang berusaha mencari minimum berarti nilainya lebih kecil/downhill) solusi hasil modifikasi ini akan digunakan sebagai solusi selanjutnya. Bila nilai fungsi evaluasi hasil modifikasi ini memburuk, pada saat temperatur annealing masih tinggi, solusi yang lebih buruk (uphill) ini masih mungkin diterima, sedangkan pada saat temperatur annealing sudah relatif rendah, solusi hasil modifikasi yang lebih buruk ini mungkin tidak dapat diterima. Dalam tahapan selanjutnya saat temperatur sedikit demi sedikit dikurangi, maka kemungkinan untuk menerima langkah modifikasi yang tidak memperbaiki nilai fungsi evaluasi semakin berkurang. Sehingga kebebasan untuk memodifikasi solusi semakin menyempit, sampai akhirnya diharapkan dapat diperoleh solusi yang mendekati solusi optimal. Pada temperatur rendah ini, SA biasanya menggunakan konsep Hill-Climbing.

Ø 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 f terbesar 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 CLOSED. OPEN 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 CLOSED adalah 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 maupun CLOSED. Pada ketiga kondisi tersebut diberikan penanganan yang berbeda-beda.

Jika suksesor sudah pernah berada di OPEN, maka dilakukan pengecekan apakah perlu pengubahan parent atau tidak tergantung pada nilai g-nya melalui parent 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 g 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 pengubahan parent atau tidak. Jika ya, maka dilakukan perbaruan nilai g 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 maupun CLOSED, maka suksesor tersebut dimasukkan ke dalam OPEN. Tambahkan suksesor tersebut sebagai suksesornya best node. Hitung biaya suksesor tersebut dengan rumus f = g + h.

Ø 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

3.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:

     https://blogaqu.wordpress.com/2009/11/09/penerapan-greedy-best-first-search-dalam-implementasi-pencarian-lintasan-terpendek-dan-efisien-berdasarkan-jalur-dan-tarif-relatif-angkutan-kota-angkot-dari-pancoran-ke-manggarai/ 

http://fryunfirst.blogspot.co.id/2015/06/pencarian-heuristik-heuristic-search.html 

http://agsmlyd.blogspot.co.id/2014/07/genetic-algorithm.html 

http://principessaprincipe.blogspot.co.id/2011/05/beam-search.htmlhttp://elib.unikom.ac.id/files/disk1/623/jbptunikompp-gdl-aerajatras-31102-10-13.unik-2.pdf