Pengertian Informed dan Uninformed Dalam Kecerdasan Buatan

Searching adalah suatu mekanisme dalam pemecahan masalah yang paling umum dalam kecerdasan buatan. Ada beberapa urutan langkah-langkah yang diperlukan untuk memperoleh solusi merupakan suatu isu yang penting untuk di buatkan pemecahan masalahnya. Hal ini harus dilakukan dengan mengidentifikasikan proses try and error dalam artiannya, harus mencoba dan mengidentifikasi kesalahan-kesalahan yang terjadi dalam prosesnya.

Algoritma searching yang sering digunakan dalam kecerdasan buatan adalah:

1.     Uninformed Search Algoritm

Algoritma ini tidak memberikan informasi apapun tentang permasalah yang ada, tetapi hanya berfokus memberikan informasi tentang algorima tersebut. Algoritma ini juga disebut Blind Search. Istilah Blind Search berpedoman bahwa, teknik pencarian ini tidak memiliki informasi tambahan lain selain dari yang disediakan.

Yang dilakukan oleh algorima ini adalah melakukan generate dari successor dan membedakan goal state dari non-goal state. Pencarian ini dilakukan berdasarkan pada urutan mana saja node yang hendak di-expand.

Macam-macam Uninformed Search Algorithm:

a.      Breadth First Search(BFS)

Pencarian dengan metode ini menggunakan teknik dimana langkah pertama yang harus dilakukan adalah root node di-ekspansi, 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 memiliki successor lagi).

                                                         

b.      Uniform Cost Search(UCS)

Pencarian dengan BFS 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).

c.       Depth First Search(DFS)

Teknik pencarian dengan metode ini adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node selesai di ekspansi, maka node tersebut akan ditinggalkan dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum di ekspansi.

d.      Depth Limited Search

Pencarian menggunakan DFS akan berlanjut sampai kedalam paling terakhir dari sebuah tree. Misalkan yang muncul pada DFS adalah ketikda proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan mengisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka sudah tidak memiliki successor.

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

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

2.     Informed Search Algorithm

Dengan menggunakan Uninformed Search Algorithm, beberapa permasalahan dapat dipecahkan, namun tidak semua algoritma dapat menyelesaikan permasalahan dengan efektif serta efisien.

Informed Search Algorithm, disebut juga dengan Heuristic Search. Pencarian dengan algoritma ini menggunakan pengetahuan yang spesifik kepada permasalahan yang dihadapi selain dari definisi masalahnya itu sendiri.

Pada pencarian dengan metode UCS(Salah satu bagian dai Uninformed Search Algorithm), kita membandingkan nilai pada path yang ada lalu kemudian melakukan ekspansi pertama kali pada path dengan nilai yang terkecil. Nilai path ini biasanya dilambangkan dengan g(n). lebih lanjut lagi, dari metode pencarian tsb, 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.

Metode metode pada Informed Search Algorithm :

a.      Greedy Best First Search

Metode pencarian ini melakukan ekspansi node yang memiliki jarak terdekat dengan goal node. 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)

b.      A * Search (A-Star 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)

c.       Generate and Test

Metode ini merupakan salah satu metode yang paling sederhana dalam pencarian heuristic atau Informed Search Algorithm. Pada dasarnya, metode ini memakai 2 langkah yaitu membangkitkan solusi yang mungkin ada, dan mengetest solusi tersebut algoritma ini memakai prosedur DFS karena suatu solusi harus di bangkitkan atau dikembangkan secara menyeluruh baru dapat dilakukan pengetesan. Sehingga metode ini kurang efektif untuk masalah-masalah yang kompleks.

d.      Hill Climbing

Metode ini hampir sama dengan metode Generate and Test, perbedaannya pada umpan balik setelah dilakukannya test. Test yang berupa fungsi heuristic menunjukan seberapa baik nilai terkaan yang diambil terhadap keadaan. Metode ini sebenarnya kurang efektif sebab terlalu banyak solusi dalam suatu masalah.

Kesimpulan

            Dalam kecerdasan buatan, terdapat beberapa metode atau istilah-istilah didalamnya. Diantaranya searching. Searching merupakan suatu mekanisme dalam pemecahan masalah yang paling umum. Ada beberapa langkah yang penting harus dibuat sehingga dapat dibuatkan pemecahan masalahnya. Searching dilakukan dengan mengidentifikasi try and error.

            Informed dan Uninformed Search Algorithm merupakan salah satu algoritma dalam kecerdasan buatan. Tidak semua algoritma dapat menyelesaikan permasalahan secara efektif dan efisien.

Uninformed Search Algorithm menggunakan metode Blind Search, artinya tidak ada tambahan informasi lain yang disediakan. Algoritma jenis ini tidak memberikan banyak solusi, pada dasarnya algoritma jenis ini hanya menjelaskan tentang algoritma tersebut.

Breadth First Search(BFS), Uniform Cost Search(UCS), Depth First Search(DFS), Depth Limited Search, Iterative Deepening Depth First Search, serta Bidirectional Search merupakan metode-metode yang terdapat dalam Uninformed Search Algorithm.

Sedangkan Informed Search Algorithm disebut juga Heuristic Search. Pencarian dengan algoritma ini menggunakan pengetahuan yang spesifik kepada masalah yang dihadapi. Metode-metode yang gunakan dalam Informed Search Algorithm lebih sedikit dibandung Uninformed Search Algorithm.

Generate and test, A* Search (dibaca A-Star Search), Greedy Best First Search, hill climbing merupakan metode yang digunakan dalam Informed Search Algorithm

Contoh Soal Latihan:

Contoh Soal:

Apabila diberikan kondisi tree seperti gambar di atas, dimana biaya lintasan (path), dan nilai prediksi/estimasi sudah diberikan, maka kita dapat melakukan simulasi proses ekspansi node untuk algoritma Uniform Cost Search, Greedy Best First Search, dan A* Search.

Jawab:

1. Uniform Cost Search

Proses ekspansi pada Uniform Cost Search dihitung berdasarkan nilai lintasan g(n) sehingga proses akan berjalan sebagai berikut:

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.

Jadi, 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.

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

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

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.

Sumber: Binus.ac,id