Pencarian Berbentuk (Heuristic Search dan Eksplorasi)

Pertemuan 3

Pencarian Berbentuk dan Eksplorasi

Nama : Bella Alysha Vira

NPM : 11115319

Kelas : 3KA10

Dosen : Essy Malays Sari Sakti

1.1. Best First Search

Sesuai dengan namanya, best-first search merupakan sebuah metode yang membangkitkan simpul dari sebuah simpul sebelumnya (yang sejauh ini terbaik diantara semua simpul yang pernah dibangkitkan). Penentuan simpul terbaik dilakukan dengan menggunakan fungsi yang disebut fungsi evaluasi f(n) (Russel and Norvig, 1995). Pada best-first search jika suksesor digunakan, maka dikatakan algoritma mengembangkan simpul tersebut. Setiap sebuah simpul dikembangkan, algoritma akan menyimpan setiap suksesor simpul n sekaligus dengan harga (cost) dan petunjuk pendahulunya yang disebut “parent”. Algoritma akan berakhir pada simpul tujuan, dan tidak akan ada lagi pengembangan simpul. Fungsi evaluasi pada best-first search dapat berupa informasi biaya perkiraan dari suatu simpul menuju ke simpul tujuan atau gabungan antara biaya sebenarnya dan biaya perkiraan tersebut. Biaya perkiraan dapat diperoleh dengan menggunakan suatu fungsi yang disebut fungsi heuristic. Pada strategi best-forst search, cost sebenarnya yaitu dari simpul awal ke simpul n, dinotasikan dengan g(n) dan fungsi heuristic yang digunakan yaitu perkiraan/etimasi nilai dari simpul n ke simpul tujuan dinotasikan dengan h(n). Algoritma yang menggunakan metode best-first search, yaitu  :

§  Greedy Best-First Search

§  Algoritma A*

Berikut akan diberikan beberapa istilah yang sering digunakan pada metode best-first search :

§  Start node, adalah sebuah terminology untuk posisi awal sebuah pencarian.

§  Current node, adalah simpul yang sedang dijalankan (yang sekarang) dalam algoritma pencarian jalan terpendek.

§  Kandidat (successor), adalah simpul-simpul yang berjasen dengan current node, dengan kata lain simpul-simpul yang akan diperiksa berikutnya.

§  Simpul (node), merupakan representasi dari area pencarian.

§  Open list, adalah tempat menyimpan data simpul yang mungkin diakses dari starting node maupun simpul yang sedang dijalankan.

§  Closed list, adalah tempat menyimpan data simpul yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan.

§  Goal node, yaitusimpul tujuan.

§  Parent, adalah current node dari suksesor/kandidat.

1.2. Greedy Best First Search

Salah satu algoritma yang termasuk kedalam kategori informed search adalah Greedy Best First Search yang dikenal juga dengan Greedy Search. Secara harfiah greedy artinya rakus atau tamak, sifat yang berkonotasi negative. Sesuai dengan arti tersebut, prinsip greedy adalah mengambil keputusan yang dianggap terbaik hanya untuk saat itu saja yang diharapkan dapat memberikan solusi terbaik secara keseluruhan. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya.

Greedy Best First Search seperti halnya algoritma yang menggunakan strategi best-first search lainnya mempuyai sebuah fungsi yang menjadi acuan kelayakan sebuah simpul yaitu fungsi evaluasi f(n). pada Greedy Best First Search fungsi evaluasi tidak bergantung pada cost sebelumnya, tetapi hanya bergantung pada fungsi heuristic itu sendiri.jika pada algoritma pencarian yang dilakukan bergantung pada cost sebenarnya dari sebuah simpul yaitu g(n), pada Greedy Best First Search fungsi evaluasi hanya bergantung pada fungsi heuristic h(n) yang mengestimasikan arah yang benar, sehingga pencarian jalur dapat berlangsung dengan sangat secapt. Secara matematis fungsi evaluasi pada greedy search diberikan oleh :

f(n) = h(n)

dengan :

g(n) = estimasi biaya dari simpul n ke simpul tujuan (goal node).

Berikut langkah-langkah pencarian lintasan terpendek yang dilakukan Greedy Best First Search :

§  Masukan simpul awal ke dalam Open List.

§  Open berisi simpul awal dan Closed List masih kosong.

§  Masukkan simpul awal ke Closed List dan suksesornya pada Open List.

§  Ulangi langkah berikut sampai simpul tujuan ditemukan dan tidak ada lagi simpul yang akan dikembangkan.

