Penyelesaian Masalah :
II. Pencarian Berbentuk / Heuristik Search dan Eksplorasi
3.1 Strategi Pencarian Berbentuk / Heuristik Search Strategy
Teknik Dasar Pencarian adalah proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space). Pencarian atau pelacakan merupakan salah satu teknik untuk menyelesaikan permasalahan AI. Teknik pencarian terbagi atas dua teknik, yaitu pencarian buta (blind search) dan pencarian heuristik (heuristic search).
Penelitian yang pernah dilakukan mengenai permainan pergeseran angka dalam bentuk bintang yaitu dengan menggunakan algoritma breadth first search. Pada penelitian ini penulis menggunakan algoritma Best First Search untuk penyelesaian permainan pergeseran angka pada bentuk bintang ini. Algoritma best first search adalah salah satu algoritma pencarian heuristik yang merupakan kombinasi dari dua algoritma pencarian buta (blind search), yaitu breadth first search dan depth first.
3.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.
3.1.2 A*Search
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.
3.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.
3.2 Fungsi Heuristik
Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian (pencarian yang lebih simple). Namun kemungkinan juga dapat mengngorbankan kelengkapan (complateness).
Fungsi 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
3.3.1 Hill Climbing Search
Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin (Sri Kusumadewi 2003, h. 34).
Ada dua macam metode Hill Climbing Search, yaitu
§ Simple Hill Climbing ,
§ Steepest-ascent Hill Climbing (Sri Kusumadewi 2003, h. 39).
Algoritma untuk Hill Climbing Search adalah sebagai berikut :
1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
2. Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada node baru yang akan diaplikasikan pada keadaan sekarang :
a. Cari node yang belum pernah digunakan; gunakan node ini untuk mendapatkan keadaan yang baru.
b. Evaluasi keadaan baru tersebut.
§ Jika keadaan baru merupakan tujuan, keluar.
§ Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
§ Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan pencarian.
3.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.3 Local Beam Search
Localbeam search adalah algoritma pencarian heuristik yang merupakan 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.
3.3.4 Genetic Algorithm
Genetic Algorithm (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
- Fungsi fitness untuk mengevaluasi solusi domain.
Hal-hal yang harus dilakukan untuk menggunakan algoritma genetika
1. Mendefinisikan individu, dimana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat
2. Mendefinisikan nilai fitness, yang merupakan ukuran baik tidaknya sebuah individu atau baik tidaknya solusi yang didapatkan
3. Menentukan proses pembangkitan solusi awal. Hal ini biasanya dilakukan dengan menggunakan pembangkitan acak seperti random walk.
4. Menentukan proses seleksi yang akan digunakan
5. Menentukan proses perkawinan silang (cross over) dan mutasi gen yang akan digunakan
3.4 Agen Pencarian Online Dan Lingkungan Yang Tidak Diketahui
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 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.
Keterangan:
Nama: Mahmud Yusuf
Kelas: 3KA10
NPM: 14116231
EmoticonEmoticon