5 Teknik Searching Menggunakan Artificial Intelligence (AI)
Pada artikel ini membahas bagaimana memecahkan suatu masalah dengan teknik searching atau pencarian. Langkah pertama yang harus dilakukan adalah mendefinisikan ruang masalah untuk suatu masalah yang dihadapi. Ruang masalah ini dapat digambarkan sebagai himpunan keadaan (state) atau bisa juga sebagai himpunan rute dari keadaan awal (initial state) menuju keadaan tujuan (goal state). Langkah ke dua adalah mendefinisikan aturan produksi yang digunakan untuk mengubah suatu state ke state lainnya. Langkah terakhir adalah memilih metode pencarian yang tepat sehinggadapat menemukan solusi terbaik dengan usaha yang minimal. Pada bab ini juga di bahas berbagai metode pencarian, yang dikelompokkan ke dalam blind atau un-informed search (pencarian buta atau tidak berbekal informasi) dan heuristic atau informed search (Pencarian dengan panduan atau berbekal informasi. Juga dibahas analisa performasi dari masing masing metode pencarian tersebut, sehingga pembaca dapat menentukan metode pencarian apa yang paling tepat untuk suatu masalah tertentu.
1. Metode-Metode Pencarian
Terdapat banyak metode pencarian yang telah diusulkan. Semua metode yang ada dapat dibedakan ke dalam dua jenis: pencarian buta atau pencarian tanpa informasi (blind atau un-informed search) dan pencarian heuristik atau dengan informasi (heuristic atau informed search). Setiap metode mempunyai karakteristik yang berbeda-beda dengan kelebihan dan kekurangannya masing-masing.
Untuk mengukur performansi metode pencarian, terdapat empat kriteria yang dapat digunakan, yaitu :
- Completeness: Apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada ?
- Time complexity : Berapa lama waktu yang diperlukan ?
- Spcae complexity : Berapa banyak memori yang diperlukan ?
- Optimality : Apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda?
1.1 Blind/Un-Informed Search
Disini digunakan istilah blind atau buta karena memang tidak ada informasi awal yang digunakan dalam proses pencarian. Di sini hanya akan dibahas enam metode yang tergolong blind search, yaitu : Breadth First Search (BFS), Uniform Cost Search (UCS), Depth First Search (DFS), Depth-Limited Search (DLS), Iterative Deepening Search (IDS), dan Bi-directional Search (BDS).
1.1.1 Breadth First Search (BFS)
Pencarian dilakukan pada semua simpul dalam setiap level secara berurutan dari kiri ke kanan. Jika pada suatu level belum ditemukan solusi, maka pencarian akan dilanjutkan pada level berikutnya. Demikian seterusnya sampai ditemukan solusi. Dengan cara seperti ini, BFS menjamin ditemukannya solusi ( jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik. Dengan kata lain BFS adalah complete dan optimal. Tetapi, BFS harus menyimpan semua simpul yang pernah dilewati. Hal ini harus dilakukan agar BFS dapat melakukan penelusuruan simpul simpul sampai pada level terbawah. Jika b adalah faktor percabngan (jumlah simpul anak yang dimiliki oleh suatu simpul) dan d adalah kedalaman solusi, maka jumlah simpul yang harus disimpan adalah sebanyak O(b^d). Misalkan, untuk b = 10 dan d = 8, maka BFS harus membangikatkan dan menyimpan sebanyak 111.111.111 = 10^8 simpul. Jika diasumsikan bahwa dalam satu detik komputer mambangkitkan dan menguji 10^6 smpul, maka waktu proses yang dilakukan untuk menemukan solusi di level 8 adalah 100 detik (1,67 menit). Jika satu simpul direpresentasikan dalam struktur data sebesar 100 bytes, maka diperlukan memori sebesar 10^10 bytes (atau 10 gigabytes). Dari segi kecepatan, hal ini mungkin masih bisa diterima. TEtapi dari sisi memori yang diperlukan ini menjadi masalah serius. Dengan permasalah dan komputer yang sama, waktu proses yang diperlukan untuk menemukan solusi di level 14 adalah 10^8 detik (lebih dari 3 tahun), dan diperlukan memori sebesar 10^15 bytes (1000 terabytes). Oleh karena itu, BFS sangat sulit diimplementasikan di dunia nyata.
1.1.2 Depth-First Search (DFS)
Pencarian dilakukan pada suatu simpul dalam setiap level dari yang paling kiri, Jika pada level yang terdalam solusi belum ditemukan, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yang kiri dapat dihapus dari memori. Pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan padal evel sebelumnya. Demikian seterusnya sampai ditemukan solusi.
Kelebihan DFS adalah pemakian memori yang lebih sedikit. DFS hanya menyimpan sekitar bd simpul, dimana b adalah faktor percabangan dan d adalah kedalaman solusi. Jika b = 10 dan d – 3, maka jumlah simpul yang disimpan di dalam memori adalah 1 + 10 + 10 + 10 = 31. Hal ini berbeda jauh dengan BFS yang harus menyimpan semua simpul yang pernah dibangkitkan. Pada kasus tersebut, BFS harus menyimpan 1 + 10 + 100 + 1000 = 1.111 Simpul. Kelebihan lainnya adalah jika solusi yang di cari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya dengan cepat.
Sedangkan kelemahan DFS adalah jika pohon yang dibangkitkan mempunyai level yang sangat dalam (tak terhingga), maka tida ada jaminam menemukan solusi. Artinya, DFS tidak complete. Kelemahan lainnya adalah jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka DFS tidak menjamin untuk menemukan solusi yang palin baik. ARtinya, DFS tidak optimal.
1.1.3 Uniform Cost Search (UCS)
Konsepnya hampir sama dengan BFS, bedanya adalah bahwa BFS menggunakan urutan level dari yang paling rendah sampai yang paling tinggi. Sedangkan UCS menggunakan urutan biaya dari yang paling kecil sampai dengan yang terbesar. UCS berusaha menemukan solusi dengan total biaya terendah yang dihitung berdasarkan biaya dari simpul asal menuju ke simpul tujuan. Biaya dari simpul asal ke suatau simpul n dilambangkan sebagai g(n). Perhatikan UCS menemukan solusi terbaik. Karena mengikuti konsep BFS, maka UCS menjamin ditemukannya solusi dan solusi yang ditemukannya selalu yang terbaik. Dengan kata lain, UCs adalah complete dan optimal.
Pada masalah jurigen air, jika diasumsikan bahwa biaya untuk setiap aturan produksi adalah sama, maka pencarian yang dilakukan UCS akan sama dengan BFS. Misalkan, jika BFs menemukan solusi dalam 6 langkah (menggunakan aturan produksi, maka UCS juga akan menemukan solusi dalam 6 langkah. Dengan kata lain, UCS akan sama dengan BFS jika g(n) = DEPTH(n).
Syarat yang harus dipenuhi oleh pohon UCS ada g(SUCCESSOR(n)) >= g(n) untuk setiap simpul n. Jika syarat ini tidak dipenuhi maka UCS menjadi tidak complete dan tidak optimal.
1.1.4 Iterative Deepening Search (IDS)
IDS merupakan metode yang menggabungkan kelebihan BFS (complete dan optimal) dengan kelebihan DFS (Space complexity rendah atau membutuhkan sedikit memori). Tetapi, konsekuesninya adalah time complexity-nya menjadi tinggi. IDS melakukan pencarian secara iteratif menggunakan penelusuran Depth Limited Search (DLS) dimulai dengan batasan level 0. Jika belum ditemukan solusi, maka dilakukan iterasi ke-2 dengan batasan level 1. Demikian seterusnya sasmpai ditemukan solusi. Untuk mempercepat proses pencarian, kita bisa menggunakan teknik parallel processing (menggunakan lebih dari satu processor).
1.1.5 Bi-Directional Search (BDS)
Pada setiap iterasi, pencarian dilakukan dari dua arah: pencarian maju (dari start ke goal) dan pencarian mundur (dari goal ke start). Ketika dua arah pencarian telah membangkitkan simpul yang sama, maka solusi telah ditemukan, yaitu dengan cara menggabungkan kedua jalur yang bertemu.
Jika pencarian maju menggunakan BFS dan pencarian mundur juga menggunakan BFS, maka jumlah langkah yang diperlukan adalah sebanyak O(2b^d/2) = O(b^d/2). Di mana b adalah faktor percabangan dan d adalah kedalaman solusi. Misalkan, untuk b = 10, dan d = 6, maka BFS akan membangkitkan 1 + 10 + 10^2 + 10^3 + …. 10^6 = 1.111.111 simpul. Sebaliknya, BDS hanya akan membangkitkan 2 x (1 + 10 + 10^2 + 10^3) = 2.222 Simpul. Jauh lebih sedikit dibanding jumlah simpul yang dibangkitkan BFS. Hal ini juga sebanding terhadap jumlah memori yang diperlukan dalam kasus ini BDS memerlukan memori untuk menyimpan hanya 2.222 simpul. Secara teori, BDS mempunyai harapan yang bagus untuk digunakan, hemat waktu maupun memori dan selalu memberikan solusi yang optimal jika solusi memang ada, Tetapi , ada beberapa masalah sebelum memutuskan untuk menggunakan BDS, diantaranya adalah
- Apakah yang dimaksud dengan pencarian mundur (dari goal ke start)? Pencarian mundur berarti membangitkan predecossor (simpul induk/pralel) dari suatu simpul. Pembangkitan predecessor berarti memerlukan pembalikan aturan produksi.
- Apakah semua operator (aturan produksi) dapat dibalik?
- Bagaimana kalau terdapat beberapa simpul tujuan yang berbeda? DAlam permainan catur, state seperti apa yang menjadi tujuan? Sebagai contoh, goal state bisa berupa keadaan dimana pihak lawan hanya memiliki tiga buah catur (raja dan dua menteri) di posisi tertentu, raja dalam posisi terancam dan tidak bisa melangkah ke posisi manapun. Dengan 64 (8 * 8) posisi berbeda yang dapat ditempati oleh 32 buah catur (hitam dan putih) atau tidak ditempat buah catur apapun, maka terdapat sangat banyak goal state. Dengan demikian jika BS digunakan untuk masalah permainan catur, maka pencarian maju dimulai dan sebuah start state ( contoh : 32 buah catur berada di posisi awal atau belum ada buah catur yang bergerak). Tetapi, pencarian mundur harus dimulai dari 33^64 state berbeda. Tentu saja BDS tidak mungkin digunakan.
- Dalam BDs terdapat ketidak efisien dalam perhitungan, yaitu harus selalu menguji apakah simpul baru yang dibangkitkan sudah pernah dibangkitkan oleh pencarian dari arah yang berlawanan. Kalau sudah berarti solusi telah ditemukan. Jika terdapat 2000 simpul yang dibangkitkan, berarti harus mmelakukan 2000 pengujian tersebut.
- Bagaimana menentukan metode pencarian untuk kedua arah tersebut ? Misalnya dari arah sumber digunakan BFS dan dari arah tujuan juga digunakan BFs. Teapi, apakah BFs adalah yang terbaik ?
Selanjutnya metode pencairan apa yang sebaiknya digunakan jika kita menghadapi suatu masalah dengan karakteristik: faktor percabangan 10, level solusinya sekitar 100, solusi yang ditemukan harus paling optimal tetapi memerlukan memori paling sedikit, dan waktu proses tidak diperhatikan ? DFS dan DLS tidak bisa digunakan karena tidak optimal. BFS dan UCS membutuhkan faktor percabangan pohon cukup besar dan level solusinya sangat dalam, maka IDS memerlukan memori yang lebih sedikit (yakni bd) dibandingkan. BDS yang memrlukan memori sekitar b^d//2. PAda kasus tersebut b = 10, dan d = 100, maka memerlukan memori untuk menyimpan 10^50 simpul. Sebenarnya, IDS membutuhkan waktu proses yang lebih lama dibandningkan dengan BDS. Tetapi karena pada kasus tersebut waktu proses tidak diperhatikan, maka IDs adalah pilihan terbaik untuk kasus tersebut.
Post a Comment for "5 Teknik Searching Menggunakan Artificial Intelligence (AI)"