§  Hitung nilai f simpul-simpul yang ada pada Open List, ambil simpul terbaik (f paling kecil).

§  Jika simpul terbesar sama dengan simpul tujuan, maka sukses.

§  Jika tidak, masukkan simpul tersebut ke dalam Closed.

§  Bangkitkan semua suksesor dari simpul tersebut.

§  Untuk setiap suksesor kerjakan :

a.    Jika suksesor tersebut belum pernah dibangkitkan, evaluasi suksesor tersebut, tambahkan ke Open dan catat “parent”nya.

b.   Jika suksesor tersebut sudah pernah dibangkitkan, ubah parent-nya jika jalur parent ini lebih baik daripada jalur melalui parent yang sebelumnya. Selanjutnya, perbarui biaya untuk suksesor tersebut.

1.3. Algoritma A* (A Star)

Terdapat banyak algoritma pencarian lintasan terpendek, algoritma Dijsktra merupakan salah satu dari algoritma tersebut. Dengan menggunakan fungsi biaya g(n) setiap simpul, algoritma Dijkstra memeriksa kelayakan biaya yang diperlukan untuk mencapai suatu simpul dari sebuah simpul lain. Proses ini dilakukan berulang sampai simpul tujuan diperiksa.

Algoritma Dijkstra memang menjamin didapatkannya jalur optimal, tetapi algoritma ini mempunyai kelemahan. Pemeriksaan simpul akan dilakukan ke segala arah yang dimungkinkan dan pada akhirnya seluruh simpul pada sebuah graf akan diperiksa. Hal ini menyebabkan algoritma ini bekerja dengan lambat, sehingga waktu yang dibutuhkan untuk menemukan solusi akan semakin besar pula.

Algoritma A* adalah algoritma yang menggabungkan Dijkstra dan algoritma Greedy Best First Search. Selain menghitung biaya yang diperlukan untuk berjalan dari simpul satu ke simpul lainnya, algoritma A* juga menggunakan fungsi heuristic untuk memprioritaskan pemeriksaan simpul-simpul pada arah yang benar, sehingga algoritma A* mempunyai efisiensi waktu yang baik dengan tidak mengorbankan perhitungan biaya sebenarnya.

1.4. Sejarah Algoritma A*

Penggunaan informasi heuristic untuk meningkatkan efisiensi pencarian telah dipelajari dalam berbagai bidang. Penggunaan fungsi evaluasi pada masalah pencarian pada graf dikemukakan oleh Lin (1965) yang digunakan pada masalah Traveling Salesman Problem (TSP). Doran dan Michie (1966) merumuskan dan mencoba dengan algoritma best-first search yang menggunakan perkiraan jarak dari current node ke simpul tujuan. Hart, Nilsson dan Raphael memperkenalkan penggunaan sebuah algoritma dalam masalah optimasi yaitu algoritma A* (A Star). Versi bi-directional algoritma A*, yang sevara bersamaan mencari dari simpul awal dan simpul tujuan diperkenalkan oleh Pohl (1971), yang selanjutnya diteliti oleh de Champeaux dan Sint (1977).

1.5. Algoritma A* dalam Pencarian Rute Terpendek

Beberapa strategi best-first search berbeda hanya pada bentuk fungsi evaluasi yang digunakan. Pada strategi best-first search, simpul yang terpilih untuk dikembangkan adalah simpul dengan nilai fungsi evaluasi terendah dan ketika dua lintasan mengarah pada simpul yang sama, simpul dengan nilai paling besar akan dibuang. Secara matematis, nilai fungsi evaluasi heuristic sebuah simpul pada algoritma A* diberikan oleh :

f(n) = h(n) + h(n)

dengan,

g(n) = biaya dari simpul awal (start node) ke simpul n.

h(n) = estimasi biaya dari simpul n ke simpul tujuan (goal node).

Algoritma A* menggunakan dua buah list yaitu Open List dan Closed List. Seperti halnya best-first search yang lain kedua list mempunyai fungsi yang sama. Pada awalnya Open List hanya berisi satu simpul awal dan Closed List masih kosong. Perlu diperhatikan setiap simpul akan menyimpan petunjuk “parent”nya sehingga stelah pencarian berakhir lintasan juga akan didapatkan. Berikut adalah langkah-langkah algoritma A* (A Star) :

§  Masukkan simpul awal ke Open List.

§  Ulangi langkah berikut sampai pencarian berakhir.

a.      Cari node n dengan nilai f(n) paling rendah, dalam Open List. Node ini akan menjadi current node.

