Senin, 31 Oktober 2016

Heuristic Search

Standard
Teknik Pencarian Heuristik (Heuristic Search)
  • Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness).
  • Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
  • Jenis-jenis Heuristic Searching:
  • – Generate and Test.
    – Hill Climbing.
    – Best First Search.
    – Means-EndAnlysis, Constraint Satisfaction, dll.
1). PEMBANGKITAN dan PENGUJIAN (Generate and Test)
  • Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.
  • Algoritma :
  • 1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal).
    2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari suatu lintasan yang  dipilih dengan kumpulan tujuan yang diharapkan.
    3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.
  • Contoh : “Travelling Salesman Problem (TSP)”
  • *) Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setaip kota hanya  boleh dikkunjungi tepat 1 kali. Misalkan ada 4 kota  dengan jarak antara tiap-tiap kota seperti berikut ini :
    Teknik Pencarian Heuristik (Heuristic Search)
    Alur pencarian dengan Generate and Test 
    Pencarian ke-
    Lintasan
    Panjang Lintasan
    Lintasan terpilih
    Panjang Lintasan terpilih
    1
    ABCD
    19
    ABCD
    19
    2
    ABDC
    18
    ABDC
    18
    3
    ACBD
    12
    ACBD
    12
    4
    ACDB
    13
    ACBD
    12
    5
    ADBC
    16
    ACBD
    12
    Dst…..




2) 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 lainnyayang mungkin.
  • Algoritma:
  • 1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
    a) Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang : Cari operator yang belum digunakan; gunakan operator 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 iterasi.
  • Contoh: TSP dengan Simple Hill Climbing Disini ruang keadaan berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Apabila ada n kota, dan kita ingin mencari kombinasi lintasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak n!/2!(n-2)!  atau sebanyak 6 kombinasi. Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi.
Teknik Pencarian Heuristik (Heuristic Search)

Contoh: TSP dengan Simple Hill Climbing 
Disini ruang keadaan berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Apabila ada n kota, dan kita ingin mencari kombinasi l intasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak: 
atau sebanyak 6 kombinasi (lihat gambar dibawah). Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi 

Daftar Pustaka : elib.unikom.ac.id/download.php?id=109014

Blind Search

Standard
Searching adalah mekanisme pemecahan masalah yang paling umum di dalam kecerdasan buatan. Di dalam permasalahan-permasalahan kecerdasan buatan, urutan langkah-langkah yang dibutuhkan untuk memperoleh solusi merupakan suatu isu yang penting untuk diformulasikan. Hal ini harus dilakukan dengan mengidentifikasikan proses try and error secara sistematis pada eksplorasi setiap alternatif jalur yang ada.
Algoritma searching di dalam kecerdasan buatan yang umumnya dikenal adalah
  1. Uninformed Search Algorithm
Algoritma yang tidak memberikan informasi tentang permasalahan yang ada, hanya sebatas definisi dari algoritma tersebut.
  1. Informed Search Algorithm
Walaupun dengan menggunakan Uninformed Search Algorithm, banyak permasalahan dapat dipecahkan, namun tidak semuanya dari algoritma tersebut dapat menyelesaikan masalah dengan efisien
Uninformed Search Algorithm
Uninformed Search sering disebut juga dengan Blind Search. Istilah tersebut menggambarkan bahwa teknik pencarian ini tidak memiliki informasi tambahan mengenai kondisi diluar dari yang disediakan oleh definisi masalah. Yang dilakukan oleh algoritma ini adalah melakukan generate dari successor dan membedakan goal state dari non-goal state. Pencarian dilakukan berdasarkan pada urutan mana saja node yang hendak di-expand.
  1. Breadth First Search (BFS)
Pencarian dengan Breadth First Search menggunakan teknik dimana langkah pertamanya adalah root node diekspansi, setelah itu dilanjutkan semua successor dari root node juga di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf (node pada level paling bawah yang sudah tidak mempunyai successor lagi).

Gambar 1 Penelusuran Ekspansi Node pada Breadth First Search
  1. Uniform Cost Search (UCS)
Pencarian dengan Breadth First Search akan menjadi optimal ketika nilai pada semua path adalah sama. Dengan sedikit perluasan, dapat ditemukan sebuah algoritma yang optimal dengan melihat kepada nilai tiap path di antara node-node yang ada.
Selain menjalankan fungsi algoritma BFS, Uniform Cost Search melakukan ekspansi node dengan nilai path yang paling kecil. Hal ini bisa dilakukan dengan membuat antrian pada successor yang ada berdasar kepada nilai path-nya (node disimpan dalam bentuk priority queue).
  1. Depth First Search (DFS)
Teknik pencarian dengan Depth First Search adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum diekspansi.

Gambar 2 Penelusuran Ekspansi Node pada Depth First Search
  1. Depth Limited Search
Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree. Permasalahan yang muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan menginisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka tidak memiliki successor.
  1. Iterative Deepening Depth First Search
