Penyelesaian Masalah Melalui Proses Pencarian atau Searching
Penyelesaian Masalah Melalui
Proses Pencarian atau Searching
Dalam membuat kecerdasan buatan (AI), tentunya tidak
akan hanya berfungsi ‘lurus-lurus’ saja. Akan tetapi, pasti akan muncul masalah
masalah yang timbul seiring beroperasinya kecerdasan buatan tersebut. Dalam
menyelesaikan masalahnya kecerdasan buatan memiliki beberapa proses yang di
antaranya adalah menyelesaikan masalah melalui proses pencarian atau searching.
Dalam
proses pencarian atau searching, AI
memiliki beberapa bagian yang menentukan bagaimana proses tersebut berjalan.
Bagian-bagian tersebut dapat dijabarkan menjadi :
1.
Agen Pemecah
Permasalahan
Dalam
menjalankan tugasnya tiap ‘kecerdasan’ selalu mempunya agen yang memprosesnya.
Jika diumpamakan dalam bentuk manusia, dalam bernafas agen yang ada untuk
memecahkan masalah ‘bernafas’ adalah paru-paru. Paru-paru disebut sebagai
‘agen’ karena ia menerima masukan (oksigen) dan memproses masukan tersebut dan
menghasilkan keluaran (karbon dioksida). Tentunya dalam masalah bernafas ini,
paru-paru bukanlah agen satu-satunya. Masih ada agen-agen lain seperti hidung,
mulut, dan tenggorokan.
Dalam
kecerdasan buatan (AI) tentunya terdapat beberapa agen juga yang memproses
permasalahan tersebut yang masing masing memiliki ‘sifat’ masing masing. Yang
di antaranya adalah :
·
Simple Reflex
Agents
Yaitu
agen yang memecahkan masalah berdasarkan persepsi yang terakhir digunakan. Yang
dapat diartikan dengan persepsi atau sudut pandang yang sebelumnya digunakan
untuk memecahkan masalah, digunakan kembali untuk memecahkan masalah yang baru.
·
Model-based Reflex
Agents
Yaitu
agen yang memiliki representasi internal tentang keadaan sekitar. Yang dapat
diartikan dengan sebelum memproses ‘reaksi’ apa yang akan agen tersebut
berikan, agen akan memproses atau mempertimbangkan keadaan lingkungan
sekitarnya terlebih dahulu. Lalu setelah mendapatkan kesimpulan dari itu, agen
akan memproses reaksi apa yang akan dilakukannya.
·
Goal-based Agents
Yaitu
agen yang memiliki informasi tentang tujuan, memilih tindakan yang mencapai
tujuan. Yang dapat diartikan bahwa sebelum memproses reaksi dari masalah, agen
akan mempertimbangkan beberapa keadaan berdasarkan ‘goal’ atau target atau
‘kuota’ yang diinginkan dari hasil yang akan diproses.
·
Utility-based
Agents
Yaitu
agen yang melakukan penilaian kuantitatif terhadap suatu keadaan lingkungan.
Yang dapat diartikan bahwa sebelum menghasilkan reaksi dari masalah, agen akan
mengumpulkan beberapa data yang dinilai berdasarkan banyaknya data
(kuantitatif) sebagai bahan pertimbangan dalam memproses atau memecahkan
masalah yang ada.
·
Learning Agents
Yaitu
agen yang belajar dari pengalaman,
meningkatkan kinerja. Yang dapat diartikan bahwa agen yang memproses akan
melihat feedback dari pengalaman
memecahkan masalah yang telah dilakukannya. Yang tentunya setelah mendapatkan
kesimpulan dari feedback yang didapat
ia akan menggunakan kesimpulan tersebut sebagai bahan pertimbangan untuk
memecahkan masalah yang ada.
2.
Pencarian sebagai
Solusi Pemecahan Masalah
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.
Dalam
memecahkan masalahnya tentunya kecerdasan buatan memiliki algoritma yang
menjadi dasarnya. Algoritma searching
di dalam kecerdasan buatan ini umumnya dikenal dengan :
·
Uninformed Search Algorithm
Algoritma
yang tidak memberikan informasi mengenai permasalahan yang ada, dan hanya
sebatas mendefinisikan algoritma atau arti dari permasalahan tersebut.
Uninformed Search Algorithm 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.
·
Informed Search Algorithm
Informed Search Algorithm 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 Search Algorithm.
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).
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.
3.
Strategi Pencarian
yang Tidak Berbentuk
Strategi pencarian yang tidak berbentuk ini sebetulnya
merupakan bagian dari Uninformed Search
Algorithm. Terdapat berbagai strategi pencarian pada Uninformed Search Algorithm, yang diantaranya adalah :
·
Breadth First Search (BFS)
Pencarian
dengan Breadth First Search
menggunakan teknik dimana langkah pertamanya adalah root node diekspansi, setelah itu dilanjutkan ke 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).
·
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).
·
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.
·
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.
·
Iterative Deepening Depth First Search
Iterative Deepening Depth First 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.
·
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.
Komentar
Posting Komentar