b.     Keluarkan current node dari Open List dan masukkan ke Closed List.

c.      Untuk setiap suksesor dari current node lakukan langkah berikut :

-  Jika sudah dalam terdapat dalam Closed List, abaikan, jika tidak lanjutkan.

- Jika belum ada pada Open List, masukkan ke Open List. Simpan current node sebagai “parent” dari suksesor ini. Simpan cost masing-masing simpul.

- Jika sudah ada dalam Open List, periksa jika simpul suksesor ini mempunyai nilai lebih disbanding suksesor sebelumnya. Jika lebih kecil, jadikan sebagai current node dang anti “parent” node ini.

d.   Walaupun telah mencapai simpul tujuan, jika masih ada suksesor yang memiliki nilai lebih kecil, maka simpul tersebut akan terus dipilih sampai bobotnya jauh lebih besar atau mencapai simpul akhir dengan bobot yang lebih kecil disbanding dengan simpul sebelumnya yang telah mencapai simpul tujuan.

e.    Pada setiap pemilihan simpul berikutnya, nilai f(n) akan dievaluasi dan jika terdapat nilai f(n) yang sama akan dipilih berdasarkan nilai g(n) terbesar.

1.6. Heuristic Best First Search

Fungsi heuristic h(n) merupakan estimasi cost dari n ke simpul tujuan. Sangat penting untuk memilih fungsi heuristic yang baik. Misalkan h*(n) merupakan cost sebenarnya dari simpul n ke simpul tujuan, maka pada algoritma A* terdapat beberapa kemungkinan yang terjadi pada pemilihan fungsi heuristic yang digunakan, yaitu (Amit Gaming) :

§  Jika h(n) = 0, sehingga hanya g(n) yang terlibat maka A* akan bekerja seperti halnya algoritma Dijkstra.

§  Jika h(n) < h*(n), maka A* akan mengembangkan titik dengan nilai paing rendah dan algoritma A* menjamin ditemukannya lintasan terpendek. Nilai h(n) terendah akan membuat algoritma mengembangkan lebih banyak simpul. Jika h(n) < h*(n), maka h(n) dikatakan heuristic yang admissible.

§ Jika h(n) = h*(n), maka A* akan mengikuti lintasan terbaik dan tidak akan mengembangkan titik-titik yang lain sehingga akan berjalan cepat. Tetapi hal ini tidak akan terjadi pada semua kasus. Informasi yang baik akan mempercepat kinerja A*.

§  Jika h(n) > h*(n), maka A* tidak menjamin pencarian rute terpendek, tetapi berjalan dengan cepat.

§ Jika h(n) terlalu tinggi relative dengan g(n) sehingga hanya h(n) yang bekerja maka A* berubah jadi Greedy Best First Search.

1.7. Algoritma Pencarian Lokal dan Masalah Optimisasi

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

1.8. Simulated Annealing Search

Merupakan ialah suatu algoritma optimasi yang mensimulasikan proses annealing pada pembuatan materi yang terdiri dari butir keristal/logam. Algoritma unt untuk optimalisasi yang bersifat generic. Berbasiskan probabilitas dan mekanika statistic,algoritma ini dapat dipakai untmencari pendekatan terhadap solusi optimum global dari suatu permasalahn. Masalah yang membutuhkan pendekatan simulated annealing ialah masalah-masalah optimisasi kombinatorial, dimana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahn itu.

Secara umum ada 3 hal pokok pada simulated annealing, yaitu:

1. Nilai awal

Unt temperature (T0). Nilai T0 biasanya ditetapkan cukup besar (tidak mendekati 0), karena jika T mendekati 0 maka gerakan simulated annealing akan sama dengan hill climbing. Biasanya temperature awal ini ditetapkan sebesar 2 kali panjang suatu jalur yang dipilih secara acak.

2. Kriteria

Yang dipakai unt memutuskan apakah temperature sistem seharusnya dikurangi.

3. Berapa besarnya pengurangan temperature dalam setiap waktu.

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

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

1. Representasi genetis dari domain solusi

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

2.2. Agen pencarian online dan lingkungan yang tidak diketahui.

1. Pencarian buta (uninformed/blind search) : tidak ada informasi awal yang digunakan dalam proses pencarian.

2. Pencarian melebar pertama (Breadth – First Search).

3. Pencarian mendalam pertama (Depth – First Search).

Referensi
Buku "Perpustakaan Universitas Pendidikan Indonesia". Hal 20-27.