Iterative deepening search merupakan sebuah strategi umum yang biasanya dikombinasikan dengan depth first tree search, yang akan menemukan berapa depth limit terbaik untuk digunakan. Hal ini dilakukan dengan secara menambah limit secara bertahap, mulai dari 0,1, 2, dan seterusnya sampai goal sudah ditemukan.
6.   Bidirectional Search
Pencarian dengan metode bidirectional search adalah dengan menjalankan dua pencarian secara simultan, yang satu dikerjakan secara forward dari initial state menuju ke goal, sedangkan yang satu lagi dikerjakan secara backward mulai dari goal ke initial state. Yang kemudian diharapkan bahwa kedua pencarian itu akan bertemu di tengah-tengah.

Informed Search Algorithm
Informed Search sering disebut juga dengan Heuristic Search. Pencarian dengan algoritma ini menggunakan knowledge yang spesifik kepada permasalahan yang dihadapi disamping dari definisi masalahnya itu sendiri. Metode ini mampu menemukan solusi secara lebih efisien daripada yang bisa dilakukan pada metode uninformed strategy.
Pada pencarian dengan menggunakan metode Uniform Cost Search (salah satu bagian dari Uninformed Search Algorithm), kita membandingkan nilai pada path yang ada, dan kemudian akan melakukan ekspansi pertama kali pada path dengan nilai yang terkecil. Nilai path ini biasanya dilambangkan dengan g(n). Lebih lanjut lagi dari metode pencarian tersebut, pada Informed Search Algorithm, kita akan mengenal nilai estimasi (prediksi) dari satu node ke node yang lainnya. Nilai estimasi ini biasanya dilambangkan dengan h(n). Jika n adalah goal node, maka nilai h(n) adalah nol.
  1. Greedy Best First Search
Metode pencarian ini melakukan ekspansi node yang memiliki jarak terdekat dengan goal. Namun, ekspansi yang dilakukan pada metode ini menggunakan evaluasi node hanya dengan melihat kepada fungsi heuristiknya. Dengan kata lain, yang dibandingkan untuk penentuan ekspansi node adalah nilai estimasi/prediksinya saja.
                     f(n) = h(n)
  1. 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)

Uninformed and Informed Search Exercise

Gambar 3 Uninformed dan Informed Search Problem
Apabila diberikan kondisi tree seperti gambar di atas, dimana biaya lintasan (path), dan nilai prediksi/estimasi diberikan, maka kita dapat melakukan simulasi proses ekspansi node untuk algoritma Uniform Cost Search, Greedy Best First Search, dan A* Search.
  1. Uniform Cost Search
Proses ekspansi pada Uniform Cost Search dihitung berdasarkan nilai lintasan g(n) sehingga proses akan berjalan sebagai berikut:
f = {S};
f = {C, A, K};  // 1, 2, 2
f = {A, K, D};  // 2, 2, 2
f = {K, D, B};  // 2, 2, 4
f = {D, L, B};  // 2, 3, 4
f = {L, E, B};  // 3, 3, 4
f = {E, B};     // 3, 4
f = {B, F};     // 4, 4
f = {F, H, G};  // 4, 6, 7
f = {G, H, G};  // 5, 6, 7
f = {H, G};     // 6, 7
Proses eksplorasi node dimulai dari S sebagai initial state. Eksplorasi node dari S akan menuju ke A, C, K sebagai successornya. Pada simulasi eksplorasi di atas, untuk mempermudah proses eksplorasi maka dituliskan dengan C, A, K karena urutannya dituliskan secara ascending dari nilai g(n) terkecil sehingga akan dihasilkan urutan node yang akan dieksplorasi selanjutnya. Pada eksplorasi node selanjutnya, nilai g(n) diakumulasikan dari node awal sampai pada node current yang baru dieksplorasikan.
Dari proses di atas, maka dihasilkan jumlah ekspansi node sebanyak 10 kali, dan path yang dilalui dengan menggunakan algoritma Uniform Cost Search adalah S-C-D-E-F-G.
  1. Greedy Best First Search
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.
  1. A* Search
Eksplorasi node dari metode A* dilakukan dengan cara menjumlahkan kombinasi nilai path g(n) dan nilai estimasi h(n). Penjumlahan dari nilai tersebut akan dibandingkan untuk menentukan node mana dulu yang akan dieksplorasikan. Prosesnya akan berjalan sebagai berikut ini:
f = {S};
f = {A, C, K};  // 4, 5, 7
f = {C, K, B};  // 5, 7, 7
f = {D, K, B};  // 5, 7, 7
f = {E, K, B};  // 5, 7, 7
f = {F, K, B};  // 5, 7, 7
f = {G, K, B};  // 5, 7, 7
f = {K, B};     // 7, 7
Dari proses di atas, maka dihasilkan jumlah ekspansi node sebanyak 7 kali, dan path yang dilalui dengan menggunakan algoritma A* Search adalah S-C-D-E-F-G.

Contoh : 
Misalkan kita memiliki ruang pencarian seperti pada gambar dibawah. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengan node A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di node A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara node n dengan node tujuan (jalan buntu). Kita bisa mengurut nilai untuk setiap node.



Daftar Pustaka : http://socs.binus.ac.id/2013/04/23/uninformed-search-dan-informed-search/